Combinatoria
Prueba de Selección de Equipos de Irán (2010)
Prueba de Selección de Equipos de Irán 2010 Problema 4
4 $S,T$ son dos árboles sin vértices de grado 2. A cada arista se le asocia un número positivo llamado longitud de esta arista. La distancia entre dos vértices arbitrarios $v,w$ en este grafo se define como la suma de las longitudes de todas las aristas en el camino entre $v$ y $w$ . Sea $f$ una función biyectiva de las hojas de $S$ a las hojas de $T$ , tal que para cada dos hojas $u,v$ de $S$ , la distancia de $u,v$ en $S$ es igual a la distancia de $f(u), f(v)$ en $T$ . Demuestre que hay una función biyectiva $g$ de los vértices de $S$ a los vértices de $T$ tal que para cada dos vértices $u,v$ de $S$ , la distancia de $u,v$ en $S$ es igual a la distancia de $g(u)$ y $g(v)$ en $T$ . Omid
0
0
Kevin
Inicia sesión para agregar soluciones y pistas