Wzór Eulera (teoria grafów)

Z testwiki
Przejdź do nawigacji Przejdź do wyszukiwania

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 G będzie spójnym grafem płaskim i niech liczba wierzchołków, krawędzi i ścian grafu G wynosi odpowiednio: ν=ν(G)=|V|, ε=ε(G)=|E| i φ=φ(G)=|S|. Wówczas:

ν−ε+φ=2.

Dowód

Dowód metodą indukcji matematycznej względem liczby krawędzi ε spójnego płaskiego grafu G. Jeśli ε=0, to ponieważ graf jest spójny ν=ν(G)=1 oraz φ=φ(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 ε−1 krawędziach i pokażemy, że zachodzi wtedy również dla spójnego grafu płaskiego G o ε krawędziach. Zauważmy, że jeżeli G jest drzewem na ν wierzchołkach, to ε=ν−1 i φ=φ(G)=1, a więc

ν−ε+φ=ν−(ν−1)+1=ν−ν+1+1=2.

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

ν(G−e)−ε(G−e)+φ(G−e)=ν−(ε−1)+(φ−1)=2,

co po przekształceniach daje: ν−ε+φ=2. Na mocy zasady indukcji matematycznej twierdzenie zachodzi dla dowolnego spójnego grafu płaskiego G.

Wnioski

  • Wszystkie grafy płaskie danego spójnego grafu planarnego mają taką samą liczbę ścian.
  • Jeżeli G jest planarnym grafem i ν⩾2 oraz jego talia (długość najkrótszego cyklu) wynosi r, to: (r−2)ε⩽r(ν−2).
  • Jeżeli G jest planarnym grafem prostym i ν⩾3, to: ε⩽3ν−6.
  • Jeżeli G jest planarnym grafem prostym i ν⩾3 oraz G nie ma trójkątów (cykli długości 3), to: ε⩽2ν−4.
  • Graf Kuratowskiego K5 nie jest planarny.
  • Graf Kuratowskiego K3,3 nie jest planarny.
  • Graf Petersena nie jest planarny.
  • Jeżeli G jest planarnym grafem prostym, to G zawiera wierzchołek stopnia co najwyżej 5, to znaczy δ(G)⩽5.
  • Jeżeli G jest grafem płaskim o ω składowych spójności, to: ν−ε+φ=ω+1.

Uogólnienie

Jeżeli G jest grafem spójnym, którego genus wynosi g, to:

|V|+|S|−|E|=2−2g.

Zobacz też

Bibliografia

Linki zewnętrzne

Szablon:Teoria grafów

Źródło: „https://pl.wiki.beta.math.wmflabs.org/w/index.php?title=Wzór_Eulera_(teoria_grafów)&oldid=7431”