Razlika med usmerjenim in ne usmerjenim grafom

Usmerjen proti Neizmerni graf

Graf je matematična struktura, ki jo sestavljajo sklopi tock in robov. Graf predstavlja niz predmetov (predstavljenih z vozlišči), ki so povezani preko nekaterih povezav (predstavljenih z robovi). Z uporabo matematičnih zapisov je graf mogoče predstaviti z G, kjer je G = (V, E) in V množica tock in E množica robov. V usmerjenem grafu ni nobene smeri, povezane z robovi, ki povezujejo točki. V usmerjenem grafu je smer, povezana z robovi, ki povezujejo točki.

Neizmerni graf

Kot smo že omenili, je usmerjeni graf graf, v katerem na robovih ni smeri, ki bi povezale točke v grafu. Slika 1 prikazuje usmerjen graf z nizom tock 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č ne preprečuje zapisovanja niza robov kot V = (V2, V1), (V3, V2), (V3, V1), ker robovi nimajo smeri. Zato robovi v usmerjenem grafu niso urejeni pari. To je glavna značilnost usmerjenega grafa. Neizmerne grafe lahko uporabimo za prikaz simetričnih razmerij med predmeti, ki so predstavljeni s točki. Na primer, dvosmerno cestno omrežje, ki povezuje niz mest, je mogoče predstaviti z uporabo usmerjenega grafa. Mesta so lahko predstavljena z vozlišči na grafu, robovi pa predstavljajo dvosmerne ceste, ki povezujejo mesta.

Usmerjeni graf

Usmerjeni graf je graf, v katerem imajo robovi v grafu, ki povezujejo točki, smer. Slika 2 prikazuje usmerjeni graf z nizom tock V = V1, V2, V3. Nabor robov v zgornjem grafu lahko zapišemo kot V = (V1, V2), (V2, V3), (V1, V3). Robovi v usmerjenem grafu so urejeni pari. Formalno lahko rob e v usmerjenem grafu predstavimo z urejenim parom e = (x, y), kjer je x točki, ki se imenujejo izvor, izvor ali začetna točka roba e, vrhovi y pa se imenuje terminus , končna točka ali končna točka. Na primer, cestno omrežje, ki povezuje niz mest z enosmernimi cestami, je mogoče predstaviti z uporabo usmerjenega grafa. Mesta so lahko predstavljena z vozlišči na grafu, usmerjeni robovi pa predstavljajo ceste, ki povezujejo mesta glede na smer, po kateri teče promet po cesti.

Kakšna je razlika med usmerjenim grafom in ne usmerjenim grafom?

V usmerjenem grafu je rob urejen par, kjer urejeni par predstavlja smer roba, ki povezuje obe točki. Po drugi strani je v ne usmerjenem grafu rob neurejen par, saj z robom ni nobene smeri. Neizmerne grafe lahko uporabimo za prikaz simetričnih razmerij med predmeti. Stopnja in višina vsakega vozlišča v usmerjenem grafu sta enaka, vendar to ne velja za usmerjeni graf. Ko uporabite matriko za predstavitev usmerjenega grafa, matrika vedno postane simetrični graf, vendar to ne velja za usmerjene grafe. Neusmerjen graf lahko pretvorimo v usmerjen graf z zamenjavo vsakega roba z dvema usmerjenima robovoma, ki gredo v nasprotno smer. Vendar usmerjenega grafa ni mogoče pretvoriti v usmerjen graf.