Usmjereni nasuprot neusmjerenom grafu
Graf je matematička struktura koja se sastoji od skupa vrhova i bridova. Graf predstavlja skup objekata (predstavljenih vrhovima) koji su povezani preko nekih veza (predstavljenih bridovima). Koristeći matematičke zapise, graf se može prikazati s G, gdje je G=(V, E) i V skup vrhova, a E skup bridova. U neusmjerenom grafu ne postoji smjer povezan s bridovima koji povezuju vrhove. U usmjerenom grafu postoji smjer povezan s bridovima koji povezuju vrhove.
Neusmjereni grafikon
Kao što je ranije spomenuto, neusmjereni graf je graf u kojem ne postoji smjer u rubovima koji povezuju vrhove u grafu. Slika 1 prikazuje neusmjereni graf sa skupom vrhova V={V1, V2, V3}. Skup bridova u gornjem grafu može se napisati kao V={(V1, V2), (V2, V3), (V1, V3)}. Također se može primijetiti da ništa ne sprječava pisanje skupa rubova kao V={(V2, V1), (V3, V2), (V3, V1)} budući da rubovi nemaju smjer. Stoga bridovi u neusmjerenom grafu nisu uređeni parovi. Ovo je glavna karakteristika neusmjerenog grafa. Neusmjereni grafovi mogu se koristiti za predstavljanje simetričnih odnosa između objekata koji su predstavljeni vrhovima. Na primjer, dvosmjerna cestovna mreža koja povezuje skup gradova može se prikazati pomoću neusmjerenog grafa. Gradovi mogu biti predstavljeni vrhovima na grafu, a rubovi predstavljaju dvosmjerne ceste koje povezuju gradove.
Usmjereni graf
Usmjereni graf je graf u kojem bridovi u grafu koji povezuju vrhove imaju smjer. Slika 2 prikazuje usmjereni graf sa skupom vrhova V={V1, V2, V3}. Skup bridova u gornjem grafu može se napisati kao V={(V1, V2), (V2, V3), (V1, V3)}. Bridovi u neusmjerenom grafu su uređeni parovi. Formalno, rub e u usmjerenom grafu može se prikazati uređenim parom e=(x, y) gdje je x vrh koji se naziva ishodištem, izvorom ili početnom točkom ruba e, a vrh y naziva se kraj, završni vrh ili krajnja točka. Na primjer, cestovna mreža koja povezuje skup gradova jednosmjernim cestama može se prikazati pomoću neusmjerenog grafa. Gradovi se mogu prikazati vrhovima u grafu, a usmjereni bridovi predstavljaju ceste koje povezuju gradove s obzirom na smjer u kojem teče promet na cesti.
Koja je razlika između usmjerenog i neusmjerenog grafikona?
U usmjerenom grafu brid je uređeni par, gdje uređeni par predstavlja smjer brida koji povezuje dva vrha. S druge strane, u neusmjerenom grafu, rub je neuređeni par, budući da ne postoji smjer povezan s rubom. Neusmjereni grafovi mogu se koristiti za predstavljanje simetričnih odnosa između objekata. Ulazni i izlazni stupanj svakog čvora u neusmjerenom grafu je jednak, ali to nije točno za usmjereni graf. Kada se koristi matrica za predstavljanje neusmjerenog grafa, matrica uvijek postaje simetrični graf, ali to ne vrijedi za usmjerene grafove. Neusmjereni graf se može pretvoriti u usmjereni graf zamjenom svakog brida s dva usmjerena brida koja idu u suprotnom smjeru. Međutim, nije moguće pretvoriti usmjereni graf u neusmjereni graf.
