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

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

[pic]

Кафедра общей теории систем

и системного анализа

Курсовой проект

по курсу:

“Общая теория систем”

по теме:

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

Группа: ДИ 102

Студент: Шеломанов Р.Б.

Руководитель: Кацман В.Е.

Москва 1998

Содеражание

Введение 3

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

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

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

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

Задание 8

Решение 8

Заключение 12

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

Введение

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

По своей сути графики являются набором из множества точек и отрезков прямых

соединяющих эти точки. Возникает вопрос: подчиняются ли графики каким-либо

законам и обладают ли они какими-нибудь свойствами? Этот вопрос был

поставлен Д. Кенигом, который впервые объединил все схематические

изображения, состоящие из совокупности точек и линий, общим термином “граф”

и рассмотрел граф как самостоятельный математический объект. Теория графов

нашла свое применение в решении целого ряда задач. В моем курсовом проекте

будет рассмотрен раздел теории графов посвященный максимальным полным

подграфам, тоесть кликам. Целью проекта является написание программы на

языке программирования, которая из заданного графа выделяла бы клику с

заданным числом вершин.

Допустим задан граф G=(Х,Г). Довольно часто возникает задача поиска таких

подмножеств множества вершин Х графа G, которые обладают определенным,

наперед заданным свойством. Например, какова максимально возможная мощность

такого подмножества S ( Х, для которого порожденный подграф S является

полным? Ответ на этот вопрос дает кликовое число графа G. Это число и

связанное с ним подмножество вершин описывает важные струтурные свойства

графа и имеет непосредственные приложения при проведение проектного

планирования исследовательских работ, в кластерном анализе и численных

методах таксономии, паралельных вычмслениях на ЭВМ, при размещении

предприятий обслуживания, а также источников и потребителей в

энергосистемах.

Часть 1

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

Глава1

Теория графов

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

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

множества X и отображения этого множества в себя Г.

При геометрическом представлении графа элементы множества Х

изображаются точками плоскости и называются вершинами графа. Линии,

соединяющие любые пары точек x и y, из которых у является отображением

х, называются дугами графа. Дуги графа имеют направление, обозначаемое

стрелкой, которая направлена острием от элемента х к его отображению у.

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

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

дуги, а В ее конец.

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

вершины х и у смежны, если они различны и существует дуга, идущая от

одной из них к другой .

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

другими вершинами графа.

Если дуга U исходит из вершины х или заходит в х, то дуга U называется

инцидентной вершине х, а вершины х инцидентной дуге U. Общее число дуг,

инцидентной вершине х, являются степенью вершины х Р(х). Вершины,

степень которых Р(х)>2, называются узлом, а со степенью Р(х)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

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