17. Способы задания графов (матрица смежности и инцидентности)

Существуют различные способы задания графов. Пусть u₁… u_n — вершины графа, а e₁… e_m — его ребра.

1.      Матрица смежности. Это матрица, размерностью nxm, такая что, A_ij — равен числу ребер или дуг, соединяющую i — тую и j- тую вершины, и равна 0 если вершины несмежны.

2.      Матрица инцидентности. B_ij =1, если u_i инцидентна ребру e_j , и = 0 если вершина и ребро неинцидентны.

3.      Перечислением упорядоченных или неупорядоченных пар смежных вершин.

4.      Заданием множества вершин графа, и способа отображения множества Х в множество Х.

Решим задачу по ходу давая необходимые определения.

Задача 4. Построить в ПДСК неориентированный граф. Вершины: v₁(0;4); v₂(4;4); v₃(4;0);. V₄(0;0). Ребра: (v_1; v₂); (v_2; v₃); (v_3; v₄); (v_1; v₄); (v_1; v₃); (v_2; v₄); (v_1; v₂).Указать основные характеристики данного графа. Найти: 1) таблицу степеней вершин: 2) матрицу соседства; 3) матрицу инцидентности; 4) таблицу расстояний, радиус и центр графа.

Решение:

В условии задачи сказано, что данный граф — неориентированный (что будет учтено в ниже следующих определениях). Более подробно о неориентированных графах можно узнать, например, в источнике [2]. Опр. Неориентированный граф G — это: 1) конечное множество вершин V; 2) конечное множество ребер Е; 3) функция f: E VV, т. е. e_ij{v_i ,v_j }.

Отметим следующие важные характеристики данного графа — он не является ни простым, ни полным, ни правильным. Опр. Простым графом называется граф, который не имеет петель (т.е. не содержит ребер. соединяющих вершину саму с собой) или множественных ребер (т.е. ребер, соединяющих одну и ту же пару вершин более одного раза). Опр. Полным графом называется граф, у которого каждая пара различных вершин связана ровно одним ребром. Опр. Граф, у которого каждая вершина имеет одинаковую степень, называется правильным. Опр. Степенью (валентностью) P(v_i) вершины v_i неориентированного графа G называется число ребер, исходящих из данной вершины. Теперь переходим к выполнению всех указанных пунктов в задании.

1) Построим таблицу степеней вершин данного графа.

vi	v1	v2	v3	v4
P(vi)	3	4	3	4

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

2) Составим матрицу соседства данного графа. Для этого введем некоторые понятия.

Опр. Матрицей соседства (смежности) А(G) неориентированного графа G называется матрица размера nn, где n — число вершин данного графа, причем ее элементы a_ij представляют собой число различных ребер, соединяющих вершины vi и vj , равно числу ребер, соединяющих вершины vi и vj.

Отметим, что если существует ребро, соединяющее две вершины, то эта пара вершин называется соседними (смежными).

Матрица соседства неориентированного графа всегда симметрична, т.к. число ребер, соединяющих вершины vi и vj, равно числу ребер, соединяющих вершины vj и vi. По матрице соседства можно определить ряд свойств графа: 1 ) если в графе есть изолированная вершина vi, то i-тая строка и i-ый столбец ц будут состоять из 0; 2) если граф имеет петлю, то на главной диагонали соответствующий элемент будет отличен от 0.

Замечание 3. Как уже было сказано, на основании матрицы соседства можно посчитать степень вершин графа, а именно: -если у графа нет петель при вершине vi, то ее степень равна сумме всех элементов i-той строки или же i-того столбца - если в графе присутствуют петли, то при подсчете валентности каждая петля учитывается дважды ( например, если петля при вершине vi , то ее степень также вычисляют суммированием всех элементов i-той строки (i-того столбца), но при этом элемент а_ii, стоящий на главной диагонали нужно увеличить в 2 раза)

Таким образом, матрица соседства нашего графа имеет вид:

А(G)=

3) Запишем матрицу инцидентности данного графа.

Опр. Матрицей инцидентности B(G) неориентированного графа G называется матрица размера nm, где n — число вершин данного графа, m - число ребер, где b_ij определяются следующим образом: - b_ij=1, если вершина v_i принадлежит ребру e_j - b_ij=0, если вершина v_i не принадлежит ребру e_j, или если e_j — петля.

Итак, матрица инцидентности нашего графа определяется следующим образом: e₁ e₂ e₃ e₄ e₅ e₆ e₇

B(G) =

4) В этом пункте нам также не обойтись без ряда определений. Опр. Расстоянием d(v_i , v_j) между вершинами v_i ‘, и v_j в неориентированном графе G называется наименьшее число ребер, соединяющих эти вершины.

Опр. Условный радиус графа относительно вершины v_i, вычисляют по следующей формуле:

г(v_i)=max d(v_i ,v_j).. Радиус граф R(G) -это наименьший из условных радиусов графа. Опр. Центром графа называется множество вершин, относительно которых условные радиусы графа совпадают с радиусом графа. Таким образом, теперь мы можем определить таблицу расстояний, радиус и центр данного графа.

	V1	v2	v3	v4	r(vi)
V1	0	1	1	1	1
V2	1	0	1	1	1
V3	1	1	0	1	1
V4	1	1	1	0	1

Следовательно, радиус графа R(G)=1, откуда получаем, что центр графа — это множество вершин { v₁ v₂ v₃ v₄ }.