Teorija grafov

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

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