Graf planarny

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
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


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


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


Graf planarnygraf, który można narysować na płaszczyźnie tak, by krzywe obrazujące krawędzie grafu nie przecinały się ze sobą. Odwzorowanie grafu planarnego na płaszczyznę o tej własności nazywane jest jego rysunkiem płaskim. Graf planarny o zbiorze wierzchołków i krawędzi zdefiniowanym poprzez rysunek płaski nazywany jest grafem płaskim.

Kryterium Kuratowskiego[edytuj | edytuj kod]

Dwa minimalne grafy, które nie są planarne, to K5 i K3,3. Twierdzenie Kuratowskiego (1930) mówi, że graf skończony jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu homeomorficznego z grafem K5 ani z grafem K3,3.

Complete graph K5.svg Complete bipartite graph K3,3.svg

Wzór Eulera[edytuj | edytuj kod]

Dowolny rysunek płaski grafu planarnego wyznacza spójne obszary płaszczyzny zwane ścianami. Dokładnie jeden z tych obszarów, zwany ścianą zewnętrzną, jest nieograniczony.

Zgodnie z wzorem Eulera, jeżeli |V| \geq 3 oraz G jest grafem spójnym i planarnym, to |V|+|S|-|E|=2, gdzie V – zbiór wierzchołków, E – zbiór krawędzi, S – zbiór ścian dowolnego rysunku płaskiego grafu G.

Wnioski ze wzoru Eulera:

  • Jeżeli G jest planarny, to |E|\leq3\cdot|V|-6.
  • Jeżeli G jest planarny, to wierzchołek o najmniejszym stopniu jest stopnia co najwyżej 5.

Zgodnie z twierdzeniem o czterech barwach, graf planarny daje się zawsze pokolorować przy użyciu co najwyżej czterech kolorów.