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)displaystyle G=(V,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 |

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

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

Graafiteooriast Eestis |

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 Kilpi 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]. Ä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 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 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 |

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

Kirjandust |

• 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 |

• Graph Theory Software