Rozdiel Medzi Usmerneným A Neusmerneným Grafom

2024 Autor: Mildred Bawerman | [email protected]. Naposledy zmenené: 2023-12-16 08:42

Directed vs Undirected Graph

Graf je matematická štruktúra, ktorá je tvorená súborom vrcholov a hrán. Graf predstavuje množinu objektov (predstavovanú vrcholmi), ktoré sú spojené cez niektoré odkazy (znázornené hranami). Použitím matematických notácií možno graf znázorniť G, kde G = (V, E) a V je množina vrcholov a E je množina hrán. V neusmernenom grafe nie je žiadny smer spojený s hranami, ktoré spájajú vrcholy. V usmernenom grafe je smer spojený s okrajmi, ktoré spájajú vrcholy.

Neusmernený graf

Ako už bolo spomenuté, neorientovaný graf je graf, v ktorom na okrajoch nie je žiadny smer, ktorý spája vrcholy v grafe. Obrázok 1 zobrazuje neusmernený graf so sadou vrcholov V = {V1, V2, V3}. Množinu hrán vo vyššie uvedenom grafe je možné zapísať ako V = {(V1, V2), (V2, V3), (V1, V3)}. Možno tiež poznamenať, že nič nebráni zápisu množiny hrán ako V = {(V2, V1), (V3, V2), (V3, V1)}, pretože hrany nemajú smer. Preto hrany v neusmernenom grafe nie sú zoradené páry. Toto je hlavná charakteristika neusmerneného grafu. Neusmernené grafy možno použiť na vyjadrenie symetrických vzťahov medzi objektmi, ktoré sú reprezentované vrcholmi. Napríklad obojsmerná cestná sieť, ktorá spája skupinu miest, môže byť znázornená pomocou neusmerneného grafu. Mestá môžu byť reprezentované vrcholmi v grafe a hrany predstavujú dvojsmerné cesty, ktoré mestá spájajú.

Nasmerovaný graf

Smerovaný graf je graf, v ktorom majú hrany v grafe, ktoré spájajú vrcholy, smer. Obrázok 2 zobrazuje smerovaný graf so sadou vrcholov V = {V1, V2, V3}. Množinu hrán vo vyššie uvedenom grafe je možné zapísať ako V = {(V1, V2), (V2, V3), (V1, V3)}. Okraje v neorientovanom grafe sú zoradené páry. Formálne môže byť hrana e v usmernenom grafe predstavovaná usporiadanou dvojicou e = (x, y), kde x je vrchol, ktorý sa nazýva počiatok, zdroj alebo počiatočný bod hrany e, a vrchol y sa nazýva koniec, koncový vrchol alebo koncový bod. Napríklad cestnú sieť, ktorá spája skupinu miest pomocou jednosmerných ciest, je možné znázorniť pomocou neusmerneného grafu. Mestá môžu byť v grafe znázornené vrcholmi a nasmerované hrany predstavujú cesty, ktoré spájajú tieto mestá, a to vzhľadom na smer, ktorým v ceste prúdi premávka.

Aký je rozdiel medzi Directed Graph a Undirected Graph?

V usmernenom grafe je hrana usporiadaná dvojica, kde usporiadaná dvojica predstavuje smer hrany, ktorá spája dva vrcholy. Na druhej strane v neusmernenom grafe je hrana neusporiadaná dvojica, pretože s hranou nie je spojený žiadny smer. Neusmernené grafy možno použiť na vyjadrenie symetrických vzťahov medzi objektmi. In-stupeň a out-stupeň každého uzla v neorientovanom grafe sú rovnaké, ale to neplatí pre smerovaný graf. Keď použijete maticu na reprezentáciu neorientovaného grafu, z matice sa vždy stane symetrický graf, čo však neplatí pre smerované grafy. Neusmernený graf je možné previesť na usmernený graf nahradením každej hrany dvoma nasmerovanými hranami idúcimi v opačnom smere. Nie je však možné previesť usmernený graf na neorientovaný graf.