Graafien sovituksista: kaksijakoiset ja yleiset graafit
Koski, Minja (2022)
Koski, Minja
2022
Matematiikan ja tilastotieteen kandidaattiohjelma - Bachelor's Programme in Mathematics and Statistics
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication 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ä
2022-04-26
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202204073097
https://urn.fi/URN:NBN:fi:tuni-202204073097
Tiivistelmä
Tämän tutkielman aiheena on graafien sovitukset. Tutkielmassa todistetaan muutamia sovitusongelmiin liittyviä lauseita koskien kaksijakoisia ja yleisiä graafeja. Tutkielman alussa määritellään graafiteorian yleisiä käsitteitä, kuten yksinkertainen graafi, solmu- ja särmäjoukko, polku, solmun aste, naapurisolmujen joukko, sekä aligraafi ja komponentti. Esitiedoissa käydään läpi myös kaksijakoisen graafin käsite, jotta ymmärretään paremmin kaksijakoisten graafien sovituksia.
Tutkielman keskivaiheilla käydään läpi sovituksen käsite ja tutustutaan täydellisen sovituksen, maksimisovituksen ja maksimaalisen sovituksen käsitteisiin. Näiden jälkeen esitellään 1-faktorin käsite, jota hyödynnetään sovituksia koskevien lauseiden todistuksissa.Tutkielmassa 1-faktorin etsintä samaistetaan täydellisen sovituksen etsintään niiden samanlaisten ominaisuuksien takia.
Kaksijakoisten graafien sovituksia koskeva kappale sisältää määritelmät käsitteille M-vuorotteleva polku ja M-kasvava polku, joita tarvitaan Königin lauseen todistuksessa. Königin lauseen mukaan kaksijakoisen graafin maksimisovituksessa on yhtä monta särmää, kuin sen pienimmässä särmät peittävässä solmupeitteessä on solmuja. Tutkielmassa todistetaan myös Hallin lauseena tunnettu tulos, jonka mukaan kaksijakoinen graafi sisältää täydellisen sovituksen jos ja vain jos millä tahansa kaksijakoisen graafin solmujen osajoukolla on vähintään yhtä paljon naapurisolmuja kuin osajoukossa itsessään on solmuja. Tulos voidaan todistaa helposti hyödyntämällä Königin lausetta. Hallin lauseesta seuraa tulos, jonka mukaan kaksijakoinen graafi sisältää 1-faktorin, jos graafi on k-säännöllinen ja k ≥ 1.
Tutkielman lopussa käydään läpi yleisille graafeille keskeisenä tuloksena Tutten lause, jonka mukaan graafilla G on 1-faktori, jos ja vain jos mille tahansa graafin G solmujen osajoukolle S pätee, että graafissa G - S on korkeintaan joukon S suuruuden verran parittomia komponentteja.
Tutkielman keskivaiheilla käydään läpi sovituksen käsite ja tutustutaan täydellisen sovituksen, maksimisovituksen ja maksimaalisen sovituksen käsitteisiin. Näiden jälkeen esitellään 1-faktorin käsite, jota hyödynnetään sovituksia koskevien lauseiden todistuksissa.Tutkielmassa 1-faktorin etsintä samaistetaan täydellisen sovituksen etsintään niiden samanlaisten ominaisuuksien takia.
Kaksijakoisten graafien sovituksia koskeva kappale sisältää määritelmät käsitteille M-vuorotteleva polku ja M-kasvava polku, joita tarvitaan Königin lauseen todistuksessa. Königin lauseen mukaan kaksijakoisen graafin maksimisovituksessa on yhtä monta särmää, kuin sen pienimmässä särmät peittävässä solmupeitteessä on solmuja. Tutkielmassa todistetaan myös Hallin lauseena tunnettu tulos, jonka mukaan kaksijakoinen graafi sisältää täydellisen sovituksen jos ja vain jos millä tahansa kaksijakoisen graafin solmujen osajoukolla on vähintään yhtä paljon naapurisolmuja kuin osajoukossa itsessään on solmuja. Tulos voidaan todistaa helposti hyödyntämällä Königin lausetta. Hallin lauseesta seuraa tulos, jonka mukaan kaksijakoinen graafi sisältää 1-faktorin, jos graafi on k-säännöllinen ja k ≥ 1.
Tutkielman lopussa käydään läpi yleisille graafeille keskeisenä tuloksena Tutten lause, jonka mukaan graafilla G on 1-faktori, jos ja vain jos mille tahansa graafin G solmujen osajoukolle S pätee, että graafissa G - S on korkeintaan joukon S suuruuden verran parittomia komponentteja.
Kokoelmat
- Kandidaatintutkielmat [8344]