Решение. Строим матрицу смежности , строки и столбцы которой обозначаем вершинами графа

Строим матрицу смежности , строки и столбцы которой обозначаем вершинами графа. Для неориентированного графа она симметричная. Элемент матрицы смежности равен 1, если вершины и смежны, и 0 в противном случае. Так как граф простой (не имеет петель и кратных ребер), на главной диагонали расположены 0, а все элементы матрицы имеют значения 0 или 1. Сумма чисел по строке (и по столбцу) равна степени вершины.

Таблица 1 – Матрица смежности неориентированного графа

Матрица инциденций строится следующим образом: строки ее соответствуют вершинам, столбцы – ребрам графа . Элемент равен 1, если вершина инцидентна ребру, и 0 – в противном случае.

Таблица 2 – Матрица инциденций неориентированного графа

	a	b	c	d	e	f	g

В каждом столбце должны находиться только 2 единицы. Сумма чисел по строке равна степени вершины.

Задание 3. Построить матрицы смежности и инциденций для ориентированного графа на рис. 5.

Рисунок 5 – Граф

Дата добавления: 2014-11-20