Матрицы графов

Матрицы графов

Для представления графов в памяти ЭВМ используют матрицы.

Матрица инцидентности. Рассмотрим граф Г без петель, определенный на n вершинах и m ребрах. Матрица инцидентности А=[a_ij] графа Г имеет n строк (по одной на каждую вершину) и m столбцов (по одному на каждую дугу).

Элемент матрицы А определяется следующим образом:

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

Пример 3. Для заданного графа построить матрицу
инцидентности.

Определение. Число ребер, инцидентных вершине х Х графа Г(Х,Е), называется локальной степенью вершины х и обозначается d(x).

Матрица смежности. Пусть Г(Х,Е) – ориентированный граф, не имеющий параллельных дуг, определенный на n вершинах. Матрицей смежности М=[mij] графа Г называется матрица порядка n×n, элементы которой определяются следующим образом:

Пример 4. Для заданного графа построить матрицу смежности:

Решение:

Если граф Г(Х,Е) содержит параллельные
ориентированные ребра, то элемент mij матрицы смежности М
такого графа равен сумме чисел ориентированных ребер, идущих
из в (или чисел неориентированных ребер, соединяющих эти
вершины).

⇐ Предыдущая 12