Curs 13 - Grafuri euleriene si grafuri hamiltoniene...

53
Colorarea grafurilor Curs 13 Grafuri euleriene ¸ si grafuri hamiltoniene. Colorarea grafurilor. Polinoame cromatice 21 decembrie 2018 Curs 13

Transcript of Curs 13 - Grafuri euleriene si grafuri hamiltoniene...

Page 1: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

Colorarea grafurilor

Curs 13Grafuri euleriene si grafuri hamiltoniene.

Colorarea grafurilor. Polinoame cromatice

21 decembrie 2018

Curs 13

Page 2: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 3: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 4: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 5: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 6: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 7: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 8: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 9: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 10: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 11: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 12: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 13: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 14: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 15: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 16: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 17: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 18: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 19: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 20: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 21: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 22: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 23: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 24: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 25: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 26: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 27: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 28: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 29: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 30: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 31: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 32: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 33: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 34: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 35: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 36: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 37: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 38: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 39: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 40: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 41: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 42: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 43: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 44: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 45: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 46: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 47: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 48: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 49: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 50: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 51: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 52: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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

Page 53: Curs 13 - Grafuri euleriene si grafuri hamiltoniene ...staff.fmi.uvt.ro/~mircea.marin/lectures/TGC/L-13ro.pdf · Colorarea grafurilor Grafuri euleriene Cum recunoa˘stem grafurile

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