5.2.3. Матрица достижимости графа

Матица достижимости неориентированного графа.

Утверждение. ЕслиА– матрица смежности графа, то элементматрицыА^правен числу маршрутов длинып, соединяющих вершиныv_i иv_jграфаG.

Доказательство.Методом математической индукции по числуп.

База индукции.Прип= 1 утверждение верно, так как всякое ребро графаG– это маршрут длины 1.

Индуктивное предположение.Пусть утверждение справедливо для всехnk.

Индуктивный переход.Рассмотрим матрицуА^k+1. В ней.

В силу индуктивного предположения произведение есть число маршрутов длиныk+ 1, соединяющих вершинуv_i с вершинойv_jс предпоследней вершиной всех таких маршрутовv_m. Значит, суммадействительно равна числу маршрутов длинk+ 1, соединяющих вершинуv_i с вершинойv_j.

Следствие.Пусть– связный граф срвершинами. Тогда любые две вершины графаможно соединить простой цепью. Но в простой цепи не может быть более (р1) ребер. Следовательно, все элементы матрицыотличны от нуля. Ясно, что верно и обратное утверждение.

В некоторых случаях при вычислениях степеней матрицы Аи матрицыСважно знать не число соответствующих маршрутов, а только есть ли в графе эти маршруты или нет. Тогда при вычислении элементов матрицА²,А³, … ,А^р-1вместо обычного сложения используют операцию, введенную нами при рассмотрении матриц конечных бинарных отношений. В результате матрицыА,А²,А³, …,A^p-1,Cсостоят только из нулей и единиц.

Полученная таким образом матрица Сназываетсяматрицей достижимостиграфаG. ГрафGсвязен тогда и только тогда, когда каждый элемент матрицы достижимости равен 1 (р3).

Матрица достижимости ориентированного графа.

Случай орграфа ничем не отличается от случая неориентированного графа. Если G– орграф ср вершинами иА– его матрица смежности, то элементматрицыА^правен числу ориентированных маршрутов длинып, соединяющих вершинуv_i с вершинойv_j.

Граф G сильно связен тогда и только тогда, когда каждый элемент его матрицы достижимостиравен 1.

3.2.4.Матрица инцидентности графа

Матрица инцидентности неориентированного графа.

Пусть – неориентированный граф срвершинами иqребрами. Произвольно переномеруем его вершины и ребра.

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

Пример графа и его матрицы инцидентности приведен на рис. 11

j i	1	2	3	4	5	6	7	8	9
1	1	0	0	0	0	0	0	0	0
2	1	1	0	0	0	0	0	1	0
3	0	1	1	1	0	1	0	0	0
4	0	0	0	1	1	0	1	0	0
5	0	0	0	0	0	1	1	1	1
6	0	0	1	0	1	0	0	0	1

Рис. 11

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

• Число единиц в i-й строке равно степениi-ой вершины,i= 1, 2, … ,р.

• Число единиц в -м столбце равно двум, так как любое ребро инцидентно двум вершинам, = 1, 2, …,р.

• Число единиц в матрице равно удвоенному числу ребер графа.

Матрица инцидентности ориентированного графа.

Если в орграфе G р вершин иqдуг, то элементыего матрицы инцидентности определяются правилом

i = 1, …,p; j= 1, … ,q.

Пример орграфа и его матрицы инцидентности показан на рис. 12.

	12	13	14	23	25	32	34	35	46	56	64	65
1	-1	-1	-1	0	0	0	0	0	0	0	0	0
2	1	0	0	-1	-1	1	0	0	0	0	0	0
3	0	1	0	1	0	-1	-1	-1	0	0	0	0
4	0	0	1	0	0	0	1	0	-1	0	1	0
5	0	0	0	0	1	0	0	1	0	-1	0	1
6	0	0	0	0	0	0	0	0	1	1	-1	-1

Рис. 12

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

• Число единиц в i-й строке равно степени входаi-ой вершины,i= 1, 2, … ,р.

• Число единиц с минусом в i-ой строке равно степени выходаi-ой вершины,i= 1, 2, … ,р.

• Число единиц в матрице равно числу единиц с минусом и равно числу дуг в графе.

• В каждом столбце матрицы есть ровно одна единица и ровно одна единица с минусом, так как всякая дуга из одной вершины выходит и в одну вершину входит.