Numero domatico

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En la teoría del gráfico, un partición domática de un gráfico ${displaystyle G=(V,E)}$ es una partición de ${displaystyle V}$ en conjuntos ${displaystyle V_{1}}$ , ${displaystyle V_{2}}$ ,... ${displaystyle V_{K}}$ tal que cada uno V_i es un conjunto dominante G. La figura de la derecha muestra una partición domática de un gráfico; aquí el conjunto dominante ${displaystyle V_{1}}$ consta de los vértices amarillos, ${displaystyle V_{2}}$ consiste en los vertices verdes, y ${displaystyle V_{3}}$ consiste en 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. La gráfica de la figura tiene el número domático 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 un límite superior simple.

Límites superiores

Vamos. ${displaystyle delta }$ ser el grado mínimo del gráfico ${displaystyle G}$ . Número domático ${displaystyle G}$ es en la mayoría ${displaystyle delta +1}$ . Para ver esto, considere un vértice ${displaystyle v}$ grado ${displaystyle delta }$ . Vamos. ${displaystyle N}$ consiste de ${displaystyle v}$ y sus vecinos. Sabemos que (1) cada conjunto dominante ${displaystyle V_{i}}$ debe contener al menos un vértice en ${displaystyle N}$ (domingo), y (2) cada vértice en ${displaystyle N}$ está contenido en la mayoría de un conjunto dominante ${displaystyle V_{i}}$ (distinción). Por lo tanto, hay en la mayoría ${displaystyle |N|=delta +1}$ disjoint dominating sets.

El gráfico de la figura tiene un grado mínimo ${displaystyle delta =2}$ , y por lo tanto su número domático es en la mayoría 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.

Límites inferiores

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

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

Complejidad computacional

Encontrar una partición domática del tamaño 1 es trivial: ${displaystyle V_{1}=V}$ . Encontrar una partición domática del tamaño 2 (o determinar que no existe) es fácil: comprobar si hay nodos aislados, y si no, encontrar un débil 2-coloring.

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

Hay un algoritmo de aproximación polinomio-tiempo con una garantía de aproximación logarítmica, es decir, es posible encontrar una partición domática cuyo tamaño está dentro de un factor ${displaystyle O(log |V|)}$ de lo óptimo.

Sin embargo, bajo hipótesis plausible de complejidad-teorética, no hay algoritmo de aproximación polinomio-tiempo con un factor de aproximación sub-logarítmica. Más específicamente, un algoritmo de aproximación de tiempo polinomio para partición domática con el factor de aproximación ${displaystyle (1-epsilon)ln |V|}$ para una constante $0}" xmlns="http://www.w3.org/1998/Math/MathML">ε ε ■0{displaystyle epsilon }0}" aria-hidden="true" class="mwe-math-fallback-image-inline mw-invert" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/568095ad3924314374a5ab68fae17343661f2a71" style="vertical-align: -0.338ex; width:5.205ex; height:2.176ex;"/>$ implicaría que todos los problemas en el NP se pueden resolver en un tiempo ligeramente superpolíno ${displaystyle n^{O(log log n)}}$ .

Comparación con conceptos similares

Partición domática: Partición de vértices en conjuntos dominantes descomunales. El número de números es el número máximo de tales conjuntos.
Colorante Vertex: Partición de vértices en conjuntos independientes descomunales. El Número cromático es el número mínimo de tales conjuntos.
Partición colectiva: Partición de vértices en camarillas disjoint. Igual a la coloración del vértice en el gráfico de complemento.
Colorante de borde: Partición de bordes en coincidencias descomunales. El borde número cromático es el número mínimo de tales 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 partición domática de 2 colores y un vértice 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 del vértice 1. El número domático de G es al menos 2. Es posible que exista una partición domática mayor; por ejemplo, el gráfico bipartito completo K_n,n para cualquier n ≥ 2 tiene número domático n.

Más resultados...