Twierdzenie Kuratowskiego
Twierdzenie Kuratowskiego – twierdzenie teorii grafów sformułowane i udowodnione przez Kazimierza Kuratowskiego w 1930 roku[1].
Uwagi
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
Skończony graf jest planarny (spłaszczalny), jeśli nie zawiera podgrafu, który jest grafem rozszerzonym grafu (graf pełny o pięciu wierzchołkach) lub (graf pełny dwudzielny o sześciu wierzchołkach, z których trzy są połączone z każdym z pozostałych trzech)[2].
- K5
- K 3,3
Zobacz też
- domki i studnie
Przypisy
Bibliografia
- Frank Harary, Graph Theory. Addison-Wesley, Reading 1969, s. 133
Linki zewnętrzne
- Planar Graphs, [w:] Numberphile [online], YouTube, 11 listopada 2019 [dostęp 2019-11-12] (ang.).
- p
- d
- e
Najważniejsze pojęcia |
więcej... |
---|---|
Wybrane klasy grafów | |
Algorytmy grafowe | |
problemy grafowe | |
Inne zagadnienia |
- Britannica: topic/Kuratowskis-theorem