Conjunto máximo independiente

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 9 de noviembre de 2021; las comprobaciones requieren 2 ediciones .

En teoría de grafos, un conjunto independiente máximo , un conjunto estable máximo o un conjunto estable máximo es un conjunto independiente que no es un subconjunto de otro conjunto independiente. Es decir, es un conjunto de vértices S tal que cualquier borde del gráfico tiene al menos un vértice final que no está en S , y cualquier vértice que no está en S tiene al menos un vecino en S. Un conjunto independiente máximo también es un conjunto dominante en un gráfico, y cualquier conjunto dominante que sea independiente debe ser un conjunto independiente máximo, por lo que los conjuntos independientes máximos también se denominan conjuntos dominantes independientes . Un gráfico puede tener muchos conjuntos independientes máximos en una amplia gama de tamaños. [una]

El conjunto independiente más grande en tamaño se llama el conjunto independiente más grande .

Por ejemplo, en un grafo P 3 , caminos con tres vértices a , b y c y dos aristas ab y bc , los conjuntos { b } y { a , c } son independientes al máximo, de los cuales solo { a , c } es el independiente más grande. El conjunto { a } es independiente, pero no maximal, ya que es un subconjunto de { a , c }. En el mismo gráfico, los conjuntos { a , b } y { b , c } son las camarillas máximas.

La frase "conjunto independiente máximo" también se usa para describir los subconjuntos máximos de elementos independientes en estructuras matemáticas distintas de gráficos, en particular, en espacios vectoriales y matroides .

Relación con otros conjuntos de vértices

Si S  es un conjunto independiente máximo en algún gráfico, entonces es una camarilla máxima en el complemento del gráfico . Una camarilla máxima es el conjunto de vértices que generan un subgrafo completo y no está contenido en un subgrafo completo más grande. Por lo tanto, este es el conjunto de vértices de S tal que cualquier par de vértices en S está conectado por una arista, y para cualquier vértice que no esté en S no hay arista que lo conecte con al menos un vértice en S. Un gráfico puede tener varias camarillas máximas de varios tamaños. Encontrar la camarilla máxima de tamaño máximo es el problema de la camarilla máxima .

Algunos autores requieren que la camarilla sea máxima en la definición y usan el término camarilla en lugar de camarilla máxima.

El complemento del conjunto máximo independiente, es decir, los vértices que no pertenecen al conjunto independiente, forman la cobertura mínima de vértices . Es decir, el complemento es una cubierta de vértices , el conjunto de vértices que contiene al menos un vértice final de cualquier arista, y es mínimo en el sentido de que ninguno de los vértices se puede eliminar sin romper la cubierta. La cobertura mínima de vértices se estudia en mecánica estadística en el modelo de red de gas sobre esferas rígidas , una abstracción matemática de la transición de un estado líquido a un estado sólido. [2]

Cualquier conjunto independiente máximo es dominante , es decir, un conjunto de vértices tales que cualquier vértice en el gráfico pertenece al conjunto o es adyacente a él. Un conjunto de vértices es un conjunto independiente máximo si y solo si es un conjunto dominante independiente.

Uso en características de familias de grafos

Algunas familias de grafos se pueden describir en términos de sus clicas máximas o conjuntos independientes máximos. Los ejemplos incluyen gráficos con camarillas máximas irreducibles y gráficos con camarillas máximas hereditariamente irreducibles. Se dice que un gráfico tiene camarillas máximas irreducibles si cualquier camarilla máxima contiene un borde que no pertenece a ninguna otra camarilla máxima, y ​​camarillas máximas hereditariamente irreducibles si esta propiedad es cierta para cualquier subgrafo. [3] Los gráficos con camarillas máximas hereditariamente irreducibles incluyen gráficos sin triángulos , gráficos bipartitos y gráficos de intervalos .

Los cografos se pueden describir como gráficos en los que cualquier camarilla máxima se cruza con cualquier conjunto independiente máximo, y en los que esta propiedad es cierta para todos los subgrafos generados.

Estimaciones del número de conjuntos

Moon y Moser ( Moon, Moser 1965 ) demostraron que cualquier gráfico con n vértices tiene como máximo 3n /3 camarillas máximas. Además, un gráfico con n vértices tiene como máximo 3 n /3 conjuntos independientes máximos. Un gráfico que tiene exactamente 3n /3 conjuntos independientes máximos es fácil de construir simplemente tomando un conjunto desconectado de n /3 gráficos triangulares . Cualquier conjunto independiente máximo en este gráfico se forma eligiendo un vértice de cada triángulo. El gráfico adicional con 3 n /3 camarillas máximas es una forma especial de los gráficos de Turan . Debido a la conexión de este gráfico con el límite Luna-Moser, estos gráficos a veces se denominan gráficos Luna-Moser. Son posibles límites más fuertes si el tamaño de los conjuntos independientes máximos es limitado: el número de conjuntos independientes máximos de tamaño k en cualquier gráfico con n vértices no excede

Los gráficos que alcanzan este límite son nuevamente gráficos de Turan. [cuatro]

Sin embargo, algunas familias de gráficos pueden tener límites sustancialmente más fuertes en el número de conjuntos independientes máximos o camarillas máximas. Por ejemplo, si los gráficos de una familia tienen aristas O(n) y la familia está cerrada por subgráficos, entonces todas las camarillas máximas tienen un tamaño constante y el número de camarillas máximas es casi lineal. [5]

Está claro que cualquier gráfico con camarillas máximas irreducibles tiene como mucho camarillas máximas que aristas. Es posible un límite más fuerte para gráficos de intervalos y gráficos de cuerdas  ; no puede haber más de n clicas máximas en estos gráficos.

El número máximo de conjuntos independientes en un ciclo con n vértices viene dado por los números de Perrin , y el número máximo de conjuntos independientes en un camino con n vértices viene dado por la sucesión de Padovan . [6] Por lo tanto, ambas secuencias son proporcionales a la potencia de 1,324718 (es decir, el número plástico ).

Establecer algoritmos de enumeración

Un algoritmo para enumerar todos los conjuntos independientes máximos o camarillas máximas en un gráfico se puede usar como rutina para resolver muchos problemas NP-completos en la teoría de gráficos. Los problemas más obvios son el problema del conjunto independiente máximo, el problema de la camarilla máxima y el problema del conjunto dominante independiente mínimo.

Todos deben ser conjuntos independientes máximos o camarillas máximas y se pueden encontrar utilizando un algoritmo que enumera todos esos conjuntos y selecciona un conjunto de tamaño máximo o mínimo. De la misma manera, la cobertura mínima de vértices se puede encontrar como el complemento de uno de los conjuntos máximos independientes. Lawler ( Lawler 1976 ) señaló que la enumeración de conjuntos independientes máximos también se puede usar para encontrar una coloración de 3 colores de un gráfico : un gráfico puede tener 3 colores si y solo si el complemento de uno de los conjuntos independientes máximos es bipartito . Usó este enfoque no solo para colorear con 3 colores, sino también como parte de un algoritmo de coloreado de gráficos más general, y otros autores han utilizado un enfoque similar para colorear gráficos. [7]

Otros problemas más complejos pueden reducirse a encontrar una camarilla o un conjunto independiente de un tipo especial. Esto proporciona motivación para encontrar algoritmos que enumeren de manera eficiente todos los conjuntos independientes máximos (o, de manera equivalente, camarillas máximas).

Es posible convertir directamente la prueba de Moon y Moser del límite 3 n /3 en el número de conjuntos independientes máximos en un algoritmo que enumera todos esos conjuntos en tiempo O (3 n /3 ). [8] Para gráficos que tienen el número máximo posible de conjuntos independientes máximos, este algoritmo proporciona un tiempo constante por conjunto encontrado. Sin embargo, un algoritmo con este límite de tiempo puede ser extremadamente ineficiente para gráficos con un número más limitado de conjuntos independientes. Por esta razón, muchos investigadores buscan algoritmos para enumerar todos los conjuntos independientes máximos en tiempo polinomial por conjunto encontrado. [9] El tiempo para encontrar un conjunto independiente máximo es proporcional al tiempo de multiplicación de matrices en gráficos densos o más rápido en varias clases de gráficos dispersos. [diez]

Notas

  1. ↑ Erdős ( Erdős 1966 ) demostró que el número de tamaños diferentes de conjuntos independientes máximos en un gráfico con n vértices puede alcanzar y nunca exceder .
  2. ↑ Weigt, Hartmann, 2001 .
  3. ↑ Sistema de información sobre inclusiones de clases de grafos: grafos con camarillas máximas irreducibles Archivado el 9 de julio de 2007 . y con camarillas máximas hereditariamente irreductibles . Archivado desde el original el 8 de julio de 2007. .
  4. ↑ ( Byskov 2003 ). Para trabajos anteriores ver ( Croitoru 1979 ) y ( Eppstein 2003 ).
  5. ↑ ( Chiba, Nishizeki 1985 ). La condición de escasez es equivalente a la condición de que una familia de gráficos tenga un árbol acotado .
  6. ↑ ( Bisdorff, Marichal 2007 ); ( Euler 2005 ); ( Füredi 1987 ).
  7. ↑ ( Eppstein 2003 ); ( Byskov 2003 ).
  8. ↑ ( Eppstein 2003 ). Para conocer los límites del algoritmo Bron-Kerbosh ampliamente utilizado, consulte ( Tomita, Tanaka, Takahashi 2006 ).
  9. ↑ ( Bomze, Budinich, Pardalos, Pelillo 1999 ); ( Eppstein 2005 ); ( Jennings, Motycková 1992 ); ( Johnson, Yannakakis, Papadimitriou 1988 ); ( Lawler, Lenstra, Rinnooy Kan 1980 ); ( Liang, Dhall, Lakshmivarahan 1991 ); ( Makino, Uno 2004 ); ( Mishra, Pitt 1997 ); ( Stix 2004 ); ( Tsukiyama, Ide, Ariyoshi, Shirakawa 1977 ); ( Yu, Chen 1993 ).
  10. ↑ ( Makino, Uno 2004 ); ( Eppstein 2005 ).

Enlaces