Saltar a contenido

Ejercicios · AyG PUJ · El centro de un árbol

Seis ejercicios para el navegador sobre el centro, el radio y el diámetro de un árbol calculados sin mirar una sola excentricidad. Van en el orden del tema: primero el descarte local que hace innecesaria la cuenta global, después el teorema que permite repetirlo, después el algoritmo línea por línea, después la traducción de vueltas a radio y a diámetro, y de último los cambios que lo rompen. Los seis cuentan. Ninguno usa los árboles ni los juegos de valores de las diapositivas, salvo el último, que es el problema de juez de la sesión y para eso está.

Una hoja nunca es el centro

Quién no puede ser el centro

Un árbol de nueve vértices donde primero se descartan candidatos sin calcular nada. Marcar un vértice que no es hoja o dejar una hoja sin marcar trae su propia explicación con los grados del caso. Después se da la excentricidad de un vecino y se pide la de la hoja, que es la cuenta \(\varepsilon(\ell) = 1 + \varepsilon(p)\) aplicada en concreto, y cada hoja del árbol sirve de ronda nueva. Al final aparecen las nueve excentricidades para comparar el descarte con el cálculo.

El teorema del centro

Qué le pasa a cada excentricidad al pelar una capa

Un árbol de diez vértices con sus excentricidades a la vista. Se quitan de un golpe las cuatro hojas y se pide predecir, casilla por casilla, la excentricidad que tendrá cada uno de los seis sobrevivientes. Las respuestas equivocadas distinguen tres confusiones: dejar el valor viejo, bajarlo dos y bajarlo donde no corresponde. Al comprobar la fila completa queda a la vista que todas bajaron exactamente uno, que el radio bajó con ellas y que el centro no se movió.

El algoritmo de pelar hojas

Pelar capas de hojas, línea por línea

El código de la sesión corriendo paso a paso sobre dos árboles, uno de doce vértices y otro de ocho. Cada vértice lleva encima su grado en lo que sigue vivo, el naranja marca la capa que se está yendo y el gris lo que ya se fue. Antes de arrancar se predice cuántas vueltas dará el ciclo, y la retroalimentación separa las vueltas del radio y de la cantidad de capas. El árbol de doce termina con dos centros y el de ocho con uno, de modo que las dos formas de cerrar la cuenta aparecen en el mismo ejercicio.

De las vueltas al radio y al diámetro

De las vueltas al radio y al diámetro

Cuatro árboles: un camino de seis, una estrella de siete, una oruga de diez y un binario completo de siete. De cada uno se predicen cuatro cifras antes de pelar nada, y la tabla del final se va llenando con los que ya quedaron bien, incluida la columna que dice si las vueltas coincidieron con el radio. Dos de los cuatro terminan con dos centros y dos con uno, que es justo donde la coincidencia se rompe.

Errores comunes

Cuatro formas de romper el pelado

Cuatro versiones cambiadas del algoritmo, una por pregunta: la condición de parada en \(|V| > 1\), los vértices nuevos agregados a la capa que se está recorriendo, el mismo código sobre un grafo con un ciclo y las vueltas leídas como el radio. Cada pregunta trae el árbol más pequeño donde el cambio se nota, y cada opción su propia explicación.

El problema de cierre

Cambiar un vuelo para acortar el peor trayecto

UVa 11695, Flight Planning, el problema con el que cierra la sesión. Hay \(n\) ciudades y \(n-1\) vuelos, se quita uno y se pone otro, y se busca que el mayor número de trasbordos quede lo más pequeño posible.

Se prueba corte por corte sobre tres redes, una de ellas la del enunciado. Cada corte parte el árbol en dos y la actividad muestra el diámetro de cada pedazo, cuál es su centro y qué diámetro queda al unirlos por ahí, con la cuenta \(\max(d_1, d_2, \lceil d_1/2 \rceil + \lceil d_2/2 \rceil + 1)\) escrita con los números del caso. Se predice el mejor resultado alcanzable y, al acertar, aparece la tabla con las \(n-1\) aristas y las que lo logran marcadas: siempre caen cerca de la mitad del camino más largo.

La última tarjeta trae la lectura de la entrada con scanf y el enlace de envío.