Graafiteorian minorilause

Abstract

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