Разработка программы нахождения всех полных подграфов (клик) данного графа - Курсовая работа

Другими словами, клика графа есть подмножество его вершин, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большому подмножеству с тем же свойством. Подграф графа - граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им ребер. E это множество пар (в случае неориентированного графа неупорядоченных) вершин, называемых ребрами.В качестве алгоритма поиска клик был выбран алгоритм Брона-Кербоша ("Algorithm 457: Finding All Cliques of an Undirected Graph".), заявленный как один из самых быстрых алгоритмов поиска клик (Cazals, F.; Karande, C. Алгоритм использует тот факт, что всякая клика в графе является его максимальным по включению полным подграфом. Начиная с одиночной вершины (образующей полный подграф), алгоритм на каждом шаге пытается увеличить уже построенный полный подграф, добавляя в него вершины из множества кандидатов.Задачей программы ставится нахождение всех полных подграфов (клик) данного неориентированного графа. Обеспечивать интерактивность графа (граф можно создавать/изменять при помощи мыши, изменения в графе сразу же отображаются на экране).Программа состоит из главного окна приложения, в котором осуществляется создание и редактирование графа, окна свойств графа, отображающего его матрицу смежности и параметры и окна поиска и отображения клик.Также класс имеет статический метод-конструктор для создания матрицы из текстового файла: static VERTEXMATRIX FROMTEXTFILE(string filename) - создает матрицу вершин графа из текстового файла с именем, указанным в filename. Public методы byte Get(int column, int row) - возвращает значение ячейки матрицы в столбце column строки row. void Set(int column, int row, byte value) - Установить значение ячейки матрицы в столбце column строки row равным value. В случае если значения column или row превышают порядок матрицы, генерируется исключение INDEXOUTOFRANGEEXCEPTION. void ADDVERTEX() - добавляет к матрице новую строку и столбец, тем самым, расширяя порядок матрицы. Новая строка и столбец заполняются нулями. void DELETEVERTEX(int index) - удаляет из матрицы строку и столбец с индексом index, тем самым, понижая ее порядок.Возвращает индекс добавленной вершины. void DELETEVERTEX(int index) - удаляет из графа вершину с индексом index. Если таких вершин не найдено или они не соединены ребром, функция возвращает null. void SETVERTEXCOORDINATS(int index, POINTF coord) - устанавливает координаты вершины с индексом index равными coord. void ARRANGEBYCIRCLE() void ARRANGEBYCIRCLE(int radius) - располагает вершины графа по окружности радиусом Radius. Возвращает объект класса Image, в котором было произведено рисование. void Draw(Graphics g) - рисует граф в области g. void SAVETOFILE(string filename) - сохраняет граф в бинарный файл. Если до вызова этой функции был создан граф или производились изменения в существующем, будет выведено диалоговое окно с предложением сохранить граф. void UNDOACTION() - отменяет последнее совершенное пользователем редактирование графа. void REDOACTION() - отменяет отмену последнего совершенного пользователем редактирования графа. void ADDTOUNDO(Graph graph) - добавляет граф graph в стек отмены. void DOCKPANEL_Paint(object sender, PAINTEVENTARGS e) - событие Paint объекта класса DOCKPANEL. void DOTOOLACTION(APPTOOL t, POINTF coords) - выполняет действие, предписанное инструментом t с начальными координатами coords. void DOCKPANEL_MOUSEDOWN(object sender, MOUSEEVENTARGS e) - обработчик события MOUSEDOWN объекта класса DOCKPANEL. Используется для уведомления инструмента "Добавление ребра" о том, что действие закончилось. void TOOLSTRIPBUTTONCURSOR_CHECKSTATECHANGED(object sender, EVENTARGS e) - изменяет выбранный инструмент на инструмент "Курсор". void TOOLSTRIPBUTTONADDVERTEX_CHECKSTATECHANGED(object sender, EVENTARGS e) - изменяет выбранный инструмент на инструмент "Добавление вершин". void TOOLSTRIPBUTTONDELVERTEX_CHECKSTATECHANGED(object sender, EVENTARGS e) - изменяет выбранный инструмент на инструмент "Удаление вершины". void TOOLSTRIPBUTTONADDNODE_CHECKSTATECHANGED(object sender, EVENTARGS e) - изменяет выбранный инструмент на инструмент "Добавление ребер". void TOOLSTRIPBUTTONDELNODE_CHECKSTATECHANGED(object sender, EVENTARGS e) - изменяет выбранный инструмент на инструмент "Удаление ребер". void TOOLSTRIPBUTTONUNDO_Click(object sender, EVENTARGS e) - обработчик клика по кнопке "Отменить" панели инструментов.Данный класс не содержит никаких пользовательских свойств или методовVERTEXMATRIX GETMATRIXFROMDATAGRID() - возвращает содержащуюся в окне матрицу. void FILLDATAGRID(VERTEXMATRIX mat) - заполняет окно матрицей mat. void SETDEFVALUES() - устанавливает в окне значения "Размер графа", "Размер вершин" и "Число вершин" равными по умолчанию, это 60, 10 и 0 соответственно. Граф в главном окне при этом не меняется. vo

Содержание

Введение

1. Описание алгоритма нахождения клик

2. Разработка структуры программы

2.1 Постановка задачи

2.2 Структура программы

2.3 Описание классов

2.3.1 Класс vertexmatrix

2.3.2 Класс graph

2.3.3 Класс from1

2.3.4 Класс toolwindow

2.3.5 Класс MATRIXWINDOW

2.3.6 Класс cliqueswindow

3. Реализация на C#

3.1 Реализация алгоритма Брона-Кербоша

3.2 Использование нестандартных компонентов

3.3 Реализация алгоритма удаления ребра графа мышью

3.4 Тестирование реализации алгоритма Брон-Кербоша

3.5 Системные требования

Заключение

Список использованной литературы и источников

Приложение

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

Подграф графа - граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им ребер.

Граф - совокупность непустого множества вершин и множества пар вершин.

Неориентированный граф - упорядоченная пара G: = (V,E), для которой выполнены следующие условия: V это непустое множество вершин или узлов

E это множество пар (в случае неориентированного графа неупорядоченных) вершин, называемых ребрами.

К примеру, для графа на рисунке 1 кликами будут являться следующие множества вершин: {1,2,3},{4,2,5},{2,3,5},{3,5,6}. Порядок следования вершин значения не имеет.

Рисунок 1 - неориентированный граф из шести вершин.