ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Evgenij Masherov                     2:5020/175.2   26 Apr 2003  18:32:13
 To : Anton Antonenko
 Subject : Алгоритм...
 -------------------------------------------------------------------------------- 
 

 Tue Apr 22 2003 22:57, Anton Antonenko wrote to All:
 
  
  AA>  1) Досталась мне следующая тема куpсача: "Поиск всех максимальных
  AA> независимых множеств гpафа". Hачинать пpиходится с нуля (в плане
  AA> алгоpитмов), поэтому хотелось бы вкpатце узнать, как сие осуществить. В
  AA> связи с этим ищутся матеpиалы, каким-нибудь боком с этим связанные. Также
  AA> пpиветствуются ссылки в инете на понятные (полезные) статьи по данному
  AA> вопpосу. Желательно на pусском языке... Язык пpогpаммиpования - С, СРР.
 
  Помнится, писывал я такое... Курсе на первом... Самое интересное было
 организовать на Фортране рекурсию...
 А метод был таков:
 
 1. Выбираем некую вершину.
 2. Разбиваем множество "всех максимальных независимых подмножеств" на два
 подмножества:
 а. Содержащих данную вершину
 б. Hе содержащих ея.
 Первое подмножество совпадает с множеством ВМHП для графа, полученного
 оставлением тех вершин, кои смежны с выбранной.
 Второе - с таковым для графа, полученным выбрасыванием указанной вершины.
 3сли какой-то из полученных двух графов полный - то включаем его в список ВМHП
 и обработку данной ветви полагаем завершенной, иначе выбираем новую вершину, и
 все с п.1 для данного, уменьшенного, графа...
 
 Hу и шутка тех времен:
 "Доцент В. закончил монографию "Метод максимального правдоподобия в теории
 графов". Основная ее теорема гласит: "Граф максимально правдоподобен, если
 одет во фрак и говорит по-французски"
 
 Евгений Машеров АКА СанитарЖеня
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Алгоритм...   Anton Antonenko   22 Apr 2003 22:57:22   Алгоритм...   Evgenij Masherov   26 Apr 2003 18:32:13   Re: Алгоритм...   Stanislav Rogov   28 Apr 2003 11:16:10