Graf planarny

Przykład grafu planarnego: Szablon:Link-interwiki

Graf planarny – graf, który można narysować na płaszczyźnie (i każdej powierzchni genusu 0) 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

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

Twierdzenie Eulera

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|⩾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 i posiada $k$ składowych spójnych, to $|V|+|S|-|E|=k+1.$
• Jeżeli G jest planarny i $|V|⩾3,$ to $|E|⩽3\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.

Kolorowanie grafu planarnego

Twierdzenie o czterech barwach stwierdza iż każdy graf planarny może zostać pokolorowany przy użyciu 4 kolorów.

Zobacz też

• domki i studnie

Linki zewnętrzne

• Szablon:Otwarty dostęp Grafy planarne, Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej (MiNI PW), kanał „Archipelag Matematyki” na YouTube, 16 sierpnia 2017 [dostęp 2024-09-04].