Kuratowskin teoreema

Kuratowskin teoreema on tasograafien tasoon piirtämistä koskeva verkkoteorian teoreema. Tasograafit ovat verkkoja, jotka voidaan piirtää tasolle siten, että pisteiden väliset viivat eivät leikkaa keskenään. Puolalainen matemaatikko Kazimierz Kuratowski todisti mukaansa nimetyn teoreeman vuonna 1930. Sen mukaan mielivaltainen graafi on tasograafi jos ja vain jos se ei sisällä täydellisen viiden pisteen graafin K5 tai täydellisen kaksijakoisen[lower-alpha 1] graafin K3,3 alijaotuksia. On helppo huomata, että näitä kahta graafia ei voi piirtää tasoon viivojen leikkaamatta, mutta sen todistaminen että nämä ovat ainoat rakenne-elementit jotka voivat tehdä verkosta ei-tasolle-piirrettävän, on vaikeampaa.[1][2]

Täydellinen viiden pisteen graafi K5 ei ole tasograafi.
Täydellinen kaksijakoinen graafi K3,3 ei ole myöskään upotettavissa tasoon.

Huomautukset
  1. Kaksijakoisuudella tarkoitetaan sitä, että verkon pisteet voidaan jakaa kahteen erilliseen joukkoon X1 ja X2 niin, että jokaisesta joukon X1 pisteestä lähtevän viivan toisena päätepisteenä on piste joukossa X2 ja toisin päin.

    Lähteet
    1. Törnroos, Miikka: Kuratowskin teoreema (Pro gradu tutkielma) 2013. Helsingin Yliopisto.
    2. Grimaldi, Ralph P.: Discrete and Combinatorial Mathematics: an Applied Introduction, s. 509. 4. painos. Addison Wesley, 1999. ISBN 0-201-19912-2. (englanniksi)
      This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.