Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Betokuha
32 / 29 / 9
Регистрация: 05.03.2012
Сообщений: 114
#1

Помогите написать программу в С++. Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств - C++

13.03.2012, 21:59. Просмотров 786. Ответов 0
Метки нет (Все метки)

Клика – полный подграф неориентированного графа. Другими словами, клика графа есть подмножество его вершин, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большому подмножеству с тем же свойством.
Подграф графа — граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер.
Граф – совокупность непустого множества вершин и множества пар вершин.
Неориентированный граф – упорядоченная пара G: = (V,E), для которой выполнены следующие условия:
V это непустое множество вершин или узлов
E это множество пар (в случае неориентированного графа неупорядоченных) вершин, называемых ребрами.

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}

Нуждаюсь помоши
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.03.2012, 21:59
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Помогите написать программу в С++. Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств (C++):

Нужно написать консольную программу для нахождения значения F в заданном промежутке с шагом 0,5 - C++
Здравствуйте, уважаемые программисты! Прошу у Вас помощи, помогите пожалуйста! Нужно написать консольную программу для нахождения...

Используя прототип функции написать программу для нахождения максимального элемента - C++
Добрый вечер. Помогите решить задачку. Заранее благодарен!!! Используя прототип функции написать программу для нахождения...

Написать программу для нахождения A28, используя шесть операций умножения - C++
Написать программу для нахождения A28, используя шесть операций умножения

Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств - C (СИ)
Помогите написать программу в С. Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств Сам...

Помогите написать программу для вычисления декартова произведения множеств - Prolog
Помогите написать программу для вычисления декартова произведения множеств

Написать программу нахождения количества встречи цифр в заданном текстовом файле - Turbo Pascal
Написать программу нахождения количества встречи цифр в заданном текстовом файле

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.03.2012, 21:59
Привет! Вот еще темы с ответами:

Написать программу нахождения количества встречи заданной буквы в заданном текстовом файле - Turbo Pascal
Написать программу нахождения количества встречи заданной буквы в заданном текстовом файле

Написать программу для нахождения максимального из n чисел,используя функцию BID - Turbo Pascal
1. Написать программу для нахождения максимального из n чисел,используя функцию BID. Function BID (m,n:integer):integer; Begin if m>n...

Составить алгоритм и написать программу вычисления определенного интеграла функции F(x) на заданном отрезке - Delphi
Помогите, пожалуйста. Составить алгоритм и написать программу вычисления определенного интеграла функции F(x) на заданном отрезке,...

Составить алгоритм и написать программу вычисления определенного интеграла на заданном отрезке интегрирования - Turbo Pascal
Составить алгоритм и написать программу вычисления определённого интеграла на заданном отрезке интегрирования с заданной точностью e ,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru