Lokaali identifiointi graafeissa
Herva, Pyry (2020-02-19)
Lokaali identifiointi graafeissa
(19.02.2020)
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
avoin
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe202003047236
https://urn.fi/URN:NBN:fi-fe202003047236
Tiivistelmä
Tässä tutkielmassa esitellään kaksi uutta peittokoodien luokkaa - lokaalisti identifioivat koodit ja lokaalisti paikallistavat-dominoivat koodit - ja todistetaan näihin liityviä tuloksia eri graafeissa. Tuloksia verrataan vastaaviin tunnettuihin tuloksiin koskien identifioivia ja paikallistavia-dominoivia koodeja. Myös vertailua peittokoodeihin tehdään.
Tutkielma alkaa lyhyellä johdannolla aiheeseen, jonka jälkeen esitellään suurin osa tarvittavista käsitteistä ja määritelmistä toisessa luvussa. Kolmannessa luvussa tutkitaan lyhyesti lokaalisti identifioivia koodeja poluissa ja sykleissä sekä erityisesti niiden suhdetta identifioiviin koodeihin samaisissa graafeissa. Luvussa neljä tarkastellaan identifiointia binäärisissä hyperkuutioissa ja todistetaan tuloksia lokaalisti 1-identifioiville koodeille näissä graafeissa. Viimeisessä luvussa siirrytään joihinkin äärrettömiin hiloihin, joissa tutkitaan lokaalisti 1-identifioivia ja lokaalisti 1-paikallistavia-dominoivia koodeja.
Tutkielma alkaa lyhyellä johdannolla aiheeseen, jonka jälkeen esitellään suurin osa tarvittavista käsitteistä ja määritelmistä toisessa luvussa. Kolmannessa luvussa tutkitaan lyhyesti lokaalisti identifioivia koodeja poluissa ja sykleissä sekä erityisesti niiden suhdetta identifioiviin koodeihin samaisissa graafeissa. Luvussa neljä tarkastellaan identifiointia binäärisissä hyperkuutioissa ja todistetaan tuloksia lokaalisti 1-identifioiville koodeille näissä graafeissa. Viimeisessä luvussa siirrytään joihinkin äärrettömiin hiloihin, joissa tutkitaan lokaalisti 1-identifioivia ja lokaalisti 1-paikallistavia-dominoivia koodeja.