Різниця між спрямованим та непрямим графіком

Спрямований проти Ненаправлений графік

Графік - це математична структура, яка складається з безлічі вершин і ребер. Графік являє собою сукупність об'єктів (представлених вершинами), які з'єднані через деякі посилання (представлені ребрами). Використовуючи математичні позначення, графік можна представити G, де G = (V, E), а V - сукупність вершин, а E - множина ребер. У непрямому графіку немає напрямку, пов'язаного з ребрами, що з'єднують вершини. У спрямованому графіку є напрямок, пов'язаний з ребрами, що з'єднують вершини.

Ненаправлений графік

Як було сказано раніше, непрямий графік - це графік, в якому немає ребра в ребрах, що пов'язують вершини в графі. На малюнку 1 зображено непрямий графік із набором вершин V = V1, V2, V3. Набір ребер у наведеному графіку можна записати у вигляді V = (V1, V2), (V2, V3), (V1, V3). Можна також зазначити, що нічого не заважає записати набір ребер як V = (V2, V1), (V3, V2), (V3, V1), оскільки ребра не мають напрямку. Тому ребра в непрямому графіку не є упорядкованими парами. Це основна характеристика ненаправленого графа. Ненаправлені графіки можна використовувати для зображення симетричних зв’язків між об'єктами, які представлені вершинами. Наприклад, двостороння дорожня мережа, яка з'єднує набір міст, може бути представлена ​​за допомогою непрямого графа. Міста можуть бути представлені вершинами на графіку, а краї представляють двосторонні дороги, що з'єднують міста.

Направлений графік

Спрямований графік - це графік, у якому ребра у графі, які пов'язують вершини, мають напрямок. На малюнку 2 зображено спрямований графік із набором вершин V = V1, V2, V3. Набір ребер у наведеному графіку можна записати у вигляді V = (V1, V2), (V2, V3), (V1, V3). Краї в непрямому графіку впорядковані парами. Формально ребро e у спрямованому графі може бути представлений упорядкованою парою e = (x, y), де x - вершина, яка називається початком, джерелом або початковою точкою краю e, а вершина y називається кінцем , кінцева вершина або кінцева точка. Наприклад, дорожню мережу, яка з'єднує набір міст за допомогою односторонніх доріг, можна представити за допомогою непрямого графа. Міста можуть бути представлені вершинами на графіку, а спрямовані краї представляють дороги, що з'єднують міста, враховуючи напрямок руху потоку в дорозі.

Яка різниця між спрямованим графіком і непрямим графіком?

У спрямованому графі ребром є впорядкована пара, де впорядкована пара представляє напрямок краю, що пов'язує дві вершини. З іншого боку, у непрямому графіку край - це не упорядкована пара, оскільки немає напрямку, пов'язаного з ребром. Ненаправлені графіки можна використовувати для зображення симетричних зв’язків між об'єктами. Ступінь і ступінь кожного вузла в непрямому графіку рівні, але це не вірно для спрямованого графа. Використовуючи матрицю для подання ненаправленого графіка, матриця завжди стає симетричним графіком, але це не вірно для спрямованих графіків. Непрямий графік можна перетворити на спрямований графік, замінивши кожне ребро на два спрямовані ребра, що йдуть у зворотному напрямку. Однак конвертувати спрямований графік у непрямий графік неможливо.