Graafiteorian minorilause
UURAINEN, RAMI (2008)
2008
Matematiikka - Mathematics
Informaatiotieteiden tiedekunta - Faculty of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2008-05-27
Julkaisun pysyvä osoite on
https://urn.fi/urn:nbn:fi:uta-1-18470
https://urn.fi/urn:nbn:fi:uta-1-18470
Tiivistelmä
Tämän tutkielman tarkoitus on esitellä minorilause, joka on yksi graafiteorian ja matematiikan syvällisimmistä lauseista. Minorilauseen todistuksesta esitellään lyhyt hahmotelma.
Tutkielman alussa esitellään perusasioita graafiteoriasta. Siinä määritellään esimerkiksi itse graafi, yhtenäisyys ja puu. Alkuosassa käydään läpi myös muutamia lauseita, jotka liittyvät näihin peruskäsitteisiin.
Tutkielman toisessa luvussa määritellään tasograafi, minori ja topologinen minori. Minorilauseen kannalta tärkeä Kuratowskin lause esitellään ja todistetaan tässä luvussa. Kuratowskin lause osoittaa edellä mainittujen käsitteiden yhteyden.
Viimeinen luku johdattaa lukijaa luvun lopussa esiteltävään minorilauseeseen. Tässä luvussa määritellään sellaisia käsitteitä kuin kvasihyvä järjestys, puuhajotelma ja kielletyt minorit, sekä esitellään ja todistetaan niihin liittyviä lauseita.
Asiasanat: graafiteoria, graafi, tasograafi, minori, minorilause
Tutkielman alussa esitellään perusasioita graafiteoriasta. Siinä määritellään esimerkiksi itse graafi, yhtenäisyys ja puu. Alkuosassa käydään läpi myös muutamia lauseita, jotka liittyvät näihin peruskäsitteisiin.
Tutkielman toisessa luvussa määritellään tasograafi, minori ja topologinen minori. Minorilauseen kannalta tärkeä Kuratowskin lause esitellään ja todistetaan tässä luvussa. Kuratowskin lause osoittaa edellä mainittujen käsitteiden yhteyden.
Viimeinen luku johdattaa lukijaa luvun lopussa esiteltävään minorilauseeseen. Tässä luvussa määritellään sellaisia käsitteitä kuin kvasihyvä järjestys, puuhajotelma ja kielletyt minorit, sekä esitellään ja todistetaan niihin liittyviä lauseita.
Asiasanat: graafiteoria, graafi, tasograafi, minori, minorilause