Graafiteooria: erinevus redaktsioonide vahel

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<ref>Bollobás, B., 1998. ''Modern Graph Theory. ''. Springer''.</ref>.

Mõned peavad graafiteooriat [[matemaatika]] osaks, mille eripäraks olevat objektide geomeetriline käsitlemine<ref>Aleksejev, V., Kozyrjev, V. jt. Алексеев, В., Козырев, B. и др., 1977. ''Графов теория''. ''Математическая Энциклопедия, Том 1'', ''Москва''.</ref>. 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<ref>Busacker, R., Saaty, T., 1965. ''Finite Graphs and Networks. An Introduction ans Application''. ''Mc Graw Hill'', N.Y.</ref>. Algebraga on asi keerulisem. Graafide sümmeetria ülesandeid on lahendatud [[rühmateooria]] abil. Paraku on see küllalti mahukaks ja keerukaks tegevuseks osutunud. [[Isomorfismiprobleem]]i on rühmateooria seisukohalt käsitlenud C. Hoffman 1982. aastal väites, et rühmade „struktuur” sarnanevat isomorfismiprobleemile<ref>Hoffman, C., 1982. ''Group-Theoretic Algorithms and Graph Isomorphism. ''. Springer'', N.Y.</ref>. Paraku jääb see sarnasus kõrvaltvaatajale raskelt tabatavaks.

[[Algoritm]]idest graafide käsitlemisel ei pääse. „Algoritmibuum” algas N. Chirtofides’e monograafia ilmumisega 1975. aastal<ref name="Christo">Christofides, N. ''Graph Theory: An Algorithmic Approach''., 1975. ''Academic Press'', London.</ref>. See kestab edasi, alles hiljuti ilmus seesama monograafia uuesti. J. Gross ja J. Yellen [1999] peavad graafe arvutiteaduse objektideks<ref>Gross, J., Yellen, J., 1999. ''Graph Theory and its Applications''. ''CRC Press''.</ref>. Selline seisukoht on küllaltki levinud. S. Pemmaraju ja S. Skiena [2003] pakuvad arvutiprogramme graafide käsitlemiseks<ref>Pemmaraju, S., Sciena, S., 2003. ''Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica''. ''Cambrige University Press''.</ref>. Ka graafide [[struktuurisemiootika|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 Appel]]i ja [[Wolfgang Haken]]i poolt 1976. aastal esitatud [[neljavärviprobleem]]i tõestus<ref>Appel, K., Haken, W.,1976. ''The Existence of Unavoidable Sets of Geographically Good Configurations, ''. Illinois J. Math., 82, 218–297''.</ref>, mida ei peeta enam korrektseks ning praegu otsitakseon leitud sellele uusi tõestusviise <ref> Ashay Dharwadker, ''The Four Colour Theorem'', Proc. Institute of Mathematics, Amazon Books, ISBN 1466265302 </ref>. [[Isomorfismiprobleem]], mille lahendamiskatsete buum toimus möödunud sajandi kaheksakümnendail, on praegu kõrvale heidetud. [[Ulami hüpotees]]i all tuntud taastatavusega tegeleb suur hulk uurijaid, kuid kõigi poolt aktsepteeritav üldine lahendus puudub tänapäevani <ref> Ulam, S. M., 1960. ''A Collection of Mathematical Problems''. ''Wiley'', N.Y.</ref>.

Graafiteooriale aluse panija on [[Leonhard Euler]] (1707–1783), [[Šveits]]i matemaatik ja füüsik, [[Peterburi Teaduste Akadeemia]] liige. Ta lahendas tuntud [[Königsbergi sildade probleem]]i – 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 <ref> Euler, L., 1736. ''Solutio problematis ad geometriam situs pertinentis. ''. Comment. Academiae Sci. I. Petropolitanae 8 (1736), 128-140'', Peterburg.</ref>. 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 [[Gustav Kirchhof|G. R. Kirchhof]] 1847. aastal oma elektrivõrkude <ref>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''.</ref> ning A. Cayley 1857. aastal orgaaniliste [[isomeerid]]e alastes uuringutes <ref>Cayley, A., 1857. ''On the theory of the analytical forms called trees. ''. Phil. Mag. (4) 13 (1857), 172–176''.</ref>. Sõna „graaf” võttis esimesena kasutusele J. J. Sylvester keemiliste struktuurvalemite kujutamisel 1878. aastal<ref>Silvester, J.J., 1878. ''Chimistry and algebra. ''. Nature 17 (1878), 284''.</ref>.

N. L. Briggs jt. on leidnud üle 250 ajavahemikus 1736–1936 ilmunud graafe puudutava artikli <ref>Biggs, N.L., Lloyd, E.K., Wilson, R.J., 1986. ''Graph Theory 1736–1936. ''. Clarendon Press''</ref>. 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, [[Julius Petersen|J. Petersen]], G. Polya, H. Weil, H. Whitney. Tähtsaim on siin [[Dénes König]]i (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 <ref> König, D., 1936. ''Theorie der endlichen und unendlichen Graphen. ''. Akad. Verlag M.B.H.'', Leipzig.</ref>. Selle kordustrükk ilmus ka veel 1950 ning ingliskeelne tõlge alles 1990.

Esimesed järgijad olid C. Berge [1958]<ref>Berge, C., 1958. ''Theorie des Graphes et Ses Applications''. Dunod, Paris.</ref> ja [[Øystein Ore|O. Ore]] [1962]<ref>Ore, O., 1962. ''TheoryGraphs ofand GraphsTheir Uses''. Random House, N. Y.</ref>. Nendes domineerib rakenduslik külg. Silmapaistvad on [[Frank Harary]] [1969]<ref>Harary, F., 1969. ''Graph Theory. ''. Addison-Wesley'', N.Y.</ref>, B. Bollobas’i [1979], W. T. Tutte [1984]<ref>Tutte, W.T., 1984. ''Graph Theory. ''. Addison-wesley'', Reading, MA.</ref>, A. Chartrand ja L. Lesniak’i [1986]<ref name="CL">Chartrand, G., Lesniak, L., 1986. ''Graphs and digraphs. ''. Wadsworth International'', Monterery, California.</ref> ning [[Aleksandr Zõkov|A. Zykovi]] [1987, 2004]<ref>*Zykov, A., 1987. Зыков, A. ''Основы теории графов. ''. Наука'', Москва.</ref> klassikalised monograafiad. Graafiteooria arenedes tekib ka erinevaid lähenemisviise. L. Collatz ja U. Sinogowitz [1957] rajasid ''spektraalse graafiteooria'' alused<ref>Collatz, L., Sinagowitz, U., 1957. ''Spektren endlicher Graphen. ''. Abh. Math. Sem. Univ. Hamburg, 21 (1957), 63–77'', Hamburg.</ref>. [[Pál Erdös|P. Erdös]] esitas ''juhuslike-'' [1961] ja ''ekstremaalse graafiteooria'' [1967] alused. N. L. Biggs [1974] avaldas ''algebralise graafiteooria'' alase monograafia<ref>Biggs, N.L., 1974. ''Algebraic Graph Theory. ''. Cambridge University Press'', Cambrige.</ref>. N. Cristofides’e [1975] monograafiaga loodi alus ''algoritmilisele graafiteooriale''<ref name="Christo"/>. D. Archdeacon ja U. Vermont edendavad ''topoloogilist graafiteooriat'' ning E. Scheinerman jt ''fraktaalset graafiteooriat''.

Aastatel 1936 kuni 2006, st pärast graafiteooria teket, ilmunud kirjanduse kohta puudub täpne teave. A. Chartrand ja L. Lesniak’iLesniak on fikseerinud 70 ajavahemikus 1936–1996 ilmunud, peamiselt inglise, saksa ja venekeelset monograafiat<ref name="CL"/>. Tegelikult on neid palju rohkem. Artikli-tuhandete arv on tabamatu.

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]]<ref> Krahn, E. 1932. ''Der Wahrscheinlichkeit der Richtigkeit des Veirfarben-satzes''. Acta Comment. Univ. Tartu (A) 22 No 2 (1932), 1–7, Tartu </ref>. 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 <ref> Kilp, M. 1984. ''Neljavärviprobleem: Ühe matemaatikaprobleemi lahenduse lugu''. Valgus, Talinn.</ref>.

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š]] <ref>Gabovitsh, J., 1968. Arvudeta matemaatika. Sissejuhatus tänapäeva matemaatikasse. Tallinn.</ref>. Graafiteooriat on käsitletud mitmesugustes diskreetse matemaatika alastes õppematerjalides. Esimene eestikeelne monograafiaülevaade graafiteooriast ilmus 1976. aastal O. Ore „Graafidmonograafia jatõlke nendenäol kasutamine”<ref> (tõlkOre, O., Mati1976. Kilp)''Graafid näolja nende kasutamine''. Tallinn.</ref>.

Esimene graafiteooria rakendusi käsitlev põhjalik oopus „Lineaarsete ahelate teooria” (paraku venekeelne) ilmus 1968. aastal, tolleaegse TPI teaduri Vello Kuke sulest <ref> Кукк, В. 1968. ''Теория линейных цепей''. Таллинн. </ref>. 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 „The First Estonian Conference on Graphs and Applications”, mis toimus Käärikul 12.–19. mail 1991 <ref> ''Proc. of the First Estonian Conference on Graühs and Applications''. Tartu, 1993 </ref>.

Käesoleval ajal esindavad eestikeelset graafiteooriat Peeter Puusempa loengukonspekt [2000] ja Ahto Buldas, Peeter Laud ja Jan Willemsoni 2003. aastal ilmunud õpik „Graafid”<ref>Buldas, A., Laud, P., Willemson, J., 2003. ''Graafid. ''. TÜ kirjastus'', Tartu. ISBN 9789949118182 </ref>. Graafiteooriat käsitlenud oma artiklites [[Leo Võhandu]] janing [[John-Tagore Tevet]] oma uurimisrühma S.E.R.R. väljaannetes aastatel 1999–20121990–2012 <ref> Tevet, J.-T. 1990. ''Interpretation on some Graph Theoretical Problems''. Proc. Estonian. Acad. of Sci.</ref> <ref> Tevet, J.-T. 2010. ''Graafide varjatud külgi''. S.E.R.R. ISBN 9789949213108 </ref>. 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 <ref> Kumlander, D., 2005. ''Some practical algorithms to solve the maximum clique problem''. Tallinn. </ref>.

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 <ref> ''The Second Estonian Conference on Graphs and Applikations''. Baltic Horizons No 8. (107) (2007) </ref>. 2010. aastal ilmus artiklite kogumik koostöös [[Ashay Dharwadker|Dharwadkeri]] matemaatikainstituudiga <ref> ''From Fundamental Problems to Applications of Graph Theory''. Baltic Horizons No 14 (111) (2010) </ref>.

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

Kodulehtede temaatika on „seinast seina”. AinukeneÜ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.

== KirjandusKirjandust ==