Numero domatico

En teoría de grafos, una partición dómática de un grafo es una partición de un conjunto de vértices en conjuntos disjuntos , ,..., , tal que cada conjunto Vi es un conjunto dominante del grafo G . La figura de la derecha muestra una partición domótica de un gráfico. En la figura, el conjunto dominante consiste en vértices amarillos, vértices verdes y vértices azules. $G=(V,E)$ $V$ $V_{1}$ $V_{2}$ $V_{K}$ $V_{1}$ $V_{2}$ $V_{3}$

El número domático es el tamaño máximo de una partición domática, es decir, el número máximo de conjuntos dominantes que no se superponen. El gráfico de la figura tiene un número domático de 3. Es fácil ver que el número domático es al menos 3, ya que hemos presentado una partición domática de tamaño 3. Para entender que un número domático no excede de 3, primero considerar los límites superiores.

Límites superiores

Sea el grado mínimo de la gráfica . El número domático del gráfico no excede . Para entender esto, considere la parte superior del grado . Que consista en un vértice y sus vecinos. Sabemos que (1) cada conjunto dominante debe contener al menos un vértice from (dominancia), y (2) cada vértice from está contenido como máximo en un conjunto dominante (sin intersecciones). Por lo tanto, hay un máximo de conjuntos dominantes que no se superponen. $\delta$ $GRAMO$ $GRAMO$ $\ delta +1$ $v$ $\delta$ $norte$ $v$ $V_i$ $norte$ $norte$ $V_i$ ${\ estilo de visualización | N | = \ delta +1}$

El grafo de la figura tiene un grado mínimo , y por lo tanto su número dominante no excede de 3. Así, hemos demostrado que el número domático es exactamente 3. La figura muestra una partición domática de tamaño máximo. $\ delta = 2$

Límites inferiores

Si el gráfico no tiene vértices aislados (es decir, ≥ 1), entonces el número domático es al menos 2. Para entender esto, tenga en cuenta que (1) una coloración débil en 2 es un mosaico domático si no hay vértices aislados, y (2) cualquier gráfico tiene una coloración 2 débil. Alternativamente, (1) el conjunto independiente más grande es el conjunto dominante y (2) el complemento del conjunto independiente máximo también es el conjunto dominante si no hay vértices aislados. $\delta$

La figura de la derecha muestra una coloración débil de 2, que es un mosaico domático de tamaño 2: los vértices oscuros son el conjunto dominante y los vértices claros son otro conjunto dominante (los vértices claros forman el conjunto independiente más grande). Consulte el artículo " Coloración débil " para obtener más información.

Complejidad computacional

La búsqueda de una partición domática de tamaño 1 es trivial, lo es . Encontrar una partición domática de tamaño 2 (o descubrir que tal partición no existe) es simple: verifique que no haya vértices aislados y, de no ser así, busque una coloración débil de 2. $V_{1}=V$

Sin embargo, es difícil encontrar una partición domática de tamaño máximo. En particular, el siguiente problema de resolución , conocido como el problema del número domático , es NP-completo : dado un gráfico y un número entero, determine si el número domático del gráfico de valor es o no menor que . Por lo tanto, el problema de encontrar el número domático de un gráfico dado es NP-difícil , por lo que el problema de encontrar el tamaño máximo de la partición domática también es NP-difícil. $GRAMO$ $k$ $GRAMO$ $k$

Existe un algoritmo de aproximación en tiempo polinomial con una garantía de aproximación logarítmica [1] , es decir, se puede encontrar una partición domática cuyo tamaño no se encuentre más allá de un factor del óptimo. $O(\log |V|)$

Sin embargo, bajo supuestos bien fundados, no existe un algoritmo de aproximación en tiempo polinomial con un factor de aproximación sublogarítmico [1] . Más específicamente, el algoritmo de aproximación en tiempo polinomial para una partición domática con un coeficiente de aproximación para una constante implica que todos los problemas de clase NP pueden resolverse en un tiempo ligeramente superpolinomial . $(1-\epsilon)\ln |V|$ $\epsilon > 0$ ${\displaystyle n^{O(\log \log n)))$

Comparación con conceptos similares

partición domótica Partición de vértices en conjuntos dominantes que no se intersecan. El número domático es el número máximo de tales conjuntos. Coloración de vértices Partición de vértices en conjuntos independientes que no se cortan . El número cromático es el número mínimo de tales juegos. División en clics Dividir vértices en camarillas que no se intersecan . Equivalente a la coloración de vértices del complemento del gráfico . borde para colorear División de bordes en coincidencias que no se intersecan . El número cromático del borde es el número mínimo de tales juegos.

Sea G = ( U ∪ V , E ) un grafo bipartito sin vértices aislados. Todos los bordes son de la forma { u , v } ∈ E , donde u ∈ U y v ∈ V . Entonces { U , V } es una coloración de 2 vértices y una partición dominante de tamaño 2. Los conjuntos U y V son conjuntos dominantes independientes. El número cromático de G es exactamente 2. No hay coloración de vértice 1. El número dominante del grafo G es al menos 2. Puede haber una partición domática más grande. Por ejemplo, un grafo bipartito completo K n , n para cualquier n ≥ 2 tiene un número domático n .

Notas

↑ 1 2 Feige, Halldórsson, Kortsarz, Srinivasan, 2002 , p. 172–195.

Literatura

Michael R. Garey, David S. Johnson. Computadoras e intratabilidad: una guía para la teoría de la integridad NP . - WH Freeman, 1979. - ISBN 0-7167-1045-5 . A1.1. . A1.1: GT3
EJ Cockayne, Stephen T. Hedetniemi. Dominación óptima en grafos // Transacciones IEEE en circuitos y sistemas. - 1975. - T. CAS-22 , núm. 11 _ — S. 855–857 . -doi : 10.1109/ TCS.1975.1083994 .
Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz, Aravind Srinivasan. Aproximando el número domático // SIAM Journal on Computing . - 2002. - T. 32 , núm. 1 . — S. 172–195 . - doi : 10.1137/S0097539700380754 .