Wersja z 22:47, 19 mar 2010 edytuj Alexbot (dyskusja \| edycje) 98 634 edycje m robot dodaje: ca:Graf planar ← poprzednia edycja		Wersja z 01:52, 13 kwi 2011 edytuj anuluj edycję PMG (dyskusja \| edycje) Redaktorzy, Użytkownicy o ukrytej aktywności, Administratorzy 361 765 edycji drobne techniczne, WP:SK następna edycja →
Linia 1: {{Teoria grafów}} '''Graf planarny''' ~~–~~– [[graf (matematyka)\|graf]], 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 [[graf płaski\|grafem płaskim]]. === Kryterium [[Kazimierz Kuratowski\|Kuratowskiego]] === Dwa minimalne grafy, które nie są planarne, to ''K<sub>5</sub>'' i ''K<sub>3,3</sub>''. '''[[Twierdzenie Kuratowskiego]]''' (1930) mówi, że graf skończony jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu [[homeomorfizm grafów\|homeomorficznego]] z grafem ''K<sub>5</sub>'' ani z grafem ''K<sub>3,3</sub>''. [[~~Grafika~~Plik:Complete graph K5.svg\|200px]] [[~~Grafika~~Plik:Complete bipartite graph K3,3.svg\|200px]] === Wzór [[Leonhard Euler\|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 [[Charakterystyka Eulera\|wzorem Eulera]], jeżeli G jest grafem [[graf spójny\|spójnym]] i planarnym, to <math>\|V\|+\|S\|-\|E\|=2</math>, 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:

Graf planarny: Różnice pomiędzy wersjami