Para otros lectores, permítanme primero definir qué es un conjunto dominante y un gráfico capacitado.
Conjunto dominante: para cualquier gráfico, G = (V, E), un conjunto de vértices D \ subseteq V se denomina conjunto dominante si todos los vértices en V están en D o son vecinos de algún vértice en D. (Conjunto de vértice que cubre todos los vértices del gráfico dado).
Gráfico capacitado: Un gráfico G = (V, E) con una función de capacidad C: V-> N tal que C (v) \ leq grado de v
- ¿Qué es la máscara de dirección?
- ¿Qué es la red adaptativa?
- ¿Hay alguna manera de hackear una red WiFi y conocer su contraseña?
- ¿Qué son los registros DNS? ¿Como funciona?
- ¿Cómo se puede medir la distancia del cable entre dos computadoras en una red?
para cualquier vértice v \ en V. Es decir, un gráfico que asocia una capacidad a cada uno de sus vértices de tal manera que la capacidad es menor que el grado total de un vértice particular. Puede ver la función de capacidad como una capacidad para cubrir vértices (bordes en el caso del problema de cobertura de vértices).
Una vez que tengamos esto, es natural hacer la siguiente pregunta:
¿Podemos encontrar todo el conjunto de vértices de manera que cubra todos los vértices con la restricción de que el número de vértices que puede cubrir un vértice particular no excede su capacidad?
Conjunto dominador capacitado: para cualquier gráfico capacitado, G = (V, E) y C, un conjunto de vértices D \ subseteq V se denomina conjunto dominador capacitado si existe una función f: (V \ D) -> V que corresponde cada vértice en V \ D a algún vértice en D de tal manera que el número de vértices f se asigne a un vértice v no sea mayor que C (v).
