Kuratowskin teoreema
Siirry navigaatioon
Siirry hakuun
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[a] 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]
Huomautukset[muokkaa | muokkaa wikitekstiä]
- ↑ 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[muokkaa | muokkaa wikitekstiä]
- ↑ Törnroos, Miikka: Kuratowskin teoreema (Pro gradu tutkielma) 2013. Helsingin Yliopisto.
- ↑ Grimaldi, Ralph P.: Discrete and Combinatorial Mathematics: an Applied Introduction, s. 509. 4. painos. Addison Wesley, 1999. ISBN 0-201-19912-2. (englanniksi)