Gráfica complementaria

En el campo matemático de la teoría de grafos , el complemento o inverso de un grafo $G$ es un grafo $H$ en los mismos vértices tal que dos vértices distintos de $H$ son adyacentes si y solo si no son adyacentes en $G.$ Es decir, para generar el complemento de un grafo, se rellenan todas las aristas faltantes requeridas para formar un grafo completo y se eliminan todas las aristas que estaban previamente allí. ^[1]

El complemento no es el complemento del conjunto del gráfico; sólo se complementan las aristas.

Definición

Sea $G = (V, E)$ un grafo 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 grafos dirigidos , el complemento se puede definir de la misma manera, como un grafo 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 grafo, si Q es la matriz de adyacencia del grafo completo del mismo número de vértices (es decir, todas las entradas son la unidad excepto las entradas diagonales que son cero), entonces la matriz de adyacencia del complemento de A es QA .

El complemento no está definido para multigrafos . En grafos que permiten bucles propios (pero no múltiples adyacencias), el complemento de $G$ se puede definir añadiendo un bucle propio a cada vértice que no tenga uno en $G$ y, de lo contrario, utilizando la misma fórmula que la anterior. Sin embargo, esta operación es diferente de la de los grafos simples, ya que al aplicarla a un grafo sin bucles propios se obtendría un grafo con bucles propios 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 grafo complementario de un grafo $G$ es el complemento del subgrafo inducido correspondiente en $G.$
Un conjunto independiente en un grafo es una camarilla en el grafo 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 grafo es el grupo de automorfismos de su complemento.
El complemento de todo grafo libre de triángulos es un grafo libre de garras , ^[3] aunque lo inverso no es cierto.

Gráficos autocomplementarios y clases de gráficos

Un grafo autocomplementario es un grafo que es isomorfo a su propio complemento. ^{[1] Algunos ejemplos son el}grafo de trayectoria de cuatro vértices y el grafo de ciclo de cinco vértices . No se conoce ninguna caracterización de los grafos autocomplementarios.

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

Los grafos perfectos son aquellos en los que, para cada subgrafo inducido, el número cromático es igual al tamaño de la clique máxima. El hecho de que el complemento de un grafo perfecto sea también perfecto es el teorema del grafo perfecto de László Lovász . ^[4]
Los cografos se definen como los grafos 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 los cografos de más de un vértice, exactamente un grafo en cada par complementario es conexo, y una definición equivalente de cografos es que cada uno de sus subgrafos inducidos conexos tiene un complemento desconectado. Otra definición autocomplementaria es que son los grafos sin subgrafo inducido en forma de un camino de cuatro vértices. ^[5]
Otra clase de grafos autocomplementarios es la clase de grafos divididos , grafos 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 grafo complementario. ^[6]
Los grafos de umbral son los grafos que se forman añadiendo repetidamente un vértice independiente (uno sin vecinos) o un vértice universal (adyacente a todos los vértices añadidos previamente). Estas dos operaciones son complementarias y generan una clase de grafos autocomplementarios. ^[7]

Aspectos algorítmicos

En el análisis de algoritmos sobre grafos, la distinción entre un grafo y su complemento es importante, porque un grafo disperso (uno con un pequeño número de aristas en comparación con el número de pares de vértices) en general no tendrá un complemento disperso, y por lo tanto un algoritmo que toma tiempo proporcional al número de aristas en un grafo dado puede tomar una cantidad de tiempo mucho mayor si el mismo algoritmo se ejecuta en una representación explícita del grafo complementario. Por lo tanto, los investigadores han estudiado algoritmos que realizan cálculos de grafos estándar en el complemento de un grafo de entrada, utilizando una representación de grafo implícita que no requiere la construcción explícita del grafo complementario. En particular, es posible simular una búsqueda en profundidad o una búsqueda en amplitud en el grafo complementario, en una cantidad de tiempo que es lineal en el tamaño del grafo dado, incluso cuando el grafo 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 grafo complementario. ^[8]^[9]

Referencias

^ ab Bondy, John Adrian ; Murty, USR (1976), Teoría de grafos con aplicaciones, Holanda Septentrional, pág. 6, ISBN 0-444-19451-7.
^ Diestel, Reinhard (2005), Teoría de grafos (3.ª ed.), Springer , ISBN 3-540-26182-6. Edición electrónica, página 4.
^ Chudnovsky, Maria ; Seymour, Paul (2005), "La estructura de los grafos sin garras" (PDF) , Encuestas en combinatoria 2005 , London Math. Soc. Lecture Note Ser., vol. 327, Cambridge: Cambridge Univ. Press, págs. 153–171, MR 2187738.
^ 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.
^ Corneil, DG ; Lerchs, H.; Stewart Burlingham, L. (1981), "Gráficos reducibles en complemento", Discrete Applied Mathematics , 3 (3): 163–174, doi : 10.1016/0166-218X(81)90013-5 , MR 0619603.
^ Golumbic, Martin Charles (1980), Teoría algorítmica de grafos y grafos perfectos , Academic Press, Teorema 6.1, pág. 150, ISBN 0-12-289260-7, Sr. 0562306.
^ Golumbic, Martin Charles; Jamison, Robert E. (2006), "Clases de grafos con tolerancia de rango", Journal of Graph Theory , 52 (4): 317–340, doi :10.1002/jgt.20163, MR 2242832.
^ ab Ito, Hiro; Yokoyama, Mitsuo (1998), "Algoritmos de tiempo lineal para la búsqueda de grafos y la determinación de la conectividad en grafos complementarios", Information Processing Letters , 66 (4): 209–213, doi :10.1016/S0020-0190(98)00071-4, MR 1629714.
^ Kao, Ming-Yang; Occhiogrosso, Neill; Teng, Shang-Hua (1999), "Esquemas de compresión de grafos simples y eficientes para grafos densos y complementarios", Journal of Combinatorial Optimization , 2 (4): 351–359, doi :10.1023/A:1009720402326, MR 1669307.