Cheegerin epäyhtälö yksinkertaisille graafeille ja hypergraafeille
Kivelä, Viivi (2025)
2025
Matematiikan ja tilastollisen data-analyysin maisteriohjelma - Master's Programme in Mathematics and Statistical Data Analytics
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
Hyväksymispäivämäärä
2025-10-24
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-2025102310080
https://urn.fi/URN:NBN:fi:tuni-2025102310080
Tiivistelmä
Graafien ja hypergraafien avulla voidaan mallintaa erilaisia ilmiöitä, kuten kemiallisten yhdisteiden isomeerejä ja nettisivujen linkkirakenteita. Tutkimalla graafien ominaisuuksia voidaan näistä ilmiöistä saada lisää tietoa. Yksi tapa tutkia graafeja on hyödyntää lineaarialgebran työkaluja, kuten ominaisarvoteoriaa.
Cheegerin epäyhtälön avulla saadaan arvio spektriraon eli normalisoidun Laplace-matriisin pienimmän positiivisen ominaisarvon rajoista hyödyntäen graafin Cheegerin vakiota. Cheegerin vakio on graafin G pienin Cheegerin suhde. Cheegerin epäyhtälö antaa graafin spektriraosta tarkemman arvion, mikäli graafista on hankala irrottaa sen aligraafi. Epäyhtälö on tärkeä työkalu graafin rakenteen selvittämisessä, kun esimerkiksi ominaisarvojen laskeminen suurista graafeista on lähes mahdotonta. Ominaisarvojen arvioiminen on hyödyllistä, sillä ne kertovat tärkeää tietoa graafin rakenteesta muun muassa sen yhtenäisyydestä.
Cheegerin suhde esitettiin vuonna 1951 yksinkertaiselle graafille, jonka jälkeen Cheegerin epäyhtälö on laajennettu useille erilaisille graafeille. Yksi uusimmista laajennuksista on Cheegerin epäyhtälö hypergraafeille vuonna 2021. Hypergraafit koostuvat solmujoukosta ja hypersärmien joukosta. Hypersärmä voi liittää toisiinsa myös enemmän, kuin kaksi solmua. Tämän ansiosta hypergraafien avulla voidaan kuvata monimutkaisempiakin graafeja ja niitä voidaan hyödyntää monissa sovelluksissa. Laajennuksessa otetaan huomioon hypergraafin k-särmäkokoisuus, jolloin epäyhtälön termien kertoimet muuttuvat. Tämä mahdollistaa ominaisarvojen arvioinnin vieläkin monimutkaisimmille hypergraafeille.
Tässä työssä esitellään graafin perusmääritelmiä ja todistetaan Cheegerin epäyhtälö yksinkertaisille graafeille. Lisäksi tutustutaan hypergraafiin ja esitellään Cheegerin epäyhtälö hypergraafeille.
Cheegerin epäyhtälön avulla saadaan arvio spektriraon eli normalisoidun Laplace-matriisin pienimmän positiivisen ominaisarvon rajoista hyödyntäen graafin Cheegerin vakiota. Cheegerin vakio on graafin G pienin Cheegerin suhde. Cheegerin epäyhtälö antaa graafin spektriraosta tarkemman arvion, mikäli graafista on hankala irrottaa sen aligraafi. Epäyhtälö on tärkeä työkalu graafin rakenteen selvittämisessä, kun esimerkiksi ominaisarvojen laskeminen suurista graafeista on lähes mahdotonta. Ominaisarvojen arvioiminen on hyödyllistä, sillä ne kertovat tärkeää tietoa graafin rakenteesta muun muassa sen yhtenäisyydestä.
Cheegerin suhde esitettiin vuonna 1951 yksinkertaiselle graafille, jonka jälkeen Cheegerin epäyhtälö on laajennettu useille erilaisille graafeille. Yksi uusimmista laajennuksista on Cheegerin epäyhtälö hypergraafeille vuonna 2021. Hypergraafit koostuvat solmujoukosta ja hypersärmien joukosta. Hypersärmä voi liittää toisiinsa myös enemmän, kuin kaksi solmua. Tämän ansiosta hypergraafien avulla voidaan kuvata monimutkaisempiakin graafeja ja niitä voidaan hyödyntää monissa sovelluksissa. Laajennuksessa otetaan huomioon hypergraafin k-särmäkokoisuus, jolloin epäyhtälön termien kertoimet muuttuvat. Tämä mahdollistaa ominaisarvojen arvioinnin vieläkin monimutkaisimmille hypergraafeille.
Tässä työssä esitellään graafin perusmääritelmiä ja todistetaan Cheegerin epäyhtälö yksinkertaisille graafeille. Lisäksi tutustutaan hypergraafiin ja esitellään Cheegerin epäyhtälö hypergraafeille.