Ненаправленное преобразование графа в дерево

Question

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

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

См. Примеры графиков ниже.Как мы находим красный узел?

Answer 1

Вот предложение о том, как решить вашу проблему.

предпосылки

• нотация:
  
  • g граф, g.v вершины графа
  • v,w,z: отдельные вершины
  • e: отдельное ребро
  • n: количество вершин
• любая комбинация неориентированного дерева g и данного узла gv однозначно определяетнаправленное дерево с корнем gv (доказуемо по индукции)

idea

• дополняют края g ориентациями в направленном дереве, подразумеваемыми g, ипока еще не найденный корневой узел с помощью локальных вычислений в узлах g.
• , эти ориентации будут представлять отношения "ребенок-родитель" между узлами (v -> w: v child, wparent).
• полностью помеченное дерево будет содержать единственный узел с конечной степенью 0, который является искомым корневым узлом.у вас может получиться 0 или более корневого узла.

алгоритм

предполагает стандартное представление структуры графа / дерева (например, списка смежности)

1. все вершины в g.v помечены изначально как не посещенные, не завершенные.

2. посещение всех вершин в произвольной последовательности.пропустить узлы, помеченные как «законченные».
   пусть v будет текущей посещенной вершиной.

   • 2.1 разверните все ребра, связывая v по часовой стрелке, начиная со случайно выбранного e_0 в порядке угла ребра с e_0.

   • 2.2,сориентируйте смежные края e_1=(v,w_1), e_2(v,w_2), которые заключают в себе острый угол.
     смежных: по порядку в соответствии с углом, который они охватывают с e_0.

     [примечание: существование такой пары не гарантируется, см. 2-й комментарий и последнее замечание.если нет острого угла, переходите к следующему узлу на 2.]

     • 2.2.1 известны ориентации ребер e_1, e_2:

       • w_1 -> v -> w_2: невозможно, поскольку сегмент «дедушка-родитель-потомок»острый угол
       • w_1 <- v <- w_2: невозможно, по той же причине

       • w_1 <- v -> w_2: невозможно, в дереве нет узлов со степенью> 1

       • w_1 -> v <- w_2:
         возможна только пара ориентаций.e_1, e_2, возможно, был ориентирован раньше.если предыдущая ориентация нарушает текущее назначение, экземпляр проблемы не имеет решения.

     • 2.2.2 это назначение подразумевает древовидную структуру на подграфах, созданную всеми вершинами, достижимыми из w_1 (w_2) на пути, не содержащем e_1 ( e_2`).пометить все вершины в обоих индуцированных поддеревьях как законченные

       [примечание: структура поддерева может нарушать ограничения угла.в этом случае проблема не имеет решения.]

   • 2,3 балла v посещений.после выполнения шагов 2.2 в вершине v, проверьте число nc ребер, соединяющих, которым еще не была назначена ориентация.

     • nc = 0: это корень, который вы искалидля - но вы должны проверить, совместимо ли решение с вашими ограничениями.

     • nc = 1: пусть это ребро будет (v,z).
       ориентация этого ребра v-> z какты на деревепометьте v как завершенное.

       • 2.3.1 проверьте z, отмечено ли оно как завершенное.если это не так, проверьте число nc2 неориентированных ребер, соединяющих z.nc2 = 1: повторите шаг 2.3, взяв z за v.

3. если вы еще не нашли корневой узел, ваш экземпляр проблемы неоднозначен: сориентируйте оставшиеся неориентированные ребра по желанию.

примечания

1. завершение: каждый узел посещается максимум 4 раза:

   • один раз за шаг 2
   • при макс. Дважды за шаг 2.2.2
   • при макс. Один раз за шаг 2.3

2. правильность:

   • все ребра, окружающие острый угол, ориентированы в соответствии с шагом 2.2.1

3. сложность (время):

   • посещение каждого узла: O (n);

   • Для обхода всех ребер, соединяющих данную вершину, по часовой стрелке требуется сортировка этих ребер.
     таким образом, вам нужно O( sum_i=1..m ( k_i * lg k_i ) ) в m <= n вершинах с ограничением sum_i=1..m k_i = n.

     Всего

     для этого требуется O ( n * lg n), так как sum_i=1..m ( k_i * lg k_i ) <= n * lg n с учетом sum_i=1..m k_i = n для любого m <= n (доказывается путем применения оптимизации Лагранжа).

     [примечание: если ваши деревья имеют степень, ограниченную константой, вы теоретически сортируете по постоянному времени в каждом затронутом узле; общая сумма в этом случае: O(n)]

   • маркировка поддерева:
     эта процедура посещает каждый узел в графике максимум 2 раза, если он реализован как dfs. таким образом, общая сумма O(n) для вызова этой подпрограммы.

     всего: O(n * lg n)

4. сложность (пробел):

   • O(n) для сортировки (с степенью вершины без постоянной привязки).

5. проблема, вероятно, плохо определена:

   • несколько решений: например, Штейнер дерево
   • нет решения: например, график в форме стрелки с двойным наконечником (<->)

Answer 2

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