Как обнаружить, если повреждение края сделает график непересекающимся?
У меня есть график, который начинается с единственным, корневым узлом. Узлы добавляются один за другим к графику. Во время создания узла они должны быть связаны или с корневым узлом, или с другим узлом, единственным краем. Края могут также быть созданы и удалены (один за другим между любыми двумя узлами). Узлы могут быть удалены по одному. Узел и граничное создание, операции удаления могут произойти в любом произвольном порядке.
Хорошо, таким образом, вот мой вопрос: То, когда край удален, он возможный действительно определяет в постоянное время (т.е. с O (1) алгоритм), если выполнение этого разделит график на два непересекающихся подграфа? Если это будет, то, какая сторона края корневой узел будет принадлежать?
Я готов поддержать в разумных пределах, любая дополнительная структура данных, которая может упростить деривацию этой информации.
Возможно, не возможно сделать это в O (1), раз так любые указатели на литературу будут цениться.
Править: График является ориентированным графом.
Редактирование 2: хорошо, возможно, я могу ограничить случай удалением краев от корневого узла. [Редактирование 3: не, на самом деле] кроме того, никакой край не приземляется в корневой узел.
3 ответа
Это направленный граф? Ниже предполагается, что неориентированный.
Вы ищете, является ли данное ребро мостом в графе. Я полагаю, что это можно найти с помощью обхода в поисках циклов, содержащих это ребро, и это будет O(|V| + |E|).
O(1) - это слишком много.
Возможно, вам пригодится поиск 2-кратных связных компонент в динамических графах.
У Эппштейна и др. есть статья на эту тему: http://www.ics.uci.edu/~eppstein/pubs/EppGalIta-TR-93-20.pdf
которая может поддерживать 2-гранные связные компоненты в графе из узлов, где разрешены вставки и удаления ребер. Он имеет время O(sqrt(n)) на обновление и O(log n) на запрос.
Таким образом, при любом удалении вы можете сделать запрос за O(logn), чтобы определить, изменилось ли количество 2-краевых связных компонентов. Я предполагаю, что это также может сказать вам, в каком компоненте находится конкретный узел.
Эта статья более общая и применима к другим проблемам графов, а не только к компонентам с 2-кратной связностью.
Я предлагаю вам поискать мосты и динамическую 2-кратную связность для начала.
Надеюсь, это поможет.
Чтобы немного ускорить процесс по сравнению с очевидным решением O (| V | + | E |), вы можете сохранить связующее дерево, которое довольно легко обновлять по мере изменения графа.
Если в остовном дереве удалено ребро , а не , то граф не разъединяется и ничего не делает. Если ребро в связующем дереве удалено, вы должны попытаться найти новый путь между этими двумя вершинами (если вы его найдете, используйте его для обновления связующего дерева, в противном случае граф отключится).
Итак, в лучшем случае O (1), в худшем случае O (| V | + | E |), но в любом случае довольно просто реализовать.
как только что сказал Морон, на самом деле вы ищете Мост на своем графике.
Теперь Мост - это ребро, которое имеет описанный атрибут, а также берет начало и заканчивается в Cut Vertexes . Вырезанная вершина - это в точности то, что есть мост, но в версии вершины (узла).
Таким образом, единственный способ (хотя и весьма отклоняющий гипотезу начальной структуры данных), который я могу придумать, получить сложность O (1) для этого, - это если вы сначала проверите каждый узел в своем графике, если это разрезанная вершина и затем просто в постоянное время проверяйте, прикреплено ли ребро, которое вы хотите удалить, к одному из этих двух.
Чтобы определить, является ли узел в графе вырезанной вершиной, требуется O (m + n), где m = # ребер и n = # узлов.
Приветствую