Есть ли ребро, которое мы можем удалить, не отключая график?

Question

Прежде чем я начну, да, это домашнее задание.Я не написал бы здесь, если бы не пытался изо всех сил, чтобы решить эту проблему в течение последних 14 часов и не получил нигде.

Проблема заключается в следующем: я хочу проверить, могу ли яудалить ребро из связанного неориентированного графа, не отключая его или нет за время O (V), а не просто линейно.

То, чего я достиг к этому моменту:

Ребро цикла можно удалить безотключив график, поэтому я просто проверяю, есть ли на графике цикл.У меня есть два метода, которые можно использовать, один из них - DFS, а затем проверка, есть ли у меня задние края;другой - путем подсчета Vs и Es и проверки, если | E |= | V |- 1, если это так, тогда граф является деревом, и нет узла, который мы можем удалить, не отключая его.

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

Могу ли я получить какие-либо подсказки, пожалуйста?

РЕДАКТИРОВАТЬ: Более конкретно, это мой вопрос;учитывая связный граф G = (V, E), могу ли я удалить некоторое ребро e в E и получить ли полученный граф еще связным?

Answer 1

Любой рекурсивный обход графа, маркировка узлов по мере их посещения и короткое замыкание для возврата true, если вы когда-либо столкнетесь с узлом, который уже отмечен, сделают свое дело. Для обхода всего графа требуется O (| V |), если нет ребра, которое можно удалить, и меньше времени, если он останавливается рано, чтобы вернуть true.

редактировать

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

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

Answer 2

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

Мы должны взять ребра не более | V | время посмотреть, удовлетворяет ли это условие.

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

Наилучший случай может быть с | V | / 2 + 1 е

Answer 3

Из того, что я читаю, DFS без повторений считается O (| V |), поэтому, если вы берете ребро e, и пусть две вершины, которые он соединяет, будут u и v, если вы запускаете DFS из u, игнорируя e , вы можете предположить, что e не является мостом, если v обнаружен, и учитывая, что DFS без повторений есть O (| V |), то это, я думаю, будет считаться O (| V |).