Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 03.03.2011, 16:57
Новичок

Отправить личное сообщение для alfur79 Посмотреть профиль Найти все сообщения от alfur79
 
Регистрация: 03.03.2011
Сообщений: 2

редукция однонаправленного графа
День добрый!

Есть конечный набор данных:
Список исходящих узлов VO = [o1, o2, o3, ...]
Список конечных узлов VI = [i1, i2, i3, i4, ...]
Список граней E = [[o1, i1], [o1, i2], [o1, i3], [o2, i1], [o2, i2], ...]
По ним строится однонаправленный граф: каждая грань начинается в VO и заканчивается в VI.

Задача:
построить кратчайший список "обобщённых граней", например
EO = [[[o1, o2], [i1, i2]], [[o1], [i3]], [[o2], [i2]]]

Что из мат. методов можно эффективно применить: минимальные ДНФ, Backtracking (не хотелось бы), архивацию a'la Huffman, ...?

Благодарю за совет,
Константин
  #2  
Старый 03.03.2011, 17:18
гocть

 
Сообщений: n/a

нифига ничего не понятно с вашей странной терминологией... и где это такому учат...

вам дан двудольный граф (множества вершин VO и VI - его доли), и требуется покрыть его множество ребер минимальным числом полных двудольных подграфов (т.е. бикликами)? Эта задача NP-полная, зовется http://en.wikipedia.org/wiki/Bipartite_dimension Так что бэктрэк, да
  #3  
Старый 03.03.2011, 18:01
Новичок

Отправить личное сообщение для alfur79 Посмотреть профиль Найти все сообщения от alfur79
 
Регистрация: 03.03.2011
Сообщений: 2

Сообщение от гocть Посмотреть сообщение
нифига ничего не понятно с вашей странной терминологией... и где это такому учат...
Давно уж отучили, повыветрилось

http://en.wikipedia.org/wiki/Bipartite_dimension
Точно, именно эта задача и есть!

С благодарностью,
Константин
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Визуализация графа vosminog Реализация, исходники, языки 4 20.05.2009 17:19
связность графа гость Графы 4 24.02.2008 20:35
Преобразование графа. гость Графы 1 13.01.2008 03:30
диаметр графа незарегистрированный Графы 3 06.06.2007 21:33
связывание графа RiV Математические алгоритмы 1 29.01.2007 10:33