Способы представления графов, Матрица смежности графа - Формирование списка окрестностей вершин ориентированного графа по заданной матрице инцидентности

Большинство задач на графах касается определения компонент связности, поиска маршрутов, нахождения расстояний и т. п. При их численном решении на ЭВМ граф должен быть представлен неким дискретным способом. Одно из направлений теории графов связано с их представлением с помощью алгебраических форм - матриц. Такое представление графов удобно для решения многих практических задач. Ниже рассматриваются некоторые такие представления.

Матрица смежности графа

Матрицей смежности ориентированного графа с n вершинами называется матрица A=[aij], i, j=1,...,n, в которой aij=1, если существует ребро (xi, xj) и aij=0, если вершины xi, xj не связаны с ребром (xi, xj). Матрица смежности однозначно определяет структуру графа. Ребро типа петли в матрице смежности представляется соответствующим единичным диагональным элементом. Недостатком представления графа с помощью матрицы смежности является отсутствие возможности представления кратных ребер.

Рис. 4

На рисунке приведен пример ориентированного графа и его матрицы смежности.

Матрицу смежности удобно использовать и для представления т. н. ВЗВЕШЕННЫХ графов. Граф называется взвешенным, если каждому его ребру сопоставлено число. Простой взвешенный граф может быть представлен своей матрицей весов W=[wij] - вес соединяющего вершины i, j. Веса несуществующих ребер полагают равными 0 или. Матрица весов, таким образом, будет являться простым обобщением матрицы смежности.

Похожие статьи




Способы представления графов, Матрица смежности графа - Формирование списка окрестностей вершин ориентированного графа по заданной матрице инцидентности

Предыдущая | Следующая