Curs 8: Grafuri planare

23
Curs 8: Grafuri planare Teoria grafurilor Radu Dumbr˘ aveanu Universitatea de Stat “A. Russo” din B˘ alt , i Facultatea de S , tiint , e Reale Aceast˘ a prezentare este pus˘ a la dispozit ¸ie sub Licent ¸a Atribuire - Distribuire-ˆ ın-condit ¸ii-identice 3.0 Ne-adaptat˘ a (CC BY-SA 3.0) alt , i, 2013 R. Dumbr˘ aveanu (USARB) Curs 8: Grafuri planare alt , i, 2013 1 / 23

Transcript of Curs 8: Grafuri planare

Page 1: Curs 8: Grafuri planare

Curs 8: Grafuri planareTeoria grafurilor

Radu Dumbraveanu

Universitatea de Stat “A. Russo” din Balt, iFacultatea de S, tiint,e Reale

Aceasta prezentare este pusa la dispozitie sub Licenta Atribuire -Distribuire-ın-conditii-identice 3.0 Ne-adaptata (CC BY-SA 3.0)

Balt, i, 2013

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 1 / 23

Page 2: Curs 8: Grafuri planare

Exemplu fabrica; Turan

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 2 / 23

Page 3: Curs 8: Grafuri planare

Grafuri planar; Graf plan

Un graf G se numes, te planar daca poate fi reprezentat ın plan astfel ıncıtmuchiile sa nu se intersecteze decıt ın vırfuri.

O astfel de reprezentare se numes, te harta (sau graf-plan), iar graful G senumes, te graful suport al hart, ii respective.

Graful K4 ımpreuna cu harta sa

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 3 / 23

Page 4: Curs 8: Grafuri planare

Numarul de intersect, ii

Numarul de intersect, ii este numarul de perechi diferite de muchii care seintersecteaza ıntr-o reprezentare a grafului.

Este logic sa vorbim despre numarul minim de astfel de perechi.

Un graf planar are numarul minim de intersect, ii egal cu zero.

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 4 / 23

Page 5: Curs 8: Grafuri planare

Fet, e

Orice reprezentare a unui graf planar ımparte planul ın regiuni numite fet, e.

Mult, imea fet, elor se noteaza prin F .

Intotdeauna exista o fat, a infinita/nemarginita numita fat, a exterioara.

Orice fat, a f este un poligon.

Numarul de muchii ale poligonului se noteaza prin d(f ) s, i se numes, tegradul fet, ei.

TeoremaPentru orice graf planar ∑

f∈Fd(f ) = 2|E |

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 5 / 23

Page 6: Curs 8: Grafuri planare

Fet, e

v

u

x

y

zf0f1

f2

|F | = 3; f0 este fat, a exterioara

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 6 / 23

Page 7: Curs 8: Grafuri planare

Fet, e

TeoremaFie G un graf plan s, i e o muchie din G, atunci:

1. Daca e apart, ine unui ciclu elementar C ⊆ G atunci e apart, inefrontierei a exact doua fet, e;

2. Daca e nu apart, ine unui ciclu elementar atunci e apart, ine frontierei aexact a unei fet, e;

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 7 / 23

Page 8: Curs 8: Grafuri planare

Fet, e

v

u

x

y

zf0f1

f2

Graf plan G

Muchia uv apart, ine ciclului elementar (u, v, x, u) s, i ın acelas, i timp apart, inefrontierei fet, elor f0 s, i f1.

Muchia xz nu aprt, ine unui ciclu elementar s, i se afla pe frontiera fet, ei f0.

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 8 / 23

Page 9: Curs 8: Grafuri planare

Fet, e

CorolarUn arbore plan are exact o fat, a.

CorolarDaca un graf plan are fet, e diferite cu aceeas, i frontiera atunci acesta esteun graf ciclu.

CorolarIntr-un graf 2-conex orice fat, a este marginita de un ciclu.

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 9 / 23

Page 10: Curs 8: Grafuri planare

Formula Euler

TeoremaPentru orice graf G = (V , E) planar s, i conex

|V | − |E |+ |F | = 2

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 10 / 23

Page 11: Curs 8: Grafuri planare

Formula Euler

Demonstratie.Demonstram prin induct, ie tare pe m = ||G|| (numarul de muchii).Pentru m = 0 avem graful nul cu un singur vırf (ıntrucıt G trebuie sa fieconex); |V | = 1 s, i |F | = 1; teorema este verificata.Presupunem ca teorema este adevarata pentru orice graf cu |E | < m.Fie G un graf cu |E | = m, m ≥ 1.Alegem, ın mod arbitrar, o muchie e s, i cercetam subgraful H = G − e.Consideram doua cazuri: H este conex s, i H nu este conex.

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 11 / 23

Page 12: Curs 8: Grafuri planare

Demonstratie.Cazul I. Daca H este conex, reiese ca e nu este o punte ın G s, i deciapart, ine unui ciclu.In acest caz e margines, te doua fet, e diferite, iar ın rezultatul eliminarii,aceste fet, e sau unit ın una singura, deci |F(H )| = |F | − 1.Astfel, ıntrucıt V (G) = V (H ) obt, inem:

|V | − |E |+ |F | = |V (H )| − (|E(H )|+ 1) + (|F(H )|+ 1)= |V (H )| − |E(H )|+ |F(H )| − 1 + 1 = 2.

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 12 / 23

Page 13: Curs 8: Grafuri planare

Demonstratie.Cazul al II-lea. Graful H nu este conex.Reiese ca e este o punte s, i ıntrucıt am eliminat doar o muchie H constadin doua compoenente conexe H1 = (V1, E1) s, i H2 = (V2, E2).Iar ıntrucıt atıt H1 cıt s, i H2 are un numar de muchii mai mic ca m pentruele este adevarata formula lui Euler:

|V1| − |E1|+ |F1| = 2

s, i|V2| − |E2|+ |F2| = 2

Dar |V | = |V1|+ |V2|, |E | = |E1|+ |E2|+ 1 s, i |F | = |F1|+ |F2| − 1 s, i

|V | − |E |+ |F | = |V1|+ |V2| − (|E1|+ |E2|+ 1) + (|F1|+ |F2| − 1)= |V1| − |E1|+ |F1|+ |V2| − |E2|+ |F2| − 1− 1= 2 + 2− 1− 1 = 2

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 13 / 23

Page 14: Curs 8: Grafuri planare

Aplicat, ii ale formulei Euler

Graful K3,3 nu este planar.

Demonstratie.Presupunem, prin absurd, ca K3,3 este planar. Atunci din formula lui Euleravem:

|F | = 2− |V |+ |E | = 2− 6 + 9 = 5.

Deci trebuie sa fie 5 fet, e. Deoarece cel mai scurt ciclu ın K3,3 arelungimea 4 reiese ca orice fat, a trebuie sa aiba gradul ≥ 4. Acum

18 = 2|E | =∑f∈F

d(f ) ≥ 5 · 4 = 20

Contradict, ie.

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 14 / 23

Page 15: Curs 8: Grafuri planare

Aplicat, ii ale formulei Euler

K5 nu este planar.

Demonstrat, i analog aceasta propozit, ie

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 15 / 23

Page 16: Curs 8: Grafuri planare

Aplicat, ii ale formulei Euler

Graful Petersen nu este planar.

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 16 / 23

Page 17: Curs 8: Grafuri planare

Teorema lui KuratowskiDefinit, ieO subdiviziune a unui graf este un graf nou obt, inut din G prin inserareade vırfuri (de gradul 2) ın muchiile lui G

Cıteva observat, ii:

1. daca G este planar atunci orice subgraf al acestuia este planar.2. daca o subdiviziune a unui graf G este un graf planar atunci G este

planar

Teorema (Kuratowski)Un graf nu este planar daca s, i numai daca o subdiviziune a lui K3,3 sau K5este un subgraf al lui G.

Aratat, i ca Petersen verifica teorema lui Kuratowski.

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 17 / 23

Page 18: Curs 8: Grafuri planare

Graf dual

Fie G un graf plan.

Amplasam cıte un vırf ın fiecare fat, a a grafului G; s, i notam mult, imeaacestor vırfuri prin V ∗.

Pentru fiecare muchie e unim doua vırfuri din V ∗ printr-o muchie e∗ dacaaceste vırfuri sınt localizate ın fet, ele cu care acesta muchie este incidenta.

Daca muchia e este incidenta cu o singura fat, a atunci vırfului asociatacestei fet, e ıi facem o bucla care intersecteaza e.

Graful G∗ = (V ∗, E∗) se numes, te graful dual al lui G.

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 18 / 23

Page 19: Curs 8: Grafuri planare

Graf dual

v

u

x

y

z

Graful dual G∗

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 19 / 23

Page 20: Curs 8: Grafuri planare

Graf dual

Taieturile minimale din G∗ sınt cilcurile din G s, i invers.

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 20 / 23

Page 21: Curs 8: Grafuri planare

Definit, ieUn poliedru este un corp 3 dimensional la care fet, ele sınt poligoane.

Un poliedru este convex daca orice segment care unes, te doua puncte dininteriorul poliedrului cont, ine numai puncte din interiorul poliedrului. Unpoliedru convex poate fi proiectat ın plan obt, inınd un graf-plan.

Definit, ieUn poliedru convex se nums, te corp platonic daca exista m ≥ 3 s, i n ≥ 3ıncıt orice vırf are gradul m s, i orice fat, a are gradul n (sau echivalent, dacatoate fet, ele sınt poligoane regulate congruente).

De ce se numesc corpuri platonice?

Cubul este un corp platonic cu m = 3 s, i n = 4.

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 21 / 23

Page 22: Curs 8: Grafuri planare

TeoremaExista exact 5 corpuri platonice.

Demonstratie.Fie G un graf planar obt, inut la proiect, ia corpului platonic. Atunci

2|E | =∑v∈V

d(v) = m|V |

2|E | =∑f∈F

d(f ) = n|F |

In acelas, i timp, din formula lui Euler

|V | − |E |+ |F | = 2

In rezultatul, ınmult, ind cu mn

2mn = mn|V | −mn|E |+ mn|F | = 2n|E | −mn|E |+ 2m|E |

Deci|E | = 2mn

2n −mn + 2m = 2mn4− (m − 2)(n − 2)

Acum deoarece |E | > 0 s, i 2mn > 0 reise ca (m − 2)(n − 2) < 4 s, i iatatoate posibilitat, ile

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 22 / 23

Page 23: Curs 8: Grafuri planare

m n —V— —E— —F— platonic solid3 3 4 6 4 tetraedru4 3 6 12 8 octaedru3 4 8 12 6 cub5 3 12 30 20 icosaedru3 5 20 30 12 dodecaedru

R. Dumbraveanu (USARB) Curs 8: Grafuri planare Balt,i, 2013 23 / 23