предлагаю сделать следующим образом: (предположим , что у тебя в графе G :) нет параллельных сторон и петлей , если есть , то просто привести его к "нормальному" виду)
Сначала запусти алгоритм DFS(improved :-), который находит связанные компоненты в графе, то есть такие , что не существует двух вершин a1,a2 (в связанном компоненте ) таких , что любой путь из a1 в a2 лежит через u ( в противном случае u называется вершина-разделитель ;).
После этого (алгоритм обычно пользуется стеком , в который кидает вершины связанного компонента C) бери из стека вершины a in C
и проходи по всем сторонам, выходяшим из a , если вторй конец тоже в C то отлично , если нет , то уменьшай на один deg(a). После этого ещё раз проходишь по всем вершинам и если для всех a in C выполнается deg(a ) == | C | - 1 , то граф - клика , если нет то возвращаемся вDFS и ждем пока он даст следующее значение в стеке и проделываем тоже самое ...
Каждый раз когда алгоритм находит клику , сохранаешь её + кол-во элементов и таким образом всегда определишь максимальную. Есть алгоритмы гораздо лучше , это я так, навскид , алгоритмик на 3-
LINKS :
computer representation of graphs(chapter 1) :
http://www.cs.technion.ac.il/~algs/EvenBook/evenbook.html DFS (same link , chapter 3)
сорu , если , что не так :))))
Народ, где можно надыбать алгоритм на каком-нить ЯП по поиску максимальной клики в графе?
И вообще где-нить есть база алгоритмов на графах??
Помогите plz.
Очень обламывает на курсач много времени тратить=)).
Теория графов11.11.02 00:50 Автор: NoBody Статус: Незарегистрированный пользователь
Всем пасиба, но я книжку толковую нашел. Там правда поиск всех клик, но переделать - раз плюнуть. Алгоритм зато весьма эффективный.
Если интересно - Б.Н. Иванов "Дискретная математика: алгоритмы и программы". 2002 г.
а что такое клика , я учил на английском, поэтому если объяснишь помогу ;))) в любом случае в с++ есть класс graph , в котором большинство нужных алгоритмов реализованы ...
предлагаю сделать следующим образом: (предположим , что у тебя в графе G :) нет параллельных сторон и петлей , если есть , то просто привести его к "нормальному" виду)
Сначала запусти алгоритм DFS(improved :-), который находит связанные компоненты в графе, то есть такие , что не существует двух вершин a1,a2 (в связанном компоненте ) таких , что любой путь из a1 в a2 лежит через u ( в противном случае u называется вершина-разделитель ;).
После этого (алгоритм обычно пользуется стеком , в который кидает вершины связанного компонента C) бери из стека вершины a in C
и проходи по всем сторонам, выходяшим из a , если вторй конец тоже в C то отлично , если нет , то уменьшай на один deg(a). После этого ещё раз проходишь по всем вершинам и если для всех a in C выполнается deg(a ) == | C | - 1 , то граф - клика , если нет то возвращаемся вDFS и ждем пока он даст следующее значение в стеке и проделываем тоже самое ...
Каждый раз когда алгоритм находит клику , сохранаешь её + кол-во элементов и таким образом всегда определишь максимальную. Есть алгоритмы гораздо лучше , это я так, навскид , алгоритмик на 3-
LINKS :
computer representation of graphs(chapter 1) :
http://www.cs.technion.ac.il/~algs/EvenBook/evenbook.html DFS (same link , chapter 3)
сорu , если , что не так :))))
Теория графов03.11.02 06:57 Автор: Razum Статус: Незарегистрированный пользователь
> Народ, где можно надыбать алгоритм на каком-нить ЯП по > поиску максимальной клики в графе? > И вообще где-нить есть база алгоритмов на графах?? > Помогите plz. > Очень обламывает на курсач много времени тратить=)).
Посмотри Кнута третий том книги "Искусство програмирования"
том называется "Сортировка и поиск" Я не уверен, но по вроде там
что-то есть.
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
