Kuratowskin lause
Tekijät
Päivämäärä
2024Tekijänoikeudet
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
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.
...
Asiasanat
Metadata
Näytä kaikki kuvailutiedotKokoelmat
- Pro gradu -tutkielmat [28164]
Samankaltainen aineisto
Näytetään aineistoja, joilla on samankaltainen nimeke tai asiasanat.
-
Kuratowskin lause
Kultalahti, Julius (2022)Tämä kandidaatin tutkielma käsittelee Kuratowskin lauseen todistuksen ja siihen vaadittavan matemaattisen pohjan. -
Perronin ja Frobeniuksen lause
Huupponen, Tuukka (2023)Tässä tutkielmassa perehdytään matriisiteoriaan. Tarkastelu keskittyy neliömatriiseihin, niiden ominaisarvoihin ja niitä vastaaviin ominaisvektoreihin. Tarkastelu rajataan kahteen osaan, joista toiseen esitetään ... -
Virtaukset ja niiden sovelluksia
Leirimaa, Elisa (2020)Tässä tutkielmassa perehdytään verkostoihin ja niihin määriteltyihin virtauksiin. Virtaus on funktio, joka liittää jokaiseen verkoston suunnattuun sivuun kokonaislukuarvon ja toteuttaa tietyt ehdot. Ensinnäkin, jokaiselle ... -
Sana-assosiaatioverkkojen koheesion yhteys ryhmädynamiikkaan
Luoma, Inga (2016)Tässä pilottitutkimuksessa selvitettiin sana-assosiaatioiden koheesiota ryhmissä. Tarkoituksena oli selvittää, löytyykö yhtenäisyyttä ryhmän keskinäisen toimeen tulemisen välillä ja sen suhteen, kuinka ryhmät assosioivat ... -
Googlen PageRankin matematiikka
Hirvelä, Juulia (2023)Tämän tutkielman tarkoituksena on esitellä matematiikkaa, johon Googlen hakutulosten järjestämiseen käyttämä PageRank-algoritmi perustuu. Tutkielmassa hyödynnetään lineaarialgebran, graafien ja Markovin ketjujen teorian ...
Ellei toisin mainittu, julkisesti saatavilla olevia JYX-metatietoja (poislukien tiivistelmät) saa vapaasti uudelleenkäyttää CC0-lisenssillä.