| Popis: |
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. |
