Rozdíl mezi přímým a nepřímým grafem

Přímý vs neřízený graf

Graf je matematická struktura, která se skládá ze sady vrcholů a hran. Graf představuje množinu objektů (představovaných vrcholy), které jsou spojeny prostřednictvím některých odkazů (představovaných hranami). Pomocí matematických zápisů lze graf reprezentovat G, kde G = (V, E) a V je sada vrcholů a E je sada hran. V neorientovaném grafu není spojen s hranami, které spojují vrcholy, žádný směr. V orientovaném grafu je směr spojený s hranami, které spojují vrcholy.

Nepřímý graf

Jak již bylo zmíněno dříve, nepřímý graf je graf, ve kterém v hranách, které spojují vrcholy v grafu, není žádný směr. Obrázek 1 zobrazuje nepřímý graf se sadou vrcholů V = V1, V2, V3. Sada 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 sady hran jako V = (V2, V1), (V3, V2), (V3, V1), protože hrany nemají směr. Hrany v neorientovaném grafu proto nejsou uspořádány páry. Toto je hlavní charakteristika nepřímého grafu. Nesměrované grafy lze použít k reprezentaci symetrických vztahů mezi objekty reprezentovanými vrcholy. Například dvousměrná silniční síť, která spojuje skupinu měst, může být reprezentována pomocí nepřímého grafu. Města mohou být reprezentována vrcholy v grafu a hrany představují obousměrné silnice, které spojují města.

Řízený graf

Směrovaný graf je graf, ve kterém okraje v grafu, které spojují vrcholy, mají směr. Obrázek 2 zobrazuje směrovaný graf se sadou vrcholů V = V1, V2, V3. Sada hran ve výše uvedeném grafu lze zapsat jako V = (V1, V2), (V2, V3), (V1, V3). Hrany v nepřímém grafu jsou uspořádané páry. Formálně může být hrana e v orientovaném grafu reprezentována uspořádaným párem e = (x, y), kde x je vrchol, který se nazývá počátek, zdroj nebo počáteční bod okraje e, a vrchol y se nazývá terminus , ukončení vrcholu nebo koncového bodu. Například lze pomocí nepřímého grafu reprezentovat silniční síť, která spojuje skupinu měst pomocí jednosměrných komunikací. Města mohou být reprezentována vrcholy v grafu a směrované okraje představují silnice, které spojují města s ohledem na směr, kterým doprava proudí po silnici.

Jaký je rozdíl mezi směrovaným grafem a nepřímým grafem??

V orientovaném grafu je hrana uspořádaná dvojice, kde uspořádaná dvojice představuje směr hrany, která spojuje dva vrcholy. Na druhé straně v neorientovaném grafu je hrana neuspořádaný pár, protože s hranou není spojen žádný směr. Nesměrované grafy lze použít k reprezentaci symetrických vztahů mezi objekty. Stupeň a mimo stupeň každého uzlu v nepřímém grafu je stejný, ale pro směrovaný graf to neplatí. Při použití matice k reprezentaci nepřímého grafu se matice vždy stává symetrickým grafem, ale u směrovaných grafů to neplatí. Neřízený graf lze převést na směrový graf nahrazením každé hrany dvěma směrovanými hranami směřujícími v opačném směru. Nelze však převést směrovaný graf na nepřímý graf.