PUERTA | PUERTA CS 2018 | Pregunta 56

¡Sea G un gráfico con 100! vértices, con cada vértice etiquetado por una permutación distinta de los números 1, 2, …, 100. Hay un borde entre los vértices u y v si y solo si la etiqueta de u se puede obtener intercambiando dos números adyacentes en la etiqueta de v. Sea y el grado de un vértice en G, y z el número de componentes conectados en G. Entonces y + 10z = _______.

Nota: esta fue una pregunta de tipo numérico.

(A) 109
(B) 110
(C) 119
(D) Ninguno de estos

Respuesta: (A)
Explicación: Hay un borde entre los vértices u y v si y solo si la etiqueta de u se puede obtener intercambiando dos números adyacentes en la etiqueta de v.
Entonces el conjunto de números de intercambio será {(1, 2), (2, 3), ………..(9, 9)}
Habrá 99 conjuntos de este tipo, es decir, número de aristas = 99
y cada vértice tendrá 99 aristas correspondientes a él.
 

Di gráfica con 3! vértices, entonces los vértices serán como {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}…
Escojamos el vértice {123}, el grado será 2 ya que estará conectado con otros dos vértices {213} y {132}.

Podemos concluir que para n, el grado será n-1.

SO, grado de cada vértice = 99 (como dice y)
Como los vértices están conectados entre sí, el número de componentes conectados formados será 1 (como dice z).

 y+10z = 99+10(1) = 109

Cuestionario de esta pregunta