Graafiteooria

Allikas: Vikipeedia

Graafiteooria on matemaatika haru, mille uurimisobjektiks on graaf. See on defineeritud kui moodustis mittetühjast hulgast V ja selle hulga elemendipaaridest E, G=(V, E), mida naabertippudeks nimetatakse.

Niisugune moodustis on käsitletav algebralisest, algoritmilisest, geomeetrilisest, kombinatoorsest, juhuslikkuse (tõenäosuslikust), struktuursest või topoloogilisest aspektist. Klassifikaatori MSC2000 järgi iseseisvat graafiteooriat ei esine ja graafi atribuudid kuuluvad kombinatoorikasse.

Üldist[muuda | redigeeri lähteteksti]

Graafiteooria saavutusi hinnatakse peamiselt nende rakendatavuse järgi praktiliste ülesannete lahendamisel. On välja kujunenud, et eelkõige huvitutakse naabertippude poolt moodustatud teede, marsruutide, tsüklite jt taoliste osiste vastu. Näiteks, teedele kinnistatud voogude baasil on graafiteooriasse tekkinud valdkond, mida „elektrivõrkudeks” nimetatakse[1].

Samas areneb ja laieneb graafiteooria stiihiliselt ega oma mingit „generaalplaani”. Arendavaks jõuks on kas „sotsiaalne tellimus” või puhas uudishimu. Nagu teisedki teooriad, jagunevad arusaamad graafiteooriast kool- ja vennaskondadeks.

Mõned peavad graafiteooriat matemaatika osaks, mille eripäraks olevat objektide geomeetriline käsitlemine[2]. Tõepoolest, graafiteoorias esineb hulk geomeetrilisi termineid. Graafide loendamine rajaneb puhtalt kombinatoorikal. Ka topoloogia mõisteid esineb küllaldaselt. R. Busacker’i ja T. Saaty on veendunud, et graafid on matemaatiliselt kirjeldatavad just topoloogia baasil[3]. Algebraga on asi keerulisem. Graafide sümmeetria ülesandeid on lahendatud rühmateooria abil. Paraku on see küllalti mahukaks ja keerukaks tegevuseks osutunud. Isomorfismiprobleemi on rühmateooria seisukohalt käsitlenud C. Hoffman 1982. aastal väites, et rühmade „struktuur” sarnanevat isomorfismiprobleemile[4]. Paraku jääb see sarnasus kõrvaltvaatajale raskelt tabatavaks.

Algoritmidest graafide käsitlemisel ei pääse. „Algoritmibuum” algas N. Chirtofides’e monograafia ilmumisega 1975. aastal[5]. See kestab edasi, alles hiljuti ilmus seesama monograafia uuesti. J. Gross ja J. Yellen (1999) peavad graafe arvutiteaduse objektideks[6]. Selline seisukoht on küllaltki levinud. S. Pemmaraju ja S. Skiena (2003) pakuvad arvutiprogramme graafide käsitlemiseks[7]. Ka graafide struktuurisemiootiline käsitlus realiseeritakse algoritmide baasil.

Graafiteoorias on ülesandeid, mis seni lahendamata on või olemasolevaid lahendusi ei peeta korrektseks. Näiteks on selline kuulus Kenneth Appeli ja Wolfgang Hakeni poolt 1976. aastal esitatud neljavärviprobleemi tõestus[8], mida ei peeta enam korrektseks ning praegu on leitud sellele uusi tõestusviise [9]. Isomorfismiprobleem, mille lahendamiskatsete buum toimus möödunud sajandi kaheksakümnendail, on praegu kõrvale heidetud. Ulami hüpoteesi all tuntud taastatavusega tegeleb suur hulk uurijaid, kuid kõigi poolt aktsepteeritav üldine lahendus puudub tänapäevani [10].

Huvitava ülevaate graafidest on andnud R. C. Read ja R. J. Wilson oma "Graafiatlases" [11].

Ajaloost[muuda | redigeeri lähteteksti]

Königsbergi sildade ülesanne

Graafiteooriale aluse panija on Leonhard Euler (1707-1783), Šveitsi matemaatik ja füüsik, Peterburi Teaduste Akadeemia liige. Ta lahendas tuntud Königsbergi sildade probleemi – läbida hargnevaid jõgesid ületavat seitset silda, neist igat üht vaid üks kord läbides. Konstrueerides teede originaalse skeemi, tõestas ta, et sellist marsruuti ei eksisteeri. Selle tulemuse avaldas ta artikli – „probleemi selgitamisest geomeetria põhjal” – näol aastal 1736 [12]. Selliseid skeeme käsitles ta ka oma töödes 1750., 1752. ja 1759. aastal.

Need Euleri tulemused jäid pikemaks ajaks unustusse ning graafe on korduvalt „uuesti avastatud”. Nii avastas need G. R. Kirchhof 1847. aastal oma elektrivõrkude [13] ning A. Cayley 1857. aastal orgaaniliste isomeeride alastes uuringutes [14]. Sõna „graaf” võttis esimesena kasutusele J. J. Sylvester keemiliste struktuurvalemite kujutamisel 1878. aastal[15].

N. L. Briggs jt. on leidnud üle 250 ajavahemikus 1736-1936 ilmunud graafe puudutava artikli [16]. Autorite hulgas esinevad sellised tuntud nimed nagu G. D. Birkhoff, A. Cayley, G. R. Kirchhof, Edgar Krahn (Tartu Ülikool), P. T. Krikman, K. Kuratowski, D. König, J. Petersen, G. Polya, H. Weil, H. Whitney. Tähtsaim on siin Dénes Königi (1884-1944) 1936. aastal ilmunud saksakeelne monograafia, millesse oli koondatud kõik selleks ajaks teadaolev ning autori poolt edasi arendatu. Seda oopust loeme graafiteooria, kui terviku, alustuseks [17]. Selle kordustrükk ilmus ka veel 1950 ning ingliskeelne tõlge alles 1990.

Esimesed järgijad olid C. Berge (1958)[18] ja O. Ore (1962) [19]. Nendes domineerib rakenduslik külg. Silmapaistvad on Frank Harary (1969)[20], B. Bollobas’i (1979), W. T. Tutte (1984)[21], A. Chartrand ja L. Lesniak’i (1986)[22] ning A. Zykovi (1987), 2004][23] klassikalised monograafiad. Graafiteooria arenedes tekib ka erinevaid lähenemisviise. L. Collatz ja U. Sinogowitz (1957) rajasid spektraalse graafiteooria alused[24]. P. Erdös esitas juhuslike- (1961) ja ekstremaalse graafiteooria (1967) alused. N. L. Biggs (1974) avaldas algebralise graafiteooria alase monograafia[25]. N. Cristofides’e (1975) monograafiaga loodi alus algoritmilisele graafiteooriale[5]. D. Archdeacon ja U. Vermont edendavad topoloogilist graafiteooriat ning E. Scheinerman jt fraktaalset graafiteooriat.

Aastatel 1936-2006, st pärast graafiteooria teket, ilmunud kirjanduse kohta puudub täpne teave. A. Chartrand ja L. Lesniak on fikseerinud 70 ajavahemikus 1936-1996 ilmunud, peamiselt inglise, saksa ja venekeelset monograafiat[22]. Tegelikult on neid palju rohkem. Artikli-tuhandete arv on tabamatu.

Tänapäevani domineerib graafiteooria generaalliinis teatud „königsberglik käsitlus”, mis avaldub erilises huvis ikka ja jälle just marsruutide, teede, tsüklite, suunatud, Euleri- ja Hamiltoni graafide ning võrkudes olevate voogude vastu. Paraku on graafide süsteemne, struktuurne ja sümmeetriaomaduste käsitlemine jäänud tahaplaanile.

Graafiteooriast Eestis[muuda | redigeeri lähteteksti]

Eesti matemaatikute esimesed jõukatsumised graafiteooria alal toimusid arvatavasti nelja-värvi-probleemi kallal. 1927. aastal avaldas matemaatikaprofessor Jaan Sarv neljavärviprobleemile pühendatud artikli. Paar aastat hiljem publitseeris professor Jüri Nuut ulatusliku sarja artikleid (kokku ligi 200 lehekülge), milles käsitles selle probleemiga seotud aritmeetikaküsimusi. Pikka aega tegeles neljavärviprobleemiga professor Hermann Jaakson. 1932. aastal avaldas artikli neljavärviprobleemi positiivse lahenduse tõenäosusest Edgar Krahn[26]. Professorid Sarv, Nuut ja Jaakson tegid selle probleemi lahendamiseks pika aja jooksul tõsiseid jõupingutusi. Ka professor Mati Kilp'i 1984. aastal ilmunud raamat on pühendatud neljavärviprobleemile [27].

Graafiteooriale pühendatud artikleid ilmus aastatel 1964-1975 ilmavalgust näinud kogumikus „Matemaatika ja kaasaeg”. Graafiteooriat on lühidalt käsitlenud oma 1968. aastal ilmunud raamatus „Arvudeta matemaatika” Tartu matemaatik Jevgeni Gabovitš [28]. Graafiteooriat on käsitletud mitmesugustes diskreetse matemaatika alastes õppematerjalides. Esimene eestikeelne ülevaade graafiteooriast ilmus 1976. aastal O. Ore monograafia tõlke näol [29].

Esimene graafiteooria rakendusi käsitlev põhjalik oopus „Lineaarsete ahelate teooria” (paraku venekeelne) ilmus 1968. aastal, tolleaegse TPI teaduri Vello Kuke sulest [30]. Tallinn.. Ära märkida võiks veel möödunud sajandi seitsmekümnendail toimunud graafiteooria rakenduste buumi nn „võrkplaneerimise” sildi all. Graafide rakenduste, ja mitte ainult nende, vastu tundis suurt huvi automaatikaprofessor Hanno Sillamaa (1928-2003), graafidele on truuks jäänud elektrivõrkude arendamise grand old man akadeemik Lembit Krumm. Teadaolevalt on Eestis graafiteooriat rakendatud ja rakendatakse krüptograafia, sidetehnika ja ökoloogia valdkondades.

Graafiteooria ergutamisele Eestis on kaasa aidanud graafiteooria suure tegija distinguished professor Frank Harary maaletoomine 1989. aastal. Märkimisväärne oli Frank Harary 70. sünnipäevale pühendatud "Eesti Esimene Graafide ja Rakenduste Konverents”, mis toimus Käärikul 12.–19. mail 1991 [31].

Käesoleval ajal esindavad eestikeelset graafiteooriat Peeter Puusempa loengukonspekt (2000) ja Ahto Buldas, Peeter Laud ja Jan Willemsoni 2003. aastal ilmunud õpik „Graafid”[32]. Graafiteooriat käsitlenud oma artiklites Leo Võhandu ning John-Tagore Tevet oma uurimisrühma S.E.R.R. väljaannetes aastatel 1990-2012 [33] [34]. Eestis on graafiteooria baasil kaitstud ka doktori väitekirju, näiteks, Leo Võhandu suunamisel on seda teinud Ahto Buldas ja Innar Liiv. Ära märkida tuleks ka Denis Kumlanderi tööd praktiliste algoritmide alal [35].

2006. aasta septembris toimus "Eesti Teine Graafide ja Rakenduste Konverents", mis oli pühendatud graafide 270. ja graafiteooria 70. sünniaasta päevale, kus osalesid ka Soome ja India matemaatikud [36]. 2010. aastal ilmus artiklite kogumik koostöös Dharwadkeri matemaatikainstituudiga [37].

Eesti „graafiteoreetilist arusaamist” iseloomustavad ka kodulehed. Näiteks, Matti Littoveri koduleht kujutab endast väga korralikku eesti-inglise-eesti graafiteooria seletavat sõnaraamatut. Koduleht ( http://www.graphs.ee ) esitab graafide struktuurisemiootilise käsitluse aluseid, arendusi ja rakendusi, selles on tegemist graafide järjekordse „taasavastamisega”.

Graafiteooriast Internetis[muuda | redigeeri lähteteksti]

Kui graafiteooria üksikartiklite kohta on raske mingit koondülevaadet saada, siis kodulehed on Internetis „luubi all” ning andmed nende kohta koondatud vastavatesse portaalidesse. Kui esitada päring graafiteooria kodulehtede kohta, saame kodulehtede toimetatud „top” nimekirju.

Kodulehtede temaatika on „seinast seina”. Üks graafiteooriat tervikuna hõlmav koduleht on Other Graph Theory and Related Pages (http://www.math.fau.edu/locke/graphoth.htm). Graafiteoreetikute „jututuba” on Graphnet (http://listserv.nodak.edu/archives/graphnet.html). Seal arutatakse aktuaalseid probleeme ning esitatakse küsimusi ja konverentsikuulutusi. Graphnet on kõigile avatud tribüün, kus paraku domineerivad Zürichi Tehnikakõrgkooli ja Põhja-Dakota Ülikooli teadurid. Graafiteoreetiliste kontseptsioonide esitamisel on suur panus India matemaatikul Ashay Dharwadker’il (http://www.dharwadker.org). Jörg Zuther (http://www.joergzuther.de/math/graph/homes.html) haldab ca poole tuhande graafiteoreetiku kodulehe süstematiseeritud loetelu.

Kodulehti haldavad ja korrastavad ka ajakirjad. Näiteks „Journal of Graph Theory”, kuhu püüab pürgida iga endast lugupidav graafiteoreetik, on artikli maht ajakirjas viidud miinimumini, tervikut võib näha vaid nende vastaval koduleheküljel. Elektronkataloogi ester.nlib.ee kaudu saab siseneda digitaalarhiivi (digar.nlib.ee), kuhu on sisestatud ka rida uurimisrühma S.E.R.R. teavikke graafiteooriast. On kodulehti, mis on pühendatud suurtele tegijatele, näiteks Frank Harary’le.

Viited[muuda | redigeeri lähteteksti]

  1. Bollobás, B., 1998. Modern Graph Theory. Springer.
  2. Aleksejev, V., Kozyrjev, V. jt. Алексеев, В., Козырев, B. и др., 1977. Графов теория. Математическая Энциклопедия, Том 1, Москва.
  3. Busacker, R., Saaty, T., 1965. Finite Graphs and Networks. An Introduction ans Application. Mc Graw Hill, N.Y.
  4. Hoffman, C., 1982. Group-Theoretic Algorithms and Graph Isomorphism. Springer, N.Y.
  5. 5,0 5,1 Christofides, N. Graph Theory: An Algorithmic Approach., 1975. Academic Press, London.
  6. Gross, J., Yellen, J., 1999. Graph Theory and its Applications. CRC Press.
  7. Pemmaraju, S., Sciena, S., 2003. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambrige University Press.
  8. Appel, K., Haken, W.,1976. The Existence of Unavoidable Sets of Geographically Good Configurations. Illinois J. Math., 82, 218–297.
  9. Dharwadker, A. The Four Colour Theorem, Proc. Institute of Mathematics, Amazon Books, ISBN 1466265302
  10. Ulam, S. M., 1960. A Collection of Mathematical Problems. Wiley, N.Y.
  11. Read, R. C, Wilson, R. J. 2004. An Atlas of Graphs. Oxford, ISBN ISBN 0198526504
  12. Euler, L., 1736. Solutio problematis ad geometriam situs pertinentis. Comment. Academiae Sci. I. Petropolitanae 8 (1736), 128-140, Peterburg.
  13. Kirchhof, T.P., 1847. Über die Auflösung der Greichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanisch Ströme geführt wird. Ann. Phys. Chem. 72 (1847), 497–508.
  14. Cayley, A., 1857. On the theory of the analytical forms called trees. Phil. Mag. (4) 13 (1857), 172–176.
  15. Silvester, J.J., 1878. Chimistry and algebra. Nature 17 (1878), 284.
  16. Biggs, N.L., Lloyd, E.K., Wilson, R.J., 1986. Graph Theory 1736–1936. Clarendon Press
  17. König, D., 1936. Theorie der endlichen und unendlichen Graphen. Akad. Verlag M.B.H., Leipzig.
  18. Berge, C., 1958. Theorie des Graphes et Ses Applications. Dunod, Paris.
  19. Ore, O., 1962. Graphs and Their Uses. Random House, N. Y.
  20. Harary, F., 1969. Graph Theory. Addison-Wesley, N.Y.
  21. Tutte, W.T., 1984. Graph Theory. Addison-wesley, Reading, MA.
  22. 22,0 22,1 Chartrand, G., Lesniak, L., 1986. Graphs and digraphs. Wadsworth International, Monterery, California.
  23. *Zykov, A., 1987. Зыков, A. Основы теории графов. Наука, Москва.
  24. Collatz, L., Sinagowitz, U., 1957. Spektren endlicher Graphen. Abh. Math. Sem. Univ. Hamburg, 21 (1957), 63–77, Hamburg.
  25. Biggs, N.L., 1974. Algebraic Graph Theory. Cambridge University Press, Cambrige.
  26. Krahn, E. 1932. Der Wahrscheinlichkeit der Richtigkeit des Veirfarben-satzes. Acta Comment. Univ. Tartu (A) 22 No 2 (1932), 1–7, Tartu
  27. Kilp, M. 1984. Neljavärviprobleem: Ühe matemaatikaprobleemi lahenduse lugu. Valgus, Talinn.
  28. Gabovitš, J., 1968. Arvudeta matemaatika. Sissejuhatus tänapäeva matemaatikasse. Tallinn.
  29. Ore, O., 1976. Graafid ja nende kasutamine. Tallinn.
  30. Кукк, В. 1968. Теория линейных цепей. Таллинн.
  31. Proc. of the First Estonian Conference on Graühs and Applications. Tartu, 1993
  32. Buldas, A., Laud, P., Willemson, J., 2003. Graafid. TÜ kirjastus, Tartu. ISBN 9789949118182
  33. Tevet, J.-T. 1990. Interpretation on some Graph Theoretical Problems. Proc. Estonian. Acad. of Sci.
  34. Tevet, J.-T. 2010. Graafide varjatud külgi. S.E.R.R. ISBN 9789949213108
  35. Kumlander, D., 2005. Some practical algorithms to solve the maximum clique problem. Tallinn.
  36. Proc. of The Second Estonian Conference on Graphs and Applikations. Baltic Horizons No 8. (107) (2007)
  37. A Special Issue on Fundamental Researches and Application in Graph Theory (In Collaboration with Imstitute of Mathematics, Gurgaon). Baltic Horizons No 14 (113) (2010)

Kirjandust[muuda | redigeeri lähteteksti]

  • Võhandu, L. 2001. Graafide korrastamine J-keele abil. A&A, 5, 51–56, 6, 38–44, Tallinn.
  • Võhandu, L., 2007. Graphs as effective models of the world. Baltic Horizons, No 8. (107) 17–22, Tallinn.
  • Tevet, J.-T. 2012. Semiotic Modelling of the Graphs. S.E.R.R., Tallinn. ISBN 9789949302475.
  • Dharwadker, A., Pirzada, B. 2011. Graph Theory. Amazon Books, ISBN 9781466254992.

Vaata ka[muuda | redigeeri lähteteksti]