Směrovaný vs. Neorientovaný graf
Graf je matematická struktura, která se skládá z množiny vrcholů a hran. Graf představuje množinu objektů (reprezentovaných vrcholy), které jsou propojeny prostřednictvím nějakých vazeb (reprezentovaných hranami). Pomocí matematických zápisů lze graf znázornit pomocí G, kde G=(V, E) a V je množina vrcholů a E je množina hran. V neorientovaném grafu není žádný směr spojený s hranami, které spojují vrcholy. V orientovaném grafu je směr spojený s hranami, které spojují vrcholy.
Neorientovaný graf
Jak již bylo zmíněno dříve, neorientovaný graf je graf, ve kterém není žádný směr na hranách, které spojují vrcholy v grafu. Obrázek 1 znázorňuje neorientovaný graf se sadou vrcholů V={V1, V2, V3}. Množinu hran ve výše uvedeném grafu lze zapsat jako V={(V1, V2), (V2, V3), (V1, V3)}. Lze také poznamenat, že nic nebrání zápisu množiny hran jako V={(V2, V1), (V3, V2), (V3, V1)}, protože hrany nemají směr. Hrany v neorientovaném grafu proto nejsou uspořádané dvojice. To je hlavní charakteristika neorientovaného grafu. Neorientované grafy lze použít k reprezentaci symetrických vztahů mezi objekty, které jsou reprezentovány vrcholy. Například obousměrnou silniční síť, která spojuje sadu měst, lze znázornit pomocí neorientovaného grafu. Města mohou být znázorněna vrcholy v grafu a okraje představují obousměrné silnice, které spojují města.
Směrovaný graf
Směrovaný graf je graf, ve kterém hrany v grafu, které spojují vrcholy, mají směr. Obrázek 2 znázorňuje orientovaný graf se sadou vrcholů V={V1, V2, V3}. Množinu hran ve výše uvedeném grafu lze zapsat jako V={(V1, V2), (V2, V3), (V1, V3)}. Hrany v neorientovaném grafu jsou uspořádané dvojice. Formálně lze hranu e v orientovaném grafu reprezentovat uspořádanou dvojicí e=(x, y), kde x je vrchol, který se nazývá počátek, zdroj nebo počáteční bod hrany e, a vrchol y se nazývá konec., ukončující vrchol nebo koncový bod. Například silniční síť, která spojuje sadu měst pomocí jednosměrných silnic, lze znázornit pomocí neorientovaného grafu. Města mohou být v grafu znázorněna vrcholy a orientované hrany představují silnice, které spojují města s ohledem na směr, kterým provoz na silnici proudí.
Jaký je rozdíl mezi Directed Graph a Undirected Graph?
V orientovaném grafu je hrana uspořádaná dvojice, kde uspořádaná dvojice představuje směr hrany, která spojuje dva vrcholy. Na druhou stranu v neorientovaném grafu je hrana neuspořádaná dvojice, protože s hranou není spojen žádný směr. Neorientované grafy lze použít k reprezentaci symetrických vztahů mezi objekty. In-stupeň a out-stupeň každého uzlu v neorientovaném grafu jsou stejné, ale to neplatí pro orientovaný graf. Při použití matice k reprezentaci neorientovaného grafu se matice vždy stane symetrickým grafem, ale to neplatí pro orientované grafy. Neorientovaný graf lze převést na orientovaný graf nahrazením každé hrany dvěma orientovanými hranami jdoucími opačným směrem. Není však možné převést orientovaný graf na neorientovaný graf.
