Teorija grafov
Iz Wikipedije, proste enciklopedije
Teoríja gráfov je veja matematike in računalništva, ki raziskuje lastnosti 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).
Strukture, ki jih lahko predstavimo z grafi v smislu teorije grafov, je moč najti povsod. Veliko praktičnih problemov lahko rešujemo s pomočjo grafov. Zgradbo povezav Wikipedije lahko predstavimo 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 lahko razširimo z vpeljavo uteži, ki so pozitivna števila prirejena vsaki povezavi. Če na primer graf predstavlja mrežo cest, lahko uteži predstavljajo dolžine vsake ceste. 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.
[uredi] Zgodovina
Eden od prvih rezultatov v teoriji grafov se je pojavil v Eulerjevem članku o sedmih königsberških mostovih, objavljenem leta 1736 v delu Solutio problematis ad geometriam situs pertinensis. Problem smatrajo tudi kot prvi topološki rezultat v geometriji, v smislu, da ni odvisen od merjenja. Tu se pokaže globoka povezava med teorijo grafov in topologijo.
Leta 1845 je Kirchhoff še kot študent objavil svoja Kirchhoffova zakona za izračun električne napetosti in toka v električnih krogih.
Mladi angleš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 smatramo 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.
[uredi] Glej tudi
- algebrska teorija grafov
- topološka teorija grafov
[uredi] Zunanje povezave
Ta matematični članek je škrbina. Slovenski Wikipediji lahko pomagate tako, da ga dopolnite z vsebino.
Ta članek, ki se nanaša na računalništvo, je škrbina. Slovenski Wikipediji lahko pomagate tako, da ga dopolnite z vsebino.
