Поиск клик в графахТеория графов нашла свое применение в решении целого ряда задач. В моем курсовом проекте будет рассмотрен раздел теории графов посвященный максимальным полным подграфам, тоесть кликам. Целью проекта является написание программы на языке программирования, которая из заданного графа выделяла бы клику с заданным числом вершин. Допустим задан граф G=(Х,Г). Довольно часто возникает задача поиска таких подмножеств множества вершин Х графа G, которые обладают определенным, наперед заданным свойством. Например, какова максимально возможная мощность такого подмножества S Х, для которого порожденный подграф S является полным? Ответ на этот вопрос дает кликовое число графа G. Это число и связанное с ним подмножество вершин описывает важные струтурные свойства графа и имеет непосредственные приложения при проведение проектного планирования исследовательских работ, в кластерном анализе и численных методах таксономии, паралельных вычмслениях на ЭВМ, при размещении предприятий обслуживания, а также источников и потребителей в энергосистемах. Часть 1 Теоретическая часть к курсовому проекту Глава1 Теория графов Понятие графа Графом G(X,U) называется совокупность двух объектов некоторого множества X и отображения этого множества в себя Г. При геометрическом представлении графа элементы множества Х изображаются точками плоскости и называются вершинами графа. Линии, соединяющие любые пары точек x и y, из которых у является отображением х, называются дугами графа. Дуги графа имеют направление, обозначаемое стрелкой, которая направлена острием от элемента х к его отображению у. Вершины и линии графа Две вершины А и В являются граничными вершинами дуги, если Аначало дуги, а В ее конец. Смежными называются различные дуги, имеющие общую граничную точку. Две вершины х и у смежны, если они различны и существует дуга, идущая от одной из них к другой . Вершина называется изолированной, если она не соединена дугами с другими вершинами графа. Если дуга U исходит из вершины х или заходит в х, то дуга U называется инцидентной вершине х, а вершины х инцидентной дуге U. Общее число дуг, инцидентной вершине х, являются степенью вершины х Р(х). Вершины, степень которых Р(х)>2, называются узлом, а со степенью Р(х) Полустепень захода Р + (х) вершины х - количество дуг, заходящих в данную вершину. Полустепень исхода Р - (х) - количество дуг, исходящих из данной вершины. Последовательность линий на графе Путь - последовательность дуг (U 1 , U 2 , ...U n ), в которой конец каждой предыдущей дуги совпадает с началом последующей. Путь может быть конечным и бесконечным. Путь называется простым, если в нем никакая дуга не встречается дважды, и составным, если любая из дуг встречается более одного раза. Путь, в котором ни одна из вершин не встречается более одного раза, называется элементарным путем. Гамильтонов путь - путь проходящий через все вершины, но только по одному разу, Эллеров путь - путь содержащий все дуги графа, при этом только по одному разу. Длинна пути - число дуг последовательности (U 1 , U 2 , ...U n ). Ветвь - путь, в котором начальная и конечная вершины являются узлами. Дуга (x,y) называется замыкающей, если удаление ее не приводит к аннулированию пути из x в y. Контур - конечный путь, начинающийся и заканчивающийся в одной и той же вершине. Контур единичной длинны называется петлей. Ориентированный граф - граф, у которого вершины соединяются направляющими стрелками. Графы можно рассматривать с учетом или без учета ориентации его дуг. Разновидности графов Нуль-граф - граф (X,U), состоящий только из изолированных вершин. Однородный граф - если степени всех вершин графа одинаковы и P + (x)= P - (x) =0. Симметрический граф - граф, в котором две любые смежные вершины соединены только двумя противоположно ориентированными дугами. Антисимметрический - граф, в котором каждая пара смежных вершин соединена только в одном направлении. Полный - граф, в котором любая пара вершин соединена одинаковым числом дуг. Мультиграф - граф, в котором хотя бы две смежные вершины соединены более чем одной дугой. Наибольшее число дуг, соединяющих смежные вершины графа называется кратностью. Подмножества графов Подграфом графа G(X,U) называется граф G(A,U A ), определяемый следующим образом: 1. Вершинами A подграфа G(A,U A ) является некоторое подмножество вершин графа G(X,U); 2. Отображением каждой вершины подграфа является пересечение отображения той же вершины в графе G(X,U) со всем подмножеством вершин A подграфа G(A,U A ). Частичным графом для графа G(X,U) называется граф G(X,U), в котором содержатся все вершины и некоторое подмножество дуг исходного графа. Частичный подграф - это частичный граф от подграфа. Фактором графа G(X,U) называется частичный граф G(X,U), в котором каждая вершина обладает полустепенями исхода и захода, равными единице, имеются одна заходящая и одна исходящая дуги. Базисным графом называется ориентированный частичный граф, образованный из исходного удалением петель и замыкающих дуг. Связность графа В общем случае граф может быть представлен несколькими отдельными графами, не имеющими общих дуг. Тогда граф G(X,U) называется несвязным, а каждый из составляющих его графов G 1 , G 2 ,...G n - компонентами связности. Граф называется связным, когда каждую его вершину можно соединить с любой другой его вершиной некоторой цепью. Операции над графами 1. Объединение графов G 3 (X 3 ,Гх 3 ) = G 1 (X 1 ,Г1х 1 ) G 2 (X 2 ,Г2х 2 ) , где X 3 =X 1 X 2 , а Гx 3 =Г1x 1 Г2x 2 Пример (Рис 1.1). Прямым произведением множеств Х{x 1 .......x n }и Y называется множество Z, элементами которого являются всевозможные пары вида x i , y j , где x i X, y j Y. Обозначают: Z=X x Y. G 3 (X 3 ,Гх 3 ) = G 1 (X 1 ,Г1х 1 ) G 2 (X 2 ,Г2х 2 ), где X 3 =X1 X2, а Гx 3 =Г1х1 Г2х2 Пример. (рис 2.3) G 1 (X,Гх)=G 1 (X 1 ,Гх 1 ) G 2 (Y,Гy)= G 2 (X 2 ,Гх 2 ) X={x 1 x 2 x 3 } Y={y 1 y 2 } Гх 1 =0 Гу 1 ={y 1 y 1 } Гх 2 ={x 1 x 3 } Гу 2 ={y 1 } Гх 3 =0 Z=X x Y={x 1 y 1 , x 1 y 2 , x 2 y 1 , x 2 y 2 , x 3 y 1 , x 3 y 2 } Z={z 1 z 2 z 3 z 4 z 5 z 6 } Расширение графа - это превращение, линии, соединяющей любые две вершины графа в элементарный путь введением новых промежуточных вершин на этой линии. 8. Сжатие графа. Сжатие графа - это превращение элементарного пути, соединяющего две любые вершины графа, в линию. 9. Стягивание графа. Если граф содержит вершины Х 1 и Y 1 , то операцией стягивания называется исключение всех дуг между вершинами Х 1 и Y 1 и превращение всех вершин в одну общую вершину Х. Некоторые числа теории графов Пусть существует мультиграф с b вершинами, p ребрами, и R компонентами связности, тогда цикломатическое число мультиграфа определяется равенством: V= p-b+R Матрицы для графов Матрицей смежности графа G(X,Гх), содержащего n вершин называется квадратная бинарная матрица А(G) n x n , c нулями на диагонали. Число единиц в строке равно степени соответствующей вершины. Матрицей инциденций ориентированного графа G(X,U) называется прямоугольная матрица порядка [m x n] n - мощность множества Х, m - мощность множества U. Каждый элемент которой определяется следующим образом: Построим матрицы смежности (М1) и инциденций (М2) для графа G(X,U) (рис 2.1). Деревья и прадеревья Деревом называется неориентированный связный граф с числом вершин не менее двух, не содержащий петель и циклов. Вершины, инцидентные только одной дуге дерева, называются висячими. Прадрево - ориентированное дерево. Корень прадерева - вершина у которой Р + (х)=0. Глава 2 Максимальные полные подграфы (клики) Максимальный полный подграф (клика) графа G есть порожденный подграф, построенный на подмножестве S вершин графа и являющийся полным и максимальным в том смысле, что любой другой подграф графа G, построенный на множестве вершин H, содержащих S, не является полным. Следовательно, в клике все вершины попарно смежны. Возможно также определить кликовое число графа (известное также как густота или плотность) - это максимальное число вершин в кликах данного графа. Часть 2 Практическая реализация курсового проекта Задание В неориентированном графе заданном матрицей смежностей выделить клики. Написать программу выполняющую это действие. Решение Мой алгоритм нахождения клик в графе Пусть задан неориентированный граф G1 матрицей смежностей M1 (рис 3.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 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. Потом из него удаляются все клики несоответствующие вышеприведенным условиям. На выходе получаем файл клик задаваемого графа. Пример Пропускаем 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. Результат работы программы выводится в виде таблицы по количеству вершин клик и номеров самих вершин составляющих клики. |
Поиск клик в графах
2. Пересечение графов G 3 (X 3 ,Гх 3 ) = G 1 (X 1 ,Г1х 1 ) G 2 (X 2 ,Г2х 2 ) , где X 3 =X 1 X 2 , а Гx 3 =Г1x 1 Г2x 2 Пример (рис 1.2). 
4. Прямое (декартово) произведение графов.
Рис 2.3 7. Расширение графа.
1, если х i - начало дуги U j a ij = -1, если х i - конец дуги U j 0, если х i - не инцидентна дуге U j Пример.
Рис 2.1 Дополнительная матрица графа G(X,U) представляет собой квадратную матрицу А 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), так как в исходной матрице столбцы попарно смежных вершин не обязательно соседствуют.