¿Qué condición hay que imponer al teorema de Havel-Hakimi para comprobar que se trata de un grafo conexo?

Question

Teorema de Havel-Hakimi : Una secuencia s: $d_1, d_2, \ldots, d_n$ de enteros no negativos con $\Delta = d_1 \geq d_2 \geq \ldots \geq d_n$ y $\Delta \geq 1$ es gráfica si y sólo si la secuencia $$s_1: d_2 - 1, d_3 - 1, \ldots d_{\Delta + 1} - 1, d_{\Delta + 2}, \ldots, d_n$$ es gráfico.
El teorema de Havel-Hakimi proporciona un algoritmo para determinar si una secuencia finita dada de enteros no negativos enteros no negativos es gráfica. Si, al aplicar repetidamente el teorema 1, llegamos a una secuencia en la que cada término de que 0, entonces la secuencia original es gráfica. Por otro lado, si llegamos a una secuencia que contiene un entero, entonces la secuencia dada no es gráfica.

He probado varias secuencias y me he dado cuenta de que la secuencia no es gráfica si falla el teorema de Havel-Hakimi. Sin embargo, no siempre funciona para gráfico conectado . Por ejemplo, la secuencia: $$ 3, 3, 1, 1, 1, 1, 1, 1$$ puede ser procesado por el algoritmo de Havel-Hakimi como sigue:

3, 3, 1, 1, 1, 1, 1, 1
2, 0, 0, 1, 1, 1, 1
2, 1, 1, 1, 1, 0, 0
0, 0, 1, 1, 0, 0
1, 1, 0, 0, 0, 0
0, 0, 0, 0, 0

Pero no se puede graficar como un componente conectado. Por otro lado, la secuencia $$5, 4, 3, 2, 2, 2, 2, 2$$ también satisface el algoritmo de Havel-Hakimi, pero se puede graficar de la siguiente manera:

Así que mi pregunta es, ¿qué otras condiciones hay que añadir para que el algoritmo de Havel-Hakimi funcione para el gráfico conectado? Gracias.

Answer 1

Tal vez alguien proponga una respuesta mejor o explique los detalles, pero he decidido convertir mi segundo comentario en una respuesta.

Después de buscar un poco en Google he encontrado lo siguiente:

Ejercicio 8.2.8 en la p. 127 en Melnikov: Ejercicios de teoría de grafos:

Demostrar que una n-secuencia gráfica propia sin ceros es potencialmente conexa si y sólo $\sum_{i=1}^n d_i \ge 2(n-1)$ .

Página 117:

Una secuencia $d$ se llama $d$ -si existe un grafo cuya secuencia de grados es $d$ . Dicho gráfico se denomina una realización de la secuencia $d$ .

Una cantidad no creciente $n$ -secuencia $d$ se llama adecuado si su suma es par y $d_1\le n-1$

A secuencia potencialmente gráfica es una secuencia de grafos que tiene una realización mediante grafos conectados.

Página 286:

Sugerencia: La suficiencia puede demostrarse 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 como sigue:

Para una adecuada $n$ -secuencia, $n>1$ El secuencia derivada $d^i$ , $1\le i\le n$ se define como sigue. El elemento $d_i$ se elimina de $d$ y la primera $d_i$ los elementos restantes se reducen en 1.

Teorema 8.1.3 (V. Havel, S. Hakimi) Una adecuada $n$ -secuencia $d\ne(0^n)$ es gráfica si y sólo si cada secuencia derivada $d^i$ , $1\le i\le n$ es gráfico.

Este papel 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 mantiene 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 da ningún algoritmo que no sea el de producir un árbol de expansión y luego utilizar el algoritmo de Havil-Hakimi en el gráfico residual.

[4] M. Mihail y N. K. Vishnoi. Sobre la generación de grafos con grados de vértice prescritos para la modelización de redes complejas . En ARACNE 2002, páginas 1-12, 2002.

(La condición anterior es la condición de Teorema de Erdős-Gallai. )

En el artículo de Fabien Viger y Matthieu Latapy se describe una modificación del algoritmo de Havel-Hakimi para obtener un grafo conectado: Generación eficiente y sencilla de grafos simples conectados al azar con una secuencia de grados prescrita . Sin embargo, este documento no menciona ninguna condición para la existencia de un grafo conectado.

EDITAR

Por fin he encontrado un libro que da también una prueba completa. La prueba es diferente de la sugerida en la pista del libro de Melnikov. (He pasado algún tiempo pensando en esta pista y no he sido capaz de completar la solución. No tengo mucha experiencia con la teoría de grafos, pero sospecho que el autor del libro puede cometer un error. O, lo que es más probable, que yo haya entendido mal 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 intercambiar las aristas varias veces hasta que se convierta en conectado.

Claude Berge: Graphs and Hypergraphs, Teorema 9, p. 117-118 :

Dejemos que $d_1\ge d_2 \ge \ldots \ge d_n$ sea una secuencia de números enteros, $n\ge 2$ . Una condición necesaria y suficiente para la existencia de un grafo simple conectado $G$ con grados $d_G(x_i)=d_i$ es que $$\begin{gather*} d_n \ge 1\\ \sum_{i=1}^n d_i \ge 2(n-1)\\ \sum_{i=1}^n d_i\text{ is even }\\ \sum_{i=1}^k d_i \le \sum_{i=1}^k \overline d_i \end{gather*}$$

Sólo las condiciones $d_n\ge 1$ y $\sum_{i=1}^n d_i \ge 2(n-1)$ se añade aquí a las condiciones del teorema que caracteriza las secuencias de grados para los grafos simples. Se trata de 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 página 111 .

Answer 2

Me enteré de las secuencias gráficas hace sólo un par de horas, y (de forma independiente) descubrí la solución Havel-Hakimi a través del juego aquí: http://jacquerie.github.io/hh/ . Realmente recomiendo jugar al menos unas cuantas "rondas" para ver si entiendes (o aprendes) cómo funciona el Havel-Hakimi.

Mis clases de teoría de grafos fueron hace un par de décadas, así que sólo tengo una prueba intuitiva y no rigurosa, pero ofrezco la siguiente observación (lema):

Dos secuencias gráficas pueden concatenarse para formar una nueva secuencia gráfica.

Corolario:

Si una secuencia gráfica puede dividirse en dos (o más) secuencias gráficas, entonces existe una solución gráfica no conectada.

La secuencia gráfica más sencilla no vacía es 1,1. Se puede añadir esto a cualquier secuencia gráfica para obtener una nueva secuencia gráfica que tiene como solución un gráfico no conectado. Sin embargo, esto no demuestra que no exista una solución conectada.

Considera 2,2,2,1,1. Esto se puede dividir en 2,2,2 y 1,1, y utilizando la implementación "tradicional" del algoritmo de Havel-Hakimi se obtendrá este gráfico (si se considera que restar uno cada vez es trazar una línea a un nodo).

Sin embargo, si los números se reordenan así:

1 2 2 2 1
- 1 2 2 1
- - 1 2 1
- - - 1 1
- - - - 0

entonces obtenemos un camino de cinco nodos (un gráfico como: o-o-o-o ).

Rompí el orden estricto como se especifica en el teorema de Havel-Hakimi. Aquí funciona, pero la mayoría de las reordenaciones arbitrarias no lo harán (juega y verás).

Para tu primer ejemplo (3,3,1,1,1,1,1,1) hay dos particiones: 3,3,1,1,1|1,1 y 3,1,1,1|3,1,1,1.

Aquí puedes ver un gráfico parcialmente construido con dos posibles soluciones, donde 2,1,1 puede convertirse en un gráfico separado, o puede conectarse al gráfico principal. (No es el ejemplo más sencillo, pero sí uno que jacquerie.github.io/hh/ que se acaba de generar).

Answer 3

@Martin Sleziak hace referencia a un documento que genera una realización conectada de una secuencia de grados de la siguiente manera 1) generar cualquier realización utilizando el procedimiento estándar de Havel-Hakimi 2) recablear las aristas de forma que se conserve la secuencia de grados, pero haciendo que el gráfico sea conectado.

Este método funciona, pero es bastante complicado de aplicar.

Encontré un algoritmo mucho más simple para generar una realización conectada directamente, y lo detallé en una entrada del blog . Aquí resumiré el método. Para las pruebas, véase la entrada del blog.

El algoritmo Havel-Hakimi suele presentarse así:

1. Toma un nodo con el mayor grado (restante). Denotemos este grado por $d$ .
2. Conéctalo a $d$ otros nodos con los grados más altos (restantes).
3. Repita desde el paso 1 hasta que se agoten todos los grados.

Sin embargo, no es necesario seleccionar el nodo de mayor grado en el paso 1. Se puede elegir cualquier nodo, y el teorema sigue siendo válido (es decir, el algoritmo construye un gráfico simple si la secuencia de partida era gráfica). En su formulación, podemos trabajar con una secuencia de grados $d_1, d_2 \ge \dots \ge d_n$ sin el requisito de que $d_1 \ge d_2$ . Creo que la presentación habitual elige el nodo de mayor grado sólo porque el algoritmo terminará en menos pasos de esta manera.

Teorema: Si en el paso 1. elegimos siempre el nodo con el El más pequeño grado restante, y si la secuencia de grados inicial era gráfica y potencialmente conectada, entonces el algoritmo construirá un gráfico conectado.

Para la prueba, véase la entrada del blog o preimpresión . Para una aplicación, véase IGRealizeDegreeSequence en IGraph/M o igraph_realize_degree_sequence en igraph.

Así, para resumir:

¿Qué condición hay que imponer al teorema de Havel-Hakimi para comprobar que se trata de un grafo conexo?

Simplemente hay que elegir el nodo de menor grado en cada paso.

Sin embargo, si no se está construyendo un gráfico, sino que sólo se comprueba la grafía, entonces es mejor el teorema de Erdős-Gallai. Véase este documento de Z. Király para una aplicación rápida y práctica.

Si la secuencia de grados es potencialmente conectada puede verificarse comprobando si $\sum_{i=1}^n d_i \ge 2(n-1)$ como señaló Martin.