Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Господа, будьте снисходительны, не бросайтесь сразу штрафовать за, как вам кажется, глупые вопросы - beginners на то и beginners.
re: 05.11.02 00:00 Число просмотров: 1057
Автор: 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 , если , что не так :))))
|
|
|
подробно о проекте
Анализ криптографических сетевых...
