Verkkoteoria
Verkkoteoria eli graafiteoria on matematiikan osa-alue, joka tutkii kohteiden välisten suhteiden esittämiseen käytettäviä matemaattisia malleja eli verkkoja[1]. Verkot koostuvat solmuista ja niitä yhdistävistä linkeistä, jotka voivat olla suunnattuja tai suuntaamattomia. Verkkoteoriaa voidaan soveltaa monilla eri tieteenaloilla[2], kuten fysiikassa[3], biologiassa[4], sosiologiassa[5].
Suomen kielessä verkkoteorian perustermistö ei ole kovin vakiintunutta, sillä aihetta käsitteleviä suomenkielisiä kirjoja on julkaistu niukasti. Yksi harvoista suomenkielisistä verkkoja käsittelevistä kirjoista on Kimmo Pietiläisen suomentama teos.[6]
Verkkoteoriaa hyödyntävää poikkitieteellistä tutkimusalaa kutsutaan verkostotieteeksi, siinä missä verkkoteoria yleisesti mielletään matematiikan ja teoreettisen tietojenkäsittelytieteen osa-alueeksi. Pohjimmiltaan verkko on verkkoteorian määrittämä solmujen ja niitä yhdistävien linkkien kokonaisuus. Verkko kuvaa verkostomaisen rakenteen neutraalisti riippumatta sen sisällöstä ja tulkinnasta ja esittää, mitä reittejä verkossa eri solmujen välillä on. Verkkoteorian keskeisiin tutkimusongelmiin kuuluvat mm. yhtenäisyys, laajentuvuus, väritettävyys ja satunnaisverkkojen analyysi.
Historia
[muokkaa | muokkaa wikitekstiä]Verkkoteorian alkuna pidetään sitä, kun Leonhard Euler ratkaisi Königsbergin siltaongelman vuonna 1736. Eulerin todistus oli samalla ensimmäinen todistus verkkoteorian alueella. Tuohon aikaan verkkoteoriasta käytettiin Leibnizin luomaa termiä "analysis situs", sanan "graph" otti käyttöön James Sylvester vuonna 1878 Nature lehdessä julkaisemassaan artikkelissa. Termi oli poimittu kemiasta.[7] Tanskalainen Julius Petersen julkaisi verkkoteoriaa koskevia papereita 1890-luvulla.[8]
Alun jälkeen verkkoteorian kehityksessä tapahtui vain vähän ennen 1930-lukua. Vuonna 1930 Kazimierz Kuratowski ratkaisi kysymyksen verkkojen piirtämisestä tasoon. Seuraava tärkeä etappi oli Dénes Kőnigin tasan 200 vuotta Eulerin siltaongelmaa koskevan tutkielman jälkeen vuonna 1936 julkaisema ensimmäinen verkkoteoriaa kattavasti käsittelevä kirja. Tärkeä verkkoteorian perusteos on myös Frank Hararyn vuonna 1968 julkaisema Graph Theory.[7][8] Satunnaisverkot muodostavat nykyään yhden keskeisistä verkkoteorian tutkimuskohteista. Tämän aihepiirin klassinen merkkipaalu on Paul Erdősin ja Alfred Rényin vuonna 1959 julkaisema artikkeli tasajakautuneiden satunnaisverkkojen yhtenäisyydestä[9]. Stokastiset satunnaisverkkomallit muodostavat modernin verkostotieteen ytimen ja niillä on paljon sovelluksia mm. bioteteissä, sosiaalitieteissä ja koneoppimisessa.
Graafialgoritmeja
[muokkaa | muokkaa wikitekstiä]- A*-etsintä
- Davidson–Harel-algoritmi
- Dijkstran algoritmi
- Floydin algoritmi
- Ford–Fulkerson-algoritmi
- IDA*-etsintä
- Karp–Held-heuristiikka
- Kruskalin algoritmi
- Leveyssuuntainen läpikäynti eli leveyshaku (engl. breadth-first search, BFS)
- Primin algoritmi
- Syvyyssuuntainen läpikäynti eli syvyyshaku (engl. depth-first search, DFS)
- Unkarilainen algoritmi
- Warshallin algoritmi
Graafiongelmia
[muokkaa | muokkaa wikitekstiä]Katso myös
[muokkaa | muokkaa wikitekstiä]Lähteet
[muokkaa | muokkaa wikitekstiä]- ↑ Nystuen, J. D., & Dacey, M. F. (1961). A graph theory interpretation of nodal regions. Papers in Regional Science, 7(1), 29-42.
- ↑ Gross, J. L., & Yellen, J. (2005). Graph theory and its applications. CRC press.
- ↑ Gutman, I. & Trinajstić, N. (1972) Graph theory and molecular orbitals. Total φ-electron energy of alternant hydrocarbons, Chemical Physics Letters, Vol. 17, No. 4
- ↑ Mason, O. & Verwoerd, M. (2007) Graph theory and networks in Biology, IET Systems Biology, Vol. 1, No. 2
- ↑ Harary, F., & Norman, R. Z. (1953). Graph theory as a mathematical model in social science. Ann Arbor: University of Michigan, Institute for Social Research.
- ↑ Barabási, Albert-László: Linkit – Verkostojen uusi teoria. Terra Cognita, 2002.
- ↑ a b N.L.Biggs, E.K.Lloyd, R.J.Wilson: Graph Theory, 1736–1936. Oxford University Press, 1976.
- ↑ a b Grimaldi, Ralph P.: Discrete and Combinatorial Mathematics: an Applied Introduction, s. 540–541. (4. painos) Addison Wesley, 1999. ISBN 0-201-19912-2 (englanniksi)
- ↑ Erdös, Paul. ja Rényi, Alfred: On random graphs I. Publicationes Mathematicae Debrecen, 1959, 6. vsk, s. 290-297.
Kirjallisuutta
[muokkaa | muokkaa wikitekstiä]- Ruohonen, Keijo: Graafiteoria (2004) (Yliopistotason opintomoniste graafiteoriaan)
- vuoden 2013 versio via archive.org
- Diestel, Reinhard: Graph Theory: Electronic (3rd) Edition
- Diestelin oppikirjan verkkoversio, 312 sivua, PDF, ei tulostettavissa
- Ruohonen, Keijo: Graafiteoria. (Opintomoniste 136) Tampere: TTKK, 1990. ISBN 951-721-530-4
- Savolainen, Vesa: Verkkoteoria (2001)
Aiheesta muualla
[muokkaa | muokkaa wikitekstiä]
Kuvia tai muita tiedostoja aiheesta Verkkoteoria Wikimedia Commonsissa