JultikaUniversity of Oulu repository

Tiivistelmä

Tämän pro gradu -tutkielman tarkoituksena on esitellä Eulerin verkkojen karakterisointiin tarvittavia verkkoteorian peruskäsitteitä, sekä niiden avulla karakterisoida Eulerin verkot. Eulerin verkoilla tarkoitetaan sellaisia verkkoja, joissa on mahdollista kulkea reitti verkon jokaisen solmun kautta siten, että jokainen kaari esiintyy täsmälleen kerran. Kierroksen lopuksi palataan takaisin lähtöpisteseen.

Verkkoteoria on saanut alkunsa 1700-luvulla Königsbergin siltaongelmasta, jonka sveitsiläinen matemaatikko Leonhard Euler onnistui ratkaisemaan vuonna 1736. Nykyisessä Kaliningradissa, joka 1700-luvulla tunnettiin nimellä Königsberg, virtaa kaupungin läpi joki, jonka keskellä on kaksi saarta. Joen molemmilta rannoilta on mahdollista kulkea kuuden eri sillan kautta saarille, ja lisäksi saarien välillä on yksi silta. Ongelmallinen kysymys oli, onko reitti mahdollista kulkea siten, että jokainen silta ylitetään täsmälleen kerran. Euler onnistui ensimmäisenä esittämään ongelman matemaattisesti ja osoittamaan, ettei siihen ollut ratkaisua [3]. Euler perusteli, että edellä kuvatun kaltaisen reitin olemassaolo verkossa edellyttää, että muodostuva verkko on yhtenäinen, ja lisäksi verkossa täytyy olla täsmälleen kaksi paritonasteista pistettä. Tätä tulosta hyödyntäen voidaan määritellä myös Eulerin verkot, joissa lisäksi on mahdollista kulkea edellä kuvatun kaltainen reitti palaten lopuksi takaisin lähtöpisteeseen. Tällaiset ehdot täyttäviä verkkoja nimitetään Eulerin verkoiksi.

Koska Königsbergin siltojen muodostama verkko ei toteuttanut näitä ehtoja, ei reittiä ollut mahdollista kulkea edellä kuvatulla tavalla. Alkuperäinen Eulerin esittämä perustelu Königsbergin siltaongelmaan on julkaistu vuonna 1736 teoksessa Solutio problematis ad geometriam situs pertinentis. Englanninkielinen käännös alkuperäistekstistä löytyy teoksesta [4]. Eulerin ongelmaan esittämän matemaattisen perustelun pohjalta on saanut alkunsa verkkoteoriaksi nimetty diskreetin matematiikan osa-alue, jolla on nykymaailmassa paljon tärkeitä solvellutuksia esimerkiksi tietoliikenneverkoissa, reittikartoissa ja kaupunkien tiestöjen suunnittelussa.

Tutkielmassa esitetyt lauseet ja määritelmät on laadittu pääosin teoksen [1] pohjalta, ellei toisin ole mainittu. Esimerkkien ja kuvien yhteydessä on mainittu erikseen niiden mahdolliset lähteet.