Twierdzenie Kuratowskiego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Twierdzenie Kuratowskiegotwierdzenie teorii grafów sformułowane i udowodnione przez Kazimierza Kuratowskiego w 1930 roku[1].

Uwagi[edytuj | edytuj kod]

Przez rozszerzenie grafu rozumiemy "wstawianie wierzchołka do krawędzi", tj. rozerwanie krawędzi między dwoma wierzchołkami, dodanie kolejnego wierzchołka i połączenia wierzchołków pierwotnych poprzez właśnie dodany wierzchołek. Grafem rozszerzonym nazwiemy graf powstały z danego poprzez co najmniej jednokrotne rozszerzenie grafu.

Teza[edytuj | edytuj kod]

Skończony graf jest planarny (spłaszczalny), jeśli nie zawiera podgrafu, który jest grafem rozszerzonym grafu K_5 (graf pełny o pięciu wierzchołkach) lub K_{3,3} (graf pełny dwudzielny o sześciu wierzchołkach, z których trzy są połączone z każdym z pozostałych trzech).

Przypisy

Bibliografia[edytuj | edytuj kod]

  • Frank Harary, Graph Theory. Addison-Wesley, Reading 1969, s. 133