Razlika između usmjerenog i neizmjerenog grafikona

Usmjeren prema neizmjerenom grafikonu

Graf je matematička struktura koja se sastoji od skupa vrhova i rubova. Graf predstavlja skup objekata (predstavljenih vrhovima) koji su povezani nekim vezama (predstavljeni rubovima). Pomoću matematičkih oznaka, graf se može predstaviti s G, gdje je G = (V, E), a V skup vrhova, a E skup rubova. U usmjerenom grafu nema smjera povezanog s rubovima koji spajaju vrhove. U usmjerenom grafu nalazi se smjer povezan s rubovima koji spajaju vrhove.

Neusmjereni graf

Kao što smo ranije spomenuli, usmjereni graf je graf u kojem ne postoji smjer u rubovima koji povezuju vrhove na grafu. Na slici 1 prikazan je usmjerni graf s nizom vrhova V = V1, V2, V3. Skup rubova u gornjem grafu može se zapisati kao V = (V1, V2), (V2, V3), (V1, V3). Također se može primijetiti da ništa ne sprečava pisanje skupa rubova kao V = (V2, V1), (V3, V2), (V3, V1) jer rubovi nemaju smjer. Stoga rubovi u neizravnom grafikonu nisu poredani parovi. To je glavna karakteristika neispravnog grafa. Neizmjereni grafovi mogu se koristiti za prikaz 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 usmjerenog grafikona. Gradovi mogu biti predstavljeni vrhovima na grafu, a rubovi predstavljaju dvosmjerne ceste koje povezuju gradove.

Usmjereni graf

Usmjereni graf je graf u kojem rubovi u grafikonu koji povezuju vrhove imaju smjer. Na slici 2 prikazan je usmjereni graf s nizom vrhova V = V1, V2, V3. Skup rubova u gornjem grafu može se zapisati kao V = (V1, V2), (V2, V3), (V1, V3). Rubovi u neizravnom grafu su poredani parovi. Formalno, rub e u usmjerenom grafu može biti predstavljen uređenim parom e = (x, y) gdje je x vršna točka koja se naziva podrijetlom, izvorom ili početnom točkom ruba e, a vrhova y naziva se krajnik , krajnja vršna ili krajnja točka. Na primjer, cestovna mreža koja povezuje skup gradova koji koriste jednosmjerne ceste može se prikazati pomoću usmjerenog grafikona. Gradovi mogu biti predstavljeni vrhovima na grafu, a usmjereni rubovi predstavljaju ceste koje povezuju gradove s obzirom na smjer koji promet protječe u cestu.

Koja je razlika između usmjerenog grafikona i neusmjerenog grafikona?

U usmjerenom grafu rub je uređeni par, gdje naredjeni par predstavlja smjer ruba koji povezuje dva vrha. S druge strane, u neizravnom je grafu rub neuređen par, jer ne postoji smjer povezan s rubom. Neizmjereni grafovi mogu se koristiti za prikaz simetričnih odnosa između objekata. Stupanj i stupanj svakog čvora u neizravnom grafu su jednaki, ali to nije točno za usmjereni graf. Kada koristite matricu za predstavljanje usmjerenog grafa, matrica uvijek postaje simetrični graf, ali to ne vrijedi za usmjereni graf. Neusmjerni graf može se pretvoriti u usmjereni graf zamijenivši svaki rub s dva usmjerena ruba koja idu u suprotnom smjeru. Međutim, nije moguće pretvoriti usmjereni graf u neusmjerni graf.