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

Матричные представления графа наиболее просты. В матрице смежности А элемент A_i,jравен 1, если имеется ребро { v_i, v_j }, иначе А_i,i = 0. Другими словами, i-я ее строка содержит р_iединиц, указывая все узлы, смежные с i-м узлом (р_i - его степень).

На главной диагонали матрицы записывают нули, ибо ребра вида { v_i, v_j } (петли) считаются недопустимыми. Размер матрицы - nn. Матрица симметрична относительно главной диагонали.

Итак, о существовании ребра {i,j} можно узнать, наблюдая (проверяя) элемент A[i,j], это удобно. Наглядность матрицы смежности особенно важна для обучаемых, например, при описании алгоритмов. Ее элементы могут быть и логического типа: наличие ребра можно представить значением true, отсутствие - false.

Пример 6.1.

В следующей программе, выводящей номера узлов, смежных с за­данным узлом, матрица смежности графа G (см. п.5.1) задана как двумерный массив А:

Const n=6;

A: Array[1..n,1..n] of byte =(( 0,1,0,0,1,1 ), {для 1 узла},

( 1,0,0,0,1,1 ), {для2 узла}

(0,0,0,1,0,0), {для 3 узла}

(0,0,1,0,0,0), {для 4 узла}

( 1,1,0,0,0,1 ), {для 5 узла}

(1,1,0,0,1,0)); {для 6 узла}

Var j,j: word;

BEGINWrite('Укажите интересующий Вас узел: '); Readln(i);

Writeln('Cписок узлов, смежных с заданным:');

For j:=1 to n do If A[i,j]=1 Then Write(j,', '); Readln;

END.

Представление матрицы двумерным массивом неэкономно, размер n не превышает 254 (при n = 255 происходит выход из сегмента памяти). Использование множеств (тип SET; см. пример 1.3) для представления строк матрицы уменьшает расход памяти в 8 раз.

Пример 6.2.

Предельная экономия памяти достигается отображением верхней треугольной части матрицы А (вспомним ее симметрию) на виртуальное множество В^, составленное из необходимого числа элементов типа SET. Функция A(ij) (см. ниже) возвращает значение true, если элемент А_i,j исходной матрицы равен 1, иначе возвращается false. Процедура Add(ij) (Del(ij)) выполняет в В^ действия, соответствующие установке элемента А_i,j , в 1 (в 0).

Данное представление позволяет довести число узлов в графе до 2880^*.

Const n = 2880; nSET = ((n*n+n) div 2) div 256;

Type mno = set of 0..255; matr = Array[0..nSET] of ^mno;

mas = Array[1..n] of word;

Var B: matr;

i,j,k: word;

Procedure ij(var i,j: Word);

Var k: Longint;

Begin If j < i Then Begin k:=i; i:=j; j:=k End;

k:= (n+n-i); k:= (k*(i-1)) div 2 +j;

i:= k div 256; j:= k mod 256

End;

Function A(i,j: Word): Boolean;

Begin If i=j Then A:=false

Else Begin ij(i,j); A:= j IN B[i]^ End

End;

Procedure Add (i,j: Word);

Begin If i=j Then Exit;

ij(i,j); B[i]^:= B[i]^ + B[i]^ End;

Procedure Del(i,j: Word);

Begin If i=j Then Exit;

ij(i,j); B[i]^:= B[i]^ - [j]End;

BEGIN {В следующем цикле создаются пустые множества В[j]^ :}

For j:=0 to nSET do Begin New(B[j]); B[j]^:= [] End;

For i:=1 to n do

Begin If Odd(i) Then j:=2 Else j:=1;

Repeat Add(i.j); j:=j+2 Until j > n {Заполняемматрицу "1" вшахматномпорядке}

End; Writeln;

Fori:=1 tondo {Для проверки выводим содержимое матрицы А}

Begin For j:=1 to n do If A(i,j) Then Write('1')

Else Write('O'); Writeln

End; Readln;

END.

Другое матричное представление графа - прямоугольная матрица инциденций – практического значения не имеет. Каждый ее столбец соответствует одному из ребер графа, а строки - узлам. В столбце, отображающем ребро {i, j}, две "1" - в i-й и в j-й строке, прочие - нули. Такое представление неоправданно усложняет решение многих задач и увеличивает расход памяти: для графов, близких к полным, емкостная сложность - О(n³ ). Ниже дана матрица инциденций для графа G из п.5.1.

1) 1 0 0 1 1 0 0

н о м е р а 2) 1 1 1 0 0 0 0

3) 0 0 0 0 0 0 1

у з л о в 4) 0 0 0 0 0 0 1

5. 0 1 0 1 0 1 0

6. 0 0 1 0 1 1 0

Задание 6.2.

• В примере 5.2 не используется процедура Del. Измените программу: исходные множества В[j]^ сделайте полными, т.е. присвойте им зна­чения [0...255], а затем исключите ненужные элементы, добиваясь "шахматного порядка" в матрице А.