El problema canónico de esta categoría es decidir si hay un gráfico simple con una secuencia de grados dada. El teorema de Erdős-Gallai resuelve esto y puede implementarse en tiempo O (n). Una solución alternativa (más lenta pero más simple) es el algoritmo Havel-Hakimi.
Si permite múltiples aristas entre los mismos vértices, el problema se vuelve significativamente más simple. Si también permite bucles automáticos (con cada autociclo contando como dos aristas) solo hay dos condiciones: existe un gráfico con los grados dados si la suma de grados es par. El gráfico se puede conectar si todos los grados son positivos y su suma es al menos 2n-2. (prueba: disminuya algunos grados hasta obtener la suma exactamente 2n-2, luego demuestre que para cualquier secuencia de este tipo puede construir un árbol y finalmente restaurar los grados originales y agregar bordes arbitrarios).
Si desea rechazar los bucles automáticos, la única restricción nueva será que ningún grado puede exceder la suma de todos los demás. (idea de prueba: en la construcción anterior, disminuya primero el mayor grado).
- ¿Cuándo crees que alcanzaremos la inteligencia general artificial?
- ¿Qué debo hacer durante el verano antes de mi segundo año como estudiante de informática?
- ¿Cuáles son los libros que deben leer para los estudiantes de Ciencias de la Computación que desean trabajar en nuevas empresas web?
- ¿Cuáles son algunas ideas innovadoras de proyectos de último año para un estudiante de TI / CS?
- Además de los transistores, ¿cuál fue la razón del éxito de reducir el tamaño de las computadoras?
