информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Атака на InternetГде водятся OGRы
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / beginners
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Господа, будьте снисходительны, не бросайтесь сразу штрафовать за, как вам кажется, глупые вопросы - beginners на то и beginners.
re:Теория графов 04.11.02 01:09  Число просмотров: 1075
Автор: NoBody Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Клика - полный подграф. Т.е. набор вершин графа, которые все попарно связаны. Задача переборная, нудная. Сам я в ИНЕТе не нашел....((
<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.
> Очень обламывает на курсач много времени тратить=)).

Посмотри Кнута третий том книги "Искусство програмирования"
том называется "Сортировка и поиск" Я не уверен, но по вроде там
что-то есть.
1




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


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