информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Портрет посетителяВсе любят мед
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Крупный взлом GoDaddy 
 Просроченный сертификат ломает... 
 Phrack #70/0x46 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / beginners
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





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








Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2021 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach