Разлика между насочена и ненасочена графика

Насочена срещу Ненасочена графика

Графиката е математическа структура, която се състои от набор от върхове и ръбове. Графиката представлява набор от обекти (представени с върхове), които са свързани чрез някои връзки (представени с ръбове). Използвайки математически обозначения, графика може да бъде представена от 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 се нарича край , завършваща върхова или крайна точка. Например, пътна мрежа, която свързва набор от градове, използващи еднопосочни пътища, може да бъде представена с помощта на насочена графика. Градовете могат да бъдат представени чрез върховете в графиката, а насочените ръбове представляват пътищата, които свързват градовете, като се има предвид посоката, по която движението протича по пътя.

Каква е разликата между насочена графика и ненасочена графика?

В насочена графика ръбът е подредена двойка, където подредената двойка представлява посоката на ръба, която свързва двата върха. От друга страна, в една насочена графика, ръбът е неподредена двойка, тъй като няма посока, свързана с ръба. Ненасочените графики могат да се използват за представяне на симетрични отношения между обекти. Степента и степента на всеки възел в неориентирана графика са равни, но това не е вярно за насочен граф. Когато използвате матрица, за да представите неориентирана графика, матрицата винаги се превръща в симетрична графика, но това не е вярно за насочени графики. Ненасочена графика може да бъде преобразувана в насочена графика, като се замени всеки ръб с два насочени ръба, които вървят в обратна посока. Въпреки това, не е възможно да се преобразува насочен граф в неориентирана графика.