Wzór Eulera (teoria grafów)

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

• 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[edytuj | edytuj kod]

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

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

Zobacz też[edytuj | edytuj kod]

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

Bibliografia[edytuj | edytuj kod]

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

Linki zewnętrzne[edytuj | edytuj kod]

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