Número de estudiantes y maestros en todos los tipos de escuelas, 1999 - 2004

Question

Tengo que probar el siguiente afirmación, dado el árbol $T=(V,E)$, $|V|=n\geq2$: $$|V_1| = 2 + \sum (j-2)|V_j|$$

donde la suma es de $j=3$ hasta el grado más alto, y $$V_i = \{ x \in V \mid \deg(x) = i\}.$$

Esta fue una pregunta extra dado por mi profesor. Estábamos sentados sobre esta cuestión de horas y no tienen idea de cómo demostrarlo.

Alguien puede ayudarme con una pista?

Gracias!

Answer 1

Demostrar por inducción sobre $n$:

• Es trivial para el caso de $n=2$. (Por qué?)
• El inductivo paso es agregar un vértice y, debido a que es un árbol, que ha cambiado en la mayoría de las tres de la $V_i$. (¿Cuáles? ¿Cómo han cambiado? Entender esto antes de continuar.) En la suma, entonces, usted está agregando $1$ a mano izquierda y $-(k-2)+(k+1-2)$ algunos $k$ a la derecha, que mantiene la igualdad.

Answer 2

Contar el número de bordes de dos maneras.

Por el Apretón de manos Lema: $|E|=\frac{1}{2}\sum\limits_{i=1}^\infty i|V_i|$. Por la caracterización de los árboles: $|E|= \sum\limits_{i=1}^\infty |V_i|-1$.

Equiparar estas dos cantidades, y recuerda que $|V_1|$ es el número de hojas.

$\frac{1}{2}\sum\limits_{i=1}^\infty i|V_i|= \sum\limits_{i=1}^\infty |V_i|-1,$

así

$\sum\limits_{i=1}^\infty (i-2)|V_i|+2=0$

así

$-|V_1|+0+\sum\limits_{i=3}^\infty (i-2)|V_i|+2=0$

así

$|V_1|=\sum\limits_{i=3}^\infty (i-2)|V_i|+2$

que es lo que está después.

Answer 3

Existe una estrecha relación entre el problema y el grado de la fórmula de la suma de los gráficos. Para cualquier finito gráfico, árbol o de otra manera, la ecuación

$$2|E| = \sum_{v\in V} \deg(v)$$

siempre se mantiene. Si no lo has probado antes, vale la pena detenerse a pensar acerca de por qué la ecuación es correcta.

Es posible transformar la ecuación

$$|V_1| = 2 + \sum (j-2)|V_j|$$

en una declaración explícita de que el grado teorema de la suma de los árboles. Sugerencia: $j|V_j|$ es sólo otra manera de escribir $\sum_{v\in V_j} \deg(v)$.