Построение графа с заданными ограничениями

Дано:

  • Список узлов
  • Список узлов, к которым эти узлы могут подключаться
  • Ограничения, что каждый узел должен подключаться к одному и только одному другому узлу (одностороннее соединение)
  • Все узлы должны быть доступны, начиная с любого узла

Существует ли алгоритм, который дал бы мне такой граф, если это возможно построить, или иным образом дал бы мне граф с максимально возможным числом узлов?

Можно ли это сделать за полиномиальное время?

В противном случае, существует ли алгоритм, который дает достаточно хорошее решение достаточно быстро?


graph algorithm graph-algorithm
person Dan    schedule 05.03.2012    source источник
comment
Полиномиальное время, разумеется - O(n(n-1)/2), если только сами ограничения не зависят от количества узлов.   -  person Alien Life Form    schedule 05.03.2012
comment
это стандартная проблема; Я думаю, вы запутались, поскольку вам дан список узлов, зачем тогда спрашивать наибольшее количество узлов? Узлы не меняются... Что достаточно быстро? Я. вы можете сделать это за полиномиальное время.   -  person Adrian    schedule 05.03.2012
comment
Второй список узлов, это карта? каждый узел в списке1 может подключаться к любому узлу в списке2? или какая-то конкретика?   -  person amit    schedule 05.03.2012
comment
Я забыл ограничение, мне нужно, чтобы все узлы были доступны со всех узлов. У меня не может быть A-›B-›C-›A и D-›E-›F-›D   -  person Dan    schedule 05.03.2012
comment
Я предполагаю, что 3. запрос должен быть обновлен до: каждый узел должен подключаться к двум другим узлам или что-то подобное.   -  person watbywbarif    schedule 05.03.2012
comment
Я отредактировал, чтобы прояснить, что соединения являются односторонними.   -  person Dan    schedule 05.03.2012
comment
@Dan: я не понимаю ввода. Это два списка? или типа карты? Чем вершина A отличается от вершины B, если они обе находятся в первом списке? Или это карта, отображающая каждую вершину в список возможных узлов?   -  person amit    schedule 05.03.2012
comment
@amit: ввод представляет собой список узлов (скажем, A, B, C и D) и список вершин, которые они могут иметь (A может быть подключен к B или D, B может быть подключен к A, C или D, C может быть соединен с D и т. д.). Для каждого узла я хочу выбрать одну вершину, к которой он будет подключаться, при этом гарантируя, что я могу следовать по пути из любой точки графа в любую другую точку.   -  person Dan    schedule 05.03.2012

Ответы (2)


arrow_upward
2
arrow_downward

Если я правильно понимаю, вы пытаетесь найти гамильтоновский цикл, который является NP-полная проблема.

Почему задача эквивалентна поиску гамильтонова цикла:

Пусть n будет количеством узлов. Учитывая ограничение, что каждый узел соединен ровно с одним другим узлом, решение имеет n ребра. Поскольку каждый узел должен быть достижим, каждый узел будет хвостом по крайней мере одного ребра. Но решение имеет n ребра, поэтому каждый узел будет хвостом ровно ребра. Таким образом, решение представляет собой объединение путей. Ограничения, заключающиеся в том, что все ребра должны быть достижимы из всех других ребер, делают решение гамильтоновым циклом.

person Edouard    schedule 05.03.2012
comment
Это правильно: данная задача эквивалентна нахождению гамильтонова цикла. Было бы неплохо, если бы вы могли показать, почему они эквивалентны. - person interjay; 05.03.2012
comment
Это не гамильтонов цикл, может быть, это может быть минимальный гамильтонов путь, также известный как. Коммивояжер с NP-трудностью - person watbywbarif; 05.03.2012
comment
@amit: единственный способ решить данные ограничения - создать гамильтонов цикл. Ваше решение дерева со всеми листьями, позже связанными с корнем, не соответствует ограничениям, потому что корень должен быть подключен более чем к одному узлу. - person interjay; 05.03.2012
comment
@interjay - я отредактировал свой ответ, чтобы показать, почему вопрос сводится к поиску гамильтонова цикла. - person Edouard; 05.03.2012
comment
+1 Хороший ответ, жаль, что был принят неправильный ответ. - person interjay; 05.03.2012
comment
@interjay Да, хорошо, при поиске ссылок одно условие редактируется, а другое добавляется, и теперь вы ставите минусы: D - person watbywbarif; 05.03.2012

arrow_upward
0
arrow_downward

Поиск алгоритма направленного минимального связующего дерева.

Это выглядит нормально: http://www.utdallas.edu/~rbk/papers/dmdst.pdf

Также проблема является NP-сложной.

РЕДАКТИРОВАТЬ: после редактирования это проблема с направленным гамильтоновым циклом -полный

person watbywbarif    schedule 05.03.2012
comment
Хех, учитывая ваше ограничение на количество максимальных подключений, это сводится к проблеме коммивояжера. - person watbywbarif; 05.03.2012
comment
Направленное остовное дерево не соответствует заданному ограничению, состоящему в том, что любой узел достижим из любого другого. Например, корень не будет доступен с любого другого узла. - person interjay; 05.03.2012
comment
@interjay Да, но это условие было добавлено позже;) - person watbywbarif; 05.03.2012
comment
Ну, это было добавлено за 7 минут до вашего ответа. Также кажется неправильным говорить о минимальном остовном дереве и коммивояжере, когда ребра не имеют весов. - person interjay; 05.03.2012
comment
@interjay Нет, оба можно использовать без весов, используя вес = 1. Но теперь я вижу, что нет никаких ограничений, согласно которым граф должен быть минимальным, я думал, что был, поэтому мы вернулись к базовому гамильтонову циклу. Смешной - person watbywbarif; 05.03.2012