Graafiteoreettinen johdanto unkarilaiseen algoritmiin
Forss, Sami (2019)
2019
Tekniikan ja luonnontieteiden TkK tutkinto-ohjelma
Tekniikan ja luonnontieteiden tiedekunta - Faculty of Engineering and Natural 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ä
2019-08-05
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-201908052812
https://urn.fi/URN:NBN:fi:tuni-201908052812
Tiivistelmä
Tässä kandidaatintyössä käsitellään unkarilainen algoritmi graafiteoriaa hyödyntäen.
Unkarilainen algoritmi on yksi sovitusongelman ratkaisevista graafiteorian metodeista. Sovitusongelman tavoitteena on löytää optimaalinen sovitus painotetulle kaksijakoiselle graafille.
Työn tavoitteena on todistaa, että unkarilainen algoritmi toimii. Algoritmi hyödyntää ratkaisun löytämisessä sekä yhtäsuuruus aligraafin olemassaoloa että algoritmin sisäistä toimintoa, joka kasvattaa sovituksen kokoa. Algoritmin toiminta osoitetaan käyttäen työssä todistettavia näihin käsitteisiin ja toimintoihin liittyviä graafiteoreettisia tuloksia. Työn lopussa esitellään yksinkertainen esimerkki unkarilaisen algoritmin toiminnasta käytännössä.
Unkarilainen algoritmi on yksi sovitusongelman ratkaisevista graafiteorian metodeista. Sovitusongelman tavoitteena on löytää optimaalinen sovitus painotetulle kaksijakoiselle graafille.
Työn tavoitteena on todistaa, että unkarilainen algoritmi toimii. Algoritmi hyödyntää ratkaisun löytämisessä sekä yhtäsuuruus aligraafin olemassaoloa että algoritmin sisäistä toimintoa, joka kasvattaa sovituksen kokoa. Algoritmin toiminta osoitetaan käyttäen työssä todistettavia näihin käsitteisiin ja toimintoihin liittyviä graafiteoreettisia tuloksia. Työn lopussa esitellään yksinkertainen esimerkki unkarilaisen algoritmin toiminnasta käytännössä.
Kokoelmat
- Kandidaatintutkielmat [4042]