Алгоритм построения матрицы метрики графа

Исходные данные для построения матрицы метрики (отклонений):

1. Граф L=(X,U).

2. Матрица смежности R графа L c элементами логического типа:

ì 1, если вершины x_i, x_j – смежны;

r_i,j = í

î0 в противном случае.

Введем обозначения:

R – матрица смежности заданного графа L;

E – единичная матрица;

М – матрица метрики (отклонений).

Описание алгоритма

Матрица метрики M= (m_i,j) строится за несколько итераций по результатам последовательного возведения матрицы R=(E+R) в степень q= до получения устойчивой матрицы R^k, где k – степень устойчивой матрицы R^k. Матрица R^k называется устойчивой, если R^k = R^{k +1}.

Размерность матрицы М равна размерности матрицы R.

Все элементы матрицы М не определены.

Шаг 1.

Степень q матрицы R равна «1»: q=1.

" m_i,i присваиваем значение «0», на основании аксиомы Фрише.

Шаг 2. Всем элементам m_i,j, значения которых не определены, присвоить значение степени q, если соответствующие им элементы матрицы R^q ¹ 0. (Не забывайте, что значения элементов m_i,j определяются только один раз).

Шаг 3. Проверяем, имеются ли в матрице M элементы m_i,j, значения которых ещё не определены?

Если такие элементы имеются, то переходим к шагу 4; в противном случае – к шагу 7.

Шаг 4. Повышаем степень q матрицы R: q=q+1.

Шаг 5. Проверяем, является ли матрица R^q–1 устойчивой.

Если матрица R^q–1 – неустойчивая, то переходим к шагу 2.

Иначе – переходим к шагу 6.

Шаг 6. Всем элементам m_i,j матрицы M, значения которых остались неопределенными, присваиваем значение ¥ (бесконечность). Это говорит о том, что граф L=(X,U) несвязный.

Шаг 7. Матрица метрики М=(m_i,j) построена. Конец алгоритма.

Примечание: 1.*Элементам m_i,j значения присваиваются только один раз! Следовательно, если элемент m_i,j уже определён, то его значение не меняется*.

2. Радиус графа определяется по матрице метрики следующим способом: в каждой строке матрицы М выделяется максимальный элемент. Минимальный элемент из этих максимальных и есть радиус графа.

3. Диаметрграфа определяется по матрице метрики следующим способом: в каждой строке матрицы М выделяется максимальный элемент. Максимальный элемент из этих максимальных и есть диаметр графа.

Задание 6.

Произвести произвольно ориентацию рёбер графа G=(X,U) (рисунок 1) и для нового графа выполнить задания 1.1, 1.3, 5.

Задание 7.

Построить скелет графа .

Скелет графа общего вида. В случае, когда при исследовании графа L=(X.U;P) общего вида требуется не полная информация о нём, а лишь знание того, какие пары его различных вершин смежны и какие нет, прибегают к носителю такой информации – скелету графа L, который обозначим как . Граф относится к классу обыкновенных графов с множеством вершин тем же, что и в графе L, и новым множеством рёбер , определённым следующим образом:

5) если в графе L есть петли, то они удаляются;

6) если в графе L есть дуги, то производится дезориентация дуг;

7) если в графе L есть кратные рёбра, то они заменяются одним эквивалентным ребром-звеном;

8) оставшиеся рёбра образуют множество рёбер .

Таким образом, множество рёбер состоит из рёбер, полученных из множества U после выполнения описанных выше процедур 1, 2, 3.

Задание 8.

В графе G=(X,U) ( рисунок 1) найти все максимальные полные и максимальные пустые подграфы с помощью алгоритма Магу-Уэйсмана.

Структурный анализ графов

Определение: а)подграф называется максимальным пустым подграфом графа L=(X,U;P), если он не является подграфом никакого большего максимального пустого подграфа заданного графа;

б)подграф называется максимальным полным подграфом графа L=(X,U;P), если он не является подграфом никакого большего максимального полного подграфа заданного графа.

Легко доказать, что задача выявления максимальных полных (плотных) и максимальных пустых подграфов в заданном графе общего вида легко сводится к случаю обыкновенных графов. Поэтому, для практического выявления всех максимальных полных и пустых подграфов в произвольном графе, достаточно уметь выявлять только максимальные плотные и пустые подграфы обыкновенных графов.

Приведём алгоритм выявления всех максимальных пустых подграфов в заданном графе общего вида, основанный на работах Х. Магу и Дж. Уэйсмана:

п.1.Для графа L=(X,U;P) общего вида построим его скелет ( смотри тему 1 данного методического пособия).

п.2. Построим матрицу инциденций А графа , элементы которой a_i,j принимают значения 0 либо 1 ( ; , где n =½X½ - число вершин в , m =½ ½- число рёбер в ).

п.3. Дополним систему логическими переменными х₁, х₂, …, х_i, …, х_n , которые принимают значения 0 и 1, и подчиним её условиям:

; ; , 1+1=1, т.е. 2=1, (i=1,2,…,n),

а также законам коммутативности, ассоциативности и дистрибутивности.

п.4. Из матрицы инциденций

графа , где n ,m соответственно равны числу вершин и рёбер графа, образуем матрицу

и составим произведение

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

п.5. Преобразуем произведение к бесскобочному виду и привести всю сумму к минимальной форме, пользуясь дистрибутивным, ассоциативным, коммутативным законами и применяя закон поглощения: а) а+ав =а; б) (а+в)(а+с)^…(а+р) = =а+вс^…р, где а,в,с,…,р - логические переменные, принимающие значения 0;1, выполняя при этом условия, описанные в п.3.

В результате выполненных преобразований выражение будет иметь минимальную форму и представлять сумму произведений переменных из множества х₁, х₂, …,х_i,…,х_{n ,} т.е. многочлен. Обозначим его .

п.6. Для каждого слагаемого многочлена выделим переменные, которые в него не входят, но входят в множество {х₁, х₂, …, х_i, …, х_n }. Эти переменные порождают максимальные пустые подграфы данного графа L, так как соответствующие им вершины графа L образуют максимальные пустые подграфы.

ПРИМЕР. В графе , представленном на рисунке 1, выделить все максимальные пустые подграфы.

 

Матрица смежности B графа L содержит элементы ( ), , равные:

b₁₁= b₂₂= b₃₃= b₅₅=0; b₄₄=1; b₁₂=2; b₁₃=1; b₁₄ =0; b₁₅ = 0;

b₂₁=2; b₂₃=0; b₂₄ =2; b₂₅ = 0; b₃₁=1; b₃₂=0; b₃₄ =0; b₃₅ = 3;

b₄₁=0; b₄₂=2; b₄₃ =0; b₄₅ = 1; b₅₁=0; b₅₂=0; b₅₃ =3; b₅₄ = 1;

 

ш.1. Строим скелет (рисунок 2) графа .

 

 

ш.2. Для графа определим его матрицу инциденций А:

 

 

ш.3. Введём новые логические переменные х_1, х_2, х_3, х_4, х₅ (по числу вершин в графе ) и из матрицы А образуем матрицу Ах :

 

 

ш.4. Составляем произведение П_L

 

ш.5. Преобразуем выражения П_L к минимальной форме:

=

(перемножаем скобки первую со второй и третью с пятой)

= =

(перемножаем скобки первую со второй)

=

(перемножаем скобки первую со второй)

(применяем законы, указанные в п.п. 3,5 данного пособия)

= .

Преобразование выражения П_L закончено. Получена минимальная форма-полином .

ш.6. Выделим для каждого слагаемого полинома

=

его дополнение до множества переменных {x₁,x₂, x₃, x₄, x₅}:

(x₂x₅); (x₂,x₃); (x₃,x₄); (x₁,x₅); (x₁,x₄);

полученные дополнения порождают максимальные пустые подграфы графа и заданного графа .

 

Алгоритм Х. Магу и Дж. Уэйсмана может быть применён и для выявления в графе L=(X,U; P) общего вида всех максимальных полных (плотных) подграфов. Для этого необходимо построить для заданного графа его скелет – граф , а для графа построить дополнительный граф (определение дополнительного графа дано в теме 1 данного методического пособия). Получить дополнительный граф легко, если исходный граф задать матрицей смежности его вершин, в которой всем элементам, равным нулю, присвоить значение «1», а всем элементам, значения которых не равны нулю, присвоить значение «0».

Далее для полученного графа с помощью алгоритма Х. Магу и Дж. Уэйсмана (рассмотренного выше) выявляем все максимальные пустые подграфы. Эти подграфы являются максимальными полными (плотными) подграфами для графов и .

ПРИМЕР. В графе , представленном на рисунке 1, выделить все максимальные полные(плотные) подграфы.

ш.1. Строим скелет (рисунок 2) графа .

ш.2. Для графа строим его дополнительный граф (рисунок 3), в котором с помощью алгоритма Х.Магу-Дж.Уэйсмана выявляем максимальные пустые подграфы.

 

 

Приведём окончательный результат решения данной задачи - полином

=

и дополнения для его слагаемых: ( ); ( ); ( ); ( ); ( ), которые порождают все максимальные пустые подграфы графа и максимальные полные (плотные) подграфы графа и заданного графа .