Курсовая работа

По предмету

"Программирование на языке высокого уровня"

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

Содержание

Введение

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 – неориентированный граф из шести вершин.

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

В качестве алгоритма поиска клик был выбран алгоритм Брона-Кербоша ("Algorithm 457: Finding All Cliques of an Undirected Graph".), заявленный как один из самых быстрых алгоритмов поиска клик (Cazals, F.; Karande, C. (2008), "A note on the problem of reporting maximal cliques"). Алгоритм разработан голландскими математиками Броном и Кербошем (Bron and Kerbosh) в 1973 году.

Алгоритм использует тот факт, что всякая клика в графе является его максимальным по включению полным подграфом. Начиная с одиночной вершины (образующей полный подграф), алгоритм на каждом шаге пытается увеличить уже построенный полный подграф, добавляя в него вершины из множества кандидатов. Высокая скорость обеспечивается отсечением при переборе вариантов, которые заведомо не приведут к построению клики, для чего используется дополнительное множество, в которое помещаются вершины, которые уже были использованы для увеличения полного подграфа.

На листинге 1.1 приведена реализация алгоритма псевдокодом. M – текущее независимое множество, K – множество кандидатов (вершин, способных образовать клику. На начальном этапе это множество содержит все вершины графа), P – множество отсеянных вершин, которые не могут более добавляться в M, v – просматриваемая вершина, G(i) – множество вершин, смежных с i.

Листинг 1.1 – реализация алгоритма Брона-Кербоша псевдокодом

while K != 0 or M != 0:

if K != 0:

v = K.first

push M, K, P, v

M = M + {v}

K = K – G(v) – {v}

P = P – G(v)

else:

if P == 0:

print M

pop v, P, K, M

K = K – {v}

P = P + {v}

2. ............