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.
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.
comp
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.
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.
comp: aún noT: aún noSin 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.