¿Hay alguna ventaja que podamos eliminar sin desconectar el gráfico?

Antes de comenzar, sí, esta es una tarea. No habría publicado aquí si no he estado haciendo todo lo posible para resolver este problema durante las últimas 14 horas y no he llegado a ninguna parte.¿Hay alguna ventaja que podamos eliminar sin desconectar el gráfico?

El problema es el siguiente: Quiero comprobar si puedo eliminar un borde de un gráfico conectado no dirigido sin desconectarlo o no en el tiempo O (V), no solo lineal.

Lo que he alcanzado hasta ahora:

Un borde ciclo se puede retirar sin desconectar el gráfico, por lo que simplemente comprobar si la gráfica tiene un ciclo. Tengo dos métodos que pueden usarse, uno es DFS y luego verifico si tengo bordes posteriores; el otro es contando Vs y Es y comprobando si | E | = | V | - 1, si eso es cierto, entonces el gráfico es un árbol y no hay ningún nodo que podamos eliminar sin desconectarlo.

Ambos enfoques previos resuelven el problema, pero ambos necesitan O (| E | + | V |), y el libro dice que hay una manera más rápida (probablemente sea un enfoque codicioso).

¿Puedo obtener alguna pista, por favor?

EDITAR: Más específicamente, esta es mi pregunta; dado un gráfico conectado G = (V, E), ¿puedo eliminar algunos bordes e en E y tener el gráfico resultante todavía conectado?

Fuente

2012-01-03 Fingolfin

Sea un poco más preciso en la afirmación. ¿Estás preguntando "dado un gráfico conectado G = (V, E), puedo eliminar un borde e particular en E y tener el gráfico resultante todavía conectado?" o "Dado un gráfico como antes, ¿existe algún borde e en E para el cual el gráfico resultante ya no está conectado?" –

Pregunta editada, lo siento. Necesito VERIFICAR si puedo eliminar un borde de E y aún tener el gráfico conectado. – Fingolfin

El término técnico es [bridge] (http://en.wikipedia.org/wiki/Bridge_ (graph_theory)) – sdcvvc

Cualquier cruce recursivo del gráfico, marcando nodos mientras se visitan y cortocircuitando para volver verdadero si alguna vez se topa con un nodo que ya está marcado hará el truco. Esto requiere que O (| V |) atraviese todo el gráfico si no hay borde que pueda eliminarse, y menos tiempo si se detiene antes para volver verdadero.

edición

Sí, un recorrido recusive de todo el gráfico requiere O (| + | | E | V) tiempo, pero sólo atraviesan todo el gráfico, si no hay ciclos - en cuyo caso | E | = | V | -1 y eso solo toma O (| V |) tiempo. Si hay un ciclo, lo encontraremos después de atravesar como máximo | V | bordes (y visitando como máximo | V | +1 nodos), que también toma O (| V |) tiempo.

También, obviamente, al atravesar desde un nodo (que no sea el primero), no considera el borde que solía llegar al nodo, ya que eso le haría ver inmediatamente un nodo ya visitado.

Fuente

2012-01-03 02:47:07

¿Puede explicarme su razonamiento aquí, señor? Ejecutar el procedimiento de exploración recursivo en un gráfico conectado normalmente toma O (| E | + | V |) porque necesito O (V) para marcar los nodos, y O (2 | E |) simplemente para verificar los bordes que conectan los nodos . Recursivo o no, esto no se acerca a O (| V |), entonces, ¿cómo devolver verdadero cuando se contrarresta un nodo visitado se reduce a O (V)? Además, si devuelvo el valor verdadero al contrarrestar una visita, en realidad podría regresar verdadero mientras hago un seguimiento retroactivo desde un receptor, podría decir que tengo un ciclo mientras todavía no he verificado si lo hago o no. – Fingolfin

¡Guau! ¡Esto ahora tiene perfecto sentido! ¡Muchas gracias, señor! – Fingolfin

Aha. Pensé que habría algún truco que implique | E | = | V | -1 pero estoy muerto de cerebro después de las vacaciones y no lo vi. –

De lo que estoy leyendo, DFS sin repetición se considera O (| V |), así que si toma el borde e, y deja los dos vértices que conecta ser uyv, si ejecuta DFS desde usted, ignorando e, puedes conjeturar que e no es un puente si v es descubierto, y dado que DFS sin repetición es O (| V |), entonces esto sería, supongo que se consideraría O (| V |).

Fuente

2012-01-03 02:30:07 PlexQ

No, un DFS completo, incluso sin repetición sigue siendo O (| V | + | E |) ya que necesita mirar todos los bordes para asegurarse de que no vayan a los nodos que aún no ha visitado. Sin embargo, si detiene el recorrido tan pronto como encuentre un bucle, eso solo requiere mirar a lo sumo | V | bordes. –

Creo que debería haber aclarado, parecía obvio que una vez que encuentras v, has demostrado que e no es un puente y, por lo tanto, has respondido el problema, a veces te olvidas de que no puedes dar nada por sentado en las pruebas: D – PlexQ

Lista todos los bordes E y toma un borde y marca uno por uno los dos vértices finales visitados. Si durante el recorrido encontramos que los dos vértices han sido visitados anteriormente por algunos bordes y podemos eliminar ese borde.

Tenemos que tomar bordes como máximo | V | tiempo para ver si esta condición satisface.

Peor caso puede ser así, cada vez que tomemos una ventaja visitará al menos un nuevo vértice. Luego están | V | vértices y tenemos que tomar | V | bordes para ese borde particular que se encuentra.

El mejor caso puede ser el que tiene | V |/2 + 1 e

Fuente

2017-04-04 22:17:35 YashM

¿Hay alguna ventaja que podamos eliminar sin desconectar el gráfico?

Respuesta

Cuestiones relacionadas