Kuratowskin lause

Abstract

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.