Поиск клик в графах

Курсовой проект студента Шеломанова Р.Б. Кафедра общей теории систем и системного анализа Московский государственный университет экономики, статистики и информатики Москва 1998 Введение

Для иллюстраций условий и решений многих задач люди пользуются графиками. По своей сути графики являются набором из множества точек и отрезков прямых соединяющих эти точки. Возникает вопрос: подчиняются ли графики каким-либо законам и обладают ли они какими-нибудь свойствами? Этот вопрос был поставлен Д. Кенигом, который впервые объединил все схематические изображения, состоящие из совокупности точек и линий, общим термином “граф” и рассмотрел граф как самостоятельный математический объект. Теория графов нашла свое применение в решении целого ряда задач. В моем курсовом проекте будет рассмотрен раздел теории графов посвященный максимальным полным подграфам, тоесть кликам. Целью проекта является написание программы на языке программирования, которая из заданного графа выделяла бы клику с заданным числом вершин.

Допустим задан граф G=(Х,Г). Довольно часто возникает задача поиска таких подмножеств множества вершин Х графа G, которые обладают определенным, наперед заданным свойством. Например, какова максимально возможная мощность такого подмножества S Í Х, для которого порожденный подграф S является полным? Ответ на этот вопрос дает кликовое число графа G. Это число и связанное с ним подмножество вершин описывает важные струтурные свойства графа и имеет непосредственные приложения при проведение проектного планирования исследовательских работ, в кластерном анализе и численных методах таксономии, паралельных вычмслениях на ЭВМ, при размещении предприятий обслуживания, а также источников и потребителей в энергосистемах.

Часть 1. Теоретическая часть к курсовому проекту

Глава1. Теория графов Понятие графа

Графом G(X,U) называется совокупность двух объектов некоторого множества X и отображения этого множества в себя Г.

При геометрическом представлении графа элементы множества Х изображаются точками плоскости и называются вершинами графа. Линии, соединяющие любые пары точек x и y, из которых у является отображением х, называются дугами графа. Дуги графа имеют направление, обозначаемое стрелкой, которая направлена острием от элемента х к его отображению у.

Вершины и линии графа

Две вершины А и В являются граничными вершинами дуги, если А- начало дуги, а В ее конец.

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

Вершина называется изолированной, если она не соединена дугами с другими вершинами графа.

Если дуга U исходит из вершины х или заходит в х, то дуга U называется инцидентной вершине х, а вершины х инцидентной дуге U. Общее число дуг, инцидентной вершине х, являются степенью вершины х Р(х). Вершины, степень которых Р(х)>2, называются узлом, а со степенью Р(х)<2 - антиузлом.

Полустепень захода Р+(х) вершины х - количество дуг, заходящих в данную вершину. Полустепень исхода Р-(х) - количество дуг, исходящих из данной вершины.

Последовательность линий на графе

Путь - последовательность дуг (U1, U2, ...Un), в которой конец каждой предыдущей дуги совпадает с началом последующей. Путь может быть конечным и бесконечным.

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

Путь, в котором ни одна из вершин не встречается более одного раза, называется элементарным путем.

Гамильтонов путь - путь проходящий через все вершины, но только по одному разу,

Эллеров путь - путь содержащий все дуги графа, при этом только по одному разу.

Длинна пути - число дуг последовательности (U1, U2, ...Un).

Ветвь - путь, в котором начальная и конечная вершины являются узлами. Дуга (x,y) называется замыкающей, если удаление ее не приводит к аннулированию пути из x в y.

Контур - конечный путь, начинающийся и заканчивающийся в одной и той же вершине. Контур единичной длинны называется петлей.

Ориентированный граф - граф, у которого вершины соединяются направляющими стрелками.

Графы можно рассматривать с учетом или без учета ориентации его дуг.

Разновидности графов

Нуль-граф - граф (X,U), состоящий только из изолированных вершин.

Однородный граф - если степени всех вершин графа одинаковы и P+(x)= P- (x) =0.

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

Антисимметрический - граф, в котором каждая пара смежных вершин соединена только в одном направлении.

Полный - граф, в котором любая пара вершин соединена одинаковым числом дуг.

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

Подмножества графов

Подграфом графа G(X,U) называется граф G(A,UA), определяемый следующим образом: