Для орграфа

Заметим, что в к – той строке матрицы смежности орграфа количество единиц равно полустепени исхода deg ⁺(v_к) вершины v_к, а количество единиц в к – том столбце матрицы смежности орграфа равно полустепени захода deg ^-(v_к) вершины v_к.

Пример 2.5. Для неориентированного графа примера 2.4 матрица смежности имеет вид

Пример 2.6. Для ориентированного графа примера 2.2 матрица смежности следующая

Как видим, матрица смежности орграфа в этом случае симметрической не является.

Матрица смежности графов применяется во многих случаях при выяснении характеристик графа, при решении конкретных оптимизационных задач для графов с помощью ЭВМ. Существуют и другие, кроме рассмотренных выше, методы представления графов (списками смежности, массивами лидеров и др.).

Дата добавления: 2014-12-16