Loading AI tools
twierdzenie teorii grafów o planarności Z Wikipedii, wolnej encyklopedii
Twierdzenie Kuratowskiego – twierdzenie teorii grafów sformułowane i udowodnione przez Kazimierza Kuratowskiego w 1930 roku[1].
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.
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].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.