Teorija grafova

Označeni graf sa 6 čvorova i 7 grana

Teorija grafova je oblast matematike, veoma zastupljena i u informatici, čija je oblast istraživanje osobina grafova. Neformalno govoreći, grafovi su sastavljeni od tačaka, odnosno čvorova (vrhova), i linija među njima, odnosno grana.

Veoma je česta upotreba grafova za opis modela ili struktura podataka. Struktura jedne veb prezentacije se može predstaviti slikovito upotrebom grafa. Čvorovi tog grafa su pojedine stranice a grane grafa su veze kojima se može sa jedne stranice prelaziti na drugu.

Proučavanje algoritama koji rešavaju probleme upotrebom grafova predstavlja veoma značajan deo informatičke nauke. Mreže imaju mnogo primena u proučavanju praktičnih aspekata teorije grafova i to se zove analiza mreža. Analiza mreža je posebno značajna za probleme modeliranja i analiziranje mrežnog saobraćaja, recimo interneta.

Osobine

Ako se može smatrati da je grana koja spaja čvorove A i B isto što i grana koja spaja čvorove B i A, onda je graf neusmeren. Ako se pak smatra da su to dve različite grane onda je graf usmeren.

Pojam grafa može biti proširen dodavanjem osobine težine svakoj grani. Ovakvi grafovi se zovu težinski grafovi i oni su zgodni za predstavljanje nekih problema, na primer mreže puteva gde se težina odnosi na dužinu puta između dva čvora. Težinski graf koji je usmeren zove se mreža.

Dve (ili više) grane grafa su paralelne ako spajaju dva ista temena. Grana može da spaja vrh sa samim sobom, i tada se naziva petljom. Graf koji nema petlje niti paralelne grane se naziva prostim grafom. Graf je prazan ako nema nijednu granu, a nulti graf nema nijedan vrh.

Stepen čvora vi=d(vi) je jednak broju grana koje ulaze/izlaze iz njega, s tim da se petlja računa kao dve grane. Totalni stepen grafa je zbir svih stepeni grafa, i jednak je dvostrukom broju grana. Nije moguće nacrtati graf sa neparnim stepenom.

Graf G'=(V',E') je podgraf grafa G=(V, E) ako je skup njegovih čvorova (V') podskup skupa čvorova grafa G (V), a skup njegovih grana (E') je podskup skupa grana vektora G (E). Ako je ovim grafovima skup čvorova jednak, onda se graf G' naziva razapinjujućim grafom, ili skeletom.

Kompletan graf, prost graf, i njegov komplement

Ako je stepen svakog čvora isti, onda je graf regularan. Kompletan graf je prost graf, kod koga su svaka dva čvora spojena granom.

Izomorfni i neizomorfni grafovi

Dva grafa, G1, i G2 su izomorfna ako i samo ako postoji „ 1-1“ i „ na“ preslikavanje vrhova i grana, tako da se očuvava susednost svih vrhova, tj. da su veze između vrhova načinjene na analogan način. Izomorfni grafovi su od velikog značaja u elektronici, pri konstruisanju štampanih kola, gde grane grafa (strujni vodovi) ne smeju da se seku osim u čvorovima. Zato je bitno da se pronađe izomorfan graf željenom grafu, ali takav da mu se grane ne seku.

Other Languages
አማርኛ: ሥነ ግራፍ
беларуская: Тэорыя графаў
č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
Simple English: Graph theory
slovenčina: Teória grafov
slovenščina: Teorija grafov
српски / srpski: Теорија графова
svenska: Grafteori
Türkçe: Çizge teorisi
українська: Теорія графів
Tiếng Việt: Lý thuyết đồ thị
中文: 图论
粵語: 圖論