PUERTA | PUERTA CS 2010 | Pregunta 1 – Part 2

Sea G = (V,E) una gráfica. Defina ξ(G) = Σd id xd, donde id es el número de vértices de grado d en G. Si S y T son dos árboles diferentes con ξ(S) = ξ(T),entonces
(A) |S| = 2|T|
(B) |S| = |T|-1
(C) |S| = |T|
(D) |S| = |T|+1

Respuesta: (C)
Explicación: La expresión ξ(G) es básicamente la suma de todos los grados en un árbol. Por ejemplo, en el siguiente árbol, la suma es 3 + 1 + 1 + 1.

    a 
  / | \
 b  c  d

Ahora la pregunta es, si la suma de los grados en los árboles es la misma, ¿cuál es la relación entre el número de vértices presentes en ambos árboles?
La respuesta es, ξ(G) y ξ(T) son iguales para dos árboles, entonces los árboles tienen el mismo número de vértices. Se puede demostrar por inducción. Sea cierto para n vértices. Si agregamos un vértice, entonces el nuevo vértice (si no es el primer Node) aumenta el grado en 2, no importa dónde lo agreguemos. Por ejemplo, intente agregar un nuevo vértice, diga ‘e’ en diferentes lugares en el ejemplo anterior.
Cuestionario de esta pregunta