Usmerjeni proti neusmerjenemu grafu
Graf je matematična struktura, ki je sestavljena iz niza vozlišč in robov. Graf predstavlja množico objektov (predstavljenih z vozlišči), ki so povezani preko nekaterih povezav (predstavljenih z robovi). Z uporabo matematičnih zapisov lahko graf predstavimo z G, kjer je G=(V, E) in V množica oglišč, E pa množica 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 neusmerjen graf graf, v katerem ni smeri v robovih, ki povezujejo vozlišča v grafu. Slika 1 prikazuje neusmerjen graf z množico vozlišč V={V1, V2, V3}. Niz robov v zgornjem grafu lahko zapišemo kot V={(V1, V2), (V2, V3), (V1, V3)}. Prav tako lahko opazimo, da nič ne preprečuje zapisa nabora robov kot V={(V2, V1), (V3, V2), (V3, V1)}, saj robovi nimajo smeri. Zato robovi v neusmerjenem grafu niso urejeni pari. To je glavna značilnost neusmerjenega grafa. Neusmerjene grafe je mogoče uporabiti za predstavitev simetričnih odnosov med objekti, ki so predstavljeni z vozlišči. Na primer, dvosmerno cestno omrežje, ki povezuje niz mest, je mogoče predstaviti z neusmerjenim grafom. Mesta so lahko predstavljena z vozlišči v grafu, robovi pa predstavljajo dvosmerne ceste, ki povezujejo mesta.
Usmerjeni graf
Usmerjeni graf je graf, v katerem imajo robovi v grafu, ki povezujejo vozlišča, smer. Slika 2 prikazuje usmerjen graf z množico vozlišč V={V1, V2, V3}. Niz 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 izvor, izvor ali začetna točka roba e, oglišče y pa se imenuje končnik, končno oglišče ali končna točka. Na primer, cestno omrežje, ki povezuje niz mest z enosmernimi cestami, je mogoče predstaviti z neusmerjenim grafom. Mesta so lahko predstavljena z vozlišči v grafu, usmerjeni robovi pa predstavljajo ceste, ki povezujejo mesta glede na smer 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 dve točki. Po drugi strani pa je v neusmerjenem grafu rob neurejen par, saj z robom ni povezana smer. Neusmerjeni grafi se lahko uporabljajo za predstavitev simetričnih odnosov med objekti. Notranja in izhodna stopnja vsakega vozlišča v neusmerjenem grafu je enaka, vendar to ne velja za usmerjen graf. Pri uporabi matrike za predstavitev neusmerjenega grafa matrika vedno postane simetrični graf, vendar to ne velja za usmerjene grafe. Neusmerjen graf lahko pretvorite v usmerjen graf tako, da vsak rob zamenjate z dvema usmerjenima robovoma, ki gresta v nasprotni smeri. Vendar usmerjenega grafa ni mogoče pretvoriti v neusmerjeni graf.
