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.
 | See artikkel ootab keeletoimetamist. (Mai 2023) |
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.
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].
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.
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”.
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 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.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
