Graf planarny
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[1].
Kryterium Kuratowskiego edytuj
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.
Twierdzenie Eulera edytuj
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 oraz jest grafem spójnym i planarnym, to gdzie – zbiór wierzchołków, – zbiór krawędzi, – zbiór ścian dowolnego rysunku płaskiego grafu
Wnioski ze wzoru Eulera edytuj
- Jeżeli G jest planarny i posiada składowych spójnych, to
- Jeżeli G jest planarny i to
- 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.
Zobacz też edytuj
Przypisy edytuj
- ↑ Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 67, 80. ISBN 0-387-95014-1.