Поиск клик в графах
вья и прадеревья
Деревом называется неориентированный связный граф с числом вершин не
менее двух, не содержащий петель и циклов. Вершины, инцидентные только
одной дуге дерева, называются висячими.
Прадрево - ориентированное дерево.
Корень прадерева - вершина у которой Р+(х)=0.
Глава 2
Максимальные полные подграфы (клики)
Максимальный полный подграф (клика) графа G есть порожденный подграф,
построенный на подмножестве S вершин графа и являющийся полным и
максимальным в том смысле, что любой другой подграф графа G, построенный
на множестве вершин H, содержащих S, не является полным. Следовательно,
в клике все вершины попарно смежны. Возможно также определить кликовое
число графа (известное также как густота или плотность) - это
максимальное число вершин в кликах данного графа.
Часть 2
Практическая реализация курсового проекта
Задание
В неориентированном графе заданном матрицей смежностей выделить клики.
Написать программу выполняющую это действие.
Решение
Мой алгоритм нахождения клик в графе
Пусть задан неориентированный граф G1 матрицей смежностей M1 (рис
3.1)
[pic]Рис 3.1
Замечаем следующее:
1) Что матрица М1 симметрична относительно главной диагонали, так как
вершины неориентированного графа попарно смежны.
2) Если выделить клику из данного графа и представить ее в виде
матрицы смежностей то получим матрицу вида:
01111 Тоесть тоже симметричную относительно главной диагонали и в
верхнем
10111 и нижнем треугольниках ее будут находится 1 а на главной
диагонали 0,
11011 так получается потому, что все вершины попарно смежны
(см опред.
11101 клики.
На основе наблюдений приходим к выводу, что для отыскания клик в
неориентированном графе нужно выделить в исходной матрице смежностей
подматрицы указанного выше вида, множества вершин образующие эти матрицы
и будут вершинами клики. Но по определению клики нам подойдут не все
такие множества, а лишь оригинальные не содержащих в себе других
множеств вершин. Так что вторая задача будет сводится к выделению из
полученных множеств оригинальных, не содержащих в себе других
подмножестве. То что исходная матрица смежностей симметрична
относительно главной диагонали позволят нам осуществлять поиск подматриц
только в ее верхнем или нижнем треугольнике.
Шаг 1.
Идем по матрице как показано на рисунке 3.2 а и ищем первую попавшуюся
единичку (рис 3.2 б) запоминаем ее координаты (R,C) .
[pic]
Шаг 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. Потом из него удаляются
все клики несоответствующие вышеприведенным условиям. На выходе получаем
файл клик задаваемого графа.
Пример
[pic]
Задаем граф 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
А Кристофидес “Теория графов. Алгоритмический подход”
| |  скачать работу |
Поиск клик в графах |
