Número domiciliario

En teoría de grafos , una partición domática de un grafo${\displaystyle G=(V,E)}$es una partición de${\displaystyle V}$en conjuntos disjuntos${\displaystyle V_{1}}$,${\displaystyle V_{2}}$,...,${\displaystyle V_{K}}$de tal manera que cada V _i es un conjunto dominante para G . La figura de la derecha muestra una partición domática de un grafo; aquí el conjunto dominante${\displaystyle V_{1}}$consta de los vértices amarillos,${\displaystyle V_{2}}$consta de los vértices verdes y${\displaystyle V_{3}}$consta de los vértices azules.

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 disjuntos. El grafo 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 porque hemos presentado una partición domática de tamaño 3. Para ver que el número domático es como máximo 3, primero revisamos una cota superior simple.

Dejar${\displaystyle \delta }$sea ​​el grado mínimo del gráfico${\displaystyle G}$. El número domiciliario de${\displaystyle G}$es como máximo${\displaystyle \delta +1}$Para ver esto, consideremos un vértice.${\displaystyle v}$de grado${\displaystyle \delta }$. Dejar${\displaystyle N}$consistir en${\displaystyle v}$y sus vecinos. Sabemos que (1) cada conjunto dominante${\displaystyle V_{i}}$debe contener al menos un vértice en${\displaystyle N}$(dominación) y (2) cada vértice en${\displaystyle N}$está contenido en como máximo un conjunto dominante${\displaystyle V_{i}}$(desunión). Por lo tanto, hay como máximo${\displaystyle |N|=\delta +1}$conjuntos dominantes disjuntos.

El gráfico de la figura tiene un grado mínimo${\displaystyle \delta =2}$y por lo tanto su número domático es como máximo 3. Por lo tanto, hemos demostrado que su número domático es exactamente 3; la figura muestra una partición domática de tamaño máximo.

Si no hay ningún vértice aislado en el grafo (es decir,${\displaystyle \delta }$ Si ≥  1), entonces el número domático es al menos 2. Para ver esto, observe que (1) una 2-coloración débil es una partición domática si no hay vértices aislados, y (2) cualquier grafo tiene una 2-coloración débil. Alternativamente, (1) un conjunto independiente maximal es un conjunto dominante, y (2) el complemento de un conjunto independiente maximal también es un conjunto dominante si no hay vértices aislados.

La figura de la derecha muestra una coloración débil de 2 colores, que también es una partición domática de tamaño 2: los nodos oscuros forman un conjunto dominante, y los nodos claros forman otro conjunto dominante (los nodos claros forman un conjunto independiente máximo). Consulte la sección sobre coloración débil para obtener más información.

Encontrar una partición domática de tamaño 1 es trivial: sea${\displaystyle V_{1}=V}$Encontrar una partición domática de tamaño 2 (o determinar que no existe) es fácil: compruebe si hay nodos aislados y, si no los hay, encuentre una coloración débil de 2 colores.

Sin embargo, encontrar una partición domática de tamaño máximo es computacionalmente difícil. Específicamente, el siguiente problema de decisión , conocido como el problema del número domático , es NP-completo : dado un grafo${\displaystyle G}$y un número entero${\displaystyle K}$, determinar si el número domiciliario de${\displaystyle G}$es al menos${\displaystyle K}$Por lo tanto, el problema de determinar el número domático de un grafo dado es NP-difícil , y el problema de encontrar una partición domática de tamaño máximo también lo es.

Existe un algoritmo de aproximación en tiempo polinomial con una garantía de aproximación logarítmica, ^{[ 1 ]} es decir, es posible encontrar una partición domática cuyo tamaño esté dentro de un factor${\displaystyle O(\log |V|)}$del óptimo.

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

partición domiciliaria

Partición de vértices en conjuntos dominantes disjuntos. El número domático es el número máximo de dichos conjuntos.

Coloreado de vértices

Partición de vértices en conjuntos independientes disjuntos . El número cromático es el número mínimo de dichos conjuntos.

partición de camarilla

Partición de vértices en camarillas disjuntas . Equivalente a la coloración de vértices en el grafo complemento .

Coloración de bordes

Partición de aristas en emparejamientos disjuntos . El número cromático de aristas es el número mínimo de dichos conjuntos.

Sea G  =  ( U  ∪ V , E ) un grafo bipartito sin nodos aislados; todas las aristas son de la forma { u , v } ∈ E con u ∈ U y v ∈ V . Entonces { U , V } es a la vez una 2-coloración de vértices y una partición domática 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 1-coloración de vértices. El número domático de G es al menos 2. Es posible que haya una partición domática mayor; por ejemplo, el grafo bipartito completo K _{n , n} para cualquier n ≥ 2 tiene número domático n .            

• Garey, Michael R.; Johnson , David S. (1979). Computadoras e intratabilidad: una guía a la teoría de la NP-completitud . Serie de libros en ciencias matemáticas (1.ª  ed.). Nueva York: WH Freeman and Company . ISBN 9780716710455. MR 0519066 . OCLC 247570676 .  . A1.1: GT3, pág.  190.
• Cockayne, EJ; Hedetniemi, Stephen T. (1975), "Dominación óptima en grafos", IEEE Transactions on Circuits and Systems , CAS-22 (11): 855–857 , doi : 10.1109/TCS.1975.1083994 , MR 0384608 .