| Summary: | Tässä tutkielmassa todistetaan Kuratowskin lause, joka on verkkoteorian
keskeinen tulos. Tutkielma jakautuu kolmeen kappaleeseen, joista ensimmäisessä tutustutaan verkkoteorian perusteisiin ja yleisiin määritelmiin alkaen
verkon kärkien sekä sivujen määrittelemisestä. Työssä keskitytään yksinkertaisiin suuntaamattomiin verkkoihin. Verkkoteorian peruskäsitteiden jälkeen
määritellään tasoverkko sellaiseksi verkoksi, joka voidaan piirtää tasoon niin,
että sen sivut eivät leikkaa toisiaan. Erilaisista tasoverkoista esitellään puut
sekä sillat. Siltojen määritelmää sekä erityisesti kierrosten siltoja tarvitaan
Kuratowskin lauseen todistamiseen.
Tutkielman kolmannessa osassa määritellään Kuratowskin lausetta varten ensin Kuratowskin verkot K5 ja K3,3. Näille verkoille osoitetaan, että ne
eivät ole tasoverkkoja. Tarvittavien tietojen jälkeen esitellään Kuratowskin
lause, jonka mukaan verkko on tasoverkko, jos ja vain jos se ei sisällä aliverkkonaan verkkoja K5 tai K3,3 eikä niiden alijaotuksia. Lisäksi esitellään
Wagnerin lause, joka näytetään yhtäpitäväksi Kuratowskin lauseen kanssa.
Wagnerin lauseen mukaan verkko on tasoverkko, jos ja vain jos sillä ei ole Kuratowskin minoria. Tätä lausetta varten määritellään verkon minori ja esitetään minoreihin liittyviä tuloksia. Tarvittavien aputulosten jälkeen esitetään
Wagnerin lauseen todistus, jolloin myös yhtäpitävä Kuratowskin lause on todistettu. Lopuksi esitetään esimerkki, jossa osoitetaan Kuratowskin lauseen
avulla, että Petersenin verkko ei ole tasoverkko.
|
|---|