Для неориентированного графа

1 2 3 4 5 6 7

V1, v2}, {v1, v3}, {v2, v3}, {v2, v4}, {v3, v4}, {v5, v6}, {v6, v4}.

1 2 3 4 5 6 7 8 9

Тогда матрица инцидентности графа G:

Для неориентированного графа элементы матрицы инцидентности задаются следующим образом

Пример 2.4. Рассмотрим граф, ассоциированный с орграфом предыдущего примера

v₂ v₅

G’:

v₁ v₃ v₄ v₆

и занумеруем его ребра, например, следующим образом

Тогда матрица инцидентности графа G’ следующая

Несмотря на то, что представление графов в виде матриц инцидентности играет весьма большую роль в теоретических исследованиях, практически этот способ весьма неэффективен. Столбцы матрицы содержат не более двух ненулевых элементов, что делает этот метод неэкономным при большом количестве вершин. Кроме того, решение практических задач с помощью матрицы инцидентности весьма трудоемко.

4. Граф (орграф) G = (V,U) может быть задан матрицей смежности. Это квадратная матрица размерности n x n, где n = | V |. Элементы матрицы смежности определяются следующим образом.

Из определения элементов матрицы сразу следует, что матрица смежности неориентированного графа симметричеcкая.

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