Teorija grafov

Teoríja gráfov je matematična in računalniška disciplina, ki raziskuje značilnosti grafov. Graf je najpreprosteje rečeno množica objektov, reči, ki se imenujejo točke (vozlišča, vozli), in so povezane s povezavami (robovi, vejami).

Graf na šestih točkah s sedmimi povezavami in z zaporedjem povezav d = {1,1,2,3,3,4}.

Enostavni neoznačeni graf 51-tih slovenskih mest od 73-tih, povezanih z železnico. Graf ni drevo, saj ima dva cikla. Graf zaradi omejitve povezave mest ne vsebuje vseh prog (vir: Slovenske železnice)

Omrežni graf, kjer so povezave uporabniki Wikipedije, točke pa različne jezikovne različice Wikipedije v času enega meseca poleti 2013

Graf relativne soseščine na 100 poljubnih točkah v enotskem kvadratu

Strukture, ki se jih lahko predstavi z grafi v smislu teorije grafov, je moč najti povsod. Veliko praktičnih problemov se lahko rešuje s pomočjo grafov. Zgradbo povezav Wikipedije se lahko predstavi kot usmerjeni graf - točke so članki v Wikipediji. Usmerjena povezava iz članka A do članka B obstaja le, če ima A povezavo na B. Razvoj algoritmov, ki obravnavajo grafe, je velikega pomena v računalništvu.

Grafe se lahko razširi z vpeljavo uteži, ki so pozitivna števila prirejena vsaki povezavi. Če na primer graf predstavlja mrežo cest ali železniških prog, lahko uteži predstavljajo dolžine vsake ceste, oziroma železniške proge. Povezave so v usmerjenih grafih (oziroma digrafih) usmerjene in lahko povezujejo točke le v eno smer. Digraf z uteženimi povezavami (uteženi digraf) se imenuje mreža.

Zelo znana uporaba grafov je v metodi mrežnega planiranja - izračun planiranega trajanja projektov.

Zgodovina

Prikaz problema königsberških mostov

Eden od prvih rezultatov v teoriji grafov se je pojavil v Eulerjevem članku o sedmih königsberških mostovih, objavljenem leta 1741 kot Rešitev problema povezanega z geometrijo lege (Solutio problematis ad geometriam situs pertinensis) v reviji Commentarii academiae scientiarum Petropolitanae. Problem imajo tudi za prvi topološki rezultat v geometriji, v smislu, da ni odvisen od merjenja. Tu se pokaže globoka povezava med teorijo grafov in topologijo. Eulerjev članek, ter Vandermondejev članek o skakačevem problemu se je nadaljeval z Leibnizevim delom.

Eulerjevo formulo, ki povezuje število oglišč, robov in ploskev konveksnega poliedra, sta raziskovala in razširila Cauchy in L'Huilier.

Leta 1845 je Kirchhoff še kot študent objavil svoja zakona za izračun električne napetosti in toka v električnih krogih.

Več kot stoletje po Eulerjevem članku o königsberških mostovih in po Listingovi vpeljavi topologije leta 1847 je Cayley raziskoval posebne analitične forme, ki so izhajale iz diferencialnega računa, za obravnavo posebnega razreda grafov, dreves. Te raziskave so imele več uporab v teoretični kemiji. Ti postopki so se večinoma ukvarjali s preštevanjem grafov s posebnimi značilnostmi. Enumerativna teorija grafov je nato zrasla iz Cayleyjevih rezultatov in temeljnih rezultatov, ki jih je objavil Pólya med letoma 1935 in 1937, ter iz njihovih posplošitev De Bruijna leta 1959. Cayley je povezal svoje rezultate o drevesih s sočasnimi raziskavami kemične sestave. Zlitje matematičnih zamisli s tistimi iz kemije predstavlja temelje dela standardnega izrazoslovja teorije grafov.

Izraz »graf« (angleško graph) je uvedel Sylvester v članku objavljenem leta 1878 v reviji Nature, kjer je potegnil analogijo med »kvantičnimi invariantami« in »kovariantami« algebre in molekularnimi diagrami:

»[…] Vsaka invarianta in kovarianta tako postaneta izrazljivi z grafom, natanko istovetno s Kekuléovim diagramom ali kemikografom. […] Tu podajam pravilo za geometrično množenje grafov, to je za konstrukcijo grafa k produktu in- ali ko-variant, katerih ločena grafa sta podana. […]« (ležeče besedilo kot v izvirniku).

Prvi učbenik o teoriji grafov je napisal Dénes Kőnig in ga objavil leta 1936. Druga knjiga, ki jo je leta 1969 objavil Frank Harary je »veljala za dovršeni učbenik tega področja,« in je omogočila matematikom, kemikom, elektroinženirjem in socialnim delavcem, da so se lahko med seboj sporazumevali. Harary je podaril avtorske tantieme za ustanovitev Pólyeve nagrade.

Mladi južnoafriški matematik Guthrie je leta 1852 verjetno prvi podal problem štirih barv, ki sprašuje ali je možno pobarvati poljuben zemljevid držav z uporabo največ štirih barv, tako da nobeni sosednji državi nista pobarvani z isto barvo. Ta problem lahko velja za rojstvo teorije grafov. Prvič se je pojavil v Cayleyjevem delu O barvanju zemljevidov (On the colourings of maps), ki ga je izdala Kraljeva geografska družba leta 1879. Čeprav je na videz preprost, je bil problem dolgo časa nedokazan. Dokazala sta ga leta 1976 Appel in Haken s pomočjo računalnika. Pri dokazovanju tega problema so matematiki iznašli veliko osnovnih pojmov in zamisli s področja teorije grafov.

Tutte je leta 1946 s protiprimerom ovrgel Taitovo domnevo iz leta 1886 o Hamiltonovih ciklih na robovih poliedrov. Če bi Taitova domneva veljala, bi to hkrati dokazalo tudi problem štirih barv.

Pólya je leta 1937 rešil problem števila izomerov alkanov.

Glej tudi

• algebrska teorija grafov
• topološka teorija grafov
• slovar izrazov teorije grafov

Viri

• Biggs, Norman L.; Lloyd, E. Keith; Wilson, Robin Wilson (1986), Graph Theory, 1736–1936, Oxford University Press, ISBN 0-19-853916-9
• Cauchy, Augustin Louis (1813), »Recherche sur les polyèdres - premier mémoire«, Journal de l'Ecole Polytechnique, 9 (Cahier 16): 66–86
• Cayley, Arthur (1857), »On the theory of the analytical forms called trees«, Philosophical Magazine, Series IV, 13 (85): 172–176, doi:10.1017/CBO9780511703690.046
• Cayley, Arthur (1875), »Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen«, Berichte der deutschen Chemischen Gesellschaft, 8: 1056–1059, doi:10.1002/cber.18750080252
• Euler, Leonhard, »Solutio problematis ad geometriam situs pertinensis«, Commentarii academiae scientiarum Petropolitanae Komentar o publikaciji in izvirno besedilo v latinščini (angleško).
• Gardner, Martin (1992), Fractal Music, Hypercards, and more…Mathematical Recreations from Scientific American, W. H. Freeman and Company
• Hale, Scott A. (2013). »Multilinguals and Wikipedia Editing«. arXiv:1312.0976 [cs.CY].
• L'Huillier, Simon Antoine Jean (1861), »Mémoire sur la polyèdrométrie«, Annales de Mathématiques, 3: 169–189
• Sylvester, James Joseph (1878), »Chemistry and Algebra«, Nature, 17: 284, doi:10.1038/017284a0
• Trudeau, Richard J. (1993), Introduction to Graph Theory (pop., pov. izd.), New York: Dover Pub., ISBN 978-0-486-67870-2, pridobljeno 8. avgusta 2012
• Tutte, W. T. (2001), Graph Theory, Cambridge University Press, ISBN 978-0-521-79489-3, pridobljeno 14. marca 2016
• Wilson, Robin James; Watkins, John Jaeger (1997), Uvod v teorijo grafov [Graphs : an introductory approach] (Knjižnica Sigma - 63 izd.), Ljubljana: DFMA Slovenije, COBISS 72250368, ISBN 961-212-081-1

Zunanje povezave

• Weisstein, Eric Wolfgang. »Graph Theory«. MathWorld.