Sucesión gráfica: ejemplos y cómo determinar si una secuencia lo es

En teoría de grafos, una sucesión gráfica es una secuencia de números enteros no negativos que representa los grados de los vértices de un grafo simple. Es decir, una secuencia (d1, d2, ..., dn) es gráfica si existe un grafo simple con n vértices tal que el grado del i-ésimo vértice es di. Determinar si una secuencia es gráfica es un problema fundamental en la teoría de grafos con diversas aplicaciones en áreas como la optimización de redes y el diseño de algoritmos.

¿Cómo determinar si una secuencia es gráfica?

Existen varios métodos para determinar si una secuencia de números enteros es gráfica. Uno de los más conocidos es el teorema de Erdős-Gallai, que proporciona una condición necesaria y suficiente para que una secuencia sea gráfica. Sin embargo, este teorema puede ser complejo de aplicar en la práctica para secuencias largas.

A continuación, se presentan algunos métodos y ejemplos:

Método del Teorema de Erdős-Gallai

El Teorema de Erdős-Gallai establece que una secuencia no creciente de enteros no negativos (d1 ≥ d2 ≥ ... ≥ dn) es gráfica si y solo si cumple con las dos condiciones siguientes:

1. La suma de los grados es un número par: Σdi = 2m, donde m es el número de aristas.
2. Para cada entero k entre 1 y n se cumple la siguiente desigualdad: Σdi ≤ k(k − 1) + Σmin(k, dj) donde la suma se realiza de j=k+1 a n.

Ejemplo:

Consideremos la secuencia (3, 2, 2, 1, 1). Para verificar si es gráfica usando el Teorema de Erdős-Gallai, primero ordenamos la secuencia de forma no creciente: (3, 2, 2, 1, 1).

La suma de los grados es 3 + 2 + 2 + 1 + 1 = 9, que es impar. Por lo tanto, esta secuencia no es gráfica según la primera condición del teorema.

Ejemplo 2:

Consideremos la secuencia (4, 3, 2, 1, 0). La suma de los grados es 10 (par). Apliquemos la segunda condición:

• k=1: 4 ≤ 1(1-1) + 0 = 0 (Falso, no cumple la condición)

Como la segunda condición no se cumple para k=1, esta secuencia no es gráfica.

Método Havel-Hakimi

El algoritmo de Havel-Hakimi es un método iterativo para determinar si una secuencia es gráfica. Consiste en los siguientes pasos:

1. Ordenar la secuencia de forma no creciente.
2. Si la secuencia contiene algún elemento negativo, entonces la secuencia no es gráfica.
3. Si todos los elementos son cero, la secuencia es gráfica.
4. Eliminar el primer elemento, llamémoslo dRestar 1 a los siguientes d1 elementos.
5. Ordenar la nueva secuencia y repetir desde el paso

Ejemplo:

Consideremos la secuencia (3, 2, 2, 1, 0).

1. La secuencia ya está ordenada.
2. No hay elementos negativos.
3. No todos los elementos son cero.
4. Eliminamos el 3, y restamos 1 a los siguientes 3 elementos: (1, 1, 0, 0).
5. Ordenamos: (1, 1, 0, 0).
6. Eliminamos el 1, restamos 1 a los siguientes elementos: (0, -1, 0).
7. Hay un elemento negativo (-1), por lo que la secuencia original no es gráfica.

Ejemplos de Sucesiones Gráficas

Ejemplo 1: (2, 2, 2) Esta secuencia es gráfica. Se puede representar con un triángulo.

Ejemplo 2: (4, 2, 1, 1, 1) Esta secuencia es gráfica. Un posible grafo sería un vértice central con grado 4 conectado a cuatro vértices con grado

Ejemplo 3: (3, 3, 3, 3, 3, 3) Esta secuencia es gráfica. Se puede representar como un ciclo o un grafo completo.

Tabla Comparativa de Métodos

Consultas Habituales sobre Sucesiones Gráficas

• ¿Cómo se construye un grafo a partir de una sucesión gráfica? Una vez que se ha determinado que una secuencia es gráfica, la construcción de un grafo correspondiente puede hacerse usando algoritmos como el algoritmo de Havel-Hakimi en reversa o mediante métodos gráficos intuitivos.
• ¿Qué aplicaciones tienen las sucesiones gráficas? Las sucesiones gráficas tienen aplicaciones en varias áreas, incluyendo el diseño de redes, química (representando moléculas), la optimización combinatoria y la teoría de redes sociales.
• ¿Existen secuencias no gráficas? Sí, muchas secuencias de números enteros no representan los grados de los vértices de ningún grafo simple. El Teorema de Erdős-Gallai y el algoritmo de Havel-Hakimi permiten determinar si una secuencia es o no gráfica.

Conclusión

La determinación de si una secuencia es gráfica es un problema importante en la teoría de grafos. Existen diferentes métodos para abordar este problema, cada uno con sus propias ventajas y desventajas en términos de complejidad y facilidad de implementación. El algoritmo de Havel-Hakimi ofrece una solución eficiente y fácil de implementar para muchos casos. El entendimiento de las sucesiones gráficas es fundamental para comprender y trabajar con grafos, una estructura de datos crucial en numerosas disciplinas.