University of Oulu

Eulerin verkkojen karakterisointi

Saved in:
Author: Heikkilä, Jenni1
Organizations: 1University of Oulu, Faculty of Science, Mathematics
Format: ebook
Version: published version
Access: open
Online Access: PDF Full Text (PDF, )
Persistent link: http://urn.fi/URN:NBN:fi:oulu-201901081009
Language: Finnish
Published: Oulu : J. Heikkilä, 2019
Publish Date: 2019-01-08
Thesis type: Master's thesis
Tutor: Järvenpää, Esa
Reviewer: Myllylä, Kari
Järvenpää, Esa
Description:
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 kerrran. 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.
see all

Subjects:
Copyright information: © Jenni Heikkilä, 2019. This publication is copyrighted. You may download, display and print it for your own personal use. Commercial use is prohibited.