Una n-tupla ordenada (d1, d2, …, dn) con d1 >= d2 >= ⋯ >= dn se llama gráfica si existe una gráfica simple no dirigida con n vértices de grados d1, d2, …, dn respectivamente. ¿Cuál de las siguientes 6 tuplas NO es gráfica?
(A) (1, 1, 1, 1, 1, 1)
(B) (2, 2, 2, 2, 2, 2)
(C) (3, 3, 3, 1, 0, 0)
(D ) (3, 2, 1, 1, 1, 0)
Respuesta: (C)
Explicación:El gráfico requerido no es posible con el conjunto de grados dado de (3, 3, 3, 1, 0, 0). Usando esta tupla de 6, el gráfico formado será un gráfico no dirigido Disjunto, donde los dos vértices del gráfico no deben estar conectados a ningún otro vértice (es decir, el grado será 0 para ambos vértices) del gráfico. Y para los 4 vértices restantes, el gráfico debe satisfacer los grados de (3, 3, 3, 1).
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA