Mengerin lause ja Tutten nowhere-zero -ongelma
214.16 KB
avoin
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
Lataukset237
Pysyvä osoite
Verkkojulkaisu
DOI
Tiivistelmä
Tässä työssä tutkitaan siirtoverkkoja sekä suuntaamattomien graafien k-virtauksia. Tutustutaan erityisesti Mengerin lauseeseen siirtoverkkojen yhtenäisyydestä sekä Tutten avoimeen ongelmaan, jonka mukaan jokaisella sillattomalla graafilla on nowhere-zero -5-virtaus. Työ alkaa graafien perusmääritelmien esittämisellä. Tämän jälkeen todistetaan siirtoverkoille maksimivirtaus-minimi-irrotus -lause sekä johdetaan samasta todistuksesta vielä Ford–Fulkerson-algoritmi. Lisäksi esitetään Mengerin tulos todistuksineen. Viimeinen luku aloitetaan osoittamalla, että jokaisella suuntaamattomalla graafilla on k-virtaus, jos ja vain jos sillä on Z_k-virtaus. Sen jälkeen tutustutaan Nash-Williamsin lauseeseen, joka yhdistää graafin yhtenäisyyden sekä virittävien puiden lukumäärän. Esitetään vielä Tutten avoin ongelma, joitain samansuuntaisia tuloksia sekä lopuksi todistetaan Seymourin lause, jonka mukaan jokaisella sillattomalla graafilla on nowhere-zero -6-virtaus. Päätulokseen johtavan lemman 4.0.3 olen muokannut ja todistanut itsenäisesti.