La secuencia de grados de un gráfico simple es la secuencia de los grados de los Nodes en el gráfico en orden decreciente. ¿Cuál de las siguientes secuencias no puede ser la secuencia de grados de ningún gráfico?
(I) 7, 6, 5, 4, 4, 3, 2, 1 (II) 6, 6, 6, 6, 3, 3, 2, 2 (III) 7, 6, 6, 4, 4, 3, 2, 2 (IV) 8, 7, 7, 6, 4, 2, 1, 1
(A) I y II
(B) III y IV
(C) IV solamente
(D) II y IV
Respuesta: (D)
Explicación: Un algoritmo o método genérico para resolver esta pregunta es
1: el procedimiento es una secuencia de grados válida (L)
2: para n en la lista L hacer
3: si L no tiene n elementos al lado del actual, devuelve falso
4: decrementar los siguientes n elementos de la lista en 1
5: organícelo de nuevo como una secuencia de grados, es decir, en orden descendente
6: si algún elemento de la lista se vuelve negativo, devuelve falso
7: devuelve verdadero
La razón detrás de este método proviene de las propiedades del gráfico simple. Enumerando los resultados falsos, 1) si L no tiene suficientes elementos después del actual o 2) si algún elemento de la lista se vuelve negativo, entonces significa que no hay suficientes Nodes para acomodar los bordes en una forma de gráfico simple , lo que conducirá a la violación de cualquiera de las dos condiciones del gráfico simple (sin bucles automáticos y sin bordes múltiples entre dos Nodes), si no otras.
Consulte https://www.geeksforgeeks.org/data-structures-and-algorithms-set-25/
Esta solución es aportada por Vineet Purswani.
Otro:
Una secuencia de grados d1,d2,d2. . . dn de entero no negativo es gráfico si es una secuencia de grados de un gráfico. Ahora presentamos una poderosa herramienta para determinar si una secuencia en particular es gráfica debido a Havel y Hakimi.
Teorema de Havel-Hakimi:
→ Según este teorema, Sea D la secuencia d1,d2,d2. . . dn con d1 ≥ d2 ≥ d2 ≥ . . . dn para n≥ 2 y di ≥ 0.
→ Entonces D0 será la sucesión obtenida por:
→ Descartando d1, y
→ Restando 1 de cada una de las próximas entradas d1 de D.
→ Esa es la secuencia de grados D0 sería: d2-1, d2-1, d3-1. . . , dd1+1 -1 . . . , dn
→ Entonces, D es gráfico si y sólo si D0 es gráfico.
Ahora, aplicamos este teorema a las sucesiones dadas:
opción I) 7,6,5,4,4,3,2,1 → 5,4,3,3,2,1,0 → 3,2,2,1,0,0 → 1,1,0 ,0,0 → 0,0,0,0 por lo que es gráfico.
Opción II) 6,6,6,6,3,3,2,2 → 5,5,5,2,2,1,2 (organizar en orden ascendente) → 5,5,5,2,2,2 ,1 → 4,4,1,1,1,0 → 3,0,0,0,0 → 2,-1,-1,-1,0 pero d (grado de un vértice) no es negativo por lo que es no un gráfico.
Opción III) 7,6,6,4,4,3,2,2 → 5,5,3,3,2,1,1 → 4,2,2,1,1,0 → 1,1,0 ,0,0 → 0,0,0,0 por lo que es gráfico.
Opción IV) 8,7,7,6,4,2,1,1, aquí el grado de un vértice es 8 y el número total de vértices es 8, por lo que es imposible, por lo tanto, no es gráfico.
Por lo tanto, solo las opciones I) y III) son una secuencia gráfica y la respuesta es la opción-D
Esta solución es aportada por Nirmal Bharadwaj.
Cuestionario de esta pregunta
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