En la teoría de grafos , el complemento o inversa de un gráfico G es un gráfico H en los mismos vértices de tal manera 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 rellenan 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; solo se complementan los bordes.
Definición
Deje que G = ( V , E ) sea un gráfico sencillo y dejar que K consiste de 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 relativa 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 entradas diagonales que son cero), entonces la matriz de adyacencia del complemento de A es QA .
El complemento no está definido para multigraphs . En los gráficos que permiten auto-bucles (pero no múltiples adyacencias), el complemento de G puede definirse agregando un auto-bucle a cada vértice que no tenga uno en G y, de lo contrario, usando la misma fórmula que la anterior. Sin embargo, esta operación es diferente de la de los 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 la teoría de grafos están relacionados entre sí a través de la complementación:
- El complemento de un gráfico sin bordes es un gráfico completo y viceversa.
- Cualquier subgrafo inducido de la gráfica complemento de un gráfico G es el complemento de la subgrafo inducido correspondiente en G .
- Un conjunto independiente en un gráfico es una camarilla en el gráfico de complemento y viceversa. Este es un caso especial de las dos propiedades anteriores, ya que un conjunto independiente es un subgrafo inducido sin bordes y una camarilla es un subgrafo inducido completo.
- El grupo de automorfismo de un gráfico es el grupo de automorfismo de su complemento.
- El complemento de cada gráfico sin triángulos es un gráfico sin garras , [3] aunque lo contrario no es cierto.
Gráficos y clases de gráficos autocomplementarios
Un gráfico autocomplementario es un gráfico que es 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 los gráficos autocomplementarios.
Varias clases de gráficos son autocomplementarios, 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 gráficos perfectos son los gráficos en los que, para cada subgráfico inducido, el número cromático es igual al tamaño de la camarilla máxima. El hecho de que el complemento de una gráfica perfecta también sea perfecto es el teorema de la gráfica perfecta de László Lovász . [4]
- Los cographs 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 gráficos autocomplementarios: el complemento de cualquier cografo es otro cografo diferente. Para las cografías de más de un vértice, se conecta exactamente una gráfica en cada par complementario, y una definición equivalente de cografías 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 una trayectoria de cuatro vértices. [5]
- Otra clase de gráficos autocomplementarios 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 en 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 toma un tiempo proporcional al número de aristas en un gráfico dado puede tomar una cantidad de tiempo mucho mayor si el mismo algoritmo se ejecuta en una representación explícita del gráfico del complemento. Por lo tanto, los investigadores han estudiado algoritmos que realizan cálculos de gráficos estándar sobre 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 del complemento. En particular, es posible simular o bien búsqueda en profundidad o amplitud-primera búsqueda en el gráfico del complemento, en una cantidad de tiempo que es lineal en el tamaño del gráfico dado, incluso cuando el gráfico de complemento puede tener un tamaño mucho más grande . [8] También es posible utilizar estas simulaciones para calcular otras propiedades relativas a la conectividad del gráfico de complemento. [8] [9]
Referencias
- ↑ a b 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), Graph Theory (3.a ed.), Springer , ISBN 3-540-26182-6. Edición electrónica , página 4.
- ^ Chudnovsky, Maria ; Seymour, Paul (2005), "La estructura de los gráficos sin garras" (PDF) , Encuestas en combinatoria 2005 , London Math. Soc. Lecture Note Ser., 327 , Cambridge: Cambridge Univ. Press, págs. 153-171, MR 2187738..
- ^ Lovász, László (1972a), "Hipergrafías normales y la conjetura de la gráfica perfecta", 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 de complemento", Matemáticas aplicadas discretas , 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. 150, ISBN 0-12-289260-7, MR 0562306.
- ^ Golumbic, Martin 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.
- ^ a b Ito, Hiro; Yokoyama, Mitsuo (1998), "Algoritmos de tiempo lineal para búsqueda de gráficos y determinación de conectividad en gráficos 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 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.