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

Курсовой проект студента Шеломанова Р.Б.

Кафедра общей теории систем и системного анализа

Московский государственный университет экономики, статистики и информатики

Москва 1998

Введение

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

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

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

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

Понятие графа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Длинна пути - число дуг последовательности (U₁, U₂, ...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₁ , G₂ ,...G_n - компонентами связности. Граф называется связным, когда каждую его вершину можно соединить с любой другой его вершиной некоторой цепью.

Операции над графами

1. Объединение графов

G₃(X₃,Гх₃) = G₁(X₁,Г1х₁)È G₂(X₂,Г2х₂), где X₃=X₁ÈX₂, а Гx₃=Г1x₁ÈГ2x₂

Пример (Рис 1.1).

Рис 1.1

2. Пересечение графов

G₃(X₃,Гх₃) = G₁(X₁,Г1х₁)ÇG₂(X₂,Г2х₂), где X₃=X₁ÇX₂, а Гx₃=Г1x₁ÇГ2x₂

Пример (рис 1.2).

Рис 1.2

4. Прямое (декартово) произведение графов.

Прямым произведением множеств Х{x₁.......x_n} и Y называется множество Z, элементами которого являются всевозможные пары вида x_i , y_j , где x_iÎX, y_jÎY. Обозначают: Z=X x Y.

G₃(X₃,Гх₃) = G₁(X₁,Г1х₁)ÇG₂(X₂,Г2х₂), где X₃=X1ÇX2, а Гx₃=Г1х1ÇГ2х2

Пример. (рис 2.3)

G₁(X,Гх)=G₁(X₁,Гх₁) G₂(Y,Гy)= G₂(X₂,Гх₂)

X={x₁ x₂ x₃ } Y={y₁ y₂}

Гх₁=0 Гу₁={y₁ y₁}

Гх₂={x₁ x₃} Гу₂={y₁}

Гх₃=0

Z=X x Y={x₁ y₁, x₁y₂, x₂y₁, x₂y₂, x₃y₁, x₃y₂}

Z={z₁ z₂ z₃ z₄ z₅ z₆}

Рис 2.3

7. Расширение графа.

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

8. Сжатие графа.

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

9. Стягивание графа.

Если граф содержит вершины Х₁ и Y₁ , то операцией стягивания называется исключение всех дуг между вершинами Х₁ и Y₁ и превращение всех вершин в одну общую вершину Х.

Некоторые числа теории графов

Пусть существует мультиграф с 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, если х_i - начало дуги U_j

a_ij = -1, если х_i - конец дуги U_j

0, если х_i - не инцидентна дуге U_j

Пример.

Построим матрицы смежности (М1) и инциденций (М2) для графа G(X,U) (рис 2.1).