Graf planarny

graf przedstawialny na płaszczyźnie bez przecięcia krawędzi

Graf planarnygraf, 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].

Przykład grafu planarnego: graf Goldnera-Harary’ego(inne języki)

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.

Kolorowanie grafu planarnego

edytuj

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

Zobacz też

edytuj

Przypisy

edytuj
  1. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 67, 80. ISBN 0-387-95014-1.

Linki zewnętrzne

edytuj