Režirani vs neusmerjeni graf
Graf je matematična struktura, ki jo sestavljajo množica točk in robov. Graf predstavlja nabor predmetov (predstavljenih z oglišči), ki so povezani prek nekaterih povezav (predstavljeni z robovi). Z uporabo matematičnih zapisov lahko graf predstavimo z G, kjer je G = (V, E) in V niz oglišč, E pa niz robov. V neusmerjenem grafu ni nobene smeri, povezane z robovi, ki povezujejo oglišča. V usmerjenem grafu je smer, povezana z robovi, ki povezujejo oglišča.
Neusmerjeni graf
Kot smo že omenili, je neusmerjeni graf graf, pri katerem na robovih ni nobene smeri, ki povezujejo točke v grafu. Slika 1 prikazuje neusmerjeni graf z naborom točk V = {V1, V2, V3}. Nabor robov v zgornjem grafu lahko zapišemo kot V = {(V1, V2), (V2, V3), (V1, V3)}. Opazimo lahko tudi, da ničesar ne preprečuje zapisovanja niza robov kot V = {(V2, V1), (V3, V2), (V3, V1)}, ker robovi nimajo smeri. Zato robovi v neusmerjenem grafu niso urejeni pari. To je glavna značilnost neusmerjenega grafa. Neusmerjeni grafi se lahko uporabljajo za predstavitev simetričnih razmerij med predmeti, ki so predstavljeni z oglišči. Na primer, dvosmerno cestno omrežje, ki povezuje nabor mest, je mogoče predstaviti z neusmerjenim grafom. Mesta so lahko predstavljena z oglišči na grafu, robovi pa predstavljajo dvosmerne ceste, ki povezujejo mesta.
Usmerjeni graf
Usmerjeni graf je graf, pri katerem imajo robovi v grafu, ki povezujejo oglišča, smer. Slika 2 prikazuje usmerjeni graf z naborom točk V = {V1, V2, V3}. Nabor robov v zgornjem grafu lahko zapišemo kot V = {(V1, V2), (V2, V3), (V1, V3)}. Robovi v neusmerjenem grafu so urejeni pari. Formalno lahko rob e v usmerjenem grafu predstavimo z urejenim parom e = (x, y), kjer je x oglišče, ki se imenuje izhodišče, vir ali začetna točka roba e, vrh y pa terminus, končna točka ali končna točka. Na primer, cestno omrežje, ki povezuje nabor mest z enosmernimi cestami, je mogoče predstaviti z neusmerjenim grafom. Mesta so lahko predstavljena z oglišči na grafu, usmerjeni robovi pa predstavljajo ceste, ki povezujejo mesta, upoštevajoč smer pretoka prometa na cesti.
Kakšna je razlika med usmerjenim grafom in neusmerjenim grafom?
V usmerjenem grafu je rob urejen par, kjer urejeni par predstavlja smer roba, ki povezuje obe točki. Po drugi strani pa je rob v neusmerjenem grafu neurejen par, saj z robom ni nobene smeri. Neusmerjeni grafi se lahko uporabljajo za predstavitev simetričnih razmerij med predmeti. Stopnja in stopnja vsakega vozlišča v neusmerjenem grafu sta enaki, vendar to ne velja za usmerjeni graf. Ko matriko uporabljamo za predstavitev neusmerjenega grafa, matrika vedno postane simetrični graf, kar pa ne velja za usmerjene grafe. Neusmerjeni graf je mogoče pretvoriti v usmerjen graf, tako da vsak rob nadomestimo z dvema usmerjenima robovoma, ki greta v nasprotno smer. Vendar usmerjenega grafa ni mogoče pretvoriti v neusmerjen graf.
