Gráfico de complemento

Grafica con los mismos nodos pero conexiones opuestas que otra

El gráfico de Petersen (a la izquierda) y su gráfico complemento (a la derecha).

En el campo matemático de la teoría de grafos , el complemento o inverso de un gráfico G es un gráfico H en los mismos vértices tal que dos vértices distintos de H son adyacentes si y sólo si no son adyacentes en G. Es decir, para generar el complemento de un gráfico, se completan todos los bordes faltantes necesarios para formar un gráfico completo y se eliminan todos los bordes que estaban allí anteriormente. ^[1]

El complemento no es el complemento establecido del gráfico; sólo se complementan los bordes.

Definición

Sea G  = ( V ,  E ) un gráfico simple y sea K formado por todos los subconjuntos de 2 elementos de V. Entonces H  = ( V ,  K  \  E ) es el complemento de G , ^[2] donde K  \  E es el complemento relativo de E en K . Para gráficos dirigidos , el complemento se puede definir de la misma manera, como un gráfico dirigido en el mismo conjunto de vértices, utilizando el conjunto de todos los pares ordenados de 2 elementos de V en lugar del conjunto K en la fórmula anterior. En términos de la matriz de adyacencia A del gráfico, si Q es la matriz de adyacencia del gráfico completo del mismo número de vértices (es decir, todas las entradas son unidades excepto las diagonales que son cero), entonces la matriz de adyacencia del complemento de A es control de calidad .

El complemento no está definido para multigrafos . En gráficos que permiten bucles propios (pero no adyacencias múltiples), el complemento de G se puede definir agregando un bucle propio a cada vértice que no tenga uno en G y, en caso contrario, usando la misma fórmula anterior. Sin embargo, esta operación es diferente de la de gráficos simples, ya que aplicarla a un gráfico sin bucles automáticos daría como resultado un gráfico con bucles automáticos en todos los vértices.

Aplicaciones y ejemplos

Varios conceptos de teoría de grafos están relacionados entre sí mediante complementación:

• El complemento de un gráfico sin aristas es un gráfico completo y viceversa.
• Cualquier subgrafo inducido del gráfico complementario de un gráfico G es el complemento del subgrafo inducido correspondiente en G.
• Un conjunto independiente en un gráfico es una camarilla en el gráfico complementario y viceversa. Este es un caso especial de las dos propiedades anteriores, ya que un conjunto independiente es un subgrafo inducido sin aristas y una camarilla es un subgrafo inducido completo.
• El grupo de automorfismos de un gráfico es el grupo de automorfismos de su complemento.
• El complemento de todo gráfico sin triángulos es un gráfico sin garras , ^[3] aunque lo contrario no es cierto.

Gráficos autocomplementarios y clases de gráficos.

El camino de los cuatro vértices es autocomplementario.

Un grafo autocomplementario es un grafo isomorfo a su propio complemento. ^{[1] Los ejemplos incluyen el} gráfico de ruta de cuatro vértices y el gráfico de ciclo de cinco vértices . No existe una caracterización conocida de gráficos autocomplementarios.

Varias clases de gráficos son autocomplementarias, en el sentido de que el complemento de cualquier gráfico de una de estas clases es otro gráfico de la misma clase.

• Los gráficos perfectos son aquellos en los que, para cada subgrafo inducido, el número cromático es igual al tamaño de la camarilla máxima. El hecho de que el complemento de un grafo perfecto también lo sea es el teorema del grafo perfecto de László Lovász . ^[4]
• Los cografos se definen como los gráficos que se pueden construir a partir de vértices individuales mediante operaciones de unión y complementación disjuntas . Forman una familia de grafos autocomplementarios: el complemento de cualquier cografo es otro cografo diferente. Para cografos de más de un vértice, exactamente un gráfico en cada par complementario está conectado, y una definición equivalente de cografos es que cada uno de sus subgrafos inducidos conectados tiene un complemento desconectado. Otra definición autocomplementaria es que son los gráficos sin subgrafo inducido en forma de un camino de cuatro vértices. ^[5]
• Otra clase de gráficos autocomplementaria es la clase de gráficos divididos , los gráficos en los que los vértices se pueden dividir en una camarilla y un conjunto independiente. La misma partición da un conjunto independiente y una camarilla en el gráfico de complemento. ^[6]
• Los gráficos de umbral son los gráficos formados agregando repetidamente un vértice independiente (uno sin vecinos) o un vértice universal (adyacente a todos los vértices agregados previamente). Estas dos operaciones son complementarias y generan una clase de gráficos autocomplementarios. ^[7]

Aspectos algorítmicos

En el análisis de algoritmos sobre gráficos, la distinción entre un gráfico y su complemento es importante, porque un gráfico disperso (uno con un número pequeño de aristas en comparación con el número de pares de vértices) en general no tendrá un complemento disperso. , por lo que un algoritmo que requiere un tiempo proporcional al número de aristas en un gráfico determinado puede requerir una cantidad de tiempo mucho mayor si el mismo algoritmo se ejecuta en una representación explícita del gráfico complementario. Por lo tanto, los investigadores han estudiado algoritmos que realizan cálculos de gráficos estándar en el complemento de un gráfico de entrada, utilizando una representación gráfica implícita que no requiere la construcción explícita del gráfico de complemento. En particular, es posible simular una búsqueda en profundidad o una búsqueda en amplitud en el gráfico complementario, en una cantidad de tiempo que es lineal en el tamaño del gráfico dado, incluso cuando el gráfico complementario puede tener un tamaño mucho mayor. . ^[8] También es posible utilizar estas simulaciones para calcular otras propiedades relacionadas con la conectividad del gráfico de complemento. ^{[8] [9]}

Referencias

1. Bondy, John Adrian ; Murty, USR (1976), Teoría de grafos con aplicaciones, Holanda Septentrional, p. 6, ISBN 0-444-19451-7.
2. Diestel, Reinhard (2005), Teoría de grafos (3.ª ed.), Springer , ISBN 3-540-26182-6. Edición electrónica, página 4.
3. Chudnovsky, María ; Seymour, Paul (2005), "La estructura de los gráficos sin garras" (PDF) , Encuestas en combinatoria 2005 , London Math. Soc. Serie de notas de conferencia, vol. 327, Cambridge: Universidad de Cambridge. Prensa, págs. 153–171, SEÑOR  2187738.
4. Lovász, László (1972a), "Hipergrafos normales y la conjetura del grafo perfecto", Matemáticas discretas , 2 (3): 253–267, doi : 10.1016/0012-365X(72)90006-4.
5. Corneil, director general ; Lerchs, H.; Stewart Burlingham, L. (1981), "Gráficos reducibles de complemento", Matemáticas aplicadas discretas , 3 (3): 163–174, doi : 10.1016/0166-218X(81)90013-5 , SEÑOR  0619603.
6. Golumbic, Martin Charles (1980), Teoría de grafos algorítmicos y gráficos perfectos , Academic Press, Teorema 6.1, p. 150, ISBN 0-12-289260-7, señor  0562306.
7. Golumbic, Martín Charles; Jamison, Robert E. (2006), "Clases de gráficos de tolerancia de rango", Journal of Graph Theory , 52 (4): 317–340, doi :10.1002/jgt.20163, MR  2242832.
8. Ito, Hiro; Yokoyama, Mitsuo (1998), "Algoritmos de tiempo lineal para búsqueda de gráficos y determinación de conectividad en gráficos de complemento", Cartas de procesamiento de información , 66 (4): 209–213, doi :10.1016/S0020-0190(98)00071-4, SEÑOR  1629714.
9. Kao, Ming-Yang; Occhiogrosso, Neill; Teng, Shang-Hua (1999), "Esquemas de compresión de gráficos simples y eficientes para gráficos densos y complementarios", Journal of Combinatorial Optimization , 2 (4): 351–359, doi :10.1023/A:1009720402326, MR  1669307.