Verificamos profundamente cada artículos de nuestro sitio web con la meta de mostrarte en todo momento la información más veraz y certera.
Solución:
Tal vez a alguien se le ocurra una mejor respuesta o explique los detalles, pero he decidido convertir mi segundo comentario en una respuesta.
Después de googlear un poco encontré lo siguiente:
Ejercicio 8.2.8 de la pág. 127 en Melnikov: Ejercicios de teoría de grafos:
Demuestre que una n-sucesión gráfica adecuada sin ceros es potencialmente conectada si y solo $sum_i=1^n d_i ge 2(n-1)$.
Página 117:
Una secuencia $d$ se llama $d$-gráfica si existe un gráfico cuya secuencia de grados es $d$. Tal gráfica se llama realización de la sucesión $d$.
Una sucesión $n$ no creciente $d$ se llama adecuado si su suma es par y $d_1le n-1$
A secuencia potencialmente gráfica es una secuencia gráfica que tiene una realización a través de un gráfico conexo.
Página 286:
Sugerencia: la suficiencia puede probarse por inducción sobre $n$. El paso inductivo puede basarse en el teorema de Havel-Hakimi.
El teorema de Havel-Hakimi se formula en este libro de la siguiente manera:
Para una sucesión $n$ adecuada, $n>1$, la secuencia derivada $d^i$, $1le ile n$ se define de la siguiente manera. El elemento $d_i$ se elimina de $d$ y los primeros $d_i$ elementos restantes se reducen en 1.
Teorema 8.1.3 (V. Havel, S. Hakimi) Una sucesión $n$ propia $dne(0^n)$ es gráfica si y sólo si toda sucesión derivada $d^i$, $1le ile n$, es gráfica.
Este documento menciona que:
En [4] se afirma que para que una secuencia sea gráfica y potencialmente conectada es necesario y suficiente que $$sum_i=1^k d_i le k(k-1) + sum_i=k+1^ n min(k,d_i)$$ se cumple y la suma de grados es al menos $2(n-1)$, es decir, hay al menos suficientes grados para producir un árbol de expansión. Sin embargo, no se proporciona ningún algoritmo más que producir un árbol de expansión y luego usar el algoritmo Havil-Hakimi en el gráfico residual.
[4] M. Mihail y NK Vishnoi. Sobre la generación de gráficos con grados de vértice prescritos para el modelado de redes complejas. En ARACNE 2002, páginas 1-12, 2002.
(La condición anterior es la condición del teorema de Erdős-Gallai).
Una modificación del algoritmo de Havel-Hakimi para obtener un gráfico conectado se describe en el artículo de Fabien Viger y Matthieu Latapy: generación eficiente y simple de gráficos conectados simples aleatorios con una secuencia de grados prescrita. Sin embargo, este artículo no menciona ninguna condición para la existencia de un grafo conexo.
EDITAR
Finalmente encontré un libro que también da una prueba completa. La prueba es diferente de la sugerida en la pista del libro de Melnikov. (Pasé algún tiempo pensando en esta sugerencia y no pude completar la solución. No tengo mucha experiencia con la teoría de grafos, pero sospecho que el autor del libro podría cometer un error allí. O, más probablemente, no entendí bien su pista.) La idea básica de la prueba dada en este libro es construir primero un gráfico a partir de la secuencia de grados y, si no está conectado, cambiar los bordes varias veces hasta que se vuelva conectado.
Claude Berge: Grafos e Hipergrafos, Teorema 9, p. 117-118:
Sea $d_1ge d_2 ge ldots ge d_n$ una secuencia de enteros, $nge 2$. Una condición necesaria y suficiente para la existencia de un grafo conexo simple $G$ con grados $d_G(x_i)=d_i$ es que $$begingather* d_n ge 1\ sum_i=1^n d_i ge 2(n-1)\ sum_i=1^n d_itext es par \ sum_i=1^k d_i le sum_i=1^k overline d_i endreunir*$$
Solo las condiciones $d_nge 1$ y $sum_i=1^n d_i ge 2(n-1)$ se agregan aquí a las condiciones del teorema que caracteriza las secuencias de grados para gráficos simples. Es solo una formulación diferente del teorema de Erdős-Gallai.
El significado de $overline d_i$ (que el autor llama conjugado corregido de la secuencia $d_i$) se explica en la página 111.
Solo me enteré de las secuencias gráficas hace un par de horas y (independientemente) descubrí la solución Havel-Hakimi a través del juego aquí: http://jacquerie.github.io/hh/. Realmente recomiendo jugar al menos algunas “rondas” para ver qué tan bien entiendes (o aprendes) cómo funciona Havel-Hakimi.
Mis clases de teoría de grafos fueron hace un par de décadas, así que solo tengo una prueba intuitiva y no rigurosa, pero ofrezco la siguiente observación (lema):
Se pueden concatenar dos secuencias gráficas para formar una nueva secuencia gráfica.
Corolario:
Si una secuencia gráfica se puede dividir en dos (o más) secuencias gráficas, entonces existe una solución gráfica no conectada.
La secuencia gráfica no vacía más simple es 1,1. Puede agregar esto a cualquier secuencia gráfica para obtener una nueva secuencia gráfica que tenga un gráfico no conectado como solución. Sin embargo, esto no muestra que no exista una solución conectada.
Considere 2,2,2,1,1. Esto se puede dividir en 2,2,2 y 1,1, y el uso de la implementación “tradicional” del algoritmo de Havel-Hakimi producirá este gráfico (si considera restar uno cada vez como dibujar una línea a un nodo).
Sin embargo, si los números se reorganizan así:
1 2 2 2 1
- 1 2 2 1
- - 1 2 1
- - - 1 1
- - - - 0
luego obtenemos una ruta de cinco nodos (un gráfico como: ooooo).
Rompí el orden estricto como se especifica en el teorema de Havel-Hakimi. Aquí funciona, pero la mayoría de los reordenamientos arbitrarios no lo harán (juega y verás).
Para su primer ejemplo (3,3,1,1,1,1,1,1) hay dos particiones: 3,3,1,1,1,1|1,1 y 3,1,1,1| 3,1,1,1.
Aquí puede ver un gráfico parcialmente construido con dos posibles soluciones, donde 2,1,1 pueden convertirse en un gráfico separado o pueden conectarse al gráfico principal. (No es el ejemplo más simple, sino uno que acaba de generar jacquerie.github.io/hh/).
Puedes añadir valor a nuestro contenido informacional dando tu veteranía en los informes.