Berge-perfektit graafit ja Shannonin kapasiteetti
Syvänen, Joel (2017)
2017
Matematiikan ja tilastotieteen tutkinto-ohjelma - Degree Programme in Mathematics and Statistics
Luonnontieteiden tiedekunta - Faculty of 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ä
2017-05-31
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:uta-201706121938
https://urn.fi/URN:NBN:fi:uta-201706121938
Tiivistelmä
Graafin G Shannonin kapasiteetti on tunnusluku, joka kuvaa graafia G vastaavan kommunikaatiokanavan maksimaalista virheetöntä tiedonsiirtokykyä. Shannonin kapasiteetin määrittäminen hyvin yksinkertaisillekin graafeille on osoittautunut erittäin vaikeaksi. Poikkeuksen muodostavat graafit, joiden riippumattomuusluku ja pienimmän mahdollisen klikkiosituksen koko ovat yhtä suuret. Perfektin graafin jokaisella aligraafilla on edellä mainittu ominaisuus.
Tässä tutkielmassa osoitetaan, että seitsemän pituinen sykli on yksinkertaisin graafi, jonka Shannonin kapasiteetin tarkka arvo on vielä tuntematon. Tämä osoitetaan todeksi näyttämällä, että tätä yksinkertaisempien graafien arvot tunnetaan seuraavien kolmen faktan ansiosta. 1) Perfektin graafin kapasiteetti on sama kuin sen riippumattomuusluku. 2) Graafi on perfekti, jos ja vain jos se on berge (vahva perfektien graafien teoreema). 3) Viiden pituisen syklin kapasiteetti on √5.
Tutkielmassa käydään läpi perfektien graafien perusteet ja todistetaan heikko perfektien graafien teoreema Lovászin tapaan normaalien hypergraafien avulla. Vahvan perfektien graafien teoreeman osalta määritellään keskeiset käsitteet. Lisäksi tutkitaan riippumattomuusluvun ja graafien tulon suhdetta. Näitä hyödynnetään Shannonin kapasiteetin määrittelyssä, sen ominaisuuksien tutkimisessa ja erityisesti heikosti α-perfektien graafien kapasiteetin määrittämisessä. Syklin C₅ Shannonin kapasiteetin todistamisessa hyödynnetään Lovászin sateenvarjotekniikkaa. Näin on osoitettu, että seitsemän pituista sykliä yksinkertaisempien graafien kapasiteettien tarkat arvot on laskettavissa. Tutkielman viimeisessä kappaleessa esitetään Shannon kapasiteetin laskemiseen menetelmiä, joilla entuudesta tunnettujen kapasiteetin arvojen perusteella voidaan joissakin tilanteissa määrittää kapasiteetti tutkittavalle graafille.
Tässä tutkielmassa osoitetaan, että seitsemän pituinen sykli on yksinkertaisin graafi, jonka Shannonin kapasiteetin tarkka arvo on vielä tuntematon. Tämä osoitetaan todeksi näyttämällä, että tätä yksinkertaisempien graafien arvot tunnetaan seuraavien kolmen faktan ansiosta. 1) Perfektin graafin kapasiteetti on sama kuin sen riippumattomuusluku. 2) Graafi on perfekti, jos ja vain jos se on berge (vahva perfektien graafien teoreema). 3) Viiden pituisen syklin kapasiteetti on √5.
Tutkielmassa käydään läpi perfektien graafien perusteet ja todistetaan heikko perfektien graafien teoreema Lovászin tapaan normaalien hypergraafien avulla. Vahvan perfektien graafien teoreeman osalta määritellään keskeiset käsitteet. Lisäksi tutkitaan riippumattomuusluvun ja graafien tulon suhdetta. Näitä hyödynnetään Shannonin kapasiteetin määrittelyssä, sen ominaisuuksien tutkimisessa ja erityisesti heikosti α-perfektien graafien kapasiteetin määrittämisessä. Syklin C₅ Shannonin kapasiteetin todistamisessa hyödynnetään Lovászin sateenvarjotekniikkaa. Näin on osoitettu, että seitsemän pituista sykliä yksinkertaisempien graafien kapasiteettien tarkat arvot on laskettavissa. Tutkielman viimeisessä kappaleessa esitetään Shannon kapasiteetin laskemiseen menetelmiä, joilla entuudesta tunnettujen kapasiteetin arvojen perusteella voidaan joissakin tilanteissa määrittää kapasiteetti tutkittavalle graafille.