Graf planarny
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
Graf planarny – graf, którego jedno lub więcej izomorficzne przekształcenie da się narysować na płaszczyźnie tak, by łuki obrazujące krawędzie grafu nie przecinały się. Tę konkretną postać grafu, zachowującą tę własność, nazywamy grafem płaskim. A więc każdy graf płaski jest planarny, a każdy graf planarny jest izomorficzny z jakimś grafem płaskim.
Dwa najmniejsze grafy, które nie są planarne, to K5 i K3,3:
Kazimierz Kuratowski dowiódł następującego twierdzenia:
- Graf skończony jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu homeomorficznego z grafem K5 ani z grafem K3,3.
Cykle grafu płaskiego wyznaczają zamknięte obszary zwane ścianami, przy czym każdy graf ma nieograniczoną ścianę "zewnętrzną".
Zgodnie z twierdzeniem o czterech barwach, graf planarny daje się zawsze pokolorować przy użyciu najwyżej czterech kolorów.
[edytuj] Twierdzenie Eulera
Jeżeli G jest płaski, to | V | + | S | − | E | = 2, gdzie V - zbiór wierzchołków, E - zbiór krawędzi, S - zbiór ścian grafu G, | V | > 2.
Wnioski z twierdzenia Eulera:
- Jeżeli G jest płaski to
. - Jeżeli G jest płaski, to wierzchołek o najniższym stopniu jest stopnia co najwyżej 5.
