Graafiteooria

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

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

Teistes keeltes
አማርኛ: ሥነ ግራፍ
Bahasa Indonesia: Teori graf
Bahasa Melayu: Teori graf
беларуская: Тэорыя графаў
čeština: Teorie grafů
dansk: Grafteori
Ελληνικά: Θεωρία γράφων
English: Graph theory
Esperanto: Grafeteorio
euskara: Grafo teoria
한국어: 그래프 이론
íslenska: Netafræði
latviešu: Grafu teorija
lietuvių: Grafų teorija
монгол: Графын онол
Nederlands: Grafentheorie
日本語: グラフ理論
norsk: Grafteori
norsk nynorsk: Grafteori
português: Teoria dos grafos
sicilianu: Tiuria dî grafi
Simple English: Graph theory
slovenčina: Teória grafov
slovenščina: Teorija grafov
српски / srpski: Теорија графова
srpskohrvatski / српскохрватски: Teorija grafova
svenska: Grafteori
Tiếng Việt: Lý thuyết đồ thị
Türkçe: Çizge teorisi
українська: Теорія графів
粵語: 圖論
中文: 图论