Wzór Eulera (teoria grafów)

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

Wzór Eulera, wzór Eulera dla grafów płaskich – twierdzenie teorii grafów opisujące zależność między liczbą wierzchołków, ścian i krawędzi grafu płaskiego.

Teza

Niech ${\displaystyle G}$ będzie spójnym grafem płaskim i niech liczba wierzchołków, krawędzi i ścian grafu ${\displaystyle G}$ wynosi odpowiednio: ${\displaystyle \nu =\nu (G)=|V|,}$ ${\displaystyle \varepsilon =\varepsilon (G)=|E|}$ i ${\displaystyle \varphi =\varphi (G)=|S|.}$ Wówczas:

${\displaystyle \nu -\varepsilon +\varphi =2.}$

Dowód

Dowód metodą indukcji matematycznej względem liczby krawędzi ${\displaystyle \varepsilon }$ spójnego płaskiego grafu ${\displaystyle G.}$ Jeśli ${\displaystyle \varepsilon =0,}$ to ponieważ graf jest spójny ${\displaystyle \nu =\nu (G)=1}$ oraz ${\displaystyle \varphi =\varphi (G)=1}$ (ściana nieograniczona). Twierdzenie jest więc prawdziwe w tym przypadku. Założymy teraz, że twierdzenie zachodzi dla dowolnego spójnego grafu płaskiego o ${\displaystyle \varepsilon -1}$ krawędziach i pokażemy, że zachodzi wtedy również dla spójnego grafu płaskiego ${\displaystyle G}$ o ${\displaystyle \varepsilon }$ krawędziach. Zauważmy, że jeżeli ${\displaystyle G}$ jest drzewem na ${\displaystyle \nu }$ wierzchołkach, to ${\displaystyle \varepsilon =\nu -1}$ i ${\displaystyle \varphi =\varphi (G)=1,}$ a więc

${\displaystyle \nu -\varepsilon +\varphi =\nu -(\nu -1)+1=\nu -\nu +1+1=2.}$

Stąd twierdzenie jest prawdziwe dla dowolnego drzewa.Załóżmy więc, że ${\displaystyle G}$ nie jest drzewem. Istnieje wtedy co najmniej jeden cykl. Niech ${\displaystyle e}$ będzie krawędzią zawartą w pewnym cyklu grafu ${\displaystyle G.}$ Wówczas ${\displaystyle e}$ należy do brzegu dokładnie dwóch ścian i ${\displaystyle e}$ nie jest krawędzią cięcia. Wyrzucenie krawędzi ${\displaystyle e}$ spowoduje więc powstanie z tych dwóch ścian jednej ściany i nie rozspójni grafu ${\displaystyle G.}$ ${\displaystyle G-e}$ jest więc spójnym grafem płaskim z ${\displaystyle \nu }$ wierzchołkami, ${\displaystyle \varepsilon -1}$ krawędziami i ${\displaystyle \varphi -1}$ ścianami. Możemy więc dla grafu ${\displaystyle G-e}$ zastosować założenie indukcyjne:

${\displaystyle \nu (G-e)-\varepsilon (G-e)+\varphi (G-e)=\nu -(\varepsilon -1)+(\varphi -1)=2,}$

co po przekształceniach daje: ${\displaystyle \nu -\varepsilon +\varphi =2.}$ Na mocy zasady indukcji matematycznej twierdzenie zachodzi dla dowolnego spójnego grafu płaskiego ${\displaystyle G.}$

Wnioski

• Wszystkie grafy płaskie danego spójnego grafu planarnego mają taką samą liczbę ścian.
• Jeżeli ${\displaystyle G}$ jest planarnym grafem i ${\displaystyle \nu \geqslant 2}$ oraz jego talia (długość najkrótszego cyklu) wynosi ${\displaystyle r,}$ to: ${\displaystyle (r-2)\varepsilon \leqslant r(\nu -2).}$
• Jeżeli ${\displaystyle G}$ jest planarnym grafem prostym i ${\displaystyle \nu \geqslant 3,}$ to: ${\displaystyle \varepsilon \leqslant 3\nu -6.}$
• Jeżeli ${\displaystyle G}$ jest planarnym grafem prostym i ${\displaystyle \nu \geqslant 3}$ oraz ${\displaystyle G}$ nie ma trójkątów (cykli długości 3), to: ${\displaystyle \varepsilon \leqslant 2\nu -4.}$
• Graf Kuratowskiego ${\displaystyle K_{5}}$ nie jest planarny.
• Graf Kuratowskiego ${\displaystyle K_{3,3}}$ nie jest planarny.
• Graf Petersena nie jest planarny.
• Jeżeli ${\displaystyle G}$ jest planarnym grafem prostym, to ${\displaystyle G}$ zawiera wierzchołek stopnia co najwyżej 5, to znaczy ${\displaystyle \delta (G)\leqslant 5.}$
• Jeżeli ${\displaystyle G}$ jest grafem płaskim o ${\displaystyle \omega }$ składowych spójności, to: ${\displaystyle \nu -\varepsilon +\varphi =\omega +1.}$

Uogólnienie

Jeżeli G jest grafem spójnym, którego genus Eulera wynosi ${\displaystyle g,}$ to:

${\displaystyle |V|+|S|-|E|=2-g.}$

Zobacz też

• charakterystyka Eulera
• graf planarny
• twierdzenie Eulera o wielościanach

Bibliografia

• Robin J. Wilson: Wprowadzenie do teorii grafów. Warszawa: PWN, 1998.
• Victor Bryant: Aspekty kombinatoryki. Warszawa: WNT, 1997.
• J.H. van Lint, R.M. Wilson: A course in combinatorics. Cambridge: Cambridge University Press, 1992.

Linki zewnętrzne

• Dwadzieścia dowodów twierdzenia Eulera (ang.)