Browsing by Author "Kangas, Juho-Kustaa"

Suuntaamattoman verkon yhtenäinen joukko on solmujen osajoukko, jonka indusoima aliverkko on yhtenäisen. Tällaisten joukkojen lukumäärä eri verkkoperheissä on viime aikoina osoittautunut kiinnostavaksi suureeksi erityisesti algoritmien analyysin kannalta. Esimerkiksi kauppamatkustajan ongelma sekä niin sanottu Tutte-polynomi voidaan ratkaista ajassa, joka on polynomisen kertoimen päässä verkon yhtenäisten joukkojen määrästä. Koska täydellisen verkon kaikki osajoukot ovat yhtenäisiä, kysymykseksi on noussut erityisesti yhtenäisten joukkojen määrän asymptoottinen kasvu verkoissa, joiden suurin aste on rajoitettu. Tällä hetkellä paras tunnettu yläraja asymptoottiselle kasvulle tällaisissa verkoissa seuraa eräänlaiseen paikalliseen analyysiin perustuvasta entropiamenetelmästä. Ylärajan laatu riippuu olennaisesti siitä, kuinka monella tavalla mielivaltainen yhtenäinen joukko voi leikata kunkin solmun suljetun naapuruston. Tunnettu alaraja puolestaan seuraa yksinkertaisesta äärettömästä verkkoperheestä, jossa yhtenäisten joukkojen määrä osataan määrittää tarkasti. Kokeellisten arvioiden perusteella vaikuttaa kuitenkin selvältä, ettei kumpikaan nykyisistä rajoista ole tiukka ja lukumäärän asymptoottinen kasvu vaatii siten tarkempaa analyysiä. Käymme läpi tunnetut analyyttiset ja algoritmiset tulokset liittyen yhtenäisten joukkojen lukumäärään sekä yleisissä että rajoitetun asteen verkoissa. Laajennamme entropiaan perustuvaa menetelmää tarkastelemalla tavallisten naapurustojen sijaan solmujen yleistettyjä naapurustoja, jotka sisältävät kaikki enintään kiinnitetyn säteen r ≥ 2 päässä olevat solmut. Näytämme koneelliseen etsintään nojaten, että leikkausten suhteellinen lukumäärä on tällöin pienempi ja johtaa hieman parempaan ylärajaan, kun verkon suurin aste ∆ on 3 tai 4. Näytämme myös kokeellisiin havaintoihin vedoten, että laajennus ei oletettavasti paranna aikaisempaa ylärajaa millään ∆ > 5 tai r > 2. Avoimeksi kysymykseksi jää, voidaanko ylärajaa parantaa kehittämällä entropiaan perustuvaa menetelmää edelleen vai vaatiko tarkempi analyysi uudenlaista lähestymistapaa. Tarkastelemme kysymystä lopuksi toisesta suunnasta osoittamalla asymptoottiselle kasvulle alarajan yksinkertaisella konstruktiolla. Luomme myös katsauksen pieniin verkkoihin, joissa yhtenäisen joukkojen määrä on suurin mahdollinen, ja tarkastelemme lähemmin tällaisten verkkojen muita ominaisuuksia.