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

Кроме рассмотренных в разделах 1 и 2 теоретико-множественной и геометрической форм определения (задания) графов, часто используется матричная форма их представления. Существуют различные виды матриц графов, однако все они, как правило, полностью передают основные свойства графов. Матричная форма задания графов обладает достаточной наглядностью при любой степени сложности графа и, что самое важное, позволяет автоматизировать процесс обработки информации, представленной в терминах теории графов, – любая матрица графа может быть введена в ЭВМ.

При задании графов в матричной форме могут учитываться либо отношения смежностей (вершин или ребер (дуг)), либо отображения инцидентности (вершин и ребер (дуг)). В связи с этим матрицы графов делятся на два основных класса: матрицы смежностей и матрицы инциденций.

Определение 3.1. Матрицей смежности вершин неориентированного графаGназывается квадратная матрицаA(G)=a_ijпорядкаp=p(G) (p– количество вершин графа), элементыa_ijкоторой равны числу ребер, соединяющих вершиныx_iиx_j.

			x1	x2	x3	x4	x5	x6	x7	x8
		x1	2	0	0	0	1	0	1	0
		x2	0	0	1	0	0	1	1	0
		x3	0	1	0	1	0	1	0	0
A(G)	=	x4	0	0	1	0	1	0	0	0
		x5	1	0	0	1	0	0	0	1
		x6	0	1	1	0	0	0	0	0
		x7	1	1	0	0	0	0	0	0
		x8	0	0	0	0	1	0	0	0

На рис. 3.1 приведен неориентированный граф G(X,E) и справа – соответствующая ему матрица смежностей вершинA(G).

Из определения 3.1 непосредственно вытекают основные свойства матриц этого вида.

1. Матрица смежностей вершин неориентированного графа A(G) является квадратной и симметричной относительно главной диагонали.

2. Элементами матрицы A(G) являются целые положительные числа и число ноль.

3. Сумма элементов матрицы A(G) поi-й строке (или поi-му столбцу) равна степени соответствующей вершины(x_i).

Из определения матрицы смежностей вершин неориентированного графа и ее основных свойств следуют некоторые особенности соответствия между графом G(X,E) и его матрицейA(G). На рис. 3.1 указана некоторая нумерация вершин графа; расположенная рядом матрица соответствует именно этой нумерации. Если же в графеG(X,E), приведенном на этом рисунке, использовать другую нумерацию вершин (например, сдвинув ее относительно вершин по часовой стрелке), то это приведет к тому, что в матрицеA(G) произойдет перестановка отдельных строк и столбцов. Поэтому говорят, что каждый неориентированный граф имеет единственную с точностью до перестановки строк и столбцов матрицу смежностей вершин. И наоборот, каждая квадратная симметричная относительно главной диагонали матрица, элементами которой являются целые положительные числа и число ноль, определяет единственный с точностью до изоморфизма неориентированный граф, матрицей смежностей вершин которого является данная матрица.

Рекомендуется самостоятельно построить матрицу смежностей вершин графа G(X,E), показанного на рис. 3.1, с использованием другой нумерации вершин и сравнить полученную при этом матрицу с матрицей смежностей вершин приведенного графа.

Определение 3.2.Матрицей смежности вершин ориентированного графаGназывается квадратная матрицаA(G)=a_ijпорядкаn(n– число вершин графа), элементы которойa_ijравны числу дуг, исходящих из вершиныx_iи заходящих в вершинуx_j.

			x1	x2	x3	x4	x5	x6	x7	x8
		x1	0	0	0	0	0	0	0	0
		x2	0	0	0	0	0	1	0	0
		x3	0	1	0	0	1	0	1	0
A(G)	=	x4	1	0	0	0	0	0	0	0
		x5	0	0	0	0	1	1	0	0
		x6	0	0	0	0	0	0	0	1
		x7	0	0	0	0	0	1	0	0
		x8	1	0	0	0	1	0	0	0

На рис. 3.2 показан ориентированный граф G(X,E) и справа – матрица смежностей его вершин. Из определения следует, что сумма элементовi-й строки матрицыA(G) орграфа равна полустепени исхода⁺(x_i), а поi-му столбцу – полустепени захода^-(x_i). По-прежнему элементы этой матрицы – целые положительные числа и число ноль. Матрица смежностей вершин орграфа может оказаться симметричной относительно главной диагонали лишь в редких частных случаях.

Как и в случае неориентированных графов, каждый орграф имеет единственную с точностью до перестановки строк и столбцов матрицу смежностей вершин. И наоборот, каждая квадратная матрица, элементы которой – целые положительные числа и число ноль, определяет единственный с точностью до изоморфизма ориентированный граф.

Определение 3.3.Матрицей инцидентности неориентированного графаGназывается матрицаB(G)=b_ijразмером (p x q) (pиq– количество вершин и ребер графа), элементыb_ijкоторой равны единице, если вершинаx_iинцидентна ребруe_jи нулю, если соответствующие вершины и ребра не инцидентны.

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

1. Сумма элементов матрицы на i-й строке равна(x_i).

2. Сумма элементов матрицы по i-му столбцы равна 2.

Матрица инцидентности графа, изображенного на рис. 3.1, а имеет вид:

			e1	E2	e3	e4	e5	e6	e7	e8	e9	e10
		x1	1	1	2	0	0	0	0	0	0	0
		x2	0	0	0	1	1	1	0	0	0	0
		x3	0	0	0	0	0	1	1	1	0	0
B(G)	=	x4	0	0	0	0	0	0	0	1	1	0
		x5	1	0	0	0	0	0	0	0	1	1
		x6	0	0	0	0	1	0	1	0	0	0
		x7	0	1	0	1	0	0	0	0	0	0
		x8	0	0	0	0	0	0	0	0	0	1

Следует отметить, что петле e_j=(x_i,x_i) в матрицах этого вида соответствуетj-й столбец, состоящий из нулей и одной единицы, расположенной наi-м месте. Ребруe_k=x_m,x_nсоответствует в матрице инциденцийk-й столбец, состоящий из нулей и двух единиц, расположенных наm-м иn-м местах. Нулевая строка матрицы соответствует изолированной вершине, а нулевой столбец – петле. Следует иметь ввиду, что нулевой столбец матрицы инцидентности лишь указывает на наличие петли, но не содержит информации о том, с какой именно вершиной связана эта петля.

Необходимо отметить, что между строками матрицы инцидентности B(G) существует очевидная зависимость. Так как каждый столбец этой матрицы содержит только два единичных элемента или состоит только из нулей, если столбец соответствует петле, то сумма по модулю 2 всех строк равна нулю. Поэтому без потери информации о графе вместо матрицыB(G) можно рассматривать сокращенную матрицуB_o(G), получаемую изB(G) вычеркиванием любой строки (чаще всего вычеркивается последняя строка). Таким образом, изpстрок матрицыB(G) связного графа (см. п. 5) одна строка всегда линейно зависима, т.е. ранг матрицыB(G) не может превышатьp-1 (ранг матрицыB(G) в точности равенp-1).

Любое подмножество столбцов матрицы B(G) можно рассматривать как матрицу инцидентностиB´(G) некоторого суграфаG´(X,E´), содержащего все вершины исходного графа и соответствующее выделенным столбцам подмножествоE´CEего ребер. Все столбцы матрицыB´(G) линейно независимы тогда и только тогда, когда суграфG´(X,E´) не содержит циклов. Действительно, если совокупность ребер образует цикл, то каждая вершина инцидента четному числу ребер этого цикла. Следовательно, сумма по модулю 2 соответствующих столбцов дает нулевой столбец, что означает из зависимость. Если же суграф не содержит циклов, то он имеет по меньшей мере две (вообще, четное число) концевых вершин, каждая из которых инцидентна только одному ребру, являющемуся концевым. Поэтому сумма по модулю 2 соответствующих столбцов будет содержать два (или четное число) единичных элемента и, следовательно, совокупность этих столбцов независима.

В связном графе с pвершинами всегда можно выделитьp-1 ребер так, чтобы они образовали суграф без циклов, представляющий собой дерево графа, являющееся каркасом (см. п. 7). Поэтому матрица инцидентности содержит не менееp-1 независимых столбцов. В то же время любой суграф, имеющий болееp-1 ребер, обязательно содержит цикл, т.е. в матрице инциденций не может быть большеp-1 независимых столбцов. Отсюда следует, что матрица инцидентности связного графа содержит в точностиp-1 независимых столбцов, и поэтому ее ранг равенp-1. Число=p-1 и определяет ранг графа.

Определение 3.4.Матрицей инцидентности орграфа G сpвершинами иq ребрами называется матрицаB(G) = [b_ij]размером (p  q), элементы которой определяются следующим образом:

1, если вершина x_i является началом дуги e_j

b_ij =-1, если вершинаx_i является концом дуги e_j;

• 0, если вершина x_i не инцидентна дугу e_{j .}

Ниже приведена матрица инцидентности графа, изображенного на рис. 3.2:

				e1	e2	e3	e4	e5	e6	e7	e8	e9	e10	e11
			x1	0	0	0	0	-1	0	0	0	0	0	-1
			x2	1	-1	0	0	0	0	0	0	0	0	0
			x3	0	1	1	1	0	0	0	0	0	0	0
B(G)		=	x4	0	0	0	0	1	0	0	0	0	0	0
			x5	0	0	0	-1	0	1	1	0	0	-1	0
			x6	-1	0	0	0	0	0	-1	1	-1	0	0
			x7	0	0	-1	0	0	0	0	0	1	0	0
			x8	0	0	0	0	0	0	0	-1	0	1	1

Матрица инцидентности орграфа Gобладает следующими свойствами.

1. Сумма строк матрицы B(G)является нулевой строкой.

2. Любая строка матрицы B(G)является линейной комбинацией остальных строк.

3. Ранг матрицы B(G)равенp-1.

Определение 3.5.Матрицей смежности ребер неориентированного графаGназывается квадратная матрицаA^*(G) = [a^*_ij]порядкаq, элементыa^*_ij которой равны единице, если ребраe_iиe_jсмежны, и нулю – в противном случае.

Для графа, изображенного на рис. 3.1, матрица смежности ребер имеет вид

			e1	e2	e3	e4	e5	e6	e7	e8	e9	e10
		e1	0	1	1	0	0	0	0	0	1	1
		e2	1	0	1	1	0	0	0	0	0	0
		e3	1	1	2	0	0	0	0	0	0	0
		e4	0	1	0	0	1	1	0	0	0	0
		e5	0	0	0	1	0	1	1	0	0	0
A*(G)	=	e6	0	0	0	1	1	0	1	1	0	0
		e7	0	0	0	0	1	1	0	1	0	0
		e8	0	0	0	0	0	1	1	0	1	0
		e9	1	0	0	0	0	0	0	1	0	1
		e10	1	0	0	0	0	0	0	0	1	0

Очевидно, что матрица A^*(G)смежности ребер неориентированного графа обладает теми же свойствами, что и матрицаA(G)смежности вершин графаG. Таким образом, можно найти графG^*, матрица смежности вершин которого равна матрицеA^*(G)смежности ребер графаG.

G(X,E)  A^*(G)  A(G^*)  G^*.

Такой граф называется реберным, или сопряженным графом G. На рис. 3.3 приведен реберный граф (для неориентированного графа, показанного на рис. 3.1).

Матрицы смежности вершин и смежности ребер неориентированного графа могут быть получены из матрицы инцидентности следующим образом.

Обозначим через B^T(G) матрицу, полученную транспонированием матрицы инцидентностиB(G). Квадратная матрицаA = B(G)B^T(G)порядкаp будет равна матрице смежности вершин графа, а квадратная матрицаА^* = B^T(G)B(G)порядкаq– матрице смежности ребер.

По матрице смежности ребер графа (орграфа) всегда можно определить ребра графа (дуги орграфа) как пары инцидентных им вершин, а для графов с параллельными ребрами (дугами), кроме того, и кратности ребер (дуг).

Однако если ребра (дуги) были пронумерованы, то восстановить их номера по матрице смежности невозможно. В этом смысле матрица инцидентности оказывается более информативной, чем матрица смежности, поскольку позволяет получить полную информацию о ребрах (дугах), включая их нумерацию.

Рассмотренные в этом параграфе матрицы графов играют большую роль в теории графов. Существуют и другие матрицы графов, однако их роль менее значительна.