![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/1/13/Graph_001.svg/langsl-640px-Graph_001.svg.png&w=640&q=50)
Teorija grafov
From Wikipedia, the free encyclopedia
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).
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/1/13/Graph_001.svg/640px-Graph_001.svg.png)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Graf_sz_001.svg/320px-Graf_sz_001.svg.png)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/Wikipedia_multilingual_network_graph_July_2013.svg/640px-Wikipedia_multilingual_network_graph_July_2013.svg.png)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e7/Relative_neighborhood_graph.svg/320px-Relative_neighborhood_graph.svg.png)
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.