Матричные представления графов

Информация о структуре графа может быть задана матрицей смежности. Матрицей смежности графа G=(X,V), | X|=n называется квадратная матрица , элементы которой определяются следующим образом:

Замечание. Матрица смежности неориентированного графа симметрична. В случае кратных ребер a_ij есть количество ребер, соединяющих вершины x_i и x_j. Для орграфа а_ij определяется как количество дуг, направленных от вершины x_i к вершине x_j.

Теорема 4.3.1. Графы изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одновременными перестановками строк и столбцов (т.е. одновременно с перестановкой i -й и j -й строк переставляются i -й и j -й столбцы).

Согласно этой теореме по матрице смежности граф восстанавливается однозначно с точностью до изоморфизма.

Матрицей инцидентности графа G=(X,V), |Х|=п,|V|=m называется матрица , элементы которой определяются следующим образом:

если G – ориентированный граф, то

если G - неориентированный граф, то

Замечание. Для ориентированного графа петлю, т. е. дугу вида (х_i, х_i) удобно представлять иным значением в строке х_i, например, 2.

Пример. Матричные представления графов проиллюстрированы на рис. 4.13, 4.14.

			(1,2)	(1,3)	(3,2)	(3,4)	(5,4)	(5,6)	(6,5)
			-1		-1
В =				-1
						-1	-1
									-1
								-1

			(1,2)	(1,3)	(1,5)	(2,3)	(2,5)	(3,4)	(4,5)	(4,6)	(5,6)
В =

Рис. 4.13.

а) ориентированный граф и его матрица инцидентности,

б) неориентированный граф и его матрица инцидентности

Рис. 4.14. Матрицы смежности для графов на рис. 4.13

Дата добавления: 2014-12-27