Как определить, не нарушит ли ребро граф?

Question

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

Хорошо, вот мой вопрос: можно ли при удалении ребра определить в постоянное время (т. Е. С помощью алгоритма O (1)), делит ли это граф на два непересекающихся подграфа? Если это так, то какой стороне края будет принадлежать корневой узел?

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

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

Редактировать: граф является ориентированным графом.

Редактировать 2: ОК, возможно, я могу ограничить дело удалением ребер из корневого узла . [Правка 3: нет, на самом деле] Кроме того, ни одно ребро не попадает в корневой узел.

Answer 1

Чтобы немного ускорить процесс по сравнению с очевидным решением O (| V | + | E |), вы можете сохранить остовное дерево, которое довольно легко обновлять при изменении графика.

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

Итак, лучший вариант O (1), наихудший O (| V | + | E |), но в любом случае достаточно простой для реализации.

Answer 2

Это ориентированный граф? Ниже предполагается ненаправленный.

То, что вы ищете, является ли данный ребро Мостом на графике. Я полагаю, что это может быть найдено с использованием обхода, ищущего циклы, содержащие это ребро и равные O (| V | + | E |).

O (1) - слишком много, чтобы спрашивать.

Возможно, вы захотите сохранить 2-реберные соединенные компоненты в динамических графах.

У Эппштейна и др. Есть статья на эту тему: http://www.ics.uci.edu/~eppstein/pubs/EppGalIta-TR-93-20.pdf

, который может поддерживать 2-реберные соединенные компоненты на графике из n узлов, где допускаются вставки и удаления ребер. Он имеет время O (sqrt (n)) на обновление и время O (log n) на запрос.

Таким образом, каждый раз, когда вы удаляете, вы можете запросить O (logn), чтобы определить, изменилось ли количество подключенных компонентов 2-ребра. Я полагаю, он также может сказать вам, в каком компоненте находится конкретный узел.

Эта статья носит более общий характер и применяется к другим задачам с графами, а не только к двум компонентам, связанным с ребрами.

Я предлагаю вам начать поиск мостов и динамических 2-х гранных соединений.

Надеюсь, это поможет.

Answer 3

Как сказал Морон как раз перед этим, вы на самом деле ищете Мост в своем графике.

Теперь мост - это ребро с описанным атрибутом, которое также начинается и заканчивается Cut Vertexes .Вырезанная вершина - это именно то, чем является Мост, но в редакции вершины (узла).

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

Для определения, является ли узел в графе отрезанной вершины, требуется O (m + n), гдеm = # ребер и n = # узлов.

Приветствия