Problemas de cortes · AyG C11¶
Viernes 9 de octubre de 2026.
Una sola búsqueda en profundidad deja \(v.d\) y \(v.low\) en cada vértice, y con esos dos números salen los puntos de articulación y los puentes en \(\Theta(V+E)\). El problema es que casi ningún enunciado de juez se queda ahí. Pide orientar calles, contar en cuántos pedazos queda una red, medir distancias. La lista de puentes es un paso intermedio, no la respuesta. La pregunta de la sesión es qué se construye con los puentes para que esas preguntas se vuelvan fáciles, y la respuesta es contraer: se encogen a un nodo los pedazos que quedan al quitarlos, y lo que resulta es un árbol. Sobre un árbol casi todo es un recorrido más.
Al terminar la sesión se espera poder:
- Construir el árbol de puentes de un grafo no dirigido en \(\Theta(V+E)\) y demostrar que lo que sale es un árbol.
- Reconocer, leyendo un enunciado de juez, si el corte que pide es por vértice o por arista.
- Orientar las calles de una ciudad para que quede fuertemente conexa, y decir cuáles no se pueden orientar.
- Contar en cuántos pedazos queda una red al quitarle un vértice, con los hijos de la raíz y la comparación \(w.low \geq v.d\).
- Escribir la profundidad con pila explícita cuando la entrada pasa del límite de recursión de Python.
Diapositivas¶
clase11-problemas-cortes.pdf, 162 páginas. Los grafos van dibujados: el de diez vértices con los tres puentes en rojo, el mismo con \(d/low\) debajo de cada vértice, el mismo con cada componente encerrado en una caja, el árbol de puentes que sale de contraerlo, la ciudad de siete intersecciones en sus tres versiones (sin orientar, orientada por el número de la intersección y orientada con la profundidad) y la red de ocho estaciones. Capital trae su muestra y el caso de dos sumideros, cada uno con su condensación, e Interplanetary el mapa de planetas, suelto y con los componentes encajonados.
Recuento¶
Los tres criterios¶
Definición (\(v.low\), CLRS Problema 22-2). \(v.low = \min\{\, v.d,\ w.d : (u,w) \text{ es de retroceso para algún descendiente } u \text{ de } v \,\}\).
Es lo más arriba del árbol a donde se llega desde el subárbol de \(v\) con un solo salto de retroceso. En un grafo no dirigido solo hay aristas de árbol y de retroceso (Teorema 22.10 de CLRS), así que no hace falta llevar pila de vértices sin componente como en Tarjan: basta excluir la arista por la que se bajó.
Teorema (la raíz, CLRS Problema 22-2a). La raíz de un árbol de la profundidad es punto de articulación si y solo si tiene al menos dos hijos en ese árbol.
Teorema (los demás vértices, CLRS Problema 22-2b). Un vértice \(v\) que no es raíz es punto de articulación si y solo si tiene un hijo \(w\) con \(w.low \geq v.d\).
Teorema (los puentes, CLRS Problema 22-2). Una arista de árbol \((v,w)\), con \(w\) hijo de \(v\), es puente si y solo si \(w.low > v.d\). Una arista de retroceso nunca es puente.
El recorrido completo, con las demostraciones de los tres criterios, está en la nota del valor low. Aquí van solo los dos detalles que esta sesión usa de otra manera.
La desigualdad estricta¶
Los dos criterios comparan el mismo par de números y no admiten lo mismo en la igualdad. Con \(w.low = v.d\) hay un retroceso desde el subárbol de \(w\) hasta \(v\) mismo. Contra la articulación ese salto no sirve, porque \(v\) es el que se quita; contra el puente sí, porque \(v\) se queda y cierra un ciclo que contiene a \((v,w)\). De ahí el \(\geq\) en uno y el \(>\) en el otro.
La arista de entrada se excluye por su identificador¶
Preguntar v != padre alcanza mientras no haya dos aristas entre el mismo par
de vértices. Si las hay, la segunda copia es un retroceso legítimo hasta el
padre, queda descartada por error, y una arista doble sale como puente sin
serlo. Dos vías entre las mismas dos estaciones forman un ciclo de longitud
dos: ninguna de las dos es puente.
El arreglo es numerar las aristas. Cada vecino viene con el número de su
arista y la comparación pasa a ser i != entrada, que distingue las dos
copias porque tienen identificadores distintos. Las aristas repetidas se
manejan entonces igual que las demás, sin un caso aparte, y es la forma en que
está escrito todo el código de esta sesión.
Lo que cuesta no cambia: una profundidad, \(\Theta(V+E)\), para las dos respuestas a la vez.
El árbol de puentes¶
Por tanteo¶
El grafo de la sección tiene diez vértices y doce aristas: un triángulo \(0\)–\(1\)–\(2\), el vértice \(3\) colgando entre dos puentes, el triángulo \(4\)–\(5\)–\(6\) y el triángulo \(7\)–\(8\)–\(9\). La lista de aristas, en el orden en que el código las numera de \(0\) a \(11\), es \(0\)–\(1\), \(1\)–\(2\), \(2\)–\(0\), \(2\)–\(3\), \(3\)–\(4\), \(4\)–\(5\), \(5\)–\(6\), \(6\)–\(4\), \(5\)–\(7\), \(7\)–\(8\), \(8\)–\(9\), \(9\)–\(7\). Los puentes son \(2\)–\(3\), \(3\)–\(4\) y \(5\)–\(7\).
Bórrelos. ¿Cuántos pedazos quedan y quién está en cada uno? Y después: si cada pedazo se encoge a un solo nodo y los tres puentes se dejan como aristas entre esos nodos, ¿qué forma tiene el dibujo que queda?
Quedan cuatro pedazos y tres aristas entre ellos, y el dibujo es un camino. Que no se cierre ningún ciclo no es casualidad. Una arista dentro de un ciclo nunca es puente, de modo que los puentes son precisamente las aristas por las que no hay por dónde volver.
Los componentes 2-arista-conexos¶
Definición. Los componentes 2-arista-conexos de un grafo no dirigido \(G\) son los componentes conexos del grafo que queda al borrar de \(G\) todas sus aristas puente.
Adentro de un componente no queda ningún puente, y el argumento es corto. Una arista \(e\) que sobrevive al borrado no es puente de \(G\), así que está en un ciclo de \(G\). Ninguna arista de ese ciclo es puente, luego el ciclo entero sobrevivió y vive dentro de un solo componente. Entonces \(e\) tampoco es puente de su componente.
Hay una lectura equivalente que explica el nombre: dos vértices distintos caen en el mismo componente exactamente cuando hay entre ellos dos caminos sin ninguna arista en común. Es el teorema de Menger para aristas, que este curso no demuestra. La definición de arriba es la que se programa.
No son los componentes biconexos. Los 2-arista-conexos reparten los vértices: cada uno cae en exactamente uno. Los biconexos reparten las aristas, y un punto de articulación queda en varios a la vez. Unos se obtienen quitando puentes; los otros, quitando puntos de corte.
El árbol¶
Teorema. Sea \(G\) un grafo no dirigido conexo. Sea \(T\) el grafo cuyos nodos son los componentes 2-arista-conexos de \(G\) y que tiene una arista \(\{\,comp(u), comp(v)\,\}\) por cada puente \((u,v)\) de \(G\). Entonces \(T\) es un árbol.
Demostración. Se procede en dos partes: la conexidad de forma directa, y la ausencia de ciclos por contradicción.
La conexidad. Un camino de \(G\) entre dos vértices cualesquiera recorre vértices de uno u otro componente, y cada vez que cambia de componente lo hace por una arista puente, que en \(T\) es una arista entre esos dos nodos. Borrando los tramos que se quedan dentro de un mismo componente queda un camino de \(T\). Como \(G\) es conexo, entre dos nodos cualesquiera de \(T\) hay camino.
La ausencia de ciclos. Supóngase que \(T\) tiene un ciclo \(C_0, e_1, C_1, e_2, \ldots, e_k, C_k\) con \(C_k = C_0\), los nodos \(C_0, \ldots, C_{k-1}\) distintos y \(k \geq 2\). Cada \(e_i\) es un puente de \(G\) con un extremo en \(C_{i-1}\) y el otro en \(C_i\). Escríbase \(e_1 = (u,v)\) con \(u \in C_0\) y \(v \in C_1\).
Desde \(v\) se llega a \(u\) sin usar \(e_1\): dentro de \(C_1\) hay camino de \(v\) hasta el extremo de \(e_2\), se cruza \(e_2\), y así hasta cruzar \(e_k\) y llegar dentro de \(C_0\) hasta \(u\). Los tramos interiores no usan puentes, porque quedan dentro de un componente, y los cruces usan \(e_2, \ldots, e_k\), todos distintos de \(e_1\). Ese camino más \(e_1\) es un ciclo que contiene a \(e_1\), y entonces \(e_1\) no es puente, en contra de lo supuesto.
Por lo tanto, se puede concluir que \(T\) es conexo y sin ciclos, es decir un árbol. Si \(G\) no es conexo el mismo argumento corre dentro de cada componente conexo, y \(T\) es un bosque con un árbol por componente. \(\blacksquare\)
Del teorema salen dos cuentas sin trabajo adicional. Con \(G\) conexo, \(T\) tiene tantas aristas como puentes tiene \(G\), y tantos nodos como esas aristas más uno. Y un componente que es hoja de \(T\) cuelga del resto del grafo por un solo puente.
Cómo se construye¶
Son tres pasadas, cada una lineal:
- Los puentes, con Tarjan. Una profundidad que calcula \(d\) y \(low\) y marca las aristas de árbol con \(w.low > v.d\). \(\Theta(V+E)\).
- 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. \(\Theta(V+E)\).
- El árbol. Una pasada por las aristas puente, agregando a \(T\) la arista entre los números de sus dos extremos. \(\Theta(E)\).
En total, \(\Theta(V+E)\) en tiempo y \(\Theta(V+E)\) de memoria. Son tres recorridos completos, no uno por vértice ni uno por arista.
La condición de la segunda pasada es la única que tiene, y es la que separa los pedazos. Si el recorrido cruza un puente, dos componentes vecinos quedan con el mismo número, \(T\) pierde una arista y el árbol sale mal armado sin que nada avise.
Al final quedan guardados tres datos: es_puente, el conjunto de
identificadores de arista; comp[v], el número de componente de cada vértice;
y T, las listas de adyacencia del árbol. Con esos tres se responde casi
cualquier pregunta del enunciado.
El grafo y sus aristas¶
# Triangulo 0-1-2, puente 2-3, el vertice 3 solo, puente 3-4,
# triangulo 4-5-6, puente 5-7, triangulo 7-8-9.
ARISTAS = [(0, 1), (1, 2), (2, 0),
(2, 3),
(3, 4),
(4, 5), (5, 6), (6, 4),
(5, 7),
(7, 8), (8, 9), (9, 7)]
def construir(vertices, aristas):
# G[u] guarda parejas (vecino, id de la arista).
G = {}
for u in vertices:
G[u] = []
for i in range(len(aristas)):
a, b = aristas[i]
G[a].append((b, i))
G[b].append((a, i))
return G
def descubrir(u, reloj, d, low):
reloj[0] = reloj[0] + 1
d[u] = reloj[0]
low[u] = reloj[0]
La lista de aristas manda: la arista \(i\) es aristas[i], y los dos extremos la
ven con el mismo número. Eso permite excluir la arista de entrada sin mirar
quién es el padre, y marcar un puente guardando un entero.
Los puentes, versión recursiva¶
def puentes_aux(G, u, entrada, reloj, d, low, es_puente):
# entrada: el id de la arista que bajo a u; -1 en la raiz.
descubrir(u, reloj, d, low)
for v, i in G[u]:
if d[v] == 0:
puentes_aux(G, v, i, reloj, d, low, es_puente)
low[u] = min(low[u], low[v])
if low[v] > d[u]:
es_puente.add(i)
elif i != entrada:
low[u] = min(low[u], d[v])
def puentes(G):
# Devuelve el conjunto de ids de arista que son puente.
d = {}
low = {}
for u in G:
d[u] = 0
low[u] = 0
es_puente = set()
reloj = [0]
for u in G:
if d[u] == 0:
puentes_aux(G, u, -1, reloj, d, low, es_puente)
return es_puente
low[v] > d[u] se evalúa al volver de la recursión, cuando low[v] ya es
definitivo. Lo que se guarda es i, el número de la arista de árbol que acaba
de bajar.
Los puentes, con pila explícita¶
def puentes_desde(G, s, reloj, d, low, es_puente):
# Ternas [u, entrada, k]: por cual vecino de u va el ciclo.
descubrir(s, reloj, d, low)
llamadas = [[s, -1, 0]]
while len(llamadas) > 0:
u, entrada, k = llamadas[-1]
if k < len(G[u]):
llamadas[-1][2] = k + 1
v, i = G[u][k]
if d[v] == 0:
descubrir(v, reloj, d, low)
llamadas.append([v, i, 0])
elif i != entrada:
low[u] = min(low[u], d[v])
else:
llamadas.pop()
if len(llamadas) > 0:
p = llamadas[-1][0]
low[p] = min(low[p], low[u])
if low[u] > d[p]:
es_puente.add(entrada)
def puentes_con_pila(G):
# Lo mismo que puentes, con la profundidad en una lista.
d = {}
low = {}
for u in G:
d[u] = 0
low[u] = 0
es_puente = set()
reloj = [0]
for s in G:
if d[s] == 0:
puentes_desde(G, s, reloj, d, low, es_puente)
return es_puente
Cambia solo dónde queda lo pendiente. Cada terna \([u, entrada, k]\) dice por
cuál vecino de \(u\) va el ciclo; lo que la recursiva hace al volver de la
llamada pasa aquí al sacar la terna de \(u\), con el padre p que queda arriba.
El entrada que se guarda en es_puente es el de la terna que se acaba de
sacar, es decir el identificador de la arista de árbol que bajó a \(u\).
El etiquetado, versión recursiva¶
def etiquetar(G, u, numero, es_puente, comp):
# No cruza puentes: lo que alcanza es un componente.
comp[u] = numero
for v, i in G[u]:
if comp[v] == -1 and i not in es_puente:
etiquetar(G, v, numero, es_puente, comp)
def componentes(G, es_puente):
# comp[v]: el componente de v, y el total de componentes.
comp = {}
for u in G:
comp[u] = -1
total = 0
for u in G:
if comp[u] == -1:
etiquetar(G, u, total, es_puente, comp)
total = total + 1
return comp, total
i not in es_puente es todo lo que distingue este recorrido de una
profundidad corriente. comp[v] == -1 dice que \(v\) sigue sin componente.
El etiquetado, con pila explícita¶
def etiquetar_con_pila(G, s, numero, es_puente, comp):
comp[s] = numero
pila = [s]
while len(pila) > 0:
u = pila.pop()
for v, i in G[u]:
if comp[v] == -1 and i not in es_puente:
comp[v] = numero
pila.append(v)
def componentes_con_pila(G, es_puente):
comp = {}
for u in G:
comp[u] = -1
total = 0
for u in G:
if comp[u] == -1:
etiquetar_con_pila(G, u, total, es_puente, comp)
total = total + 1
return comp, total
comp[v] = numero va antes de pila.append(v), no al sacarlo. Si se deja para
después, un vértice entra a la pila varias veces y el recorrido deja de ser
lineal.
Contraer el grafo¶
def arbol_de_puentes(aristas, es_puente, comp, total):
# Un nodo por componente, una arista por puente.
T = {}
for c in range(total):
T[c] = []
for i in sorted(es_puente):
a, b = aristas[i]
T[comp[a]].append(comp[b])
T[comp[b]].append(comp[a])
return T
def contraer(n, aristas):
# Las tres pasadas seguidas. Theta(V+E) en total.
G = construir(range(n), aristas)
es_puente = puentes_con_pila(G)
comp, total = componentes_con_pila(G, es_puente)
T = arbol_de_puentes(aristas, es_puente, comp, total)
return T, comp, es_puente
contraer devuelve el árbol, la etiqueta de cada vértice y el conjunto de
puentes, en ese orden, y es la función que los problemas llaman.
Paso a paso, arrancando en \(0\)¶
La profundidad baja \(0, 1, 2, 3, 4, 5, 6, 7, 8, 9\) en una sola rama. Las aristas de retroceso son \(2\)–\(0\), \(6\)–\(4\) y \(9\)–\(7\). Cada vértice con \(d/low\) al terminar:
| Vértice | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) |
|---|---|---|---|---|---|---|---|---|---|---|
| \(d/low\) | \(1/1\) | \(2/1\) | \(3/1\) | \(4/4\) | \(5/5\) | \(6/5\) | \(7/5\) | \(8/8\) | \(9/8\) | \(10/8\) |
Las aristas de árbol, en el orden en que la recursión vuelve por ellas:
| Arista de árbol \((v,w)\) | \(w.low\) frente a \(v.d\) | ¿Puente? | Quién es |
|---|---|---|---|
| \((8,9)\) | \(8 < 9\) | no | |
| \((7,8)\) | \(8 = 8\) | no | |
| \((5,7)\) | \(8 > 6\) | sí | arista \(8\) |
| \((5,6)\) | \(5 < 6\) | no | |
| \((4,5)\) | \(5 = 5\) | no | |
| \((3,4)\) | \(5 > 4\) | sí | arista \(4\) |
| \((2,3)\) | \(4 > 3\) | sí | arista \(3\) |
| \((1,2)\) | \(1 < 2\) | no | |
| \((0,1)\) | \(1 = 1\) | no |
\((5,7)\) tiene \(8 > 6\) y la columna dice puente. \((7,8)\) tiene \(8 = 8\) y dice que no, igual que \((0,1)\) con \(1 = 1\). ¿Qué cambia cuando el \(low\) del hijo cae justo en el \(d\) del padre, y no por debajo?
Las dos igualdades valen la pena. En \((0,1)\) y en \((7,8)\) el retroceso llega hasta \(v\) mismo y cierra un ciclo que contiene la arista, así que no hay puente. Con el criterio de articulación, que admite la igualdad, el \(0\) y el \(7\) serían puntos de corte; el \(7\) lo es y el \(0\) no, porque la raíz se decide contando hijos y tiene uno solo.
Los cuatro componentes¶
El etiquetado arranca en \(0\) y alcanza el \(1\) y el \(2\) sin cruzar la arista \(3\): componente \(A = 0\). Sigue con el \(3\), que tiene sus dos aristas marcadas y queda solo: \(B = 1\). Después el \(4\), que alcanza el \(5\) y el \(6\): \(C = 2\). Y el \(7\), que alcanza el \(8\) y el \(9\): \(D = 3\).
En el código, comp queda [0, 0, 0, 1, 2, 2, 2, 3, 3, 3] para los vértices
\(0\) a \(9\).
El árbol que queda¶
Los cuatro nodos son \(A = \{0,1,2\}\), \(B = \{3\}\), \(C = \{4,5,6\}\) y
\(D = \{7,8,9\}\), y las tres aristas son los tres puentes: \(A\)–\(B\) por \(2\)–\(3\),
\(B\)–\(C\) por \(3\)–\(4\) y \(C\)–\(D\) por \(5\)–\(7\). T queda
{0: [1], 1: [0, 2], 2: [1, 3], 3: [2]}: un camino. Las hojas son \(A\) y \(D\),
los dos componentes que cuelgan por un solo puente.
Con esos tres datos las preguntas del enunciado se contestan en un recorrido:
- ¿Cuántos puentes hay que cruzar para ir del \(1\) al \(8\)? La distancia de \(A\) a \(D\) en el árbol: tres.
- ¿El \(4\) y el \(6\) siguen conectados si se cae cualquier arista sola?
comp[4] == comp[6], así que sí. - ¿Qué arista separa más parejas de vértices? Un puente, y se mide con los tamaños de los dos lados en el árbol.
Ejercicios resueltos¶
UVa 610 — Street Directions¶
El problema¶
Enunciado: https://vjudge.net/problem/UVA-610. Envío: https://vjudge.net/problem/UVA-610.
Hay \(n\) intersecciones (\(2 \leq n \leq 1000\)) y \(m\) calles de doble vía, a lo sumo una por cada par. Hay que convertir en una vía tantas calles como se pueda, de modo que desde cada intersección se siga pudiendo llegar a todas las demás. La calle que no se pueda convertir se imprime en los dos sentidos.
La entrada trae varios casos. Cada uno abre con \(n\) y \(m\) y sigue con las \(m\)
parejas i j; la entrada termina con \(n = m = 0\). Por caso se imprime el
número de caso, una línea en blanco, cada calle como la pareja orientada
i j, y una línea con #. Las calles pueden ir en cualquier orden, y
cualquier orientación que cumpla se acepta.
El dato del enunciado que decide todo es este: con todas las calles de doble vía se puede ir de cualquier intersección a cualquier otra. El grafo es conexo.
El ejemplo del enunciado¶
En una frase: un solo sentido para el mayor número de calles, sin que ninguna intersección quede incomunicada de otra.
Las entradas del primer caso de ejemplo son \(n = 7\), \(m = 10\) y las calles
\(1\)–\(2\), \(1\)–\(3\), \(2\)–\(4\), \(3\)–\(4\), \(4\)–\(5\), \(4\)–\(6\), \(5\)–\(7\), \(6\)–\(7\),
\(2\)–\(5\), \(3\)–\(6\). La salida trae el número de caso, una línea en blanco, una
línea por cada sentido habilitado y una línea con #; para ese caso el
ejemplo imprime diez: 1 2, 2 4, 3 1, 3 6, 4 3, 5 2, 5 4, 6 4,
6 7, 7 5.
Cada línea se busca en la lista de calles. 1 2 es la calle \(1\)–\(2\). 3 1 es
la \(1\)–\(3\), leída de \(3\) a \(1\). 5 2 es la \(2\)–\(5\), y 4 3 es la \(3\)–\(4\).
Siguiendo así con las diez líneas se cubren las diez calles sin repetir
ninguna: aquí todas quedaron de una vía. El segundo caso trae nueve calles y su
salida ocupa diez líneas, y ahí aparecen 4 5 y 5 4, la calle \(4\)–\(5\) en los
dos sentidos.
¿Por qué el segundo caso gasta diez líneas en nueve calles, y el primero diez en diez? La calle repetida es la \(4\)–\(5\). ¿Qué tiene de distinta?
Qué es el grafo¶
El segundo caso de ejemplo tiene siete intersecciones y nueve calles: \(1\)–\(2\), \(1\)–\(3\), \(1\)–\(4\), \(2\)–\(4\), \(3\)–\(4\), \(4\)–\(5\), \(5\)–\(6\), \(5\)–\(7\), \(7\)–\(6\).
Los vértices son las intersecciones y las aristas no dirigidas, las calles. Convertir una calle en una vía es orientar una arista; que desde cada intersección se llegue a todas las demás es que el grafo dirigido resultante sea fuertemente conexo.
Antes del algoritmo conviene mirar el dibujo y preguntarse qué calle no se puede orientar, y por qué las otras ocho sí.
Un puente no se puede orientar¶
Teorema. Si \((u,v)\) es puente de \(G\), ninguna orientación que le dé un solo sentido a \((u,v)\) deja el grafo dirigido fuertemente conexo.
Demostración. Se procede de forma directa, partiendo el grafo por la arista. Al quitar \((u,v)\) el grafo queda en dos pedazos, \(U\) con \(u\) y \(V\) con \(v\), sin ninguna arista entre ellos. Todo camino de \(v\) a \(u\) en \(G\) usa \((u,v)\), porque es la única arista que cruza. Si se orienta \(u \rightarrow v\), desde \(v\) no hay forma de volver a \(u\); si se orienta \(v \rightarrow u\), desde \(u\) no hay forma de llegar a \(v\). Por lo tanto, se puede concluir que un puente tiene que quedar en doble vía, y las calles que el enunciado llama no convertibles son exactamente los puentes. \(\blacksquare\)
Orientar por el número de la intersección¶
El puente \(4\)–\(5\) queda en doble vía, que es lo único que ya se sabe. Las otras ocho calles reciben un sentido cualquiera, y el más fácil de escribir es de la intersección menor a la mayor.
La orientación se rompe en dos sitios. Al \(1\) no entra nada: sus tres calles, \(1\)–\(2\), \(1\)–\(3\) y \(1\)–\(4\), salieron todas. Del \(7\) no sale nada: sus dos calles, \(5\)–\(7\) y \(6\)–\(7\), entraron las dos. Nadie llega al \(1\), y quien llegue al \(7\) se queda ahí.
Voltear la \(1\)–\(2\) le da entrada al \(1\), pero entonces las dos calles del \(2\) salen de él y el \(2\) se queda sin entrada. Voltear la \(6\)–\(7\) le da salida al \(7\) y deja al \(6\) sin salida. El agujero se mueve.
Orientando siempre del número menor al mayor, todo camino dirigido aumenta el número: no hay ciclos. Y en un grafo dirigido sin ciclos nadie vuelve al punto de partida. El sentido de una calle no se decide mirándola sola, y el orden de los números no sabe nada de la ciudad. El recorrido que sí sabe por dónde se llegó a cada intersección es la profundidad.
Las demás sí, y la profundidad las orienta¶
Teorema. Sea \(G\) conexo y sea \(r\) un vértice. Oriéntense las aristas de árbol de la profundidad desde \(r\) del padre al hijo, las de retroceso del descendiente al ancestro, y cada puente en los dos sentidos. El grafo dirigido que resulta es fuertemente conexo.
Demostración. Se procede de forma directa para la ida desde \(r\), y por contradicción sobre el vértice de menor \(d\) que no logra volver.
La ida. Toda arista de árbol quedó orientada del padre al hijo, así que el camino de árbol de \(r\) a cualquier \(x\) es un camino dirigido. Desde \(r\) se llega a todos.
La vuelta. Sea \(S\) el conjunto de vértices desde los que se llega a \(r\). Si \(S \neq V\), tómese \(v \notin S\) con \(v.d\) mínimo, y sea \(p\) su padre. Hay dos casos.
Si \((p,v)\) es puente, quedó en doble vía y existe \(v \rightarrow p\), con \(p.d < v.d\).
Si no lo es, entonces \(v.low \leq p.d\), y por la definición de \(low\) hay un descendiente \(u\) de \(v\) con un retroceso \((u,w)\) tal que \(w.d = v.low \leq p.d < v.d\). Bajando por aristas de árbol de \(v\) a \(u\), todas orientadas hacia abajo, y cruzando \(u \rightarrow w\), se llega a \(w\).
En los dos casos \(v\) alcanza un vértice de \(d\) menor que \(v.d\). Ese vértice está en \(S\), por la minimalidad de \(v.d\) o porque es \(r\). Entonces \(v \in S\), en contra de lo supuesto.
Por lo tanto, se puede concluir que desde \(r\) se llega a todos y desde todos se llega a \(r\): el grafo dirigido es fuertemente conexo. Como solo los puentes quedaron en doble vía y ninguno podía dejar de estarlo, la orientación convierte el máximo número de calles. \(\blacksquare\)
El resultado es de Robbins, 1939: un grafo conexo admite una orientación fuertemente conexa si y solo si no tiene puentes.
El algoritmo¶
\(Orientar(G)\)
- Para cada vértice \(s\) sin descubrir, ejecutar \(OrientarDesde(s)\)
\(OrientarDesde(u)\)
- Asignar \(u.d\) y \(u.low\)
- Para cada vecino \(v\) de \(u\) por la arista \(i\):
- Si \(v\) no ha sido descubierto: emitir \((u,v)\), \(OrientarDesde(v)\), \(u.low = \min(u.low, v.low)\) y, si \(v.low > u.d\), emitir también \((v,u)\)
- Si no, y \(i\) no es la arista de entrada y \(v.d < u.d\): emitir \((u,v)\) y \(u.low = \min(u.low, v.d)\)
La comparación \(v.d < u.d\) del paso 2.2 es la que evita imprimir dos veces la misma calle. Una arista que no es de árbol se ve desde los dos extremos: desde el descendiente el otro tiene \(d\) menor, y desde el ancestro, mayor. La comparación deja pasar una sola de las dos miradas.
Es una profundidad por caso, \(\Theta(n+m)\) en tiempo y \(\Theta(n+m)\) de memoria. Con \(n \leq 1000\) cada caso es inmediato; lo que suma es la cantidad de casos, así que la salida se arma en una lista y se imprime de un golpe.
El código, versión recursiva¶
def orientar_aux(G, u, entrada, reloj, d, low, salida):
descubrir(u, reloj, d, low)
for v, i in G[u]:
if d[v] == 0:
salida.append((u, v))
orientar_aux(G, v, i, reloj, d, low, salida)
low[u] = min(low[u], low[v])
if low[v] > d[u]:
salida.append((v, u))
elif i != entrada and d[v] < d[u]:
salida.append((u, v))
low[u] = min(low[u], d[v])
def orientar(G):
d = {}
low = {}
for u in G:
d[u] = 0
low[u] = 0
reloj = [0]
salida = []
for s in G:
if d[s] == 0:
orientar_aux(G, s, -1, reloj, d, low, salida)
return salida
Hay tres emisiones y cada una ocurre en un momento distinto. La de árbol, al
bajar. La de retroceso, en el elif. Y la vuelta del puente, al subir, cuando
low[v] > d[u].
El código, con pila explícita¶
def orientar_desde(G, s, reloj, d, low, salida):
descubrir(s, reloj, d, low)
llamadas = [[s, -1, 0]]
while len(llamadas) > 0:
u, entrada, k = llamadas[-1]
if k < len(G[u]):
llamadas[-1][2] = k + 1
v, i = G[u][k]
if d[v] == 0:
salida.append((u, v))
descubrir(v, reloj, d, low)
llamadas.append([v, i, 0])
elif i != entrada and d[v] < d[u]:
salida.append((u, v))
low[u] = min(low[u], d[v])
else:
llamadas.pop()
if len(llamadas) > 0:
p = llamadas[-1][0]
low[p] = min(low[p], low[u])
if low[u] > d[p]:
salida.append((u, p))
def orientar_con_pila(G):
d = {}
low = {}
for u in G:
d[u] = 0
low[u] = 0
reloj = [0]
salida = []
for s in G:
if d[s] == 0:
orientar_desde(G, s, reloj, d, low, salida)
return salida
Esta es la que se envía. El límite de recursión de Python es de \(1000\) marcos, y una ciudad de \(1000\) intersecciones en línea tiene una rama de profundidad \(1000\): la versión recursiva se cae antes de imprimir nada.
La lectura y la salida¶
def leer_pareja(datos, pos):
# Los dos enteros desde pos, y la posicion siguiente.
return int(datos[pos]), int(datos[pos + 1]), pos + 2
def main():
datos = stdin.read().split()
lineas = []
caso = 1
n, m, pos = leer_pareja(datos, 0)
while n != 0 or m != 0:
aristas = []
for _ in range(m):
a, b, pos = leer_pareja(datos, pos)
aristas.append((a, b))
G = construir(range(1, n + 1), aristas)
lineas.append(str(caso))
lineas.append("")
for u, v in orientar_con_pila(G):
lineas.append(str(u) + " " + str(v))
lineas.append("#")
caso = caso + 1
n, m, pos = leer_pareja(datos, pos)
print("\n".join(lineas))
Tres detalles del formato se cobran solos: después del número de caso va una
línea en blanco, cada caso cierra con una línea que trae solo #, y las
intersecciones van de \(1\) a \(n\), así que el diccionario se arma con
range(1, n + 1) y no con range(n).
El segundo caso, orientado¶
| Paso | Qué emite | Por qué |
|---|---|---|
| \(1 \to 2 \to 4\) | 1 2, 2 4 |
aristas de árbol |
| \(4\) mira el \(1\) | 4 1 |
retroceso, \(1.d < 4.d\) |
| \(4 \to 3\) | 4 3 |
arista de árbol |
| \(3\) mira el \(1\) | 3 1 |
retroceso |
| \(4 \to 5 \to 6 \to 7\) | 4 5, 5 6, 6 7 |
aristas de árbol |
| \(7\) mira el \(5\) | 7 5 |
retroceso |
| \(5\) termina | 5 4 |
\(5.low = 5 > 4.d = 3\): puente |
Diez líneas para nueve calles. El único puente es \(4\)–\(5\) y sale en los dos sentidos; las otras ocho salen una vez cada una.
La comprobación se hace a ojo sobre el dibujo orientado. Desde el \(5\) se llega al \(4\) por el puente y de ahí al \(1\); desde el \(1\) se vuelve al \(5\) por \(1 \to 2 \to 4 \to 5\). El triángulo \(5\)–\(6\)–\(7\) gira en un sentido y el \(1\)–\(2\)–\(4\) en el otro.
UVa 10765 — Doves and Bombs¶
El problema¶
Enunciado: https://vjudge.net/problem/UVA-10765. Envío: https://vjudge.net/problem/UVA-10765.
Una red conexa de \(n\) estaciones (\(3 \leq n \leq 10000\)) unidas por vías. El valor paloma de una estación es en cuántos pedazos queda la red al bombardearla, que es cuántas palomas hacen falta para que un mensaje llegue a todas las estaciones que siguen en pie. Hay que listar las \(m\) estaciones de mayor valor.
Cada caso abre con \(n\) y \(m\), sigue con las parejas x y de las vías y cierra
con una línea -1 -1. La entrada termina con \(n = m = 0\). Por caso se imprimen
exactamente \(m\) líneas con la estación y su valor, ordenadas por valor
decreciente y, a igual valor, por número creciente; después, una línea en
blanco.
El valor es el número de pedazos porque una paloma entra a un pedazo y de ahí el mensaje sigue en tren. Cada pedazo necesita la suya, y una sola no alcanza para dos pedazos: la paloma no vuelve a volar.
El ejemplo del enunciado¶
Para cada estación hay que contar en cuántos pedazos queda la red si esa estación cae, y listar las \(m\) que dejan más pedazos.
Las entradas del caso de ejemplo: \(n = 8\), \(m = 4\) y las ocho vías \(0\)–\(4\),
\(1\)–\(2\), \(2\)–\(3\), \(2\)–\(4\), \(3\)–\(5\), \(3\)–\(6\), \(3\)–\(7\), \(6\)–\(7\), cerradas con el
-1 -1. Las salidas: \(m = 4\) líneas con la estación y su valor, que en el
ejemplo son 2 3, 3 3, 4 2 y 0 1.
Sin el \(2\) la red queda en \(\{0,4\}\), \(\{1\}\) y \(\{3,5,6,7\}\): tres pedazos. Sin el \(3\) queda en \(\{0,1,2,4\}\), \(\{5\}\) y \(\{6,7\}\): tres otra vez. Sin el \(4\) queda en \(\{0\}\) y el resto: dos. Las otras cinco estaciones se pueden quitar sin partir nada, así que valen \(1\).
La vía \(0\)–\(4\) es la única que toca al \(0\), y aun así el \(0\) vale \(1\) mientras
el \(4\) vale \(2\). ¿Por qué los dos extremos de una misma vía no valen lo mismo?
Y de las cinco estaciones que valen \(1\) se imprime una sola: ¿por qué la cuarta
línea es 0 1 y no 1 1?
Qué es el grafo¶
El caso de ejemplo tiene ocho estaciones y ocho vías: \(0\)–\(4\), \(1\)–\(2\), \(2\)–\(3\), \(2\)–\(4\), \(3\)–\(5\), \(3\)–\(6\), \(3\)–\(7\), \(6\)–\(7\). Las cinco primeras son puentes; las tres últimas forman el triángulo \(3\)–\(6\)–\(7\).
Los vértices son las estaciones, numeradas de \(0\) a \(n-1\), y las aristas no dirigidas son las vías. Bombardear una estación es quitar un vértice, así que el corte es por vértice: el valor paloma de \(v\) es el número de componentes de \(G - v\).
Antes del algoritmo, sobre el dibujo: ¿cuánto vale el \(3\)? ¿Y el \(2\)? ¿Y el \(6\)? Una de las tres respuestas es \(1\), y conviene ver por qué.
La red sin el \(3\)¶
Se borra el \(3\) y con él las cuatro vías que lo tocan: \(2\)–\(3\), \(3\)–\(5\), \(3\)–\(6\) y \(3\)–\(7\). Quedan siete estaciones y cuatro vías. Hay dos números a mano que podrían dar la respuesta. Uno es el grado del \(3\), que es \(4\). El otro es su número de hijos en el árbol de la profundidad: bajando desde el \(0\) el recorrido pasa por \(0\), \(4\), \(2\), y del \(2\) salen el \(1\) y el \(3\); del \(3\) bajan el \(5\) y el \(6\), y del \(6\) el \(7\), de modo que el \(3\) tiene dos hijos. ¿Cuál de los dos números tiene algo que ver con la respuesta?
Quedan tres pedazos: \(\{5\}\), que colgaba solo del \(3\); \(\{6,7\}\), que conserva su vía \(6\)–\(7\) y perdió las dos que lo sostenían; y \(\{0,1,2,4\}\), el lado por donde la profundidad llegó al \(3\). El número que los cuenta es el de los hijos: son dos, el \(5\) y el \(6\), y los dos subárboles se desprendieron: \(1 + 2 = 3\), donde ese \(1\) es el lado que contiene al \(0\). El grado \(4\) no sirve, porque la vía \(2\)–\(3\) sube al pedazo de arriba y la \(3\)–\(6\) y la \(3\)–\(7\) llegan las dos al mismo pedazo de abajo.
El triángulo no salva al \(6\) ni al \(7\). El \(3\), el \(6\) y el \(7\) lo forman, y el par \(6\)–\(7\) se desprende igual: las dos vías que lo unían al resto iban al \(3\). Un ciclo aguanta la caída de una vía, no la del vértice que lo cierra.
De contar componentes a contar hijos¶
Teorema. Sea \(G\) conexo y sea \(T\) un árbol de la profundidad con raíz \(r\). El número de componentes de \(G - v\) es
Demostración. Se procede de forma directa, contando qué queda pegado al quitar \(v\): los subárboles de sus hijos, por un lado, y lo que está fuera del subárbol de \(v\), por el otro.
Los subárboles de los hijos. Todo vértice de \(G - v\) está en el subárbol de algún hijo de \(v\) o fuera del subárbol de \(v\). El subárbol de un hijo \(w\) se mantiene conexo por sus propias aristas de árbol. Entre los subárboles de dos hijos distintos no hay ninguna arista, porque sería cruzada y en un grafo no dirigido no las hay (Teorema 22.10). Lo único que puede pegarlos a algo es un retroceso que salte por encima de \(v\), y eso pasa exactamente cuando \(w.low < v.d\).
Lo de afuera. Con \(v \neq r\), lo que está fuera del subárbol de \(v\) no es vacío: contiene a \(r\) y al padre de \(v\). Y es un solo pedazo, porque ninguno de sus vértices es descendiente de \(v\) y su camino de árbol hasta \(r\) no pasa por \(v\). Los subárboles con \(w.low < v.d\) se le pegan y los de \(w.low \geq v.d\) quedan sueltos, uno por uno. De ahí el \(1\) más la cuenta.
Con \(v = r\) no hay nada afuera. Un retroceso desde el subárbol de un hijo solo puede ir a un ancestro, y el único ancestro es \(r\), que ya no está. Cada subárbol queda suelto y los pedazos son tantos como hijos.
Por lo tanto, se puede concluir que al quitar \(v\) quedan tantos pedazos como hijos tiene la raíz, si \(v\) es la raíz, y uno más el número de hijos con \(w.low \geq v.d\) en los demás casos. De paso, \(c(v) \geq 2\) exactamente cuando \(v\) es punto de articulación: los dos criterios del recuento son ese caso de esta cuenta. \(\blacksquare\)
Sobre el dibujo, el \(3\) vale \(3\): se desprenden el \(5\) y el par \(6\)–\(7\), y queda el resto con el \(2\). El \(2\) vale \(3\): se desprenden el \(1\) y todo lo que cuelga del \(3\), y queda el lado del \(4\). El \(6\) vale \(1\): está en el triángulo con el \(3\) y el \(7\), y al quitarlo nada se parte.
El código, versión recursiva¶
def paloma_aux(G, u, entrada, raiz, reloj, d, low, valor):
descubrir(u, reloj, d, low)
if u == raiz:
valor[u] = 0
for v, i in G[u]:
if d[v] == 0:
paloma_aux(G, v, i, raiz, reloj, d, low, valor)
low[u] = min(low[u], low[v])
if low[v] >= d[u] or u == raiz:
valor[u] = valor[u] + 1
elif i != entrada:
low[u] = min(low[u], d[v])
def valores_paloma(G):
d = {}
low = {}
valor = {}
for u in G:
d[u] = 0
low[u] = 0
valor[u] = 1
reloj = [0]
for s in G:
if d[s] == 0:
paloma_aux(G, s, -1, s, reloj, d, low, valor)
return valor
valor[u] arranca en \(1\), que es el pedazo que se queda con el padre. Encima
se suma un hijo por cada low[v] >= d[u]. La raíz no tiene padre, así que se
pone en \(0\) al descubrirla y suma todos sus hijos, que es lo que dice la otra
rama del teorema.
El código, con pila explícita¶
def paloma_desde(G, s, reloj, d, low, valor):
descubrir(s, reloj, d, low)
valor[s] = 0
llamadas = [[s, -1, 0]]
while len(llamadas) > 0:
u, entrada, k = llamadas[-1]
if k < len(G[u]):
llamadas[-1][2] = k + 1
v, i = G[u][k]
if d[v] == 0:
descubrir(v, reloj, d, low)
llamadas.append([v, i, 0])
elif i != entrada:
low[u] = min(low[u], d[v])
else:
llamadas.pop()
if len(llamadas) > 0:
p = llamadas[-1][0]
low[p] = min(low[p], low[u])
if low[u] >= d[p] or p == s:
valor[p] = valor[p] + 1
def valores_paloma_con_pila(G):
d = {}
low = {}
valor = {}
for u in G:
d[u] = 0
low[u] = 0
valor[u] = 1
reloj = [0]
for s in G:
if d[s] == 0:
paloma_desde(G, s, reloj, d, low, valor)
return valor
Esta es la que se envía. Con \(n = 10000\) en línea, la rama tiene profundidad
\(10000\) y la recursiva levanta RecursionError contra el límite de \(1000\)
marcos. La de pila entrega la respuesta en centésimas de segundo.
El orden de la salida¶
def mejores(valor, m):
# Valor decreciente y, a igual valor, numero creciente.
pares = []
for v in valor:
pares.append((-valor[v], v))
pares.sort()
lineas = []
for k in range(m):
peso, v = pares[k]
lineas.append(str(v) + " " + str(-peso))
return lineas
def main():
datos = stdin.read().split()
bloques = []
n, m, pos = leer_pareja(datos, 0)
while n != 0 or m != 0:
aristas = []
a, b, pos = leer_pareja(datos, pos)
while a != -1 or b != -1:
aristas.append((a, b))
a, b, pos = leer_pareja(datos, pos)
G = construir(range(n), aristas)
bloques.append("\n".join(mejores(valores_paloma_con_pila(G), m)))
n, m, pos = leer_pareja(datos, pos)
for bloque in bloques:
print(bloque)
print()
El signo menos hace todo el trabajo del ordenamiento. El orden pedido es decreciente por valor y creciente por número; las parejas se arman como \((-valor, v)\) y se ordenan de forma corriente, de modo que el signo invierte el primer campo y deja el segundo como está.
Paso a paso, arrancando en \(0\)¶
La rama es \(0 \to 4 \to 2\), y de \(2\) salen el \(1\) y el \(3\); de \(3\) salen el \(5\) y el \(6\), y de \(6\) el \(7\). El único retroceso es \(7\)–\(3\), con \(3.d = 5\): baja \(7.low\) y \(6.low\) a \(5\).
| Vértice | \(0\) | \(4\) | \(2\) | \(1\) | \(3\) | \(5\) | \(6\) | \(7\) |
|---|---|---|---|---|---|---|---|---|
| \(d\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) |
| \(low\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(5\) | \(5\) |
| Hijo \(w\) de \(v\) | \(w.low\) frente a \(v.d\) | ¿Suma? | \(valor[v]\) |
|---|---|---|---|
| \(1\) de \(2\) | \(4 \geq 3\) | sí | \(2\) |
| \(5\) de \(3\) | \(6 \geq 5\) | sí | \(2\) |
| \(7\) de \(6\) | \(5 \geq 7\) | no | \(1\) |
| \(6\) de \(3\) | \(5 \geq 5\) | sí | \(3\) |
| \(3\) de \(2\) | \(5 \geq 3\) | sí | \(3\) |
| \(2\) de \(4\) | \(3 \geq 2\) | sí | \(2\) |
| \(4\) de \(0\) | raíz con un hijo | no | \(1\) |
Los valores son \(2{:}3\), \(3{:}3\), \(4{:}2\) y \(1\) para las demás, así que con
\(m = 4\) las cuatro líneas quedan 2 3, 3 3, 4 2, 0 1.
El \(6\) tiene un hijo, el \(7\), y se queda en \(1\). El \(3\) tiene dos hijos y llega a \(3\). Los tres están en el mismo triángulo. ¿Qué tiene el \(7\) que no tengan el \(5\) ni el \(6\)?
La fila del \(7\) está en la tabla y no suma. \(7.low = 5\) es menor que \(6.d = 7\): el retroceso \(7\)–\(3\) salta por encima del \(6\) y lo deja fuera del corte. Es el mismo número que sí hace sumar al \(3\), leído desde otro padre.
Cuesta una profundidad por caso, \(\Theta(n+m)\), más \(O(n \log n)\) por el ordenamiento de la salida. Las estaciones tienen grado a lo sumo \(10\), de modo que \(m = O(n)\).
Capital¶
El problema¶
Hay \(N\) ciudades y \(M\) carreteras de una sola vía, con \(N \leq 10^5\) y \(M \leq 2 \cdot 10^5\). La capital tiene que ser alcanzable desde todas las demás ciudades. Se piden todas las candidatas, en orden creciente.
Entra un grafo dirigido. Sale cuántas ciudades cumplen y cuáles, ordenadas.
El ejemplo del enunciado¶
Con \(4\) ciudades y las carreteras \(1 \to 2\), \(3 \to 2\), \(4 \to 3\) y \(2 \to 1\), la salida es \(2\) y la lista \(1\ 2\).
A mano: desde el \(4\) se llega al \(3\), al \(2\) y al \(1\). Desde el \(3\), al \(2\) y al \(1\). Entre el \(1\) y el \(2\) se va y se vuelve. Al \(3\) no llega nadie salvo el \(4\), y al \(4\) no llega nadie, de modo que ninguno de los dos puede ser capital. Quedan el \(1\) y el \(2\).
¿Por qué la respuesta trae dos y no una? Porque \(1\) y \(2\) se alcanzan entre sí: cualquiera de los dos sirve, y el enunciado pide todas las candidatas.
Qué es el grafo¶
Es el de componentes, otra vez. Los vértices son las ciudades y las aristas las carreteras, dirigidas. Se contraen los componentes fuertemente conexos y queda \(G^{SCC}\), que es un DAG.
Una ciudad es candidata exactamente cuando su componente es el sumidero de \(G^{SCC}\), el que no tiene aristas de salida. Si del componente sale una arista, de allá no se vuelve, y las ciudades del otro lado se quedan sin camino a la capital.
Con más de un sumidero no hay capital: dos sumideros no se alcanzan entre sí, así que ninguna ciudad sirve. En un DAG con un solo sumidero, ese sumidero se alcanza desde todos.
El algoritmo¶
- Calcular los componentes fuertemente conexos.
- Marcar los componentes con alguna arista que salga hacia otro.
- Si queda exactamente un componente sin marcar, imprimir sus vértices ordenados; si no, no hay candidatas.
Los componentes cuestan \(\Theta(V+E)\), el barrido de aristas \(\Theta(E)\) y el orden final \(O(V \log V)\). El peor caso del orden es que todas las ciudades sean candidatas, con el grafo entero en un solo componente.
Quien calcula los componentes es Tarjan, con el mismo \(low\) de los puentes. Lo que cambia es que el grafo va dirigido: el recorrido lleva una pila con los vértices abiertos, una arista baja el \(low\) solo si apunta a un vértice que sigue en esa pila, y el vértice que termina con \(low[u] = d[u]\) cierra su componente.
El grafo y la pila¶
def construir(vertices, aristas):
# G[u] guarda los vecinos de u; cada carretera entra en un solo sentido.
G = {}
for u in vertices:
G[u] = []
for a, b in aristas:
G[a].append(b)
return G
La carretera \(a \to b\) entra una vez, en la lista de \(a\). Por eso el vecino va
solo, sin el identificador de arista que pedían los puentes: aquí nadie tiene
que excluir la arista por la que bajó. descubrir es la misma de la primera
parte de la sesión.
def cerrar(u, pila, en_pila, comp, total):
# u quedo como raiz de su componente: lo que esta encima de u en la pila,
# y u mismo, son un componente.
ultimo = None
while ultimo != u:
ultimo = pila.pop()
en_pila[ultimo] = False
comp[ultimo] = total[0]
total[0] = total[0] + 1
De la pila sale lo que entró después de \(u\) y todavía no tiene componente, más \(u\) mismo. Esos vértices se alcanzan entre sí, así que reciben el mismo número.
Los componentes, versión recursiva¶
def scc_aux(G, u, reloj, d, low, pila, en_pila, comp, total):
# La pila guarda los vertices abiertos cuyo componente aun no se cierra.
descubrir(u, reloj, d, low)
pila.append(u)
en_pila[u] = True
for v in G[u]:
if d[v] == 0:
scc_aux(G, v, reloj, d, low, pila, en_pila, comp, total)
low[u] = min(low[u], low[v])
elif en_pila[v]:
low[u] = min(low[u], d[v])
if low[u] == d[u]:
cerrar(u, pila, en_pila, comp, total)
def componentes(G):
# comp[v]: el componente de v, y cuantos componentes hay.
d = {}
low = {}
en_pila = {}
comp = {}
for u in G:
d[u] = 0
low[u] = 0
en_pila[u] = False
comp[u] = -1
reloj = [0]
total = [0]
pila = []
for s in G:
if d[s] == 0:
scc_aux(G, s, reloj, d, low, pila, en_pila, comp, total)
return comp, total[0]
El elif es lo que separa este Tarjan del de los puentes. Una arista hacia un
vértice ya visitado baja el \(low\) solo cuando ese vértice sigue en la pila; si
su componente ya se cerró, de allá no se vuelve y la arista no dice nada de
\(u\). Al terminar queda comp, con el componente de cada ciudad, y cuántos
componentes hay.
Los componentes, con pila explícita¶
def scc_desde(G, s, reloj, d, low, pila, en_pila, comp, total):
# Parejas [u, k]: por cual vecino de u va el recorrido.
descubrir(s, reloj, d, low)
pila.append(s)
en_pila[s] = True
llamadas = [[s, 0]]
while len(llamadas) > 0:
u, k = llamadas[-1]
if k < len(G[u]):
llamadas[-1][1] = k + 1
v = G[u][k]
if d[v] == 0:
descubrir(v, reloj, d, low)
pila.append(v)
en_pila[v] = True
llamadas.append([v, 0])
elif en_pila[v]:
low[u] = min(low[u], d[v])
else:
llamadas.pop()
if low[u] == d[u]:
cerrar(u, pila, en_pila, comp, total)
if len(llamadas) > 0:
p = llamadas[-1][0]
low[p] = min(low[p], low[u])
def componentes_con_pila(G):
# Lo mismo que componentes, con la profundidad en una lista.
d = {}
low = {}
en_pila = {}
comp = {}
for u in G:
d[u] = 0
low[u] = 0
en_pila[u] = False
comp[u] = -1
reloj = [0]
total = [0]
pila = []
for s in G:
if d[s] == 0:
scc_desde(G, s, reloj, d, low, pila, en_pila, comp, total)
return comp, total[0]
Esta es la que se envía. Con \(N = 10^5\) y las carreteras en línea, la rama de la profundidad se pasa del límite de recursión de Python.
El sumidero¶
def salidas(G, comp, total):
# Cuantas carreteras salen de cada componente hacia otro componente.
salen = {}
for c in range(total):
salen[c] = 0
for u in G:
for v in G[u]:
if comp[u] != comp[v]:
salen[comp[u]] = salen[comp[u]] + 1
return salen
def capitales(G):
# Los vertices del unico componente sumidero, en orden creciente. La lista
# queda vacia cuando hay mas de un sumidero.
comp, total = componentes_con_pila(G)
salen = salidas(G, comp, total)
sumideros = []
for c in range(total):
if salen[c] == 0:
sumideros.append(c)
elegidas = []
if len(sumideros) == 1:
for u in G:
if comp[u] == sumideros[0]:
elegidas.append(u)
elegidas.sort()
return elegidas
El DAG no se construye. Basta contar, para cada componente, las carreteras que
terminan en otro componente; el que queda en cero es un sumidero. Con un solo
sumidero salen sus ciudades en orden creciente. Con dos o más la lista queda
vacía, y de ahí sale el 0 del enunciado.
El barrido que recoge las ciudades del sumidero las encuentra ya crecientes,
porque el diccionario se armó de \(1\) a \(N\). El sort final deja el orden
asegurado sin depender de eso.
La lectura y la salida¶
def main():
datos = stdin.read().split()
lineas = []
pos = 0
while pos + 1 < len(datos):
n, m, pos = leer_pareja(datos, pos)
aristas = []
for _ in range(m):
a, b, pos = leer_pareja(datos, pos)
aristas.append((a, b))
elegidas = capitales(construir(range(1, n + 1), aristas))
lineas.append(str(len(elegidas)))
if len(elegidas) > 0:
numeros = []
for u in elegidas:
numeros.append(str(u))
lineas.append(" ".join(numeros))
print("\n".join(lineas))
leer_pareja es el mismo de UVa 610. La entrada trae casos hasta que se agotan
los números, y las líneas se acumulan para imprimirlas de un golpe: un print
por ciudad con \(N = 10^5\) se paga en tiempo.
La otra forma de resolverlo¶
El titular calcula los componentes con Gabow. Donde Tarjan guarda un número
por vértice, Gabow lleva dos pilas: pilaS con los vértices abiertos, que es
la misma de Tarjan, y pilaP con los candidatos a representante del
componente.
for(int i = 0; i < adj[v].size(); i++){
w = adj[v][i];
if(visitado[w] == -1)
gabowAux(w);
else if(sccInd[w] == -1){
while(visitado[pilaP.top()] > visitado[w])
pilaP.pop();
}
}
Al bajar, una arista hacia un vértice abierto saca de pilaP todo lo que se
descubrió después de él. Ese es el efecto de bajar el \(low\): lo que queda en
pilaS por encima de la cima de pilaP va a parar al mismo componente que
esa cima.
if(v == pilaP.top()){
numSCC++;
while(pilaS.top() != v){
sccInd[pilaS.top()] = numSCC - 1;
pilaS.pop();
}
sccInd[pilaS.top()] = numSCC - 1;
pilaS.pop();
pilaP.pop();
}
El vértice que sobrevive en la cima de pilaP cierra el componente, y la
pregunta v == pilaP.top() es la condición low[u] == d[u]. Lo que se vacía
de pilaS hasta \(v\) es lo que saca cerrar en la versión con \(low\). La
partición es la misma y el conteo de carreteras entre componentes no cambia. El
archivo completo, en C++, es capital.cpp.
Interplanetary¶
El problema¶
El grafo es no dirigido, con un valor de influencia en cada vértice y un vértice de arranque. El recorrido arranca ahí y cruza un puente solo hacia un componente de más influencia.
El algoritmo¶
- Tarjan marca los puentes.
- El etiquetado que no los cruza da los componentes 2-arista-conexos, y de paso suma la influencia de cada uno.
- El recorrido desde el inicio cruza una arista cuando no es puente, o cuando lo es y lleva a un componente de influencia mayor.
Las tres pasadas son profundidades sobre el mismo grafo, \(\Theta(V+E)\) cada una. El orden final de la salida, \(O(V \log V)\).
Los componentes y su influencia¶
def sumar_aux(G, u, numero, es_puente, influencia, comp, suma):
# No cruza puentes: lo que alcanza es un componente, y de paso acumula la
# influencia de cada vertice que etiqueta.
comp[u] = numero
suma[numero] = suma[numero] + influencia[u]
for v, i in G[u]:
if comp[v] == -1 and i not in es_puente:
sumar_aux(G, v, numero, es_puente, influencia, comp, suma)
def componentes(G, es_puente, influencia):
# comp[v]: el componente de v; suma[c]: la influencia de todo c.
comp = {}
for u in G:
comp[u] = -1
suma = []
total = 0
for u in G:
if comp[u] == -1:
suma.append(0)
sumar_aux(G, u, total, es_puente, influencia, comp, suma)
total = total + 1
return comp, suma
Es el etiquetado que no cruza puentes, con una suma encima: cada vértice que se
etiqueta aporta su influencia al componente. Salen dos cosas, el componente de
cada vértice en comp y la influencia de todo el componente en suma. Los
puentes llegan ya calculados por puentes, y construir es la de la primera
parte, con las parejas de vecino e identificador de arista.
def sumar_desde(G, s, numero, es_puente, influencia, comp, suma):
comp[s] = numero
suma[numero] = suma[numero] + influencia[s]
pila = [s]
while len(pila) > 0:
u = pila.pop()
for v, i in G[u]:
if comp[v] == -1 and i not in es_puente:
comp[v] = numero
suma[numero] = suma[numero] + influencia[v]
pila.append(v)
def componentes_con_pila(G, es_puente, influencia):
comp = {}
for u in G:
comp[u] = -1
suma = []
total = 0
for u in G:
if comp[u] == -1:
suma.append(0)
sumar_desde(G, u, total, es_puente, influencia, comp, suma)
total = total + 1
return comp, suma
La misma pasada, con lo pendiente en una lista en vez de en la pila de llamadas.
El recorrido que respeta los puentes¶
def se_puede(u, v, i, es_puente, comp, suma):
# Una arista que no es puente se cruza en los dos sentidos; un puente,
# solo hacia el componente de influencia estrictamente mayor.
return i not in es_puente or suma[comp[u]] < suma[comp[v]]
def alcance_aux(G, u, es_puente, comp, suma, visto, llegan):
visto[u] = True
llegan.append(u)
for v, i in G[u]:
if not visto[v] and se_puede(u, v, i, es_puente, comp, suma):
alcance_aux(G, v, es_puente, comp, suma, visto, llegan)
def alcance(G, inicio, es_puente, comp, suma):
# Los vertices a los que se llega desde inicio.
visto = {}
for u in G:
visto[u] = False
llegan = []
alcance_aux(G, inicio, es_puente, comp, suma, visto, llegan)
return llegan
La condición va aparte porque es lo único que separa esto de una profundidad
corriente. Dentro de un componente se anda libre: ninguna de esas aristas es
puente. El puente se cruza solo hacia más influencia, y la desigualdad es
estricta, así que un empate lo deja cerrado en los dos sentidos. Lo que
devuelve alcance son los vértices en el orden en que el recorrido los
encontró, y ese no es el orden de la salida.
def alcance_con_pila(G, inicio, es_puente, comp, suma):
visto = {}
for u in G:
visto[u] = False
visto[inicio] = True
llegan = [inicio]
pila = [inicio]
while len(pila) > 0:
u = pila.pop()
for v, i in G[u]:
if not visto[v] and se_puede(u, v, i, es_puente, comp, suma):
visto[v] = True
llegan.append(v)
pila.append(v)
return llegan
El mismo recorrido con lo pendiente en una lista, y se_puede consultada igual.
El orden de la salida¶
def ordenar(llegan, influencia, comp, suma):
# Creciente por la influencia del componente, luego por la propia y al
# final por el numero del vertice.
claves = []
for u in llegan:
claves.append((suma[comp[u]], influencia[u], u))
claves.sort()
salida = []
for total, propia, u in claves:
salida.append(u)
return salida
def resolver(vertices, aristas, influencia, inicio):
# Las tres pasadas seguidas. Theta(V+E) en total, mas el orden final.
G = construir(vertices, aristas)
es_puente = puentes_con_pila(G)
comp, suma = componentes_con_pila(G, es_puente, influencia)
llegan = alcance_con_pila(G, inicio, es_puente, comp, suma)
return ordenar(llegan, influencia, comp, suma)
Tres claves: la influencia del componente, la del vértice y el número. El
número desempata siempre, así que la línea que sale es única. resolver entra
por las versiones de pila, que son las que se envían cuando la profundidad
puede pasarse del límite de recursión de Python; resolver_recursivo hace las
mismas tres pasadas con puentes, componentes y alcance.
La otra forma de resolverlo¶
La del titular hace las tres pasadas iguales. Lo que cambia es dónde vive el estado: el grafo, los puentes, las etiquetas y las influencias son arreglos globales de tamaño fijo, y la influencia del componente sube como valor de retorno de la recursión en vez de acumularse en una lista.
def getCCAux(u, ind):
ans = infl[u]
comps[ind].append(u)
ccInd[u] = ind
for v in G[u]:
if ccInd[v] == -1 and (u, v) not in bridges:
ans += getCCAux(v, ind)
return ans
Cada llamada devuelve la influencia de lo que etiquetó y el padre la agrega a
la suya. getCC recoge el total de cada componente en inflComps.
def dfs(u):
vis[u] = 1
reach.append(u)
for w in G[u]:
if vis[w] == -1 and ((u, w) not in bridges
or inflComps[ccInd[u]] < inflComps[ccInd[w]]):
dfs(w)
La diferencia está en cómo se reconoce un puente. bridges guarda las parejas
\((u,v)\) y \((v,u)\) en lugar del identificador de la arista, y el padre se
excluye por vértice con w != p[v]. Con una sola arista entre cada
par de vértices las dos formas coinciden. Con una ruta doble no: la pareja no
distingue las dos copias, la exclusión por vértice tapa las dos, el \(low\) del
hijo nunca baja hasta el padre y la ruta sale marcada como puente. El archivo
completo es interplanetary.py.
Cómo atacar estos problemas¶
Los dos de UVa comparten el mismo camino, y son cinco pasos:
- Leer el grafo. Quiénes son los vértices y quiénes las aristas, y si viene dirigido o no. Intersecciones y calles; estaciones y vías.
- Decidir qué se corta. Si lo que el enunciado quita o rompe es un vértice, el criterio es el de articulación (\(w.low \geq v.d\) y los hijos de la raíz). Si es una arista, el de puente (\(w.low > v.d\)).
- Calcular con Tarjan. Una profundidad, \(d\) y \(low\), \(\Theta(V+E)\). Con pila explícita si la entrada puede dar una rama de más de mil vértices.
- Contraer, si la pregunta no es local. Si pregunta por caminos, distancias o cuántos puentes se cruzan, se arma el árbol de puentes.
- Recorrer lo que quedó. Sobre el árbol, una profundidad o una amplitud más; sobre el grafo original, una pasada por las aristas.
No todos llegan al final. UVa 10765 se queda en el paso 3, porque la respuesta es una cuenta por vértice. UVa 610 llega al paso 3 y emite en la misma pasada. Los problemas que piden distancias llegan al 5.
El paso que más se salta es el 2. Un enunciado que habla de destruir ciudades pide articulaciones; uno que habla de cortar cables o inundar carreteras pide puentes. Resolver el otro da una respuesta razonable que el juez rechaza.
Errores comunes¶
- Contar mal los hijos de la raíz. Hijos en el árbol de la profundidad, no vecinos. En el ejemplo de UVa 10765 la raíz \(0\) tiene un vecino y un hijo, y vale \(1\); una raíz con tres vecinos de los que dos ya fueron descubiertos también tiene un solo hijo. Contar vecinos infla el valor de la raíz y la lista de salida sale encabezada por la estación equivocada.
- Usar
low[v] > d[u]para la articulación. Con la desigualdad estricta se pierden los vértices cuyo hijo tiene un retroceso que llega hasta ellos mismos. En el ejemplo, el \(3\) dejaría de sumar por su hijo \(6\), porque \(6.low = 5 = 3.d\), y saldría con valor \(2\) en lugar de \(3\). El criterio de articulación admite la igualdad; el de puente, no. - Olvidar las aristas repetidas. Dos vías entre las mismas dos estaciones
forman un ciclo de longitud dos, así que ninguna de las dos es puente. Con
v != padrela segunda copia queda descartada por error y la primera sale como puente. Se arregla comparando identificadores de arista:i != entrada. - Cruzar puentes en el etiquetado. Si el recorrido del paso 2 no revisa
i not in es_puente, llega al otro lado del puente y dos componentes vecinos se fusionan. El árbol pierde nodos y aristas, el programa no se queja, y las respuestas salen de otro grafo. En el grafo de la sección quedaría un solo nodo en lugar de cuatro. - Reutilizar los arreglos entre casos. Si \(d\), \(low\), el reloj o el conjunto de puentes se quedan con los valores del caso anterior, el segundo caso sale mal y el primero bien, que es la forma más costosa de buscar el error.
- Mandar la versión recursiva. Con \(n = 10000\) y la red en línea, la
profundidad recursiva se cae contra el límite de \(1000\) marcos de Python.
Subirlo con
setrecursionlimitcambia elRecursionErrorpor un desbordamiento de la pila del sistema. La versión de pila explícita no tiene ese techo. - Emitir dos veces la misma arista de retroceso. En UVa 610, sin la
comparación
d[v] < d[u]cada arista que no es de árbol se emite desde sus dos extremos. La salida trae una calle de más en los dos sentidos y el juez la rechaza, aunque la orientación sea fuertemente conexa. - Imprimir dentro del ciclo de casos. Con muchos casos, un
printpor línea es el cuello de botella. Las líneas se acumulan en una lista y se imprimen de un golpe al final.
El código de la clase¶
- arbol_de_puentes.py:
construir,descubrir,puentes_aux,puentes,puentes_desde,puentes_con_pila,etiquetar,componentes,etiquetar_con_pila,componentes_con_pila,arbol_de_puentesycontraer. Al correrlo imprime los tres puentes del grafo de diez vértices con las dos versiones, el componente de cada vértice y el árbol que queda, y los compara con quitar cada arista y contar componentes sobre 500 grafos aleatorios, comprobando además que lo contraído sea siempre un árbol o un bosque. - uva610_street_directions.py:
orientar_aux,orientar,orientar_desde,orientar_con_pila,leer_parejaymain. Lee porstdine imprime la orientación de cada caso, con el puente en doble vía. - uva10765_doves_and_bombs.py:
paloma_aux,valores_paloma,paloma_desde,valores_paloma_con_pila,mejores,leer_parejaymain. Lee porstdine imprime las \(m\) estaciones de mayor valor paloma por caso. - capital.py:
construir,descubrir,cerrar,scc_aux,componentes,scc_desde,componentes_con_pila,salidas,capitales,leer_parejaymain, másinvertir,alcanzados,capitales_brutoygrafo_aleatorio. Lee porstdine imprime, por caso, cuántas candidatas hay y la lista ordenada. Al correrlo da las candidatas de la muestra y las del caso con dos sumideros, y compara las dos versiones de Tarjan contra probar cada ciudad una por una sobre 400 grafos aleatorios. - capital.cpp:
gabow,gabowAuxymain, en C++. Calcula los componentes fuertemente conexos con Gabow, cuenta las aristas que salen de cada uno y, si hay un solo sumidero, imprime cuántas candidatas son y la lista ordenada; si hay más, imprime0. - interplanetary_cortes.py:
construir,descubrir,puentes_aux,puentes,puentes_desde,puentes_con_pila,sumar_aux,componentes,sumar_desde,componentes_con_pila,se_puede,alcance_aux,alcance,alcance_con_pila,ordenar,resolver,resolver_recursivo,leer_parejaymain, máscontar_componentes,puentes_brutoygrafo_aleatorio. Lee porstdine imprime los vértices alcanzados desde el vértice de arranque. Al correrlo da la salida del grafo de siete vértices y la del caso de empate, y contrasta las dos versiones de cada pasada sobre 300 grafos aleatorios. - interplanetary.py:
bridgesAux,bridgesTarjan,getCCAux,getCC,dfs,solveymain. Lee porstdin, arma los componentes 2-arista-conexos con su influencia y imprime los vértices alcanzados desde el vértice de arranque.
Ejercicios¶
Los interactivos y los de papel están en la
página de ejercicios. Los ocho de las diapositivas pueden
aparecer en el parcial, y van sobre el mismo grafo \(H\), con
\(V = \{0, \ldots, 8\}\) y aristas \(0\)–\(1\), \(1\)–\(2\), \(2\)–\(0\), \(2\)–\(3\), \(3\)–\(4\),
\(4\)–\(2\), \(4\)–\(5\), \(5\)–\(6\), \(6\)–\(7\), \(7\)–\(5\), \(7\)–\(8\): el árbol de puentes de
\(H\) a mano, con \(d\), \(low\) y la tabla de aristas de árbol; qué pasa al
agregarle una segunda arista \(4\)–\(5\) y qué devolvería un programa que excluye
la entrada con v != padre; los puntos de articulación y los puentes de \(H\),
con un vértice que es articulación sin tener ningún puente incidente; el valor
paloma de los nueve vértices, calculado de las dos formas; la orientación de
\(H\) con la regla de UVa 610 arrancando en \(0\); las dos tablas de \(d\) y \(low\)
que salen de arrancar en \(0\) y en \(4\), con la razón de que el conjunto de
puentes no dependa de la raíz; cuántas aristas nuevas hacen falta para dejar un
grafo conexo sin puentes, en función de las hojas del árbol; y el puente que
deja los dos pedazos más parejos, con el cálculo en \(\Theta(V+E)\).
Para enviar al juez¶
- UVa 610 — Street Directions.
Enunciado: https://vjudge.net/problem/UVA-610.
Envío: https://vjudge.net/problem/UVA-610.
El parámetro es la calle: hay que decidir cuáles se orientan. La propiedad
está en que un puente no puede ser de una vía. La trampa es el formato:
línea en blanco tras el número de caso y una línea con
#al cerrar. - UVa 10765 — Doves and Bombs.
Enunciado: https://vjudge.net/problem/UVA-10765.
Envío: https://vjudge.net/problem/UVA-10765.
El parámetro es la estación y la propiedad es el conteo de hijos con
\(w.low \geq v.d\). La trampa es doble: el
-1 -1que cierra las vías y los \(10000\) vértices, que obligan a la pila explícita. - UVa 796 — Critical Links. Enunciado: https://vjudge.net/problem/UVA-796. Envío: https://vjudge.net/problem/UVA-796. Pide la lista de puentes ordenada, con el extremo menor primero. Sirve para probar la primera de las tres pasadas por separado, antes de armar el árbol.
Lo que sigue¶
El árbol de puentes corta por aristas y agrupa vértices. Cortar por puntos de articulación da otra partición, y esa reparte las aristas: cada arista pertenece a un solo componente biconexo y un punto de articulación queda en varios a la vez. La misma profundidad con \(low\) los encuentra, guardando aristas en una pila en lugar de vértices.
Para investigar: CLRS, Problema 22-2, partes g y h. Por qué la partición va sobre las aristas y no sobre los vértices, y qué se apila en cada llamado para sacar un componente al cerrar un punto de articulación.
Referencias¶
- Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 3.ª ed. MIT Press, 2009. Problema 22-2 (puntos de articulación, puentes y componentes biconexos); Sección 22.3, Teorema 22.10 (en un grafo no dirigido solo hay aristas de árbol y de retroceso).
- Robbins, H. E. A theorem on graphs, with an application to a problem of traffic control. The American Mathematical Monthly, 46(5):281–283, 1939.
- Tarjan, R. E. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146–160, 1972.
- Halim, Halim, Effendy. Competitive Programming 4. Lulu, 2020. Capítulo 4: puntos de articulación, puentes y orientación de grafos.
- UVa 610 — Street Directions. https://vjudge.net/problem/UVA-610.
- UVa 10765 — Doves and Bombs. https://vjudge.net/problem/UVA-10765.
Lo que se trabajó en clase¶
La prueba de \(w.low > v.d\)¶
En el tablero quedaron dos componentes 2-arista-conexos, \(C_i\) con \(v\) y \(C_j\) con \(w\), unidos por la arista de árbol \((v,w)\). En un grafo no dirigido toda arista que no es de árbol une un vértice con un ancestro suyo, así que todo depende de hasta dónde sube un retroceso que salga del subárbol de \(w\).
Si \(w.low \leq v.d\), hay un retroceso \((x,y)\) con \(x\) en el subárbol de \(w\) y \(y.d = w.low \leq v.d\). Como \(y\) es ancestro de \(x\) y no se descubrió después de \(v\), es \(v\) o un ancestro de \(v\). El camino de árbol de \(y\) a \(v\), la arista \((v,w)\), el camino de árbol de \(w\) a \(x\) y el retroceso \((x,y)\) cierran un ciclo que contiene a \((v,w)\), y la arista no es puente. Si \(w.low > v.d\), ningún retroceso del subárbol de \(w\) llega a \(v\) ni más arriba: la única arista entre ese subárbol y el resto es \((v,w)\), y quitarla deja a \(C_j\) del otro lado.
La igualdad \(w.low = v.d\) es el caso \(y = v\). El ciclo existe y pasa por \(v\). Contra el puente sirve, porque al quitar la arista \(v\) se queda. Contra la articulación no, porque al quitar \(v\) el subárbol de \(w\) pierde el único vértice por el que tocaba el resto. La raíz \(r\) se trata aparte por la misma cuenta: ningún vértice tiene \(d\) menor que \(r.d\), así que \(w.low \geq r.d\) se cumple en todos sus hijos y el criterio la marcaría siempre.
En el grafo de diez vértices los que terminan con \(low = d\) son \(0\), \(3\), \(4\) y \(7\), uno por componente: el primero que la profundidad descubre en cada uno. Fuera de la raíz, la arista que llega a cada uno desde su padre es puente, porque \(w.low = w.d > v.d\).
Preguntas que salieron¶
- ¿Y si hubiera otra arista entre dos componentes? Cierra un ciclo con el camino que los une en el árbol. Los puentes de ese camino dejan de serlo y sus componentes se funden en uno.
- ¿El árbol de puentes es siempre un camino? En el ejemplo sí, por cómo está dibujado. Un componente del que salen tres puentes da un nodo de grado tres. Lo que no cambia es que sea conexo y acíclico.
- ¿Para qué guardar el número de arista junto al vecino? Al volver de la
recursión por \((v,w)\) con \(w.low > v.d\) se guarda ese número en
es_puente, y el etiquetado preguntai not in es_puentesin buscar la arista en la lista. - ¿Por qué el reloj arranca en \(1\)? Porque \(d = 0\) marca no descubierto. El origen es arbitrario; si se toma \(0\) como tiempo válido, la marca pasa a ser \(-1\).
- ¿Subir el límite de recursión o pasar a la pila? Antes de subirlo conviene revisar si la recursión baja más de lo necesario o si cada marco carga demasiadas variables. Para el parcial basta la versión recursiva.
- ¿Y si se piden distancias entre puntos críticos? Los puentes salen con Tarjan y las distancias con un algoritmo de caminos, tema de la semana que viene: amplitud sin pesos, Dijkstra con pesos no negativos, Floyd–Warshall si puede haber negativos.
- ¿Qué arista separa más parejas? Un puente que deja \(s\) vértices de un lado separa \(s\,(n-s)\) parejas. En el grafo de diez vértices, \(2\)–\(3\) separa \(3 \cdot 7 = 21\), \(3\)–\(4\) separa \(4 \cdot 6 = 24\) y \(5\)–\(7\) separa \(7 \cdot 3 = 21\). Gana el que deja los pedazos más parejos.
Un error más, que apareció al explicar el criterio: comparar al revés. Lo que se compara es el \(low\) del hijo con el \(d\) del padre, \(w.low > v.d\); \(v.low\) frente a \(w.d\) no dice nada sobre la arista.
Capital, la muestra a mano¶
Con \(1 \to 2\), \(3 \to 2\), \(4 \to 3\) y \(2 \to 1\) salen tres componentes fuertemente conexos: \(\{1,2\}\), \(\{3\}\) y \(\{4\}\). Un vértice solo es un componente: la definición pide camino de \(u\) a \(v\) y de \(v\) a \(u\), y con \(u = v\) basta el camino vacío. Las aristas entre componentes son \(4 \to 3\) y \(3 \to 2\); de \(\{1,2\}\) no sale ninguna, y es el único sumidero. En el tablero quedaron marcados el \(1\) y el \(2\), tachados el \(3\) y el \(4\).
Gabow, arrancando en \(1\), lleva en la pila \(S\) los vértices abiertos y en \(P\) los posibles representantes. Descubre \(1\) y \(2\) y los pone en las dos. La arista \(2 \to 1\) llega a un vértice ya descubierto y sin componente, y saca de \(P\) todo lo descubierto después de \(1\): queda \(P = [1]\). Al cerrar \(2\), el tope de \(P\) no es \(2\) y no pasa nada; al cerrar \(1\), sí es \(1\), y de \(S\) sale \(\{2,1\}\). El representante es el que en Tarjan tendría \(low = d\).
Interplanetary, las muestras a mano¶
La primera muestra trae seis colonias con influencias \(3, 1, 2, 10, 4, 5\), las aristas \(1\)–\(2\), \(2\)–\(3\), \(3\)–\(1\), \(3\)–\(4\), \(4\)–\(5\), \(5\)–\(6\) y el arranque en \(1\). Los puentes son \(3\)–\(4\), \(4\)–\(5\) y \(5\)–\(6\):
| Componente | \(\{1,2,3\}\) | \(\{4\}\) | \(\{5\}\) | \(\{6\}\) |
|---|---|---|---|---|
| Influencia | \(6\) | \(10\) | \(4\) | \(5\) |
Desde \(\{1,2,3\}\) se cruza \(3\)–\(4\), porque \(6 < 10\), y no \(4\)–\(5\), porque
\(10 > 4\). Llegan \(1, 2, 3, 4\), y la clave (suma[comp[x]], influencia[x], x)
los ordena como \(2\ 3\ 1\ 4\): las tuplas se comparan componente a componente.
En la versión del titular la suma sube por el retorno. getCCAux(1, 0) llama a
getCCAux(2, 0), que llama a getCCAux(3, 0): ahí el \(2\) y el \(1\) ya tienen
etiqueta y \((3,4)\) es puente, así que devuelve \(2\); el \(2\) devuelve
\(1 + 2 = 3\), y el \(1\), \(3 + 3 = 6\). La condición ccInd[v] == -1 evita sumar
dos veces un vértice del ciclo. sumar_aux llega a los mismos \(6\) sin
retorno: cada vértice etiquetado agrega su influencia a suma[numero].
En el grafo de siete vértices de las diapositivas los triángulos \(\{1,2,3\}\) y \(\{4,5,6\}\) suman \(6\) y \(12\), y el \(7\) cuelga solo del \(1\) con influencia \(1\). Desde el \(1\) se sube por \(3\)–\(4\) y no se baja por \(1\)–\(7\); la salida es \(2\ 1\ 3\ 5\ 4\ 6\). La segunda muestra del enunciado tiene componentes \(\{1,2,3\}\), \(\{4,5,9\}\), \(\{6\}\), \(\{7\}\) y \(\{8\}\) con sumas \(8\), \(11\), \(6\), \(1\) y \(13\). El recorrido sube de \(8\) a \(11\) y de \(11\) a \(13\), no baja al \(6\), y sale \(2\ 3\ 1\ 5\ 9\ 4\ 8\): el \(5\), con influencia \(-3\), abre su componente.
Dos preguntas sobre el código. bridges guarda \((v,w)\) y \((w,v)\) porque el
grafo es no dirigido y la consulta llega en el sentido en que se recorre. La
influencia propia no ordena solo dentro de un componente: es la segunda clave,
y también decide entre vértices de dos componentes alcanzables con la misma
suma. Guardar la influencia junto a la lista del componente, como un par, o en
los nodos del árbol de puentes, es lo mismo con otra estructura.
interplanetary.py excluye la arista de entrada con w != p[v]: con rutas
repetidas marcaría como puente una ruta doble.
Las páginas del tablero¶
Las primeras traen las dos partes de la prueba de que \(T\) es un árbol,
el árbol de puentes del grafo de diez vértices, la prueba de \(w.low > v.d\) con
los dos componentes, la muestra de Capital y getCCAux con su suma
(tres páginas):
Las segundas traen los cuatro componentes encerrados en el grafo de diez vértices, las comparaciones de los tres puentes con sus \(d/low\), la muestra de Capital y las de Interplanetary con la influencia de cada componente (tres páginas):