Colorarea grafurilor
Curs 13Grafuri euleriene si grafuri hamiltoniene.
Colorarea grafurilor. Polinoame cromatice
21 decembrie 2018
Curs 13
Colorarea grafurilor
Grafuri euleriene
Fie G = (V ,E ) un graf neorientat.
O cale euleriana este o cale care contine fiecare muchie a lui G osingura data.
Un ciclu eulerian este un ciclu care contine fiecare muchie a lui G osingura data.
G este graf eulerian daca are un ciclu eulerian.
Exemple:
11
2
3
5
4
nu este graf eulerian (de ce?)are calea euleriana (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 recunoastem grafurile euleriene?
Teorema de caracterizare a grafurilor euleriene
Pentru un graf conex G = (V ,E), afirmatiile urmatoare sunt echivalente:
1 G este graf eulerian.
2 Fiecare nod al lui G are grad par.
3 Muchiile lui G pot fi partitionate ın cicluri care nu au muchii ın comun.
Demonstratia lui 1⇒ 2: Presupunem ca
B G este Eulerian ⇔ ∃ un ciclu care contine 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 cate ori ciclul eulerian intra ın un nod v pe o muchie, trebuie sa plece din acel
nod pe alta 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 eulerieneDemonstratie a Teoremei de Caracterizare (continuare)
Demonstratia lui 2⇒ 3: Presupunem ca fiecare nod al lui G aregrad par. Gandim inductiv dupa numarul de cicluri disjuncte ale lui G .
G nu are noduri de grad 1 ⇒ G nu este arbore ⇒ G are cel putin unciclu Cn1 .Fie G ′ graful produs din G prin eliminarea muchiilor lui Cn1 ⇒ toatenodurile lui G ′ au grad par ⇒ se deduce recursiv ca G ′ poate fipartitionat ın cicluri disjuncte Cn2 , . . . ,Cnk .
Rezulta ca Cn1 ,Cn2 , . . . ,Cnk este o partitie a lui G ın cicluri (cu muchii)disjuncte.
Demonstratia lui 3⇒ 1: evident.
Curs 13
Colorarea grafurilor
Detectia ciclurilor eulerieneAlgoritmul lui Hierholzer
Se da: un graf eulerian G = (V ,E )
Sa cauta un ciclu eulerian al lui G .
1 Se identifica un circuit R1 al lui G si se marcheaza muchiile lui R1.Fie i = 1.
2 Daca Ri contine toate muchiile lui G , stop: Ri este Eulerian.
3 Daca Ri nu contine toate muchiile lui G , fie vi un nod al Ri incidentla o muchie nemarcata ei .
4 Se construieste un ciclu de muchii nemarcate Qi , pornind de lanodul vi de-a lungul muchiei ei . Se marcheaza muchiile lui Qi .
5 Se creaza un ciclu nou Ri+1 ınlantuind Qi ın Ri la nodul vi .
6 Se incrementeaza i cu 1 si se revine la pasul (2).
Curs 13
Colorarea grafurilor
Detectia 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
Detectia cailor euleriene
Intrebare: Cum detectam daca un graf contine o cale euleriana?
Raspuns: Se observa ca:
Un graf eulerian contine un o cale eulerianadeoarece orice ciclu eulerian este si caleeuleriana.Exista grafuri ne-euleriene care contin caieuleriene.
Observatie
Un graf conex G contine o cale euleriana daca si numai daca arecel mult 2 noduri cu grad impar.
Curs 13
Colorarea grafurilor
Detectia cailor euleriene
Intrebare: Cum detectam daca un graf contine o cale euleriana?
Raspuns: Se observa ca:
Un graf eulerian contine un o cale eulerianadeoarece orice ciclu eulerian este si caleeuleriana.Exista grafuri ne-euleriene care contin caieuleriene.
Observatie
Un graf conex G contine o cale euleriana daca si numai daca arecel mult 2 noduri cu grad impar.
Curs 13
Colorarea grafurilor
Detectia cailor euleriene
Intrebare: Cum detectam daca un graf contine o cale euleriana?
Raspuns: Se observa ca:
Un graf eulerian contine un o cale eulerianadeoarece orice ciclu eulerian este si caleeuleriana.Exista grafuri ne-euleriene care contin caieuleriene.
Observatie
Un graf conex G contine o cale euleriana daca si numai daca arecel mult 2 noduri cu grad impar.
Curs 13
Colorarea grafurilor
Grafuri hamiltoniene
Fie G = (V ,E ) un graf neorientat.
O cale hamiltoniana este o cale care contine fiecare nod a lui G osingura data.
Un ciclu hamiltonian este un ciclu care trece prin fiecare nod a lui Go singura data.
G este traversabil daca contine o cale hamiltoniana.
G este graf hamiltonian daca are un ciclu hamiltonian.
Observatii:
1 Toate grafurile hamiltoniene sunt traversabile.
2 Exista grafuri traversable care nu sunt hamiltoniene; De exemplu,P3.
Curs 13
Colorarea grafurilor
Detectia grafurilor hamiltoniene
Nu se cunosc conditii necesare si suficiente de caracterizare agrafurilor hamiltoniene.
Se cunosc conditii suficiente pentru ca un graf sa fie sau sa nu fiehamiltonian:
1 Teorema lui Dirac2 Teorema lui Dirac generalizata3 Teorema lui Chvatal si Erdos4 Teorema Goodman si Hedetniemi5 Teorema lui Duffus, Gould si Jacobson
. . .
Curs 13
Colorarea grafurilor
Detectia grafurilor hamiltonieneTeorema lui Dirac
Teorema lui Dirac
Fie G un graf simplu cu ordinul n ≥ 3. Daca δ(G) ≥ n/2 atunci G este hamiltonian.
Demonstratie. Presupunem ca G satisface conditiile date, ınsa G nu estehamiltonian. Fie P = (v1, . . . , vp) o cale simpla ın G de lungime maximala ⇒ totivecinii lui v1 si ai lui vp sunt ın P. Deasemenea, v1 si vp au cel putin n/2 vecini ın Pfiindca δ(G) ≥ n/2.
Demonstram ca ∃j ∈ {1, . . . , p − 1} astfel ıncat vj ∈ N(vp) si vj+1 ∈ N(v1). Daca n-ar
fi asa, atunci pentru fiecare vecin vi de pe P al lui vp (retinem ca sunt ≥ n/2 astfel de
vi ), vi+1 nu este vecin al lui v1. Ar rezulta ca deg(v1) ≤ p − 1−n
2< n −
n
2=
n
2,
contradictie cu faptul ca δ(G) ≥ n/2. Deci, exista un astfel de j , pentru care avem
situatia ilustrata ın figura de mai jos:
Curs 13
Colorarea grafurilor
Detectia grafurilor hamiltonieneTeorema lui Dirac (continuare)
Teorema lui Dirac
Fie G un graf simplu cu ordinul n ≥ 3. Daca δ(G ) ≥ n/2 atunci G estehamiltonian.
Demonstratie. (continuare)
Fie C ciclul v1, v2, . . . , vj , vp, vp−1, . . . , vj+1, v1. Presupunand ca G nueste hamiltonian, exista un nod al lui G care nu este ın P.
Se observa ca, daca δ(G ) ≥ n/2 atunci G este conex.
⇒ G are un nod w care nu-i ın P si este adiacent la un nod vi din P.Dar atunci calea care porneste cu w , vi si continua ın jurul ciclului C estemai lunga decat P, contradictie.
In concluzie G trebuie sa fie graf hamiltonian. �
Curs 13
Colorarea grafurilor
Detectia grafurilor hamiltonieneAlte criterii si notiuni auxiliare
Teorema lui Dirac generalizata
Fie G un graf simplu cu ordinul n ≥ 3. Daca deg(x) + deg(y) ≥ n pentru toateperechile de noduri neadiacente x , y , atunci G este hamiltonian.
O multime de noduri a unui graf G este independenta daca nu contine noduriadiacente. Numarul de independenta α(G) al unui graf G este marimea cea mai mareposibila a unei multimi independente a lui G .
Exemplu
Se considera grafurile
Cea mai mare multime independenta a lui G1 este {c, d}, deci α(G1) = 2. Exista 2multimi independente cu marimea 3 ın G2 : {a, c, e} si {b, d , f }, si nici una cumarimea 4, deci α(G2) = 3.
Curs 13
Colorarea grafurilor
Detectia grafurilor hamiltonieneAlte criterii si notiuni auxiliare
Teorema lui Dirac generalizata
Fie G un graf simplu cu ordinul n ≥ 3. Daca deg(x) + deg(y) ≥ n pentru toateperechile de noduri neadiacente x , y , atunci G este hamiltonian.
O multime de noduri a unui graf G este independenta daca nu contine noduriadiacente. Numarul de independenta α(G) al unui graf G este marimea cea mai mareposibila a unei multimi independente a lui G .
Exemplu
Se considera grafurile
Cea mai mare multime independenta a lui G1 este {c, d}, deci α(G1) = 2. Exista 2multimi independente cu marimea 3 ın G2 : {a, c, e} si {b, d , f }, si nici una cumarimea 4, deci α(G2) = 3.
Curs 13
Colorarea grafurilor
Detectia grafurilor hamiltonieneAlte criterii si notiuni auxiliare. Teorema lui Chvatal si Erdos
Conectivitatea κ(G ) unui graf G este este marimea minima a uneimultimi de taiere a lui G . Spunem ca G este k-conectat daca k ≤ κ(G ).
Teorema (Chvatal si Erdos, 1972)
Fie G un graf conectat cu ordinal n ≥ 3, conectivitatea κ(G ), si numarulde independenta α(G ). Daca κ(G ) ≥ α(G ), atunci G este hamiltonian.
Exercitiu (Jocul icosian al lui Hamilton)
Sa se arate ca graful ilustrat ın cercul de mai jos este hamiltonian.
Curs 13
Colorarea grafurilor
Detectia grafurilor hamiltonieneDoua definitii si trei grafuri speciale
Date fiind doua grafuri G si H, spunem ca G este liber de Hdaca G nu contine subgraful H.
Daca S este o colectie de grafuri, spunem ca G este liber de Sdaca G nu contine nici unul din grafurile lui S ca subgraf.
Trei grafuri speciale
K1,3 Z1 N
Curs 13
Colorarea grafurilor
Detectia grafurilor hamiltonieneAlte rezultate
Teorema (Goodman si Hedetniemi, 1974)
Daca G este un graf 2-conectat si liber de {K1,3,Z1} atunci G estehamiltonian.
Demonstratie. Fie G un astfel de graf, si fie C un ciclu de lungimemaxima ın G . Deoarece G este 2-conectat, un astfel de ciclu C exista.Demonstram ca C este ciclu hamiltonian.Daca G nu ar fi hamiltonian, ar exista un nod v care nu este ın C si careeste adiacent la un nod w din C . Fie a si b succesorul si predecesorulimediat al lui w ın ciclul C .
Daca {a, b} ∩ N(v) 6= ∅ ⇒ ∃ un ciclu mai lung decat C ⇒ {a, b} ∩ N(v) = ∅.
Daca a, b nu sunt adiacente atunci subgraful indus de {w , v , a, b} este K1,3,
contradictie cu ipoteza ca G este liber de K1,3 ⇒ ab trebuie sa fie muchie ın G .
Insa ın acest caz subgraful indus de {w , v , a, b} este Z1, contradictie cu ipoteza
ca G este liber de Z1.
⇒ C este ciclu hamiltonian. �Curs 13
Colorarea grafurilor
Detectia grafurilor hamiltonieneAlte rezultate
Teorema (Duffus, Gould si Jacobson, 1981)
Fie G un graf liber de {K1,3,N}.1 Daca G este conectat atunci G este traversabil.
2 Daca G este 2-conectat atunci G este hamiltonian.
Observatii.
Ultimele 2 teoreme interzic ca graful K1,3 sa apara ca subgraf. Deobicei, graful K1,3 se numeste gheara, si este un graf interzis saapara ın numeroase teoreme din teoria grafurilor.
Curs 13
Colorarea grafurilor
Detectia grafurilor hamiltonieneAlte rezultate
Teorema (Duffus, Gould si Jacobson, 1981)
Fie G un graf liber de {K1,3,N}.1 Daca G este conectat atunci G este traversabil.
2 Daca G este 2-conectat atunci G este hamiltonian.
Observatii.
Ultimele 2 teoreme interzic ca graful K1,3 sa apara ca subgraf. Deobicei, graful K1,3 se numeste gheara, si este un graf interzis saapara ın numeroase teoreme din teoria grafurilor.
Curs 13
Colorarea grafurilor
Problema motivanta
Adi, Barbu, Calin, Dan, Eugen, Florin, Gelu si Ion sunt senatori aiunui stat, si fac parte din 7 comitete:
C1 = {Adi, Barbu, Calin}, C2 = {Calin, Dan, Eugen},C3 = {Dan,Florin}, C4 = {Adi, Gelu}, C5 = {Eugen, Ion},C6 = {Eugen,Barbu,Gelu}, C7 = {Ion, Calin, Florin}.
Fiecare comitet trebuie sa fixeze o ora la care sa se ıntalneasca totimembrii sai.
Intrebare: Care este numarul minim de ore ce trebuiesc fixatepentru ıntalniri, daca se stie ca nici un membru nupoate participa simultan la doua ıntalniri fixate laaceeasi ora?
Curs 13
Colorarea grafurilor
Raspuns la problema motivanta
Observatii:
Doua comitete Ci si Cj nu se pot ıntalni la aceeasi ora daca sinumai daca au un membru comun (adica Ci ∩ Cj = ∅).
⇒ Putem considera graful neorientat G cu
noduri = comitetele C1,C2,C3,C4,C5,C6,C7
muchii {Ci ,Cj} daca Ci si Cj au un membru comun (adicaCi ∩ 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}
Coloram fiecare nod Ci cu o culoare care reprezinta ora la careare loc ıntalnirea comitetului Ci
⇒ problema se poate reformula astfel: care este numarul minimde culori pentru nodurile lui G , astfel ıncat nici o muchie sa nuaiba capetele colorate la fel?
Curs 13
Colorarea grafurilor
Raspuns la problema motivanta
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)
Definitie (colorare de noduri, numar cromatic)
O k-colorare a nodurilor unui graf G = (V ,E ) este o functieK : V → {1, . . . , k} astfel ıncat K (u) 6= K (v) daca (u, v) ∈ E .Numarul cromatic χ(G ) al unui graf G este valoarea minima a luik ∈ N pt. care exista o k-colorare a lui G .
Curs 13
Colorarea grafurilor
Raspuns la problema motivanta
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)
Definitie (colorare de noduri, numar cromatic)
O k-colorare a nodurilor unui graf G = (V ,E ) este o functieK : V → {1, . . . , k} astfel ıncat K (u) 6= K (v) daca (u, v) ∈ E .Numarul cromatic χ(G ) al unui graf G este valoarea minima a luik ∈ N pt. care exista o k-colorare a lui G .
Curs 13
Colorarea grafurilor
Raspuns la problema motivanta
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)
Definitie (colorare de noduri, numar cromatic)
O k-colorare a nodurilor unui graf G = (V ,E ) este o functieK : V → {1, . . . , k} astfel ıncat K (u) 6= K (v) daca (u, v) ∈ E .Numarul cromatic χ(G ) al unui graf G este valoarea minima a luik ∈ N pt. care exista o k-colorare a lui G .
Curs 13
Colorarea grafurilor
Colorari de noduriPolinoame cromatice
Calculul lui χ(G ) este o problema dificila (NP-completa).
Birkhoff (≈ 1900) a descoperit o metoda de calcul al unuipolinom cG (z) pentru orice graf G , numit polinomul cromatical lui G , astfel ıncat
cG (k) = numarul de k-colorari ale nodurilor lui G
⇒ χ(G ) = valoarea minima 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
Colorari de noduriPolinoame cromatice
Calculul lui χ(G ) este o problema dificila (NP-completa).
Birkhoff (≈ 1900) a descoperit o metoda de calcul al unuipolinom cG (z) pentru orice graf G , numit polinomul cromatical lui G , astfel ıncat
cG (k) = numarul de k-colorari ale nodurilor lui G
⇒ χ(G ) = valoarea minima 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 si χ(En) = 1
2 Arbore Tn cu n noduri:
z optiuni pentru culoarea radaciniiorice alt nod poate fi colorat cu orice culoare diferita ce cea anodului parinte ⇒ z − 1 optiuni pentru colorarea lui
⇒ cTn(z) = z · (z − 1)n−1 si χ(Tn) =
{1 daca n = 1,2 daca 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 si χ(Pn) =
{1 daca n = 1,2 daca n > 1.
4 Graful complet Kn:cKn(z) = z · (z − 1) · . . . · (z − n + 1) si χ(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 si χ(En) = 1
2 Arbore Tn cu n noduri:
z optiuni pentru culoarea radaciniiorice alt nod poate fi colorat cu orice culoare diferita ce cea anodului parinte ⇒ z − 1 optiuni pentru colorarea lui
⇒ cTn(z) = z · (z − 1)n−1 si χ(Tn) =
{1 daca n = 1,2 daca 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 si χ(Pn) =
{1 daca n = 1,2 daca n > 1.
4 Graful complet Kn:cKn(z) = z · (z − 1) · . . . · (z − n + 1) si χ(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 si χ(En) = 1
2 Arbore Tn cu n noduri:
z optiuni pentru culoarea radaciniiorice alt nod poate fi colorat cu orice culoare diferita ce cea anodului parinte ⇒ z − 1 optiuni pentru colorarea lui
⇒ cTn(z) = z · (z − 1)n−1 si χ(Tn) =
{1 daca n = 1,2 daca 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 si χ(Pn) =
{1 daca n = 1,2 daca n > 1.
4 Graful complet Kn:cKn(z) = z · (z − 1) · . . . · (z − n + 1) si χ(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 si χ(En) = 1
2 Arbore Tn cu n noduri:
z optiuni pentru culoarea radaciniiorice alt nod poate fi colorat cu orice culoare diferita ce cea anodului parinte ⇒ z − 1 optiuni pentru colorarea lui
⇒ cTn(z) = z · (z − 1)n−1 si χ(Tn) =
{1 daca n = 1,2 daca 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 si χ(Pn) =
{1 daca n = 1,2 daca n > 1.
4 Graful complet Kn:cKn(z) = z · (z − 1) · . . . · (z − n + 1) si χ(Kn) = n.
Curs 13
Colorarea grafurilor
Calculul polinoamelor cromaticeOperatii speciale asupra unui graf
Fie G = (V ,E ) un graf neorientat si e = (x , y) o muchie din E
I G − e este graful obtinut din G prin eliminarea muchiei e
I G/e este graful obtinut din G astfel:
Se ınlocuiesc nodurile x si y cu un singur nod, care seınvecineaza cu vecinii lui x si 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 observa ca, pentru orice e ∈ E : cG (z) = cG−e(z)− cG/e(z)⇒ doi algoritmi de calcul recursiv al polinomului cromatic:
1 Se reduce G eliminand pe rand cate o muchie e ∈ E :
cG (z) = cG−e(z)− cG/e(z)
pana cand se obtin grafuri speciale En sau Tn:
Cazuri de baza: cEn(z) = zn si cTn(z) = z · (z − 1)n−1
2 Se extinde G adaugand pe rand muchii e care lipsesc din G :
cG (z) = cG (z) + cG/e(z)
unde e este o muchie lipsa din G , si G = G + e
Caz de baza: 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)si G12 = G1/(b, c)
G2:
a&b
cd
e cG2(z) = cG21
(z)− cG22(z)
unde G21 = G2 − (a&b, c)si G22 = G2/(a&b, c)
G11:
a b
cd
eG12:
a b&c
de
G21:
a&b
cd
eG22:
a&b&c
de
Grafurile urmatoare sunt izomorfe: G12 ≡ G21 si 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)si G12 = G1/(b, c)
G2:
a&b
cd
e cG2(z) = cG21
(z)− cG22(z)
unde G21 = G2 − (a&b, c)si G22 = G2/(a&b, c)
G11:
a b
cd
eG12:
a b&c
de
G21:
a&b
cd
eG22:
a&b&c
de
Grafurile urmatoare sunt izomorfe: G12 ≡ G21 si 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 observa ca
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, si
cG1(z) = cG11
(z) + cG12(z) unde G11 :
a b
cd
eG12 :
a b&e
cd
cG11(z) = cG111
(z) + cG112(z)
= cK5(z) + cK4
(z) undeG111 :
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
Proprietati ale polinomului cromatic
Daca G = (V ,E ) este un graf neorientat cu n noduri si q muchiiatunci polinomul cromatic cG (z) satisface conditiile urmatoare:
I Are gradul n.
I Coeficientul lui zn este 1.
I Coeficientii sai 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 remarcabileHarti si grafuri planare
Fiecare tara a unei harti se reprezinta ca nod al unui graf
Doua noduri se conecteaza daca si numai daca tarilerespective au o granita nebanala (mai mult decat un punct)
⇒ graf neorientat GH corespunzator unei harti H. De exemplu:
Curs 13
Colorarea grafurilor
Rezultate remarcabileColorarea hartii cu 4 culori
Observatii:
1 Un graf G este planar daca poate fi redesenat astfel ıncatmuchiile sa nu i se intersecteze.
2 H este harta daca si numai daca GH este graf planar.
Tarile unei harti H pot fi colorate cu 4 culori, astfel ıncat sanu existe tari ınvecinate colorate la fel.
1 Una dintre cele mai faimoase teoreme din Teoria GrafurilorDemonstratie extrem de lunga si complexaProblema propusa in 1858, rezolvata de-abia ın 1976 (Appel &Haken)Echivalenta cu faptul ca graful planar GH este 4-colorabil.
2 Teorema este echivalenta cu afirmatia:
χ(G ) ≤ 4 pentru orice graf planar G .
Curs 13
Colorarea grafurilor
Rezultate remarcabileColorarea hartii cu 4 culori
Observatii:
1 Un graf G este planar daca poate fi redesenat astfel ıncatmuchiile sa nu i se intersecteze.
2 H este harta daca si numai daca GH este graf planar.
Tarile unei harti H pot fi colorate cu 4 culori, astfel ıncat sanu existe tari ınvecinate colorate la fel.
1 Una dintre cele mai faimoase teoreme din Teoria GrafurilorDemonstratie extrem de lunga si complexaProblema propusa in 1858, rezolvata de-abia ın 1976 (Appel &Haken)Echivalenta cu faptul ca graful planar GH este 4-colorabil.
2 Teorema este echivalenta cu afirmatia:
χ(G ) ≤ 4 pentru orice graf planar G .
Curs 13
Colorarea grafurilor
Rezultate remarcabileColorarea hartii cu 4 culori
Observatii:
1 Un graf G este planar daca poate fi redesenat astfel ıncatmuchiile sa nu i se intersecteze.
2 H este harta daca si numai daca GH este graf planar.
Tarile unei harti H pot fi colorate cu 4 culori, astfel ıncat sanu existe tari ınvecinate colorate la fel.
1 Una dintre cele mai faimoase teoreme din Teoria GrafurilorDemonstratie extrem de lunga si complexaProblema propusa in 1858, rezolvata de-abia ın 1976 (Appel &Haken)Echivalenta cu faptul ca graful planar GH este 4-colorabil.
2 Teorema este echivalenta cu afirmatia:
χ(G ) ≤ 4 pentru orice graf planar G .
Curs 13
Colorarea grafurilor
Rezultate remarcabileColorarea hartii cu 4 culori
Observatii:
1 Un graf G este planar daca poate fi redesenat astfel ıncatmuchiile sa nu i se intersecteze.
2 H este harta daca si numai daca GH este graf planar.
Tarile unei harti H pot fi colorate cu 4 culori, astfel ıncat sanu existe tari ınvecinate colorate la fel.
1 Una dintre cele mai faimoase teoreme din Teoria GrafurilorDemonstratie extrem de lunga si complexaProblema propusa in 1858, rezolvata de-abia ın 1976 (Appel &Haken)Echivalenta cu faptul ca graful planar GH este 4-colorabil.
2 Teorema este echivalenta cu afirmatia:
χ(G ) ≤ 4 pentru orice graf planar G .
Curs 13
Colorarea grafurilor
Colorarea hartii cu 5 culori
Tarile unei harti H pot fi colorate cu 5 culori, astfel ıncat sanu existe tari ınvecinate colorate la fel. sau, echivalent:χ(G ) ≤ 5 pentru orice graf planar G .
Demonstratie: Inductie dupa n = numarul de noduri din G .Teorema este evidenta pt. n ≤ 5, deci consideram doar n ≥ 6.δ(G ) ≤ 5 datorita consecintei 4, deci G are un nod v cudeg(v) ≤ 5. Fie G ′ graful obtinut prin eliminarea lui v din G ⇒ G ′
are n − 1 noduri, deci χ(G ′) ≤ 5 conform ipotezei inductive. Deciputem presupune ca 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 hartii cu 5 culoriContinuarea demonstratiei
Cazul 2: deg(v) = 5, deci v are 5 vecini v1, v2, v3, v4, v5 pe care-ipresupunem colorati cu culorile c1, c2, c3, c4, c5.
1 Daca {c1, c2, c3, c4, c5} 6= {1, 2, 3, 4, 5}, putem sa-l colorampe v cu orice culoare c ∈ {1, 2, 3, 4, 5} − {c1, c2, c3, c4, c5}⇒ G este 5-colorabil.
2 Daca {c1, c2, c3, c4, c5} = {1, 2, 3, 4, 5}, putem presupune cac1 = 1, c2 = 2, c3, c4 = 4, c5 = 5.
v
v1
v2v3
v4 v5
1
2
3
4 5
Idee de baza: Vom rearanja culorile lui G ′ pentru a facedisponibila o culoare pentru v .
Curs 13
Colorarea grafurilor
Colorarea hartii cu 5 culoriContinuarea demonstratiei
v
v1
v2v3
v4 v5
1
2
3
4 5
Consideram toate nodurile lui G ′ care sunt colorate cu 1 (rosu) si 3 (verde).Cazul 2.1. G ′ nu are nici o cale de la v1 la v3 colorata doar cu 1 si 3.Fie H subgraful lui G ′ care contine toate caile ce pornesc din v1 si sunt colorate doarcu 1 (rosu) si 3 (verde).
v
..
. .
. ..
. ..
.
interschimbare
de culori ın Hv
..
. .
. ..
. ..
.
V [v3] ∩ V (H) = ∅, adica nici v3 si nici vecinii lui v3 nu sunt noduri din H.
Putem interschimba culorile 1 si 3 ın H, iar apoi sa atribuim culoarea 1 (rosu)lui v ⇒ G este 5-colorabil.
Curs 13
Colorarea grafurilor
Colorarea hartii cu 5 culoriContinuarea demonstratiei
v
v1
v2v3
v4 v5
1
2
3
4 5
Consideram toate nodurile lui G ′ care sunt colorate cu 1 (rosu) si 3 (verde).Cazul 2.1. G ′ nu are nici o cale de la v1 la v3 colorata doar cu 1 si 3.Fie H subgraful lui G ′ care contine toate caile ce pornesc din v1 si sunt colorate doarcu 1 (rosu) si 3 (verde).
v
..
. .
. ..
. ..
.
interschimbare
de culori ın Hv
..
. .
. ..
. ..
.
V [v3] ∩ V (H) = ∅, adica nici v3 si nici vecinii lui v3 nu sunt noduri din H.
Putem interschimba culorile 1 si 3 ın H, iar apoi sa atribuim culoarea 1 (rosu)lui v ⇒ G este 5-colorabil.
Curs 13
Colorarea grafurilor
Colorarea hartii cu 5 culoriContinuarea demonstratiei
v
v1
v2v3
v4 v5
1
2
3
4 5
Consideram toate nodurile lui G ′ care sunt colorate cu 1 (rosu) si 3 (verde).Cazul 2.1. G ′ nu are nici o cale de la v1 la v3 colorata doar cu 1 si 3.Fie H subgraful lui G ′ care contine toate caile ce pornesc din v1 si sunt colorate doarcu 1 (rosu) si 3 (verde).
v
..
. .
. ..
. ..
.
interschimbare
de culori ın Hv
..
. .
. ..
. ..
.
V [v3] ∩ V (H) = ∅, adica nici v3 si nici vecinii lui v3 nu sunt noduri din H.
Putem interschimba culorile 1 si 3 ın H, iar apoi sa atribuim culoarea 1 (rosu)lui v ⇒ G este 5-colorabil.
Curs 13
Colorarea grafurilor
Colorarea hartii cu 5 culoriContinuarea demonstratiei
v
v1
v2v3
v4 v5
1
2
3
4 5
Consideram toate nodurile lui G ′ care sunt colorate cu 1 (rosu) si 3 (verde).Cazul 2.1. G ′ nu are nici o cale de la v1 la v3 colorata doar cu 1 si 3.Fie H subgraful lui G ′ care contine toate caile ce pornesc din v1 si sunt colorate doarcu 1 (rosu) si 3 (verde).
v
..
. .
. ..
. ..
.interschimbare
de culori ın Hv
..
. .
. ..
. ..
.
V [v3] ∩ V (H) = ∅, adica nici v3 si nici vecinii lui v3 nu sunt noduri din H.
Putem interschimba culorile 1 si 3 ın H, iar apoi sa atribuim culoarea 1 (rosu)lui v ⇒ G este 5-colorabil.
Curs 13
Colorarea grafurilor
Colorarea hartii cu 5 culoriContinuarea demonstratiei
v
v1
v2v3
v4 v5
12
3
4 5
Cazul 2.2. G ′ are o cale de la v1 la v3 colorata doar cu culorile 1 si cu 3 ⇒ una dinurmatoarele situatii are loc:
v
v2v3
v4 v5
v1
sauv
v2v3
v4 v5
v1
In ambele cazuri, nu poate exista o cale de la v2 la v4 colorata doar cu culorile 2 si 4 ⇒cazul 2.1 este aplicabil pentru nodurile v2 si v4 ⇒ G este 5-colorabil si ın cazul acesta.
Curs 13