Graph Algorithms for Constructing and Enumerating Cycles and Related Structures

Julkaisun otsikon käännös: Graafialgoritmeja syklien ja niihin liittyvien rakenteiden konstruointiin ja enumerointiin

Ville Pettersson

    Tutkimustuotos: Doctoral ThesisCollection of Articles

    Abstrakti

    Graafi on matemaattinen objekti joka koostuu solmuista ja solmujen välillä olevista kaarista. Yksinkertaisesta määritelmästä huolimatta graafit ovat hyvin monipuolisia; sen lisäksi että graafit ovat kiinnostavia teoreettisesta näkökulmasta, niillä on suuri määrä sovelluksia monella tieteen ja teknologian alalla, kuten fysiikassa, biologiassa ja tietoliikennetekniikassa. Tässä väitöskirjassa tutkitaan algoritmeja, joita voidaan käyttää syklien ja eräiden sykleihin liittyvien rakenteiden konstruoimiseen ja lukumäärän laskemiseen graafeissa. Syklit ovat keskeisiä objekteja graafiteoriassa, ja niitä esiintyy lukuisissa sovelluksissa. Monien sovellusten kannalta on tärkeää konstruoida tai laskea sellaisia graafeissa olevia syklejä joilla on joitain tiettyjä ominaisuuksia. Väitöskirjatyössä luodut algoritmit perustuvat kanoniseen augmentointiin, dynaamiseen ohjelmointiin ja rekursiiviseen hakuun, ja ne käyttävät hyväkseen tutkittavien graafien symmetriaa. Väitöskirjan kontribuutio on seuraavanlainen. Esitämme uuden menetelmän Hamiltonin syklien lukumäärän laskemiseen yleisissä graafeissa, tasograafeissa ja hilagraafeissa. Laskemme täydellisten paritusten lukumäärän n-kuutiossa arvoon n = 7 asti. Löydämme uusia indusoituja syklejä ja polkuja 8-kuutiossa ja todistamme että näiden pituus on suurin mahdollinen. Löydämme uusia pieniä hypohamiltonisia tasograafeja, joissa on vain 40 solmua; pienin aiemmin tunnettu esimerkki sisälsi 42 solmua. Lopuksi tutkimme Toeplitzin konjektuuria laskemalla tietynlaisten syklien lukumäärän hilagraafissa.
    Julkaisun otsikon käännösGraafialgoritmeja syklien ja niihin liittyvien rakenteiden konstruointiin ja enumerointiin
    AlkuperäiskieliEnglanti
    PätevyysTohtorintutkinto
    Myöntävä instituutio
    • Aalto-yliopisto
    Valvoja/neuvonantaja
    • Östergård, Patric, Vastuuprofessori
    • Östergård, Patric, Ohjaaja
    Kustantaja
    Painoksen ISBN978-952-60-6364-5
    Sähköinen ISBN978-952-60-6365-2
    TilaJulkaistu - 2015
    OKM-julkaisutyyppiG5 Artikkeliväitöskirja

    Tutkimusalat

    • graafit
    • algoritmit
    • syklit
    • konstruointi
    • enumerointi

    Sormenjälki

    Sukella tutkimusaiheisiin 'Graafialgoritmeja syklien ja niihin liittyvien rakenteiden konstruointiin ja enumerointiin'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

    Siteeraa tätä