Teorija grafov

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
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)
Graf relativne soseščine na 100 poljubnih točkah v enotskem kvadratu

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

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 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[uredi | uredi kodo]

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.[1][2] 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.[3][4]

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. Preštevalna 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 rezultae o drevesih s sočasnimi raziskavami kemične sestave.[5] Zlitje matematičnih zamisli s tistimi iz kemije predstavlja temelje dela standardnega izrazoslovja teorije grafov.

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

Glej tudi[uredi | uredi kodo]

Opombe in sklici[uredi | uredi kodo]

  1. ^ Biggs, Lloyd, Wilson (1986).
  2. ^ Euler (1741).
  3. ^ Cauchy (1813)
  4. ^ L'Huilier (1861).
  5. ^ Cayley (1875).

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]