Grafuri planare. Teorema lui Kuratowski. Teoria lui...

Curs 14Grafuri planare. Teorema lui Kuratowski.

Teoria lui Ramsey

11 ianuarie 2019

Curs 14

Grafuri planareDefinitii si exemple

Un graf G este planar daca poate fi desenat ın plan astfel ıncatmuchiile sa nu se intersecteze decat ın nodurile grafului. O astfelde desenare se numeste reprezentare planara a lui G .

Exemplu (Grafuri planare)

. . . . ...

.. . .

..

. .

.

.

.

.

.

Curs 14

Notiuni auxiliare

Regiune a unei reprezentari planare a grafului G : portiune din plan ıncare orice 2 puncte pot fi unite cu o curba care nu intersecteaza G

Exemplu

. . .

.

.

.

. .

.

. .

determina 7 regiuni

R1R7

R2 R3R4

R5 R6

R7 este regiunea exterioara

Orice regiune este delimitata de muchii.

Orice muchie este ın contact cu una sau doua regiuni.

O muchie margineste o regiune R daca este ın contact cu R si cualta regiune.

Curs 14

Notiuni auxiliare

Regiune a unei reprezentari planare a grafului G : portiune din plan ıncare orice 2 puncte pot fi unite cu o curba care nu intersecteaza G

Exemplu

. . .

.

.

.

. .

.

. .

determina 7 regiuniR1R7

R2 R3R4

R5 R6

R7 este regiunea exterioara

Orice regiune este delimitata de muchii.

Orice muchie este ın contact cu una sau doua regiuni.

O muchie margineste o regiune R daca este ın contact cu R si cualta regiune.

Curs 14

Regiuni si grade de marginire

.

.

.

.

..

. .

e1

e2

e3

e4

e5

e 6e 7

e8

e9

S1

S2 S3

e1 este ın contact doar cu S1

e2 si e3 sunt ın contact doar cu S2

S1 este marginita de e7, e8, e9

S3 este marginita de e4, e5, e6

S2 este marginita de e4, e5, e6, e7, e8, e9

Gradul de marginire b(S) al unei regiuni S este numarul de muchiicare marginesc S .

b(S1) = 3, b(S2) = 6, b(S3) = 3

Curs 14

Proprietati

Fie G un graf conex cu n noduri, q muchii, si o reprezentare planara a luiG cu r regiuni.

n − q + r = 2 ın toate cazurile.

Curs 14

Proprietati ale grafurilor planare conexe

Teorema (Formula lui Euler)

Daca G este un graf planar conex cu n noduri, q muchii si rregiuni, atunci n − q + r = 2.

Demonstratie: Inductie dupa q.Cazul 1: q = 0⇒ G = K1, pentru care n = 1, q = 0, r = 1, decin − q + r = 2.Cazul 2: G este arbore ⇒ q = n − 1 si r = 1, decin − q + r = n − (n − 1) + 1 = 2.Cazul 3: G este arbore conex cu cel putin 1 ciclu. Fie e omuchie din ciclul respectiv, si G ′ = G − e.G ′ este conex cu n noduri, q − 1 muchii, si r − 1 regiuni ⇒conform ipotezei inductive: n − (q − 1) + (r − 1) = 2. Rezulta can − q + r = 2 are loc si ın acest caz.

Curs 14

Consecinte ale formulei lui Euler

Consecinta 1

K3,3 nu este graf planar.

Demonstratie: K3,3 are n = 6 si q = 9 ⇒ daca ar fi planar, ar

avea r = q − n + 2 = 5 regiuni Ri (1 ≤ i ≤ 5). Fie C =5∑

i=1

b(Ri ).

Orice muchie margineste cel mult 2 regiuni ⇒ C ≤ 2 q = 18.

K3,3 este bipartit ⇒ nu contine C3 ca subgraf, deci b(Si ) ≥ 4pentru toti i , si prin urmare C ≥ 4 · 5 = 20

⇒ contradictie, deci K3,3 nu poate fi graf planar.

Curs 14


Consecinta 2

Daca G este graf planar cu n ≥ 3 noduri si q muchii atunci q ≤ 3 n − 6.Mai mult, daca q = 3 n− 6 atunci b(S) = 3 pentru orice regiune S din G .

Demonstratie. Fie R1, . . . ,Rr regiunile lui G , si C =r∑

i=1

b(Ri ). Stim

ca C ≤ 2 q si ca C ≥ 3r (deoarece b(Ri ) ≥ 3 pentru toti i). Deci3 r ≤ 2 q ⇒ 3 (2 + q − n) ≤ 2 q ⇒ q ≤ 3n − 6.Daca egalitatea are loc, atunci3 r = 2 q ⇒ C =

∑ri=1 b(Ri ) = 3 r ⇒ b(Ri ) = 3 pt. toate regiunile Ri .

Consecinta 3

K5 nu este graf planar.

Demonstratie: K5 are n = 5 noduri si q = 10 muchii

⇒ 3 n − 6 = 9 < 10 = q ⇒ K5 nu poate fi planar (cf. Consecintei 2).

Curs 14


Consecinta 4

δ(G ) ≤ 5 pentru orice graf planar G .

Demonstratie: Presupunem ca G este graf planar cu n noduri siq muchii.Cazul 1: n ≤ 6⇒ orice nod are grad ≤ 5 ⇒ δ(G ) ≤ 5.

Cazul 2: n > 6. Fie D =∑v∈V

deg(v). Rezulta ca

D = 2 q (evident)

≤ 2 (3 n − 6) (conform Consecintei 2)

= 6 n − 12.

Daca δ(G ) ≥ 6 atunci D =∑v∈V

deg(v) ≥∑v∈V

6 = 6 n, contradictie.

Deci δ(G ) ≤ 5 trebuie sa aiba loc.

Curs 14

Subdiviziuni

Fie G = (V ,E ) un graf neorientat, si (x , y) o muchie.

O subdiviziune a lui (x , y) ın G este o ınlocuire a lui (x , y) ınG cu o cale de la x la y prin puncte intermediare noi.

Un graf H este o subdiviziune a unui graf G daca H se poateobtine din G printr-o secventa finita de subdiviziuni de muchii.

Exemplu

G :.

. .

.

. H :.

. .

.

...

.

.

Curs 14

Criterii de detectie a grafurilor planare

Spunem ca un graf G contine un graf H daca H se poate obtineprin eliminarea de noduri si muchii din G .

Remarca

Daca H este subgraf al lui G atunci G contine H. Reciproca estefalsa: ,,G contine H” nu implica ,,H este subgraf al lui G”.

H este subgraf al lui G doar daca se poate obtine din G prineliminare de noduri.

Teorema (Teorema lui Kuratowski)

G este graf planar daca si numai daca nu contine subdiviziuni alelui K3,3 si ale lui K5.

Curs 14

Detectia grafurilor neplanareCriteriu bazat pe Teorema lui Kuratowski

Este G = (V ,E ) neplanar?1 Mai ıntai verificam daca G contine o subdiviziune a lui K3,3:

I Determinam multimea S de noduri v ∈ E cu deg(v) ≥ 3.

Daca |S | < 6, G nu poate contine o subdiviziune a lui K3,3.Altfel, verificam daca putem alege 6 puncte din S care pot ficapete ale unei subdiviziuni a lui K3,3.

2 Apoi, verificam daca G contine o subdiviziune a lui K5:I Determinam multimea S ′ de noduri v ∈ E cu deg(v) ≥ 4.

Daca |S ′| < 5, G nu poate contine o subdiviziune a lui K5.Altfel, verificam daca putem alege 5 puncte din S ′ care pot ficapete ale unei subdiviziuni a lui K3,3.

3 Daca ambele verificari esueaza ⇒ G este graf planar.

Curs 14

Teorema lui KuratowskiExemple ilustrate

Aplicati teorema lui Kuratowski pentru a decide care din grafurileurmatoare este planar:

1. 1

7

23

4

5 6

Nu, deoarece contine o subdiviziune a lui K3,3:

1 7

3

5

2

4

6

2. 1

23

4

5

67

8

Nu, deoarece contine o subdiviziune a lui K3,3:

4

5

6

2

1

8

3

7

Curs 14



3. 1

23

4

5

67

8

Nu, deoarece contine o subdiviziune a lui K5:

2

35

6 4 87

1

4.

a1

a2

a3 a4

a5

1

2

3 4

5

Nu, deoarece contine o subdiviziune a lui K3,3:a4

1

a3

5

a1

2

4

3

a5 a2

Curs 14



3. 1

23

4

5

67

8

Nu, deoarece contine o subdiviziune a lui K5:

2

35

6 4 87

1

4.

a1

a2

a3 a4

a5

1

2

3 4

5Nu, deoarece contine o subdiviziune a lui K3,3:a4

1

a3

5

a1

2

4

3

a5 a2

Curs 14

Teoria lui RamseyIntroducere

Teoria lui Ramsey = teorie referitoare la studiul obiectelorcombinatoriale si a conditiilor care se ocupa cu distributiasubmultimilor de elemente ale unei multimi.

Numita dupa matematicianul si filozoful englez Frank P.Ramsey (1903-1930).

Rezultate semnificative au fost descoperite ulterilor de P.Erdos.

In prezent: tema activa de cercetare ın TGC: numeroaseprobleme nerezolvate ınca.

Problema grupului de persoane ıntrunite:

Care este numarul minim R(m, n) de persoane care trebuieinvitate la o ıntrunire, pentru a fi siguri ca una dinurmatoarele conditii are loc:

1 ori exista un grup de m persoane care se cunosc toate ıntre ele2 ori exista un grup de n persoane ın care nimeni nu se cunoaste

cu nimeni.

Curs 14

Notiuni preliminare

O 2-colorare a muchiilor unui graf G este o functie careatribuie o culoare din o multime de 2 culori la toate muchiilelui G .

Exemplu (O 2-colorare a lui K5)•

••

••

Pentru doua numere pozitive date p si q, numarul Ramsey (clasic)R(p, q) asociat lor este cel mai mic ıntreg n astfel ıncat orice2-colorare a lui Kn cu rosu si albastru sa contina un subgraf Kp

rosu, sau un subgraf Kq albastru.

Intrebare: care este valoarea lui R(1, 3)?Raspuns: 1 . . . de ce?Intrebare: care este valoarea lui R(1, q)?

Curs 14

Notiuni preliminare



••

••



Intrebare: care este valoarea lui R(1, 3)?

Raspuns: 1 . . . de ce?Intrebare: care este valoarea lui R(1, q)?

Curs 14

Notiuni preliminare



••

••



Intrebare: care este valoarea lui R(1, 3)?Raspuns: 1 . . . de ce?

Intrebare: care este valoarea lui R(1, q)?

Curs 14

Notiuni preliminare



••

••



Intrebare: care este valoarea lui R(1, 3)?Raspuns: 1 . . . de ce?Intrebare: care este valoarea lui R(1, q)?

Curs 14

Numere RamseyExemplu: R(2, 4)

Fapt: R(2, 4) = 4.Demonstratie. Conform definitiei, R(2, 4) ≥ 2.R(2, 4) ≥ 4 deoarece existenta urmatoarelor 2-colorari de muchiiindica faptul ca R(2, 4) 6∈ {2, 3}.

• • • •

•

K2 K3

Orice colorare rosu-albastru a lui K4 contine fie un K2 rosu sau unK4 albastru deoarece:

Daca exista o muchie rosie, exista un subgraf K2 rosu.

Altfel, toate muchiile sunt albastre, deci graful ınsusi este unsubgraf K4 albastru.

Curs 14

Exercitii

1 Cate 2-colorari diferite (modulo simetrii) are K3? K4? K5?K10?

2 Dati o demonstratie simpla a faptului ca R(1, k) = 1 pentrutoti ıntregii pozitivi k.

3 Dati o demonstratie simpla a faptului ca R(2, k) = k pentrutoti ıntregii k ≥ 2.

4 Explicati de ce, pentru totii ıntregii pozitivi p si q are locR(p, q) = R(q, p).

5 Daca 2 ≤ p′ ≤ p si 2 ≤ q′ ≤ q, demonstrati caR(p′, q′) ≤ R(p, q). Mai mult, egalitatea R(p′, q′) = R(p, q)are loc ın acest caz daca si numai daca p′ = p si q′ = q.

Curs 14

O problema Ramsey clasica

Cate persoane trebuiesc invitate la o petrecere a.ı. sa existecel putin un grup de 3 persoane care se cunosc toti ıntre ei,sau un grup de 3 persoane ın care nimeni nu se cunoaste cunimeni?

Sau, ın teoria lui Ramsey: Care este valoarea minima a lui na.ı. orice colorare rosu-albastru a muchiilor lui Kn sa continafie un K3 rosu sau un K3 albastru?

. Altfel spus, care este valoarea lui R(3, 3)?

Curs 14

O problema Ramsey clasica

Teorema

R(3, 3) = 6.

Demonstratie. R(3, 3) > 5 deoarece 2-colorarea lui K5 de mai jos nucontine nici un K3 rosu si nici un K3 albastru.

K5:

•

••

••

K6:

v

x

y

z

•

•

Subcazul 1: toate muchiile (x,y),(x,z),(y,z) sunt albastre

⇒ exista un K3 albastru

Subcazul 2: cel putin una din muchiile (x,y),(x,z),(y,z) este rosie

⇒ exista un K3 rosu

Fie o colorare rosu-albastru a muchiilor lui K6, si v unul din noduri.

I v este incident la 5 muchii.I Conform Principiului Porumbelului, fie v este incident la ≥ 3 muchiirosii, fie v este incident la ≥ 3 muchii albastre.

Putem presupune ca, ın general, v este incident la 3 muchii rosii (v , x),

(v , y), (v , z).

Curs 14

Alta problema Ramsey

Teorema

R(3, 4) = 9.

Demonstratie. 2-colorarea lui K8 de mai jos nu contine nici un K3

rosu si nici un K4 albastru, deci R(3, 4) > 8.

•

••

•

•

••

•

Vom demonstra ca R(3, 4) ≤ 9 stiind ca R(2, 4) = 4 si R(3, 3) = 6.Sa presupunem ca muchiile lui G = Kn (n ≥ 9) au fost colorate curosu-albastru, si fie v un nod al lui G . Distingem 3 cazuri:

(vezi slide-urile urmatoare.)

Curs 14

Teorema: R(3, 4) = 9Demonstratia cazului 1: v este incident la ≥ 4 muchii rosii

Fie S := multimea nodurilor incidente la v cu o muchie rosie.

•v

•

•

•

•

R(2, 4) = 4 si |S | ≥ 4⇒ fie S are un K2 rosu sau un K4 albastru.Prima posibilitate implica faptul ca G are un K3 rosu, iar a douaimplica faptul ca G are un K4 albastru.

Curs 14

Teorema: R(3, 4) = 9Demonstratia cazului 2: v este incident la ≥ 6 muchii albastre

Fie T :=multimea nodurilor incidente la v cu o muchie albastra.

•v

••••••

|T | = 6 si R(3, 3) = 6⇒ T contine un K3 rosu sau albastru.Primul caz implica faptul ca G are un K3 rosu. In cazul al doileaavem situatia ilustrata mai jos ⇒ G contine un K4.

•v

•

•

••••

Curs 14

Teorema: R(3, 4) = 9Demonstratia cazului 3: v este incident la < 4 muchii rosii si la < 6 muchii albastre

Fie T :=multimea nodurilor incidente la v cu o muchie albastra.Deoarece presupunem ca G are ≥ 9 noduri, trebuie ca G sa aibeexact 9 noduri ⇒ v este incident la 3 muchii rosii si 5 albastre.Deoarece v a fost ales arbitrar, putem presupune ca aceastaproprietate are loc pentru toate nodurile lui G .

⇒ subgraful rosu al lui G are 9 noduri, si fiecare nod are gradul3. Aceasta situatie este imposibila deoarece orice graf are unnumar par de noduri cu grad impar.

Curs 14

Numere Ramsey

Mai jos sunt indicate toate valorile cunoscute de numere Ramsey:

R(1, k) = 1,R(2, k) = k ,

R(3, 3) = 6,R(3, 4) = 9,R(3, 5) = 14,R(3, 6) = 18,R(3, 7) = 23,R(3, 8) = 28,R(3, 9) = 36,

R(4, 4) = 18,R(4, 5) = 25.

In general, determinarea valorilor exacte ale numerelor Ramseyeste extrem de dificila.

Curs 14

Limite cunoscute

Teorema (Erdos si Szekeres)

Daca p ≥ 2 si q ≥ 2 atunci R(p, q) ≤ (p + q − 2)!

(p − 1)!(q − 1)!.

Teorema

Daca p ≥ 2 si q ≥ 2, atunci R(p, q) ≤ R(p − 1, q) + R(p, q − 1).

Teorema

Pentru orice q ≥ 3, R(3, q) ≤ q2 + 3

2.

Teorema (Erdos)

Daca p ≥ 3 atunci R(p, p) > b2n/2c.

Curs 14

Exercitii

1 Sa se demonstreze ca R(3, 5) ≥ 14. Graful urmator esteextrem de util.

K13

••

•

•

•

•• •

•

•

•

•

•

2 Folositi a doua teorema de pe slide-ul precedent ın combinatiecu rezultatul din exercitiul precedent pentru a demonstra caR(3, 5) = 14.

3 Folositi a doua teorema de pe slide-ul precedent pentru ademonstra teorema a treia.

Curs 14

Teoria lui Ramsey pentru grafuri

Generalizare a teoriei clasice a lui Ramsey.

Definitie

Numarul Ramsey R(G ,H) asociat la doua grafuri G si H estevaloarea minima a lui n a.ı. orice colorare rosu-albastru a muchiilorlui Kn contine fie o copie rosie a lui G sau o copie albastra a lui H.

Remarca

In acest context, numarul Ramsey clasic R(p, q) coincide cuR(Kp,Kq).

Teorema

Daca G este un graf de ordin p iar H un graf de ordin q, atunciR(G ,H) ≤ R(p, q).

Demonstratie. Evident.

Curs 14

Teoria lui Ramsey pentru grafuriO margine inferioara pentru R(G ,H)

Numarul cromatic χ(G ) al unui graf G este cel mai mic numark astfel ıncat G este k-colorabil. Acest lucru ınseamna ca:

I folosim k culori pentru nodurile lui G .I nodurile adiacente ın G au culori diferite.

C (H) = ordinul (adica numarul de noduri) al celei mai maricomponente conexe a grafului H.

Teorema urmatoare indica o relatie ıntre R(G ,H), numarulcromatic χ(G ) al lui G , si marimea C (H) a celei mai maricomponente conexe a lui H:

Teorema

R(G ,H) ≥ (χ(G )− 1)(C (H)− 1) + 1.

Curs 14

O margine inferioara pentru R(G ,H)

Teorema

R(G ,H) ≥ (χ(G )− 1)(C (H)− 1) + 1.

Demonstratie. Fie m = χ(G )− 1 si n = C (H)− 1. Fie S graful Km·nformat din m copii ale lui Kn toate muchiile posibile ıntre copii. Apoi secoloreaza albastru muchiile din fiecare copie a lui Kn, si rosu toatecelelalte muchii.

S :

Kn

Kn

Kn

Kn

Nu exista copie albastra a lui C(H) ın S fiindca C(H) aren + 1 noduri si nu intra ın nici un Kn⇒ nu poate exista o copie albastra a lui H ın S.

Nu exista nici o copie rosie a lui G ın S fiindcadaca coloram fiecare copie a lui Kn ın S cu o culoare diferitaatunci producem o m-colorare a lui G .Dar G nu este m-colorabil deoarece χ(G) = m + 1.

S este prea mic: avem nevoie de

p > |S | = m · n = (χ(G )− 1)(C (H)− 1) noduri pentru a garanta

existenta unei copii albastre a lui H sau a unei copii rosii a lui G ın Kp.

Curs 14


Teorema

Daca Tm este arbore cu m noduri atunci R(Tm,Kn) = (m−1)(n−1) + 1.

Demonstratie. Rezultatul are loc pt. m = 1 sau n = 1. De acumıncolo presupunem m ≥ 2 si n ≥ 2.Afirmatia A. R(Tm,Kn) ≥ (m − 1)(n − 1) + 1.

Km−1

Km−1

Km−1

Km−1

Pt. a demonstra acest lucru, fie K(m−1)(n−1) format din n − 1 copii rosiiale lui Km−1, si toate muchiile posibile dintre copii colorate albastru.Nu poate exista nici un Tm rosu si nici un Kn albastru⇒ Are locafirmatia A.Afirmatia B. R(Tm,Kn) ≤ (m − 1)(n − 1) + 1.

O demonstratie a acestei afirmatii este ın [Harris et al. 2008]Curs 14


Teorema

Daca Tm este un arbore de ordin m si daca m − 1 divide n − 1atunci R(Tm,K1,n) = m + n − 1.

In teorema de mai jos, mK2 reprezinta graful format din m copii ale lui

K2, iar n K2 are o semnificatie similara.

Teorema

Daca m ≥ n ≥ 1 atunci R(mK2, n K2) = 2m + n − 1.

Curs 14

Exercitii

1 Sa se calculeze R(P3,P3).

2 Sa se calculeze R(P3,C4).

3 Sa se calculeze R(C4,C4).

4 Demonstrati ca R(K1,3,K1,3) = 6.

5 Demonstrati ca R(2K3,K3) = 8.

Reamintim ca

Cn reprezinta ciclul cu n noduri.

Km,n este graful bipartit complet dintre doua multimi X si Ycu cardinalitatile |X | = m, |Y | = n. Multimea de muchii aacestui graf este E = {(x , y) | x ∈ X , y ∈ Y }.Pn este o cale prin n noduri.

Curs 14

Grafuri planare. Teorema lui Kuratowski. Teoria lui...

Documents

Transcript of Grafuri planare. Teorema lui Kuratowski. Teoria lui...