Demostrar la existencia de un grafo de 15 vértices con ciertos grados de vértices dados

Question

Este es el ejercicio:

Si es posible dibujar un gráfico con 15 vértices teniendo
3 vértices con grado 4;
4 vértices con grado 3;
6 vértices con grado 2;
0 vértices con grado mayor que los anteriores.

Este es el gráfico que he hecho por mi cuenta:

mis preguntas son,

¿El gráfico que he hecho es correcto?

y además, dado que en el ejercicio dado tenemos el número de vértices y el grado de algunos de ellos, ¿existe algún teorema o algoritmo que nos diga si es posible dibujar un grafo con una cierta configuración? A veces es laborioso intentar dibujar un gráfico haciendo intentos, y sin ninguna certeza de su existencia.

¿Puedes ayudarme? ¡Gracias!

Answer 1

El teorema sobre la existencia en el que estás interesado probablemente sea el siguiente resultado integral para grafos simples (sin bucles ni aristas múltiples): https://es.wikipedia.org/wiki/Teorema_de_Erd%C5%91s%E2%80%93Gallai. También hay un enfoque algorítmico, al que se hace referencia en otra respuesta, pero si lo que buscas es una verificación antes de intentar realizar la secuencia de grados con un grafo, entonces Erdos-Gallai debería ayudarte. Yo simplemente escribiría un programa simple para usar el teorema como verificador para una secuencia dada. (Una posible implementación en Python se da al final)

Pero también podemos verificar a mano, por supuesto. En tu caso, las condiciones dadas determinan que tu secuencia de grados sea: $$(4,4,4,3,3,3,3,2,2,2,2,2,2,x,y)$$ donde $x \geq y$ y $x,y \in \{0,1\}$. Como puedes ver en tu propio trabajo, $(x,y)$ podría ser $(1,1)$ o $(0,0)$. Pero el lema del apretón de manos muestra que $(1,0)$ no es posible (la suma de la secuencia de grados debe ser par).

Trabajemos con tu secuencia, $$(4,4,4,3,3,3,3,2,2,2,2,2,2,1,1)$$. En primer lugar, el lema del apretón de manos sale bien porque la suma de la secuencia de grados es par.

Las sumas parciales de tu secuencia de grados son $$(4,8,12,15,18,21,24,26,28,30,32,34,36,37,38)$$ La secuencia $(k(k-1))$ para $k=1\ldots n$ es $$(0,2,6,12,20,30,42,56,72,90,110,132,156,182,210)$$ La suma de $\sum\limits_{i=k+1}^{n}\min(d_i,k)$ arroja la secuencia: $$(14, 24, 26, 23, 20, 17, 14, 12, 10, 8, 6, 4, 2, 1, 0)$$ Sumando las dos secuencias anteriores vemos que la secuencia de la parte derecha de la igualdad del teorema es $$(14, 26, 32, 35, 40, 47, 56, 68, 82, 98, 116, 136, 158, 183, 210)$$ Lo cual es en todos los casos mayor que la secuencia de la suma parcial de la secuencia de grados $$(4,8,12,15,18,21,24,26,28,30,32,34,36,37,38)$$ Esto verifica que existe un grafo que satisface tu secuencia de grados, ¡lo cual ahora sabes porque has construido justo ese grafo!

Posible implementación en Python del código: def erdos_gallai(ds): n = len(ds) lhs = reduce(lambda c, x: c + [c[-1] + x], ds, [0])[1:] rhs1 = [k*(k-1) for k in range (1, n+1)] rhs2 = [sum([min(ds[i], k+1) for i in range (k+1, n)]) for k in range (0,n)] for i in range (n): if lhs[i] > rhs1[i] + rhs2[i]: return False return True

Answer 2

Su ejemplo es correcto. El algoritmo de Havel–Hakimi es un procedimiento efectivo para determinar si una secuencia de grados dada puede ser realizada (por un grafo simple) y construir tal grafo si es posible.

P.D. En un comentario pregunta si el algoritmo funciona para árboles. En general, si aplicamos el algoritmo de Havel–Hakimi a la secuencia de grados de un árbol, el grafo resultante no necesariamente será un árbol; por ejemplo, $3,3,3,1,1,1,1,1$ es la secuencia de grados de un árbol, pero el algoritmo no produce un árbol. Sin embargo, el algoritmo puede ser fácilmente adaptado para producir un árbol siempre que sea posible.

Sean $d_1,\dots,d_n$ una secuencia de enteros no negativos, $n\gt1.$ Si algún $d_i=0$ entonces no es la secuencia de grados de un árbol, porque un árbol (con más de un vértice) no puede tener un vértice aislado. Por lo tanto, podemos asumir que todos los $d_i$ son positivos. Además, podemos asumir que $d_1+\cdots+d_n=2(n-1),$ de lo contrario no puede ser la secuencia de grados de un árbol.

Sea $G$ el resultado del algoritmo de Havel–Hakimi. El grafo $G$ tiene $n$ vértices y $n-1$ aristas. Si no es un árbol, entonces tiene al menos dos componentes, al menos una de las cuales no es un árbol. Sean $H_1,H_2$ dos componentes de $G,$ y supongamos que $H_2$ no es un árbol. Sea $uv$ una arista de $H_1,$ y sea $xy$ una arista de $H_2$ que está en un ciclo, de modo que $H_2-xy$ es conexo. Si borramos las aristas $xy$ y $uv$ y las reemplazamos con las aristas $xu$ e $yv,$ el grafo resultante $G'=G-xy-uv+xv$ tiene la misma secuencia de grados que $G$ pero con una componente menos. Repetir esta construcción hasta obtener un grafo con la misma secuencia de grados pero solo una componente, es decir, un árbol.