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

Задание: по матрице смежности графа: построить диаграмму графа; выписать его аналитическое представление, матрицу инцидентности 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

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

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

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

Варианты заданий практических занятий

№	Матрица смежности	№	Матрица смежности
1.		2.
3.		4.
5.		6.
7.		8.
9.		10.
11.		12.
13.		14.
15.		16.
17.		18.
19.		20.
21.		22.
23.		24.
25.		26.