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. Al quitar un vértice
se desprende un pedazo por cada hijo w con
low[w] ≥ d[u], y queda además el pedazo que sigue pegado al
padre. La raíz no tiene padre: su valor es el número de hijos. La profundidad
ya corrió y cada vértice trae su d/low.
d/low
Las estaciones van de 0 a n−1 y la profundidad arranca en la 0, recorriendo los vecinos de menor a mayor.
Para cada vértice que no es la raíz, el
valor arranca en 1 y suma un hijo por cada low[w] ≥ d[u]. La
comparación admite la igualdad: si el subárbol de w vuelve a
u pero no sube más, quitar u lo deja aparte igual.
La definición ejecutada: se bombardea una estación y el dibujo recolorea los pedazos que quedan.
Las estaciones de mayor
valor, ordenadas por valor decreciente y, a igual valor, por número
creciente. Las parejas se arman como (-valor, v) y se ordenan
de forma corriente: el signo invierte el primer campo y deja el segundo como
está.
| Línea | Sale | Por qué va ahí |
|---|
La tabla se llena al comprobar los valores de arriba.
Sin solución aquí. En la segunda red, agregue una vía
entre la estación de mayor valor y la que está más lejos de ella en el
árbol, y diga cuántos valores cambian. Después, en la tercera, corra la
profundidad desde la estación 2 en lugar de la 0: los d y los
low cambian, y la que era raíz deja de serlo. ¿Cambia algún
valor paloma? Y por último: encuentre en alguna de las tres redes un vértice
cuyo valor sea 2 sin que ninguna de sus vías sea puente, y explique con
d y low por qué pasa.