Loading AI tools
Van Wikipedia, de vrije encyclopedie
In de grafentheorie, een deelgebied van de wiskunde, is de stelling van Kuratowski een karakterisering van planaire grafen. De stelling is genoemd naar Kazimierz Kuratowski, die in 1930 voor het eerst een bewijs ervan publiceerde[1].
Een graaf, die bestaat uit knopen en bogen, kan op verschillende manieren op een plat vlak worden getekend. Een graaf is planair als hij in het euclidische vlak kan worden getekend zonder dat de bogen elkaar kruisen (behalve bij de knopen). Het kan zijn dat dezelfde graaf ook met kruisende bogen getekend kan worden, maar dat maakt niet uit.
Hierboven staan twee manieren om de volledige graaf met vier knopen op het platte vlak te tekenen. Aangezien de bogen van de rechter elkaar niet kruisen, gaat het hier om een planaire graaf, hoewel de graaf ook met elkaar kruisende bogen getekend kan worden.
Een subdivisie van een graaf is die graaf waarin bogen door paden van willekeurige lengte zijn vervangen.
De rechter graaf is een subdivisie van de linker. |
is de volledige graaf met knopen, en is de volledige bipartiete graaf waarvan de eerste partitie en de tweede knopen heeft. De volledige grafen die een rol spelen in de stelling van Kuratowski zijn en .
De volledige graaf | De volledige bipartiete graaf |
De stelling van Kuratowski luidt:
In het vervolg noemen we een subgraaf die isomorf is met een subdivisie van of een Kuratowski-subgraaf.
Het gaat hier om een karakterisering van planaire grafen: grafen die een Kuratowski-subgraaf bevatten zijn niet planair, en geen enkele planaire graaf bevat een Kuratowski-subgraaf.
In de volgende afbeelding wordt met behulp van de stelling van Kuratowski bewezen dat de graaf die een hypercubus representeert, niet planair is:
In de bovenste figuur wordt een subdivisie van als subgraaf aangegeven, terwijl in de onderste een subdivisie van aangegeven wordt.
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.