Реализация основных операций над графами, представленных в виде матриц смежностей (стр. 3 из 5)

Граф, изоморфный своему дополнению, называется самодополнительным. Например,

и граф, изображённый на рис. 3.1.2, – самодополнительные.

Рисунок. 3.1.2–Самодополнительные графы.

Теорема Пусть G – обыкновенный граф с матрицей смежности вершин А. Тогда матрицей смежности вершин графа

является матрица , образованная поэлементным логическим отрицанием матрицы А, исключая диагональные элементы, которые остаются нулевыми.

Если число вершин графа G равно p, то матрицы А и имеют одинаковую размерность . Если G – неориентированный обыкновенный граф, то элемент ( ) матрицы А равен 1, если вершины и смежны, и 0 в противном случае. Так как и ( ) смежны в тогда и только тогда, когда они не смежны в G, то равно 1 (0) в тогда и только тогда, когда равно 0 (1) в А.

Если G – обыкновенный орграф, то элемент

( ) матрицы А равен 1, если существует дуга в G, и 0 в противном случае. Элемент ( ) в равен 1 (0) тогда и только тогда, когда не существует (существует) дуга в G, т.е. элемент равен 0 (1) в А.

в А и в , т. к. G и – обыкновенные графы.

Матрицы смежности вершин А графа

и графа , изображённых на рис. 3.1.3, имеют вид:

, .

Правильность построения матрицы

можно легко проверить по рис. 3.1.3

Объединение графов G1 и G2 , обозначаемое как G1

G2 , представляет такой граф G3 = (Х1 Х2, A1 A2), что множество его вершин является объединением Х1 и Х2 , а множество ребер – объединением A1 и A2 . ГрафG3 , полученный операцией объединения графов G1 и G2 , показан на рис. 2.2.1,д, а его матрица смежности – на рис. 2.2.1,е. Матрица смежности результирующего графа получается операцией поэлементного логического сложения матриц смежности исходных графов G1 и G2 .

Объединение графов.

Пусть

и – произвольные графы. Объединением графов и называется граф со множеством вершин и множеством рёбер .

Операция объединения графов обладает следующими свойствами, которые следуют из её определения и свойств операции объединения множеств:

для любых графов

и – свойство коммутативности;

для любых графов

, и – свойство ассоциативности.

Операция объединения распространяется на любое конечное число графов по индукции:

.

Операция объединения графов может быть выполнена в матричной форме.

Теорема . Пусть

и – два графа (ориентированные или неориентированные одновременно), и пусть и – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа является матрица А, полученная поэлементным взятием максимального элемента вспомогательных матриц А1¢ и А2¢. Матрицы Аi¢, i=1,2, получаются из с помощью добавления нулевых строк и столбцов, соответствующих вершинам, отсутствующим в , но присутствующим в .

По определению графа его матрица смежности А имеет размерность . Построим вспомогательные графы и . Очевидно, что их матрицами смежности вершин будут и соответственно. Очевидно также, что . Для каждой пары вершин и из V в входит максимальное число рёбер, соединяющих их в и , что и определяет значение элемента матрицы А.

Следствие. Если элементы матриц смежности вершин

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