НАУЧНАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Поиск клик в графах
Поиск клик в графах
[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
А Кристофидес “Теория графов. Алгоритмический подход”
|