Mengerin lause ja Tutten nowhere-zero -ongelma

Abstract

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.