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

2024 Автор: Mildred Bawerman | [email protected]. Последно модифициран: 2023-12-16 08:37

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

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

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

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