5Представление графов с помощью матриц

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

Представление графа с помощью квадратной булевской матрицы M размером ,отражающей смежность вершин, называется матрицей смежности, где для неориентированного графа

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

Пример. Для графа G и орграфа D, диаграммы которых представлены на рис. 19, матрицы смежности имеют соответственно вид

граф G орграф D

Рис. 19. Пример неориентированного и ориентированного графов

5.2Матрица инцидентности

Представление графов с помощью матрицы I размером , отражающей инцидентность вершин и ребер, называется матрицей инцидентности, где для неориентированного графа

,

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

Для графа G и орграфа D, диаграммы которых представлены на рис. 19, матрицы инцидентности имеют соответственно вид:

5.3Матрица Кирхгофа

Для неориентированного графа матрица Кирхгофа B размером определяется следующим образом:

В матрице Кирхгофа сумма элементов каждого столбца или строки равна 0.

Если B – матрица Кирхгофа простого неориентированного графа, I₀ – матрица инцидентности любой его ориентации, т.е., графа, полученного из исходного путем замены произвольным образом ребер на дуги, то выполняется следующее соотношение:

B = I₀ I₀^T.

Для графа G на рис. 19 матрица Кирхгофа имеет вид

6Пример выполнения задания практического занятия

Задание: по матрице смежности графа: построить диаграмму графа; выписать его аналитическое представление, матрицу инцидентности I, матрицу Кирхгофа B; проверить соотношение , где I_О – матрица инцидентности его произвольной ориентации; выписать по одному примеру маршрута, цепи, простой цепи, цикла и простого цикла, найти диаметр графа; определить, является ли граф планарным путем построения изоморфных графов.

В качестве примера возьмем следующую матрицу смежности размером

.

Диаграмма графа G, соответствующего выбранной матрице смежности, представлена на рис. 20. Матрица инцидентности размером и матрица Кирхгофа размером этого графа имеют соответственно вид

.

.

На рис. 21 представлена диаграмма одной из ориентацией графа G. Матрица инцидентности размером полученного ориентированного графа имеет вид

.

Рис. 20. Диаграмма графа G по выбранной матрице смежности

Рис. 21. Одна из ориентаций графа G

Далее проверяем соотношение путем перемножения матриц и :

Далее выписываем примеры маршрута, цепи, простой цепи, цикла и простого цикла:

маршрут v₁, v₄, v₇, v₃, v₄, v₁, v₆;

цепь v₁, v₄, v₇, v₃, v₅, v₇, v₆;

простая цепь v₁, v₄, v₇, v₃, v₂;

цикл v₁, v₄, v₇, v₃, v₅, v₇, v₆, v₁;

простая цикл v₁, v₄, v₇, v₆, v₁.

Для нахождения диаметра графа выпишем в таблице 2 кратчайшие цепи и их длины между всеми парами вершин. Для визуального удобства можно пользоваться диаграммой графа, изоморфного графу G, которая представлена на рис. 22. Граф, диаграмма которого представлена на рис. 22, является плоским, следовательно граф G является планарным.

Таблица 2

Кратчайшие цепи и их длины

Кратчайшая цепь	Длина цепи		Кратчайшая цепь	Длина цепи
v1, v4, v3, v2	3		v3, v4	1
v1, v4, v3	2		v3, v5	1
v1, v4	1		v3, v7, v6	2
v1, v4, v3, v5	3		v3, v7	1
v1, v6	1
v1, v6, v7	2		v4, v3, v5	2
			v4, v1, v6	2
v2, v3	1		v4, v7	1
v2, v3, v4	2
v2, v3, v5	2		v5, v7, v6	2
v2, v3, v7, v6	3		v5, v7	1
v2, v3, v7	2
			v6, v7	1

Наибольшая из длин кратчайших цепей равна 3, т.е. диаметр графа G равен 3.

Рис. 22. Граф, изоморфный графу G