Rozdiel medzi riadeným a nepriamym grafom

Réžia vs Nepriamy graf

Graf je matematická štruktúra, ktorá sa skladá zo sady vrcholov a hrán. Graf predstavuje skupinu objektov (predstavovaných vrcholmi), ktoré sú spojené pomocou niektorých odkazov (predstavovaných hranami). Pomocou matematických zápisov môže byť graf reprezentovaný G, kde G = (V, E) a V je množina vrcholov a E je množina hrán. V neorientovanom grafe nie je nijaký smer spojený s hranami, ktoré spájajú vrcholy. V orientovanom grafe je smer spojený s okrajmi, ktoré spájajú vrcholy.

Nepriame Graf

Ako už bolo spomenuté, nepriamy graf je graf, v ktorom na hranách, ktoré spájajú vrcholy grafu, neexistuje žiadny smer. Obrázok 1 zobrazuje nepriamy graf so sadou vrcholov V = V1, V2, V3. Množinu hrán vo vyššie uvedenom grafe je možné písať ako V = (V1, V2), (V2, V3), (V1, V3). Možno tiež poznamenať, že nič nebráni zapisovaniu sady hrán ako V = (V2, V1), (V3, V2), (V3, V1), pretože hrany nemajú smer. Hrany v nepriamom grafe preto nie sú usporiadané páry. Toto je hlavná charakteristika nepriameho grafu. Nepriame grafy môžu byť použité na znázornenie symetrických vzťahov medzi objektmi reprezentovanými vrcholmi. Napríklad obojsmerná cestná sieť, ktorá spája skupinu miest, môže byť znázornená pomocou nepriameho grafu. Mestá môžu byť v grafe znázornené vrcholmi a hrany predstavujú obojsmerné cesty spájajúce mestá.

Réžia Graf

Usmernený graf je graf, v ktorom okraje v grafe, ktoré spájajú vrcholy, majú smer. Obrázok 2 zobrazuje orientovaný graf so sadou vrcholov V = V1, V2, V3. Množinu hrán vo vyššie uvedenom grafe je možné písať ako V = (V1, V2), (V2, V3), (V1, V3). Hrany v nepriamom grafe sú zoradené páry. Formálne môže byť hrana e v riadenom grafe reprezentovaná usporiadaným párom e = (x, y), kde x je vrchol, ktorý sa nazýva pôvod, zdroj alebo počiatočný bod okraja e, a vrchol y sa nazýva koncový bod , ukončenie vrcholu alebo koncového bodu. Napríklad môže byť cestná sieť, ktorá spája skupinu miest pomocou jednosmerných ciest, zastúpená pomocou nepriameho grafu. Mestá môžu byť v grafe znázornené vrcholmi a smerované hrany predstavujú cesty, ktoré spájajú mestá vzhľadom na smer, ktorým premávka prechádza po ceste..

Aký je rozdiel medzi riadeným grafom a nepriamym grafom??

V orientovanom grafe je hrana usporiadaná dvojica, kde usporiadaná dvojica predstavuje smer hrany, ktorá spája dva vrcholy. Na druhej strane, v nepriamom grafe je hrana neusporiadaný pár, pretože s hranou nie je spojený žiadny smer. Nepriame grafy môžu byť použité na znázornenie symetrických vzťahov medzi objektmi. Stupeň a stupeň mimo každého uzla v nepriamom grafe je rovnaký, ale to neplatí pre smerovaný graf. Pri použití matice na reprezentovanie nepriameho grafu sa matica vždy stáva symetrickým grafom, ale to neplatí pre smerované grafy. Nepriamy graf možno previesť na smerový graf nahradením každej hrany dvoma smerovanými hranami smerujúcimi v opačnom smere. Nie je však možné previesť nasmerovaný graf na nepriamy graf.