Mine sisu juurde

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, , mida nimetatakse naabertippudeks.

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 | muuda 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 teistegi teooriate puhul, jagunevad ka arusaamad graafiteooriast kool- ja vennaskonniti.

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 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 isomorfismiprobleemiga[4]. Paraku jääb see sarnasus kõrvaltvaatajale raskelt tabatavaks.

Algoritmidest graafide käsitlemisel ei pääse. „Algoritmibuum” algas N. Chirtofidese 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 mille seniseid lahendusi ei peeta korrektseks. Näiteks on selline kuulus Kenneth Appeli ja Wolfgang Hakeni 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 1980. aastatel, on praegu kõrvale heidetud. Ulami hüpoteesi all tuntud taastatavusega tegeleb suur hulk uurijaid, kuid kõiki rahuldav üldine lahendus puudub tänapäevani.[10]

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

Ajaloost

[muuda | muuda 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 struktuurivalemite 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. Bollobasi (1979), W. T. Tutte (1984)[21], A. Chartrand ja L. Lesniaki (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. Cristofidese (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 inglis-, saksa- ja venekeelset monograafiat[22]. Tegelikult on neid palju rohkem.

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 tagaplaanile.

Graafiteooriast Eestis

[muuda | muuda lähteteksti]

Eesti matemaatikute esimesed jõukatsumised graafiteooria alal toimusid arvatavasti neljavärviprobleemi kallal. 1927. aastal avaldas matemaatikaprofessor Jaan Sarv neljavärviprobleemist artikli. Paar aastat hiljem ilmus professor Jüri Nuudilt ulatuslik sari artikleid (kokku ligi 200 lehekülge), milles ta 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 Kilpi 1984. aastal ilmunud raamat on neljavärviprobleemi teemal.[27]

Graafiteooriateemalisi 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]. Ära märkida võiks veel 1970. aastail 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 valdkonnas.

Graafiteooria ergutamisele Eestis on kaasa aidanud graafiteooria suure tegija Frank Harary töö tutvustamine 1989. aastal. Märkimisväärne oli Frank Harary 70. sünnipäeva puhul korraldatud 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 on käsitlenud oma artiklites Leo Võhandu ja 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ünniaastapä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 | muuda 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 tippnimekirju.

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 Dharwadkeril (http://www.dharwadker.org). Jörg Zuther (http://www.joergzuther.de/math/graph/homes.html) haldab umbes 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 kodulehel. Elektronkataloogi ester.nlib.ee kaudu saab siseneda digitaalarhiivi (digar.nlib.ee), kuhu on sisestatud ka rida uurimisrühma S.E.R.R. teavikud graafiteooriast. On kodulehti, mis on pühendatud suurtele tegijatele, näiteks Frank Hararyle.

Viited

[muuda | muuda 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. Cambridge 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 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 Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer 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, Cambridge.
  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, Tallinn.
  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)

Kirjandus

[muuda | muuda 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.

Välislingid

[muuda | muuda lähteteksti]
Pärit leheküljelt "https://et.wikipedia.org/w/index.php?title=Graafiteooria&oldid=6773120"