Теория графов: лучший алгоритм для нахождения комбинации «направлений» ребер, где каждый узел имеет не более одного ребра, направленного на него

Question

Я имею дело с графиком, где есть определенное количество узлов, и между ними есть предопределенные связи, у которых пока нет «направлений».

Проблема состоит в том, чтобы дать всем ребрам направление (например, если есть связь между А и В, задайте этому ребру направление А-> В или В-> А) таким образом, чтобы ни один узел не находился на приемный конец более чем одного края.

Примеры: Для этой модели (A-B-C) A-> B-> C работает, но A-> B <-C не работает, так как B находится на приемном конце более чем одного соединения. Хотя A <-B-> C работает, так как B находится на подающем конце обоих своих соединений.

Я пробовал обнаружение петель, но тот факт, что эти узлы могут быть произвольно связаны друг с другом, могут быть многочисленные петли, которые могут или не могут быть напрямую связаны друг с другом, я не мог найти решение для использования информации.

Количество узлов может быть к северу от тысяч, а в моем случае количество соединений может быть много сотен. Это также исключает грубую силу.

Не гарантируется, что будет определенное решение, цель алгоритма - найти комбинацию, в которой наименьшее количество соединений приводит к тому, что узлы имеют более одного ребра, указывающего на них.

Answer 1

Это продолжение ответа Диллона Дэвиса .

После удаления древовидных ветвей и разрешения простых циклов оставшийся граф имеет узлы степени 2 или более. Я предлагаю, чтобы (для анализа графа) все узлы степени 2 были удалены.

Позвольте мне объяснить на примере. В этом примере, когда узел представлен числом, это число является степенью узла. Когда узел представлен буквой, этот узел имеет степень 2. Таким образом, график

3 - A - B - C - 4

представляет узел степени 3, связанный с цепочкой узлов степени 2, связанный с узлом степени 4.

Два идеальных варианта для этого раздела графика:

3 -> A -> B -> C -> 4
3 <- A <- B <- C <- 4

Они идеальны в том смысле, что каждый буквенный узел имеет ровно один входящий фронт. Я полагаю, что это не просто идеальный выбор, это выбор only . Рассмотрим первое идеальное решение

3 -> A -> B -> C -> 4

Если узел 4 имеет слишком много входящих ребер, мы можем уменьшить его количество, вернув ребро в C, давая

3 -> A -> B -> C <- 4

Но это не улучшило ситуацию, оно торгует "слишком много ребер в 4" с "слишком много ребер в C" . Впоследствии изменение границы между C и B разрешает C, но разрывает B. Продолжайте поворачивать вдоль цепи, и в конечном итоге связь между A и 3 меняется на противоположную, и мы пришли ко второму идеальному решению.

Что приводит меня к выводу, что (для целей анализа)

3 - A - B - C - 4

эквивалентно

3 - 4

Так как это полезно для упрощения проблемы. Рассмотрим следующий график:

Когда узлы A и B удалены, оставшийся край соединяет верхний узел 3 с самим собой, так что край может быть удален. Аналогично для C и D. Что оставляет график с одним ребром. Выберите любое направление для этого края. Затем завершите решение, выбрав направление для простого цикла A-B-3, и независимо выберите направление для простого цикла C-D-3.

Вот еще один пример:

В этом случае удаление A и B создает избыточные ребра между оставшимися узлами. После удаления лишних ребер выберите любое направление для ребра. Направление этого ребра определяет направление цикла 3-A-3 и цикла 3-B-3.

Answer 2

Не полный алгоритм, но, учитывая ваше описание проблемы в комментариях, я чувствую, что эти шаги, вероятно, вернут проблему обратно в грубый диапазон.

Во-первых, вы должны «обрезать» свой график. Любые узлы первой степени следует обрезать так, чтобы их связанный край был направлен на обрезанный узел. Поскольку никакое другое ребро не может указывать на этот узел, мы знаем, что этот выбор является оптимальным. Промойте и повторяйте, пока все оставшиеся узлы не будут иметь два или более ребер.

Далее, как вы упомянули, вы должны исключить любые изолированные узлы. Вы можете расширить это до подключенных компонентов size <= 3. Это связано с тем, что для максимум трех узлов количество ребер не может превышать количество узлов, поэтому вы можете случайным образом назначить одно ребро, а остальные станут на свои места.

Теперь то, что останется, это куча больших, сильно связанных, связанных компонентов. Вы могли бы на самом деле сделать еще одну проверку и посмотреть, образуют ли какие-либо из них один цикл (все узлы степени два), а затем случайным образом назначить одно ребро, но это, вероятно, довольно редкий случай. Вы, вероятно, просто захотите начать грубое форсирование каждого из них независимо. Вероятно, было бы лучше начать сначала с узлов с наименьшим числом ребер, обновляя степень узлов при назначении ребер (а также обрезая ребра в любом градусе, как раньше), при необходимости возвращая их обратно.

Answer 3

Я не был уверен в добавлении другого ответа, но ответ от user3386109 дал мне понимание того, что я считаю законченным решением, и я чувствовал, что оно слишком сильно отличается от духа моего оригиналаответ для включения в качестве правки.

Напомним, у нас есть несколько инструментов ниже пояса:

• Мы можем оптимально обрезать узлы с одним ребром, повторяя процессдо завершения

• Мы можем назначить направление любому ребру в простом цикле (соединенные компоненты только с узлами степени 2), а остальное последует (оптимально).

• Узлы с двумя ребрами в более сложных циклах можно временно игнорировать, так как их направления ребер будут назначаться узлами более высокой степени.

После прочтения последней точки,сама проблема становится немного яснее.После того, как мы удалили узлы степени один в пуле один, все остальные узлы имеют как минимум два ребра.Мы можем с уверенностью сказать в оптимальном графе, что каждый из этих узлов будет иметь хотя бы одно направленное ребро, указывающее на них.В качестве доказательства, поскольку каждый узел имеет по крайней мере два ребра, но связанный компонент не является простым циклом (иначе это будет исключено в пуле 2), у нас больше ребер, чем узлов.Если какой-либо узел имеет нулевые ребра, направленные к нему, один из этих ребер может быть обращен вспять, чтобы уменьшить количество конфликтующих ребер или «освободить» другой узел, чтобы иметь нулевые внутренние ребра, чтобы затем сделать то же самое.

Вооружившись этим знанием, мы знаем, что минимальное количество конфликтов (дополнительные ребра, направленные на узлы, у которых уже есть ребро, направленное на них), равно количеству ребер минус количество вершин в нашем обрезанном графе.Мы также можем сделать вывод, что до тех пор, пока нам удастся направить по крайней мере одно ребро на каждый узел, у нас будет оптимальный график, независимо от того, как мы рассеиваем конфликтующие ребра.

Изначально я пытался составить алгоритмна основании третьего пункта для выполнения этого задания, но оказывается, что ответ на самом деле намного проще, чем даже.Единственный способ, которым мы можем случайно создать узел без ребер, направленных от него, - это активное направление всех ребер от этого узла.Решение состоит в том, чтобы выбрать одно ребро в подключенном компоненте и назначить ему случайное направление.Затем выполните поиск (DFS, BFS и т. Д.) Вне узла, на который он направлен, назначая направления ребрам по ходу движения в том направлении, в котором вы их проходите.Любой узел, к которому вы достигнете, будет иметь ребро, направленное на него (ребро, которое вы взяли, чтобы добраться до него), а корневой узел будет иметь ребро, которое вы ему присвоили вручную.

В итоге получится график сминимальное количество дополнительных ребер, направленных на узлы.Если вы вместо этого хотите минимизировать количество узлов, содержащих конфликтующие ребра, решите проблему, как указано выше, а затем сформируйте подграф узлов степени три или более и их соединительных ребер.Найдите минимальное покрытие вершин этого подграфа, а затем измените направление ребер, соединяющих узлы, не находящиеся в минимальном покрытии вершин, но содержащие конфликтующие ребра, с соответствующими узлами в минимальном покрытии вершин.