Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Господа, будьте снисходительны, не бросайтесь сразу штрафовать за, как вам кажется, глупые вопросы - beginners на то и beginners.
Теория графов 02.11.02 16:40
Автор: NoBody Статус: Незарегистрированный пользователь
|
Народ, где можно надыбать алгоритм на каком-нить ЯП по поиску максимальной клики в графе?
И вообще где-нить есть база алгоритмов на графах??
Помогите plz.
Очень обламывает на курсач много времени тратить=)).
|
|
Теория графов 11.11.02 00:50
Автор: NoBody Статус: Незарегистрированный пользователь
|
Всем пасиба, но я книжку толковую нашел. Там правда поиск всех клик, но переделать - раз плюнуть. Алгоритм зато весьма эффективный.
Если интересно - Б.Н. Иванов "Дискретная математика: алгоритмы и программы". 2002 г.
|
|
re:Теория графов 03.11.02 13:09
Автор: beginner Статус: Незарегистрированный пользователь
|
|
а что такое клика , я учил на английском, поэтому если объяснишь помогу ;))) в любом случае в с++ есть класс graph , в котором большинство нужных алгоритмов реализованы ...
|
| |
re:Теория графов 04.11.02 01:09
Автор: NoBody Статус: Незарегистрированный пользователь
|
|
Клика - полный подграф. Т.е. набор вершин графа, которые все попарно связаны. Задача переборная, нудная. Сам я в ИНЕТе не нашел....((
|
| | |
re: 05.11.02 00:00
Автор: beginner Статус: Незарегистрированный пользователь
|
предлагаю сделать следующим образом: (предположим , что у тебя в графе 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.
> Очень обламывает на курсач много времени тратить=)).
Посмотри Кнута третий том книги "Искусство програмирования"
том называется "Сортировка и поиск" Я не уверен, но по вроде там
что-то есть.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
