Matematyka dyskretna
Dr Marek Zakrzewski
Wykład 09
Grafy planarne i wzór Eulera
Jeżeli graf można narysować na płaszczyz
nie bez przecinania siÄ™ to
nazywamy go grafem planarnym, a po narysowaniu grafem
płaskim.
Graf płaski wyznacza rozbicie płaszczyzny na obszary zwane
ścianami, w tym jedną ścianę nieograniczoną.
Rysunek przedstawia projekcjÄ™ stereograficznÄ… sfery bez
bieguna na płaszczyznę.
Wzór Eulera dla grafu planarnego
W -K ƒÄ…S =2 W - wierzchoÅ‚ki, - krawÄ™dzie, - Å›ciany
K S
Dowód:
Twierdzenie jest oczywiste dla drzew:
W =n K =n-1 S =1 n-śąn-1źąƒÄ…1=2
Pokażemy, że po dodaniu krawędzi do grafu spełniającego wzór Eulera, nowy graf też spełnia
wzór Eulera:
W ' =W K ' =KƒÄ…1 S '=SƒÄ…1 W ' -K 'ƒÄ…S '=W -śą K ƒÄ…1źąƒÄ…S ƒÄ…1=W -KƒÄ…S =2
Tak więc możemy wyjść z drzewa spinającego graf dla niego zachodzi wzór Eulera i kolejno
dodawać krawędzi.
Zastosowanie wzoru Eulera
I. Zadanie o cięciwach
n n
Rozważmy graf wyznaczony przez punktów okręgu, łuków okręgu, wszystkie
możliwe cięciwy i punkty przecięcia cięciw.
W - wierzchołki wyjściowe i punkty przecięcia cięciw
K - łuki wyjściowe i odcinki cięciw
S - obszary
Na ile obszarów dzielą te cięciwy koło?
W =5
K =12
S =9 (w tym nieograniczona)
n
- bo każde 4 punkty okręgu wyznaczają czworokąt wypukły, a
W =nƒÄ…
śą źą
2
jego przekątne punkt przecięcia.
n
nƒÄ…
Gdyby nie było punktów przecięcia to krawędzi byłoby , każdy punkt przecięcia
śą źą
2
n n
K =nƒÄ… ƒÄ…2
dodaje 2 krawędzie. Stąd .
śą źą śą źą
2 4
W to
Zatem, skoro -K ƒÄ…S =2 S=K -W ƒÄ…2
n n n n n
S=nƒÄ… ƒÄ…2 -n- ƒÄ…2= ƒÄ… ƒÄ…2
to obejmuje ścianę nieograniczoną.
śą źą śą źą śą źą śą źą śą źą
2 4 4 2 4
n n n n n
1ƒÄ… ƒÄ… = ƒÄ… ƒÄ…
Ostatecznie mamy:
śą źą śą źą śą źą śą źą śą źą
2 4 0 2 4
Twierdzenie
Jest tylko 5 wielościanów foremnych (platońskich).
Dowód:
Ścianami mogą być tylko trójkąty równoboczne, kwadraty lub pięciokąty foremne.
3
2K=3S Śą K= S
1. Załóżmy, że ścianami są trójkąty.
2
a) Załóżmy, że w wierzchołku stykają się 3 trójkąty. Wówczas 3W=3S ŚąW =S
3 1
S- S ƒÄ…S =2 Śą S=2Śą S =4 - czworoÅ›cian
2 2
3
4W=3SŚąW = S
b) Załóżmy, że w wierzchołku stykają się 4 trójkąty. Wówczas
4
3 3 1
S - S ƒÄ…S=2Śą S=2 ŚąS=8 - oÅ›mioÅ›cian
4 2 4
c) Załóżmy, że w wierzchołku stykają się 5 trójkątów. Wówczas
3 3 3 1
5W=3S ŚąW = S S- S ƒÄ…S =2 Śą S=2Śą S =20 - dwudziestoÅ›cian
5 5 2 10
2. Załóżmy, że ścianami są kwadraty. Podobnie  sześcian.
3. Załóżmy, że ścianami są pięciokąty foremne. Podobnie  dwunastościan.
Ile łat ma tradycyjna piłka?
" Ściany są pięciokątami lub sześciokątami.
" W każdym punkcie schodzą się 3 łaty.
X - liczba łat pięciokątnych, - liczba łat sześciokątnych.
Y
S= X ƒÄ…Y 2K=5XƒÄ…6Y 3W=5XƒÄ…6Y W -K ƒÄ…S =2 6W-6KƒÄ…6S=12
2śą5XƒÄ…6Yźą-3śą5XƒÄ…6YźąƒÄ…6śą X ƒÄ…Y źą=12 X =12
Każdy sześciokąt sąsiaduje z 3 pięciokątami i 3 sześciokątami.
12 pięciokątów daje 60 krawędzi. Każdy sześciokąt wykorzystuje 3 takie krawędzie. Stąd
Y =20 . Czyli tradycyjna piłka ma 32 łaty w tym 12 pięciokątnych i 20 sześciokątnych.
Dwa nieplanarne grafy. Twierdzenie Kuratowskiego
Lemat 1:
Dla grafu planarnego zwykłego K d"3W-6
Dowód:
Każda ściana ma przynajmniej 3 boki tzn. 3Sd"2K .
2 1
W
Zatem -K ƒÄ…S =2 Śą2=W -K ƒÄ…Sd"W -K ƒÄ… K =W - K
3 3
Stąd 6d"3W-K Śą K d"3W-6
K
Wniosek: nie jest planarny.
5
Uzasadnienie: W =5 K =10 10d"3"5-6 Sprzeczność.
Lemat 2:
Załóżmy, że graf zwykły nie zawiera trójkątów wówczas mamy K d"2W-4 .
Dowód:
K
Sd"
Każda ściana ma przynajmniej 4 boki. Stąd 4Sd"2K , tzn.
2
K K K
2=W -K ƒÄ…S d"W -K ƒÄ… =W - StÄ…d , tzn. K d"2W-4 .
d"W -2
2 2 2
K
Wniosek nie jest planarny.
3,3
Uzasadnienie: W grafie dwudzielnym cykle mają długość parzystą, więc nie ma trójkątów.
K
Zatem gdyby był planarny to mielibyśmy 9d"2"6-4 - sprzeczność.
3,3
Rozdrobieniem grafu G nazywamy graf powstały z G przez dodanie wierzchołka stopnia
2 na jego krawędziach.
Twierdzenie Kazimierza Kuratowskiego (ok. 1930)
K5 K
Graf jest planarny wtedy i tylko wtedy, gdy nie zawiera rozdrobnień ani .
3,3
 walec
 wstÄ™ga Möbiusa
 butelka Kleina (4 wymiary)