curs 13 - grafuri euleriene si grafuri hamiltoniene. colorarea...
TRANSCRIPT
-
Colorarea grafurilor
Curs 13Grafuri euleriene şi grafuri hamiltoniene.
Colorarea grafurilor. Polinoame cromatice
21 decembrie 2018
Curs 13
-
Colorarea grafurilor
Grafuri euleriene
Fie G = (V ,E ) un graf neorientat.
O cale euleriană este o cale care conţine fiecare muchie a lui G osingură dată.
Un ciclu eulerian este un ciclu care conţine fiecare muchie a lui G osingură dată.
G este graf eulerian dacă are un ciclu eulerian.
Exemple:
11
2
3
5
4
nu este graf eulerian (de ce?)are calea euleriană (2,5,4,3,1,2,3)
21
2
3
5
4
6este graf eulerian:(2,3,1,2,4,5,3,2,5,6,4,3,2) este ciclu eulerian
3 Orice graf ciclic Cn cu n ≥ 3 este eulerian.4 Nici un graf Pn cu n ≥ 2 nu este eulerian.
Curs 13
-
Colorarea grafurilor
Grafuri eulerieneCum recunoaştem grafurile euleriene?
Teorema de caracterizare a grafurilor euleriene
Pentru un graf conex G = (V ,E), afirmaţiile următoare sunt echivalente:
1 G este graf eulerian.
2 Fiecare nod al lui G are grad par.
3 Muchiile lui G pot fi partiţionate ı̂n cicluri care nu au muchii ı̂n comun.
Demonstraţia lui 1⇒ 2: Presupunem căB G este Eulerian ⇔ ∃ un ciclu care conţine toate muchiile lui G
De exemplu, (v1, v3, v4, v1, v2, v6, v1) este un ciclu al grafului
v1
v3
v4v2
v6
deg(v2) = deg(v3) = deg(v4) = deg(v6) = 2
deg(v1) = 4
Ori de câte ori ciclul eulerian intră ı̂n un nod v pe o muchie, trebuie să plece din acel
nod pe altă muchie. Deoarece nici o muchie nu apare de 2 ori ı̂n ciclu, nr. de muchii
incidente la v este par ⇒ deg(v) este par.
Curs 13
-
Colorarea grafurilor
Grafuri eulerieneDemonstraţie a Teoremei de Caracterizare (continuare)
Demonstraţia lui 2⇒ 3: Presupunem că fiecare nod al lui G aregrad par. Gândim inductiv după numărul de cicluri disjuncte ale lui G .
G nu are noduri de grad 1 ⇒ G nu este arbore ⇒ G are cel puţin unciclu Cn1 .Fie G ′ graful produs din G prin eliminarea muchiilor lui Cn1 ⇒ toatenodurile lui G ′ au grad par ⇒ se deduce recursiv că G ′ poate fipartiţionat ı̂n cicluri disjuncte Cn2 , . . . ,Cnk .
Rezultă că Cn1 ,Cn2 , . . . ,Cnk este o partiţie a lui G ı̂n cicluri (cu muchii)disjuncte.
Demonstraţia lui 3⇒ 1: evident.
Curs 13
-
Colorarea grafurilor
Detecţia ciclurilor eulerieneAlgoritmul lui Hierholzer
Se dă: un graf eulerian G = (V ,E )
Sa caută un ciclu eulerian al lui G .
1 Se identifică un circuit R1 al lui G şi se marchează muchiile lui R1.Fie i = 1.
2 Dacă Ri conţine toate muchiile lui G , stop: Ri este Eulerian.
3 Dacă Ri nu conţine toate muchiile lui G , fie vi un nod al Ri incidentla o muchie nemarcată ei .
4 Se construieşte un ciclu de muchii nemarcate Qi , pornind de lanodul vi de-a lungul muchiei ei . Se marchează muchiile lui Qi .
5 Se crează un ciclu nou Ri+1 ı̂nlănţuind Qi ı̂n Ri la nodul vi .
6 Se incrementează i cu 1 şi se revine la pasul (2).
Curs 13
-
Colorarea grafurilor
Detecţia ciclurilor eulerieneAlgoritmul lui Hierholzer: exemplu ilustrat
1
2
3
4
5
6
7
8
9
Cicluri:
Q1 = (3, 6, 7, 8, 2, 4, 9, 3)Q2 = (3, 8, 5, 1, 3)Q3 = (6, 2, 7, 9, 5, 6)Q4 = (4, 5, 7, 4)
Primele 2 cicluri au nodul comun 3 ⇒ ciclulR2 = (3, 8, 5, 1, 3, 6, 7, 8, 2, 4, 9, 3)
R2 are nodul 6 ı̂n comun cu al 3-lea ciclu ⇒ ciclulR3 = (3, 8, 5, 1, 3, 6, 2, 7, 9, 5, 6, 7, 8, 2, 4, 9, 3)
R3 are nodul 4 ı̂n comun cu a 4-lea ciclu ⇒ ciclul eulerianR4 = (3, 8, 5, 1, 3, 6, 2, 7, 9, 5, 6, 7, 8, 2, 4, 5, 7, 4, 9, 3)
Curs 13
-
Colorarea grafurilor
Detecţia căilor euleriene
Întrebare: Cum detectăm dacă un graf conţine o cale euleriană?
Răspuns: Se observă că:
Un graf eulerian conţine un o cale eulerianădeoarece orice ciclu eulerian este şi caleeuleriană.Există grafuri ne-euleriene care conţin căieuleriene.
Observaţie
Un graf conex G conţine o cale euleriană dacă şi numai dacă arecel mult 2 noduri cu grad impar.
Curs 13
-
Colorarea grafurilor
Detecţia căilor euleriene
Întrebare: Cum detectăm dacă un graf conţine o cale euleriană?
Răspuns: Se observă că:
Un graf eulerian conţine un o cale eulerianădeoarece orice ciclu eulerian este şi caleeuleriană.Există grafuri ne-euleriene care conţin căieuleriene.
Observaţie
Un graf conex G conţine o cale euleriană dacă şi numai dacă arecel mult 2 noduri cu grad impar.
Curs 13
-
Colorarea grafurilor
Detecţia căilor euleriene
Întrebare: Cum detectăm dacă un graf conţine o cale euleriană?
Răspuns: Se observă că:
Un graf eulerian conţine un o cale eulerianădeoarece orice ciclu eulerian este şi caleeuleriană.Există grafuri ne-euleriene care conţin căieuleriene.
Observaţie
Un graf conex G conţine o cale euleriană dacă şi numai dacă arecel mult 2 noduri cu grad impar.
Curs 13
-
Colorarea grafurilor
Grafuri hamiltoniene
Fie G = (V ,E ) un graf neorientat.
O cale hamiltoniană este o cale care conţine fiecare nod a lui G osingură dată.
Un ciclu hamiltonian este un ciclu care trece prin fiecare nod a lui Go singură dată.
G este traversabil dacă conţine o cale hamiltoniană.
G este graf hamiltonian dacă are un ciclu hamiltonian.
Observaţii:
1 Toate grafurile hamiltoniene sunt traversabile.
2 Există grafuri traversable care nu sunt hamiltoniene; De exemplu,P3.
Curs 13
-
Colorarea grafurilor
Detecţia grafurilor hamiltoniene
Nu se cunosc condiţii necesare şi suficiente de caracterizare agrafurilor hamiltoniene.
Se cunosc condiţii suficiente pentru ca un graf să fie sau să nu fiehamiltonian:
1 Teorema lui Dirac2 Teorema lui Dirac generalizată3 Teorema lui Chvátal şi Erdös4 Teorema Goodman şi Hedetniemi5 Teorema lui Duffus, Gould şi Jacobson
. . .
Curs 13
-
Colorarea grafurilor
Detecţia grafurilor hamiltonieneTeorema lui Dirac
Teorema lui Dirac
Fie G un graf simplu cu ordinul n ≥ 3. Dacă δ(G) ≥ n/2 atunci G este hamiltonian.
Demonstraţie. Presupunem că G satisface condiţiile date, ı̂nsă G nu estehamiltonian. Fie P = (v1, . . . , vp) o cale simplă ı̂n G de lungime maximală ⇒ toţivecinii lui v1 şi ai lui vp sunt ı̂n P. Deasemenea, v1 şi vp au cel puţin n/2 vecini ı̂n Pfiindcă δ(G) ≥ n/2.Demonstrăm că ∃j ∈ {1, . . . , p − 1} astfel ı̂ncât vj ∈ N(vp) şi vj+1 ∈ N(v1). Dacă n-arfi aşa, atunci pentru fiecare vecin vi de pe P al lui vp (reţinem că sunt ≥ n/2 astfel devi ), vi+1 nu este vecin al lui v1. Ar rezulta că deg(v1) ≤ p − 1−
n
2< n −
n
2=
n
2,
contradicţie cu faptul că δ(G) ≥ n/2. Deci, există un astfel de j , pentru care avemsituaţia ilustrată ı̂n figura de mai jos:
Curs 13
-
Colorarea grafurilor
Detecţia grafurilor hamiltonieneTeorema lui Dirac (continuare)
Teorema lui Dirac
Fie G un graf simplu cu ordinul n ≥ 3. Dacă δ(G ) ≥ n/2 atunci G estehamiltonian.
Demonstraţie. (continuare)
Fie C ciclul v1, v2, . . . , vj , vp, vp−1, . . . , vj+1, v1. Presupunând că G nueste hamiltonian, există un nod al lui G care nu este ı̂n P.
Se observă că, dacă δ(G ) ≥ n/2 atunci G este conex.
⇒ G are un nod w care nu-i ı̂n P şi este adiacent la un nod vi din P.Dar atunci calea care porneşte cu w , vi şi continuă ı̂n jurul ciclului C estemai lungă decât P, contradicţie.
În concluzie G trebuie să fie graf hamiltonian. �
Curs 13
-
Colorarea grafurilor
Detecţia grafurilor hamiltonieneAlte criterii şi noţiuni auxiliare
Teorema lui Dirac generalizată
Fie G un graf simplu cu ordinul n ≥ 3. Dacă deg(x) + deg(y) ≥ n pentru toateperechile de noduri neadiacente x , y , atunci G este hamiltonian.
O mulţime de noduri a unui graf G este independentă dacă nu conţine noduriadiacente. Numărul de independenţă α(G) al unui graf G este mărimea cea mai mareposibilă a unei mulţimi independente a lui G .
Exemplu
Se consideră grafurile
Cea mai mare mulţime independentă a lui G1 este {c, d}, deci α(G1) = 2. Există 2mulţimi independente cu mărimea 3 ı̂n G2 : {a, c, e} şi {b, d , f }, şi nici una cumărimea 4, deci α(G2) = 3.
Curs 13
-
Colorarea grafurilor
Detecţia grafurilor hamiltonieneAlte criterii şi noţiuni auxiliare
Teorema lui Dirac generalizată
Fie G un graf simplu cu ordinul n ≥ 3. Dacă deg(x) + deg(y) ≥ n pentru toateperechile de noduri neadiacente x , y , atunci G este hamiltonian.
O mulţime de noduri a unui graf G este independentă dacă nu conţine noduriadiacente. Numărul de independenţă α(G) al unui graf G este mărimea cea mai mareposibilă a unei mulţimi independente a lui G .
Exemplu
Se consideră grafurile
Cea mai mare mulţime independentă a lui G1 este {c, d}, deci α(G1) = 2. Există 2mulţimi independente cu mărimea 3 ı̂n G2 : {a, c, e} şi {b, d , f }, şi nici una cumărimea 4, deci α(G2) = 3.
Curs 13
-
Colorarea grafurilor
Detecţia grafurilor hamiltonieneAlte criterii şi noţiuni auxiliare. Teorema lui Chvátal şi Erdös
Conectivitatea κ(G ) unui graf G este este mărimea minimă a uneimulţimi de tăiere a lui G . Spunem că G este k-conectat dacă k ≤ κ(G ).
Teoremă (Chvátal şi Erdös, 1972)
Fie G un graf conectat cu ordinal n ≥ 3, conectivitatea κ(G ), şi numărulde independenţă α(G ). Dacă κ(G ) ≥ α(G ), atunci G este hamiltonian.
Exerciţiu (Jocul icosian al lui Hamilton)
Să se arate că graful ilustrat ı̂n cercul de mai jos este hamiltonian.
Curs 13
-
Colorarea grafurilor
Detecţia grafurilor hamiltonieneDouă definiţii şi trei grafuri speciale
Date fiind două grafuri G şi H, spunem că G este liber de Hdacă G nu conţine subgraful H.
Dacă S este o colecţie de grafuri, spunem că G este liber de Sdacă G nu conţine nici unul din grafurile lui S ca subgraf.
Trei grafuri speciale
K1,3 Z1 N
Curs 13
-
Colorarea grafurilor
Detecţia grafurilor hamiltonieneAlte rezultate
Teoremă (Goodman şi Hedetniemi, 1974)
Dacă G este un graf 2-conectat şi liber de {K1,3,Z1} atunci G estehamiltonian.
Demonstraţie. Fie G un astfel de graf, şi fie C un ciclu de lungimemaximă ı̂n G . Deoarece G este 2-conectat, un astfel de ciclu C există.Demonstrăm că C este ciclu hamiltonian.Dacă G nu ar fi hamiltonian, ar exista un nod v care nu este ı̂n C şi careeste adiacent la un nod w din C . Fie a şi b succesorul şi predecesorulimediat al lui w ı̂n ciclul C .
Dacă {a, b} ∩ N(v) 6= ∅ ⇒ ∃ un ciclu mai lung decât C ⇒ {a, b} ∩ N(v) = ∅.
Dacă a, b nu sunt adiacente atunci subgraful indus de {w , v , a, b} este K1,3,contradicţie cu ipoteza că G este liber de K1,3 ⇒ ab trebuie să fie muchie ı̂n G .Însă ı̂n acest caz subgraful indus de {w , v , a, b} este Z1, contradicţie cu ipotezacă G este liber de Z1.
⇒ C este ciclu hamiltonian. �Curs 13
-
Colorarea grafurilor
Detecţia grafurilor hamiltonieneAlte rezultate
Teoremă (Duffus, Gould şi Jacobson, 1981)
Fie G un graf liber de {K1,3,N}.1 Dacă G este conectat atunci G este traversabil.
2 Dacă G este 2-conectat atunci G este hamiltonian.
Observaţii.
Ultimele 2 teoreme interzic ca graful K1,3 să apară ca subgraf. Deobicei, graful K1,3 se numeşte gheară, şi este un graf interzis săapară ı̂n numeroase teoreme din teoria grafurilor.
Curs 13
-
Colorarea grafurilor
Detecţia grafurilor hamiltonieneAlte rezultate
Teoremă (Duffus, Gould şi Jacobson, 1981)
Fie G un graf liber de {K1,3,N}.1 Dacă G este conectat atunci G este traversabil.
2 Dacă G este 2-conectat atunci G este hamiltonian.
Observaţii.
Ultimele 2 teoreme interzic ca graful K1,3 să apară ca subgraf. Deobicei, graful K1,3 se numeşte gheară, şi este un graf interzis săapară ı̂n numeroase teoreme din teoria grafurilor.
Curs 13
-
Colorarea grafurilor
Problemă motivantă
Adi, Barbu, Călin, Dan, Eugen, Florin, Gelu şi Ion sunt senatori aiunui stat, şi fac parte din 7 comitete:
C1 = {Adi, Barbu, Călin}, C2 = {Călin, Dan, Eugen},C3 = {Dan,Florin}, C4 = {Adi, Gelu}, C5 = {Eugen, Ion},C6 = {Eugen,Barbu,Gelu}, C7 = {Ion, Călin, Florin}.
Fiecare comitet trebuie să fixeze o oră la care să se ı̂ntâlnească toţimembrii săi.
Întrebare: Care este numărul minim de ore ce trebuiesc fixatepentru ı̂ntâlniri, dacă se ştie că nici un membru nupoate participa simultan la două ı̂ntâlniri fixate laaceeaşi oră?
Curs 13
-
Colorarea grafurilor
Răspuns la problema motivantă
Observaţii:
Două comitete Ci şi Cj nu se pot ı̂ntâlni la aceeaşi oră dacă şinumai dacă au un membru comun (adică Ci ∩ Cj = ∅).
⇒ Putem considera graful neorientat G cunoduri = comitetele C1,C2,C3,C4,C5,C6,C7muchii {Ci ,Cj} dacă Ci şi Cj au un membru comun (adicăCi ∩ Cj 6= ∅)⇒ muchiile{C1,C2}, {C1,C4}, {C1,C6}, {C1,C7}, {C2,C3}, {C2,C5}, {C2,C7},{C3,C7}, {C4,C6}, {C5,C6}, {C5,C7}
Colorăm fiecare nod Ci cu o culoare care reprezintă ora la careare loc ı̂ntâlnirea comitetului Ci⇒ problema se poate reformula astfel: care este numărul minim
de culori pentru nodurile lui G , astfel ı̂ncât nici o muchie să nuaibă capetele colorate la fel?
Curs 13
-
Colorarea grafurilor
Răspuns la problema motivantă
G : C1
C2C3
C4
C5
C6C7
C1
C2C3
C4
C5
C6C7
K(C1) = K(C3) = K(C5) = 1
K(C2) = K(C4) = 2
K(C6) = K(C7) = 3
⇒ nr. minim de date este 3.(sunt necesare 3 culori)
Definiţie (colorare de noduri, număr cromatic)
O k-colorare a nodurilor unui graf G = (V ,E ) este o funcţieK : V → {1, . . . , k} astfel ı̂ncât K (u) 6= K (v) dacă (u, v) ∈ E .Numărul cromatic χ(G ) al unui graf G este valoarea minimă a luik ∈ N pt. care există o k-colorare a lui G .
Curs 13
-
Colorarea grafurilor
Răspuns la problema motivantă
G : C1
C2C3
C4
C5
C6C7
C1
C2C3
C4
C5
C6C7
K(C1) = K(C3) = K(C5) = 1
K(C2) = K(C4) = 2
K(C6) = K(C7) = 3
⇒ nr. minim de date este 3.(sunt necesare 3 culori)
Definiţie (colorare de noduri, număr cromatic)
O k-colorare a nodurilor unui graf G = (V ,E ) este o funcţieK : V → {1, . . . , k} astfel ı̂ncât K (u) 6= K (v) dacă (u, v) ∈ E .Numărul cromatic χ(G ) al unui graf G este valoarea minimă a luik ∈ N pt. care există o k-colorare a lui G .
Curs 13
-
Colorarea grafurilor
Răspuns la problema motivantă
G : C1
C2C3
C4
C5
C6C7
C1
C2C3
C4
C5
C6C7
K(C1) = K(C3) = K(C5) = 1
K(C2) = K(C4) = 2
K(C6) = K(C7) = 3
⇒ nr. minim de date este 3.(sunt necesare 3 culori)
Definiţie (colorare de noduri, număr cromatic)
O k-colorare a nodurilor unui graf G = (V ,E ) este o funcţieK : V → {1, . . . , k} astfel ı̂ncât K (u) 6= K (v) dacă (u, v) ∈ E .Numărul cromatic χ(G ) al unui graf G este valoarea minimă a luik ∈ N pt. care există o k-colorare a lui G .
Curs 13
-
Colorarea grafurilor
Colorări de noduriPolinoame cromatice
Calculul lui χ(G ) este o problemă dificilă (NP-completă).
Birkhoff (≈ 1900) a descoperit o metodă de calcul al unuipolinom cG (z) pentru orice graf G , numit polinomul cromatical lui G , astfel ı̂ncât
cG (k) = numărul de k-colorări ale nodurilor lui G
⇒ χ(G ) = valoarea minimă a lui k pentru care cG (k) > 0.
Vom prezenta
1 formule simple de calcul al lui cG (z) pentru grafuri speciale G .
2 doi algoritmi recursivi de calcul al lui cG (z) pentru orice grafG .
Curs 13
-
Colorarea grafurilor
Colorări de noduriPolinoame cromatice
Calculul lui χ(G ) este o problemă dificilă (NP-completă).
Birkhoff (≈ 1900) a descoperit o metodă de calcul al unuipolinom cG (z) pentru orice graf G , numit polinomul cromatical lui G , astfel ı̂ncât
cG (k) = numărul de k-colorări ale nodurilor lui G
⇒ χ(G ) = valoarea minimă a lui k pentru care cG (k) > 0.Vom prezenta
1 formule simple de calcul al lui cG (z) pentru grafuri speciale G .
2 doi algoritmi recursivi de calcul al lui cG (z) pentru orice grafG .
Curs 13
-
Colorarea grafurilor
Polinoame cromatice pentru grafuri speciale
1 Graful vid En:v1 v2 . . . vn
pentru fiecare nod, putem alege oricare din z culori:⇒ cEn(z) = zn şi χ(En) = 1
2 Arbore Tn cu n noduri:
z opţiuni pentru culoarea rădăciniiorice alt nod poate fi colorat cu orice culoare diferită ce cea anodului părinte ⇒ z − 1 opţiuni pentru colorarea lui
⇒ cTn(z) = z · (z − 1)n−1 şi χ(Tn) ={
1 dacă n = 1,2 dacă n > 1.
3 Caz special: graful Pn (cale cu n noduri) este un arbore
special cu n noduri: v1 v2. . . vn
⇒ cPn(z) = z · (z − 1)n−1 şi χ(Pn) ={
1 dacă n = 1,2 dacă n > 1.
4 Graful complet Kn:cKn(z) = z · (z − 1) · . . . · (z − n + 1) şi χ(Kn) = n.
Curs 13
-
Colorarea grafurilor
Polinoame cromatice pentru grafuri speciale
1 Graful vid En:v1 v2 . . . vn
pentru fiecare nod, putem alege oricare din z culori:⇒ cEn(z) = zn şi χ(En) = 1
2 Arbore Tn cu n noduri:
z opţiuni pentru culoarea rădăciniiorice alt nod poate fi colorat cu orice culoare diferită ce cea anodului părinte ⇒ z − 1 opţiuni pentru colorarea lui
⇒ cTn(z) = z · (z − 1)n−1 şi χ(Tn) ={
1 dacă n = 1,2 dacă n > 1.
3 Caz special: graful Pn (cale cu n noduri) este un arbore
special cu n noduri: v1 v2. . . vn
⇒ cPn(z) = z · (z − 1)n−1 şi χ(Pn) ={
1 dacă n = 1,2 dacă n > 1.
4 Graful complet Kn:cKn(z) = z · (z − 1) · . . . · (z − n + 1) şi χ(Kn) = n.
Curs 13
-
Colorarea grafurilor
Polinoame cromatice pentru grafuri speciale
1 Graful vid En:v1 v2 . . . vn
pentru fiecare nod, putem alege oricare din z culori:⇒ cEn(z) = zn şi χ(En) = 1
2 Arbore Tn cu n noduri:
z opţiuni pentru culoarea rădăciniiorice alt nod poate fi colorat cu orice culoare diferită ce cea anodului părinte ⇒ z − 1 opţiuni pentru colorarea lui
⇒ cTn(z) = z · (z − 1)n−1 şi χ(Tn) ={
1 dacă n = 1,2 dacă n > 1.
3 Caz special: graful Pn (cale cu n noduri) este un arbore
special cu n noduri: v1 v2. . . vn
⇒ cPn(z) = z · (z − 1)n−1 şi χ(Pn) ={
1 dacă n = 1,2 dacă n > 1.
4 Graful complet Kn:cKn(z) = z · (z − 1) · . . . · (z − n + 1) şi χ(Kn) = n.
Curs 13
-
Colorarea grafurilor
Polinoame cromatice pentru grafuri speciale
1 Graful vid En:v1 v2 . . . vn
pentru fiecare nod, putem alege oricare din z culori:⇒ cEn(z) = zn şi χ(En) = 1
2 Arbore Tn cu n noduri:
z opţiuni pentru culoarea rădăciniiorice alt nod poate fi colorat cu orice culoare diferită ce cea anodului părinte ⇒ z − 1 opţiuni pentru colorarea lui
⇒ cTn(z) = z · (z − 1)n−1 şi χ(Tn) ={
1 dacă n = 1,2 dacă n > 1.
3 Caz special: graful Pn (cale cu n noduri) este un arbore
special cu n noduri: v1 v2. . . vn
⇒ cPn(z) = z · (z − 1)n−1 şi χ(Pn) ={
1 dacă n = 1,2 dacă n > 1.
4 Graful complet Kn:cKn(z) = z · (z − 1) · . . . · (z − n + 1) şi χ(Kn) = n.
Curs 13
-
Colorarea grafurilor
Calculul polinoamelor cromaticeOperaţii speciale asupra unui graf
Fie G = (V ,E ) un graf neorientat şi e = (x , y) o muchie din E
I G − e este graful obţinut din G prin eliminarea muchiei eI G/e este graful obţinut din G astfel:
Se ı̂nlocuiesc nodurile x şi y cu un singur nod, care seı̂nvecinează cu vecinii lui x şi ai lui y .
Exemplu
G :
• •
•••• •
w za
b c
x y
G − (b, c):
G/(b, c):
• •
•••• •w za
b c
x y
• •
••• •w za
b&c
x y
Curs 13
-
Colorarea grafurilor
Calculul polinoamelor cromaticeFormule de calcul recursiv
Se observă că, pentru orice e ∈ E : cG (z) = cG−e(z)− cG/e(z)⇒ doi algoritmi de calcul recursiv al polinomului cromatic:
1 Se reduce G eliminând pe rând câte o muchie e ∈ E :
cG (z) = cG−e(z)− cG/e(z)
până când se obţin grafuri speciale En sau Tn:
Cazuri de bază: cEn(z) = zn şi cTn(z) = z · (z − 1)n−1
2 Se extinde G adăugând pe rând muchii e care lipsesc din G :
cG (z) = cḠ (z) + cḠ/e(z)
unde e este o muchie lipsă din G , şi Ḡ = G + e
Caz de bază: cKn(z) = z · (z − 1) · . . . · (z − n + 1)
Curs 13
-
Colorarea grafurilor
Calculul polinomului cromatic prin reducereExemplu ilustrat
G : cG (z) = cG1 (z)− cG2 (z), unde
a b
cd
e
G1:
a b
cd
e cG1 (z) = cG11 (z)− cG12 (z)unde G11 = G1 − (b, c)şi G12 = G1/(b, c)
G2:
a&b
cd
e cG2 (z) = cG21 (z)− cG22 (z)unde G21 = G2 − (a&b, c)şi G22 = G2/(a&b, c)
G11:
a b
cd
eG12:
a b&c
de
G21:
a&b
cd
eG22:
a&b&c
de
Grafurile următoare sunt izomorfe: G12 ≡ G21 şi G22 = K3, deci:
cG (z) = cG11(z)− 2 · cG12(z) + z(z − 1)(z − 2)︸ ︷︷ ︸cK3 (z)
Curs 13
-
Colorarea grafurilor
Calculul polinomului cromatic prin reducereExemplu ilustrat
G : cG (z) = cG1 (z)− cG2 (z), unde
a b
cd
e
G1:
a b
cd
e cG1 (z) = cG11 (z)− cG12 (z)unde G11 = G1 − (b, c)şi G12 = G1/(b, c)
G2:
a&b
cd
e cG2 (z) = cG21 (z)− cG22 (z)unde G21 = G2 − (a&b, c)şi G22 = G2/(a&b, c)
G11:
a b
cd
eG12:
a b&c
de
G21:
a&b
cd
eG22:
a&b&c
de
Grafurile următoare sunt izomorfe: G12 ≡ G21 şi G22 = K3, deci:
cG (z) = cG11(z)− 2 · cG12(z) + z(z − 1)(z − 2)︸ ︷︷ ︸cK3 (z)
Curs 13
-
Colorarea grafurilor
Calculul polinomului cromatic prin reducereExemplu ilustrat (continuare)
cG (z) = cG11(z)− 2 · cG12(z) + z(z − 1)(z − 2)
G11:
a b
cd
eG12:
a b&c
de
Se observă că
cG11(z) = cT5(z)− cT4(z) = z(z − 1)4 − z(z − 1)3
cG12(z) = cT4(z)− cT3(z) = z(z − 1)3 − z(z − 12)
⇒ cG (z) =z(z − 1)4 − z(z − 1)3 − 2(z(z − 1)3 − z(z − 1)2)+ z(z − 1)(z − 2)= z5 − 7 z4 + 18 z3 − 20 z2 + 8 z
Curs 13
-
Colorarea grafurilor
Calculul polinomului cromatic prin extindereExemplu ilustrat
G : cG (z) = cG1 (z) + cG2 (z), unde
a b
cd
e
G1 = G + (c, e) :
a b
cd
eG2 = G1/(c, e) :
a b
c&ed
cG2 (z) = z(z − 1)(z − 2)(z − 3) deoarece G2 ≡ K4, şi
cG1 (z) = cG11 (z) + cG12 (z) undeG11 :
a b
cd
eG12 :
a b&e
cd
cG11 (z) = cG111 (z) + cG112 (z)= cK5 (z) + cK4 (z) unde
G111 :
a b
cd
e
G111 ≡ K5
G112 :
b
a&cd
e
G112 ≡ K4
Curs 13
-
Colorarea grafurilor
Calculul polinomului cromatic prin extindereExemplu ilustrat (continuare)
cG (z) = cG1 (z) + cG2 (z) = (cG11 (z) + cG12 (z)) + cK4 (z)
= cK5 (z) + cK4 (z) + cG12 (z) + cK4 (z)
unde G12 :
a b&e
cd
cG12 (z) = cG121 (z) + cG122 (z) = cK4 (z) + cK3 (z) unde
unde G121 :
a b&e
cd
G121 ≡ K4
unde G122 :
a&c b&e
d
G122 ≡ K3
⇒ cG (z) = cK5 (z) + 3cK4 (z) + cK3 (z) = z5 − 7 z4 + 18 z3 − 20 z2 + 8 z
Curs 13
-
Colorarea grafurilor
Calculul polinomului cromatic prin extindereExemplu ilustrat (continuare)
cG (z) = cG1 (z) + cG2 (z) = (cG11 (z) + cG12 (z)) + cK4 (z)
= cK5 (z) + cK4 (z) + cG12 (z) + cK4 (z)
unde G12 :
a b&e
cd
cG12 (z) = cG121 (z) + cG122 (z) = cK4 (z) + cK3 (z) unde
unde G121 :
a b&e
cd
G121 ≡ K4
unde G122 :
a&c b&e
d
G122 ≡ K3
⇒ cG (z) = cK5 (z) + 3cK4 (z) + cK3 (z) = z5 − 7 z4 + 18 z3 − 20 z2 + 8 z
Curs 13
-
Colorarea grafurilor
Calculul polinomului cromatic prin extindereExemplu ilustrat (continuare)
cG (z) = cG1 (z) + cG2 (z) = (cG11 (z) + cG12 (z)) + cK4 (z)
= cK5 (z) + cK4 (z) + cG12 (z) + cK4 (z)
unde G12 :
a b&e
cd
cG12 (z) = cG121 (z) + cG122 (z) = cK4 (z) + cK3 (z) unde
unde G121 :
a b&e
cd
G121 ≡ K4
unde G122 :
a&c b&e
d
G122 ≡ K3
⇒ cG (z) = cK5 (z) + 3cK4 (z) + cK3 (z) = z5 − 7 z4 + 18 z3 − 20 z2 + 8 z
Curs 13
-
Colorarea grafurilor
Proprietăţi ale polinomului cromatic
Dacă G = (V ,E ) este un graf neorientat cu n noduri şi q muchiiatunci polinomul cromatic cG (z) satisface condiţiile următoare:
I Are gradul n.
I Coeficientul lui zn este 1.
I Coeficienţii săi au semne alternante.
I Termenul constant este 0.
I Coeficientul lui zn−1 este −q.
Exemplu
G :n = 5, q = 7
cG (z) = z5 − 7 z4 + 18 z3 − 20 z2 + 8 z
a b
cd
e
Curs 13
-
Colorarea grafurilor
Rezultate remarcabileHărţi şi grafuri planare
Fiecare ţară a unei hărţi se reprezintă ca nod al unui graf
Două noduri se conectează dacă şi numai dacă ţărilerespective au o graniţă nebanală (mai mult decât un punct)
⇒ graf neorientat GH corespunzător unei hărţi H. De exemplu:
Curs 13
-
Colorarea grafurilor
Rezultate remarcabileColorarea hărţii cu 4 culori
Observaţii:
1 Un graf G este planar dacă poate fi redesenat astfel ı̂ncâtmuchiile să nu i se intersecteze.
2 H este hartă dacă şi numai dacă GH este graf planar.
Ţările unei hărţi H pot fi colorate cu 4 culori, astfel ı̂ncât sănu existe ţări ı̂nvecinate colorate la fel.
1 Una dintre cele mai faimoase teoreme din Teoria GrafurilorDemonstraţie extrem de lungă şi complexăProblemă propusă in 1858, rezolvată de-abia ı̂n 1976 (Appel &Haken)Echivalentă cu faptul că graful planar GH este 4-colorabil.
2 Teorema este echivalentă cu afirmaţia:
χ(G ) ≤ 4 pentru orice graf planar G .
Curs 13
-
Colorarea grafurilor
Rezultate remarcabileColorarea hărţii cu 4 culori
Observaţii:
1 Un graf G este planar dacă poate fi redesenat astfel ı̂ncâtmuchiile să nu i se intersecteze.
2 H este hartă dacă şi numai dacă GH este graf planar.
Ţările unei hărţi H pot fi colorate cu 4 culori, astfel ı̂ncât sănu existe ţări ı̂nvecinate colorate la fel.
1 Una dintre cele mai faimoase teoreme din Teoria GrafurilorDemonstraţie extrem de lungă şi complexăProblemă propusă in 1858, rezolvată de-abia ı̂n 1976 (Appel &Haken)Echivalentă cu faptul că graful planar GH este 4-colorabil.
2 Teorema este echivalentă cu afirmaţia:
χ(G ) ≤ 4 pentru orice graf planar G .
Curs 13
-
Colorarea grafurilor
Rezultate remarcabileColorarea hărţii cu 4 culori
Observaţii:
1 Un graf G este planar dacă poate fi redesenat astfel ı̂ncâtmuchiile să nu i se intersecteze.
2 H este hartă dacă şi numai dacă GH este graf planar.
Ţările unei hărţi H pot fi colorate cu 4 culori, astfel ı̂ncât sănu existe ţări ı̂nvecinate colorate la fel.
1 Una dintre cele mai faimoase teoreme din Teoria GrafurilorDemonstraţie extrem de lungă şi complexăProblemă propusă in 1858, rezolvată de-abia ı̂n 1976 (Appel &Haken)Echivalentă cu faptul că graful planar GH este 4-colorabil.
2 Teorema este echivalentă cu afirmaţia:
χ(G ) ≤ 4 pentru orice graf planar G .
Curs 13
-
Colorarea grafurilor
Rezultate remarcabileColorarea hărţii cu 4 culori
Observaţii:
1 Un graf G este planar dacă poate fi redesenat astfel ı̂ncâtmuchiile să nu i se intersecteze.
2 H este hartă dacă şi numai dacă GH este graf planar.
Ţările unei hărţi H pot fi colorate cu 4 culori, astfel ı̂ncât sănu existe ţări ı̂nvecinate colorate la fel.
1 Una dintre cele mai faimoase teoreme din Teoria GrafurilorDemonstraţie extrem de lungă şi complexăProblemă propusă in 1858, rezolvată de-abia ı̂n 1976 (Appel &Haken)Echivalentă cu faptul că graful planar GH este 4-colorabil.
2 Teorema este echivalentă cu afirmaţia:
χ(G ) ≤ 4 pentru orice graf planar G .Curs 13
-
Colorarea grafurilor
Colorarea hărţii cu 5 culori
Ţările unei hărţi H pot fi colorate cu 5 culori, astfel ı̂ncât sănu existe ţări ı̂nvecinate colorate la fel. sau, echivalent:χ(G ) ≤ 5 pentru orice graf planar G .Demonstraţie: Inducţie după n = numărul de noduri din G .Teorema este evidentă pt. n ≤ 5, deci considerăm doar n ≥ 6.δ(G ) ≤ 5 datorită consecintȩi 4, deci G are un nod v cudeg(v) ≤ 5. Fie G ′ graful obţinut prin eliminarea lui v din G ⇒ G ′are n − 1 noduri, deci χ(G ′) ≤ 5 conform ipotezei inductive. Deciputem presupune că G ′ are o 5-colorare cu culorile 1,2,3,4,5.Cazul 1: deg(v) = d ≤ 4. Fie v1, . . . , vd vecinii lui v , cu culorilec1, . . . , cd .
v
v1
v2
vdc1
c2
cdpentru nodul v putem alege orice culoarec ∈ {1, 2, 3, 4, 5} − {c1, . . . , cd}⇒ G este 5-colorabil.
Curs 13
-
Colorarea grafurilor
Colorarea hărţii cu 5 culoriContinuarea demonstraţiei
Cazul 2: deg(v) = 5, deci v are 5 vecini v1, v2, v3, v4, v5 pe care-ipresupunem coloraţi cu culorile c1, c2, c3, c4, c5.
1 Dacă {c1, c2, c3, c4, c5} 6= {1, 2, 3, 4, 5}, putem să-l colorămpe v cu orice culoare c ∈ {1, 2, 3, 4, 5} − {c1, c2, c3, c4, c5}⇒ G este 5-colorabil.
2 Dacă {c1, c2, c3, c4, c5} = {1, 2, 3, 4, 5}, putem presupune căc1 = 1, c2 = 2, c3, c4 = 4, c5 = 5.
v
v1v2
v3
v4 v5
1
2
3
4 5
Idee de bază: Vom rearanja culorile lui G ′ pentru a facedisponibilă o culoare pentru v .
Curs 13
-
Colorarea grafurilor
Colorarea hărţii cu 5 culoriContinuarea demonstraţiei
v
v1v2
v3
v4 v5
1
2
3
4 5
Considerăm toate nodurile lui G ′ care sunt colorate cu 1 (roşu) şi 3 (verde).Cazul 2.1. G ′ nu are nici o cale de la v1 la v3 colorată doar cu 1 şi 3.Fie H subgraful lui G ′ care conţine toate căile ce pornesc din v1 şi sunt colorate doarcu 1 (roşu) şi 3 (verde).
v
..
. .
. ..
. ..
.
interschimbare
de culori ı̂n Hv
..
. .
. ..
. ..
.
V [v3] ∩ V (H) = ∅, adică nici v3 şi nici vecinii lui v3 nu sunt noduri din H.Putem interschimba culorile 1 şi 3 ı̂n H, iar apoi să atribuim culoarea 1 (roşu)lui v ⇒ G este 5-colorabil.
Curs 13
-
Colorarea grafurilor
Colorarea hărţii cu 5 culoriContinuarea demonstraţiei
v
v1v2
v3
v4 v5
1
2
3
4 5
Considerăm toate nodurile lui G ′ care sunt colorate cu 1 (roşu) şi 3 (verde).Cazul 2.1. G ′ nu are nici o cale de la v1 la v3 colorată doar cu 1 şi 3.Fie H subgraful lui G ′ care conţine toate căile ce pornesc din v1 şi sunt colorate doarcu 1 (roşu) şi 3 (verde).
v
..
. .
. ..
. ..
.
interschimbare
de culori ı̂n Hv
..
. .
. ..
. ..
.
V [v3] ∩ V (H) = ∅, adică nici v3 şi nici vecinii lui v3 nu sunt noduri din H.
Putem interschimba culorile 1 şi 3 ı̂n H, iar apoi să atribuim culoarea 1 (roşu)lui v ⇒ G este 5-colorabil.
Curs 13
-
Colorarea grafurilor
Colorarea hărţii cu 5 culoriContinuarea demonstraţiei
v
v1v2
v3
v4 v5
1
2
3
4 5
Considerăm toate nodurile lui G ′ care sunt colorate cu 1 (roşu) şi 3 (verde).Cazul 2.1. G ′ nu are nici o cale de la v1 la v3 colorată doar cu 1 şi 3.Fie H subgraful lui G ′ care conţine toate căile ce pornesc din v1 şi sunt colorate doarcu 1 (roşu) şi 3 (verde).
v
..
. .
. ..
. ..
.
interschimbare
de culori ı̂n Hv
..
. .
. ..
. ..
.
V [v3] ∩ V (H) = ∅, adică nici v3 şi nici vecinii lui v3 nu sunt noduri din H.Putem interschimba culorile 1 şi 3 ı̂n H, iar apoi să atribuim culoarea 1 (roşu)lui v ⇒ G este 5-colorabil.
Curs 13
-
Colorarea grafurilor
Colorarea hărţii cu 5 culoriContinuarea demonstraţiei
v
v1v2
v3
v4 v5
1
2
3
4 5
Considerăm toate nodurile lui G ′ care sunt colorate cu 1 (roşu) şi 3 (verde).Cazul 2.1. G ′ nu are nici o cale de la v1 la v3 colorată doar cu 1 şi 3.Fie H subgraful lui G ′ care conţine toate căile ce pornesc din v1 şi sunt colorate doarcu 1 (roşu) şi 3 (verde).
v
..
. .
. ..
. ..
.interschimbare
de culori ı̂n Hv
..
. .
. ..
. ..
.
V [v3] ∩ V (H) = ∅, adică nici v3 şi nici vecinii lui v3 nu sunt noduri din H.Putem interschimba culorile 1 şi 3 ı̂n H, iar apoi să atribuim culoarea 1 (roşu)lui v ⇒ G este 5-colorabil.
Curs 13
-
Colorarea grafurilor
Colorarea hărţii cu 5 culoriContinuarea demonstraţiei
v
v1v2
v3
v4 v5
12
3
4 5
Cazul 2.2. G ′ are o cale de la v1 la v3 colorată doar cu culorile 1 şi cu 3 ⇒ una dinurmătoarele situaţii are loc:
v
v2v3
v4 v5
v1
sauv
v2v3
v4 v5
v1
În ambele cazuri, nu poate exista o cale de la v2 la v4 colorată doar cu culorile 2 şi 4 ⇒cazul 2.1 este aplicabil pentru nodurile v2 şi v4 ⇒ G este 5-colorabil şi ı̂n cazul acesta.
Curs 13
Colorarea grafurilor