Browsing by Author "Törnroos, Miikka"

Tutkielma käsittelee verkkoteoriaa ja päätuloksena esitellään ja todistetaan Kazimierz Kuratowskin (1896 - 1980) todistama tasoverkkoihin liittyvä Kuratowskin teoreema (1930). Teoreema antaa ehdot sille, milloin verkko on tasoverkko, ja sen mukaan verkko on tasoverkko jos ja vain jos se ei sisällä täydellisen viiden pisteen verkon K_5 tai täydellisen kaksijakoisen verkon K_{3,3} alijaotuksia. Verkko määritellään parina G = (X, V), missä X on äärellinen joukko (verkon pisteet) ja V ⊂ P_2(X) (verkon viivat). Verkko voidaan esittää graaffisesti piste-viiva-esityksenä, jossa pisteitä vastaavat piirretyt pisteet tai ympyrät ja viivoja pisteiden välille piirretyt viivat. Tarkemmin verkon, pisteiden ja viivojen ominaisuuksista käydään läpi pisteiden vierekkäisyys, verkon säännöllisyys ja täydellisyys, isomorfismi, pisteiden ja viivojen vähentäminen ja verkon lyhentäminen sekä yhtenäisyys. Verkossa voidaan 'kulkea reittejä' pisteiden välillä olevia viivoja pitkin. Nämä reitit muodostavat kulkuja ja kierroksia. Isomorfismi on oleellinen osa verkkoteoriaa. Verkot G = ( X, V ) ja Q = ( X ', V' ) ovat isomorfiset, merkitään ... , jos on olemassa bijektio ... siten, että xy ∈ V jos ja vain jos ... kaikilla x ja y, jotka kuuluvat joukkoon X. Pisteitä ja viivoja poistamalla muodostetaan aliverkkoja ja minoreita. Verkosta G saadaan kyseisen verkon minori Q vähentämällä siitä n-joukko pisteitä ja m-joukko viivoja ja suorittamalla näin muodostuneelle verkolle lyhennyksiä. Kuratowskin verkoiksi kutsutaan täydellistä viiden pisteen verkkoa K_5 ja täydellistä kaksijakoista verkkoa K_{3,3}. Kaksijakoisuudella tarkoitetaan sitä, että verkon pisteet voidaan jakaa kahteen erilliseen joukkoon X_1 ja X_2 niin, että jokaisesta joukon X_1 pisteestä lähtevän viivan toisena päätepisteenä on piste joukossa X_2 ja toisin päin. Tasoverkot ovat verkkoja, jotka voidaan piirtää tasolle siten, että pisteiden väliset viivat eivät leikkaa keskenään. Tasoverkkoja määriteltäessä tarvitaan Jordanin käyriä ja verkon upotuksen käsitettä. Verkoista vain tasoverkoille voidaan määritellä alueet ja näiden avulla tasoverkon duaali. Verkosta G voidaan muodostaa uusi verkko G_0 jakamalla verkon viivoja kahteen osaan. Tämä kahtiajako tehdään viivalle v = pq niin, että viiva v vähennetään verkosta, jonka jälkeen lisätään uusi piste x ja liitetään se poistetun viivan v päätepisteisiin p ja q, jolloin saadaan uudet viivat px ja qx. Tätä viivan jakamistekniikkaa kutsutaan verkon alijaotukseksi. Verkkoa G, jonka viivoille on tehty alijaotuksia, kutsutaan verkon G alijaotukseksi tai G-alijaotukseksi.