← Volver a los ejercicios

El árbol de puentes paso a paso

Borrar los puentes de un grafo no dirigido lo parte en componentes 2-arista-conexos. Si cada pedazo se encoge a un nodo y cada puente se deja como arista entre esos nodos, lo que queda es un árbol, y sobre un árbol casi todo es un recorrido. Se construye en tres pasadas: los puentes con Tarjan, un etiquetado que no los cruza y una pasada por las aristas puente. Aquí se hacen las tres, en orden.

1. El grafo y la predicción

Grafo:

Entrada: un grafo no dirigido conexo de , sin aristas repetidas.  Salida: el árbol de puentes. La profundidad arranca en el 0 y recorre los vecinos de menor a mayor.

━ puente el número gris sobre cada arista es su identificador sobre cada vértice, su comp
¿Cuántos nodos va a tener el árbol?

2. Primera pasada: los puentes

Una arista de árbol (v, w), con w hijo de v, es puente cuando low[w] > d[v], con desigualdad estricta. Una arista de retroceso nunca lo es. Marque las que lo son.

3. Segunda pasada: el etiquetado

Para cada vértice sin componente, un recorrido que no cruza puentes; a todo lo que alcanza se le pone el mismo número. Esa es la única condición del recorrido, y es la que separa los pedazos. Escoja el comp de cada vértice, numerando desde el 0 en el orden en que el código abre los componentes.

4. Las pasadas dos y tres, línea por línea

Recorrido:
pila: vacía
comp: aún no
T: aún no
Paso 0 de 0

5. El árbol que queda

6. Para llevarse

Sin solución aquí. En el tercer grafo, agregue una arista entre los dos vértices que son hoja del árbol y vuelva a construirlo: ¿cuántos nodos tiene ahora y qué forma tiene? Después conteste con el segundo grafo: si el árbol de puentes tiene L hojas, ¿cuántas aristas nuevas hacen falta como mínimo para que el grafo quede sin ningún puente, y entre cuáles vértices se ponen? Y por último, en el primer grafo, quite el etiquetado de la segunda pasada y use en su lugar una profundidad corriente: diga qué nodos y qué aristas pierde el árbol.