Поиск клик в графах (стр. 2 из 2)

Рис 2.1

Дополнительная матрица графа G(X,U) представляет собой квадратную матрицу А¹ , которая получается из матрицы смежности этого графа путем замены всех нулей единицами и наоборот.

Деревья и прадеревья

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

Прадрево - ориентированное дерево.

Корень прадерева - вершина у которой Р⁺(х)=0.

Глава 2. Максимальные полные подграфы (клики)

Максимальный полный подграф (клика) графа G есть порожденный подграф, построенный на подмножестве S вершин графа и являющийся полным и максимальным в том смысле, что любой другой подграф графа G, построенный на множестве вершин H, содержащих S, не является полным. Следовательно, в клике все вершины попарно смежны. Возможно также определить кликовое число графа (известное также как густота или плотность) - это максимальное число вершин в кликах данного графа.

Часть 2. Практическая реализация курсового проекта

Задание

В неориентированном графе заданном матрицей смежностей выделить клики. Написать программу выполняющую это действие.

Решение

Мой алгоритм нахождения клик в графе

Пусть задан неориентированный граф G1 матрицей смежностей M1 (рис 3.1)

Рис 3.1

Замечаем следующее:

1) Что матрица М1 симметрична относительно главной диагонали, так как вершины неориентированного графа попарно смежны.

2) Если выделить клику из данного графа и представить ее в виде матрицы смежностей то получим матрицу вида:

01111 Тоесть тоже симметричную относительно главной диагонали и в верхнем

10111 и нижнем треугольниках ее будут находится 1 а на главной диагонали 0,

11011 так получается потому, что все вершины попарно смежны (см опред.

11101 клики.

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

Шаг 1.

Идем по матрице как показано на рисунке 3.2 а и ищем первую попавшуюся единичку (рис 3.2 б) запоминаем ее координаты (R,C) .

Шаг 2.

Ищем следующую 1 по адресу (R,C1)

Шаг 3.

Начинаем спускаться по столбцу (С1) в поисках 1 , причем ищем ее по адресу (С,С1), так как в исходной матрице столбцы попарно смежных вершин не обязательно соседствуют. Запоминаем строку каждой найденной таким образом 1 для поиска в следующих столбцах. Увеличиваем длину множества вершин на 1.

Количество повторений шага 3 равно текущему размеру множества вершин.

Если по указанному адресу мы не встречаем 1 то значит данный столбец не образует подматрицу смежностей клики - пропускаем его. Начинаем Шаг 2.

Если размер множества вершин образующих клику больше 2 то запоминаем это множество.

Так до конца строки.

Повторяем Шаг 1 для всех 1 в строке.

Таким образом проходим всю матрицу. На выходе получаем несколько множеств вершин, отбираем среди них только оригинальные, не содержащие в себе других подмножеств.

Отобранные подмножества и есть клики заданного графа.

Программная реализация

procedure MakeKliks;

var StolbecSravn,StringSravn,Num,size,i1,i,lenStolb,

Stolbec,RetStolb:byte;

Kstring:klik;

f1:file of byte;

klika:tKlik;

begin

assign(FileKlics,'klics.ots');

rewrite(fileKlics);

assign(f1,'matrica.ots');

reset(f1);

read(f1,size);

for I:=1 to size do

begin

for stolbecsravn:=1 to size do

begin

read(f1,smezh[i,stolbecsravn]);

end;

end;

for i:=1 to size do

begin {начало пpохода по стpокам}

KString[1]:=i;

for stolbec:=i+1 to size do

begin {пеpебиpаем в стpоке все возможные места начала клики}

If Smezh[i,stolbec]=1 then

begin

lenStolb:=1;

for StolbecSravn:=Stolbec to size do

begin {с найденного места пpовеpяем все возможные ваpианты}

StringSravn:=i;

Num:=1;

while (Smezh[KString[num],StolbecSravn]=1)and(num<=LenStolb) do

begin

StringSravn:=KString[num];

num:=num+1;

end;

If num-1=LenStolb then

begin

lenStolb:=lenStolb+1;

Kstring[lenStolb]:=StolbecSravn;

end;

end; {конецпpовеpкиваpиантов}

if lenstolb>2 then

begin

klika.lenmass:=lenstolb;

for i1:=1 to lenstolb do

klika.Klikmass[i1]:=Kstring[i1];

write(fileKlics,klika);

end;

end;

end; {конец пеpебоpа возможных мест в стpоке}

end; {конец пpохода по стpокам}

close(fileklics);

end;

Выше представлена процедура нахождения клик в графе.

Описание переменных:

StolbecSravn: номер сравниваемого столбца.

StringSravn: номер текущей строки.

Num ,i1,i: счетчики.

lenStolb: размер множества вершин клики.

Stolbec: номер столбца первой единицы в текущем цикле сравнения.

size: размер матрицы смежностей.

Kstring: вектор хранящий координаты строк для сравнения. По выходе из цикла сравнения этот массив представляет собой множество вершин найденной клики.

Smezh: Матрица смежностей;

Найденные клики сохраняются в файле klics.ots. Потом из него удаляются все клики несоответствующие вышеприведенным условиям. На выходе получаем файл клик задаваемого графа.

Пример

Задаем граф G1 его матрицей смежности М1.

Берем первую строку, находим первую единичку по адресу (1,2).

Запоминаем адрес первой 1 (1,2). Ищем следующую 1 в первой строке. Она находится по адресу (1,5). Проверяем адрес (2,5) на 1. Там ее нет. Пропускаем 5-й столбец. Находим следующую 1 в 6 столбце. Проверяем адрес (2,6) на 1. Там ее нет. так до конца строки. Убеждаемся что в данном цикле сравнений матрица смежностей получаемой клики имеет размерность два. Что означает наличие в клике двух вершин - простейшее сочетание - оно не рассматривается в моей программе. Мы записываем в файл клик клики не меньше третьего порядка.

Выбираем в первой строке следующую 1. Она находится по адресу (1,5) запоминаем этот адрес в массиве строк. Ищем следующую 1 в первой строке. Она находится по адресу (1,6). Спускаемся по 6 столбцу, проверяем адрес (5,6) на 1. Она там есть. Количество найденных 1 в 6 столбце =размеру массива содержащего множества. Тогда увеличиваем длину этого массива на 1 и записываем туда 6. Получаем в массиве [1,5,6]. И т.д.

В итоге получим клики с номерами вершин: 1 5 6 8; 6 4 8; 1 7 8.

Матрица смежностей клики 1568.

1 5 6 8

10 1 1 1

51 0 1 1

61 1 0 1

81 1 1 0

Работа с программой

Программа позволяет найти клики в неориентированном графе размером не более 10 вершин. Граф вводится в ЭВМ матрицей смежностей. Данную матрицу можно взять из вшитого в программу файла. Программа позволяет удобно редактировать заданную матрицу, для выхода из редактирования нажать Esc. Результат работы программы выводится в виде таблицы по количеству вершин клик и номеров самих вершин составляющих клики.

Программа реализована на языке программирования Turbo Pascal 7.0.

Заключение

Программная реализация на ЭВМ поиска максимальных полных подграфов(клик) значительно облегчает работу с графами, как представлением каких либо систем, в смысле исследования этих систем. Мой алгоритм позволяет найти клики в графе любой размерности, но для наглядности я реализовал алгоритм только для графов чья мощность не превышает 10. Так же мой алгоритм за добавлением одного условия будет искать клики и в ориентированном графе. Но моей целью не было создание профессиональной часто используемой программы, а скорее я хотел показать возможность решения данной задачи на ЭВМ.

Список литературы

Ковалева Л.Ф. “Математическая логика и теория графов” МЭСИ 1977

А Кристофидес “Теория графов. Алгоритмический подход”