Relación entre el conjunto máximo independiente y la cobertura mínima de vértices

Question

Demostrar que $I$ es un conjunto máximo independiente de $G(V,E)$ si y sólo si $V\setminus I$ es una cubierta de vértices mínima de $G(V,E)$ .

Creo que he conseguido demostrar que el complemento de $I$ es una cubierta de vértices, pero tengo problemas para demostrar que es la cubierta de vértices mínima.

Mi prueba hasta ahora es:

\=> Supongamos que $I$ es un conjunto independiente máximo en $G(V,E)$ . Entonces, para cada arista $e \in E$ existe un $i \in I$ y un $j \in V\setminus I$ tal que $e=(i,j)$ . Así, $V\setminus I$ forma una cubierta de vértices de $G(V,E)$ .

A partir de aquí, creo que tengo que suponer que no es una cubierta de vértices mínima y luego demostrar que lo es por contradicción, pero estoy teniendo problemas con eso. ¿Estoy en el camino correcto? ¿Alguna pista?

Answer 1

Dejemos que $I$ sea un conjunto independiente máximo. Entonces, para $e\in E(G)$ , $e$ tiene al menos un vértice que no está en $I$ . Por lo tanto, $V(G)\setminus I$ es una cubierta de vértices. Supongamos que $V(G)\setminus I$ no es una cubierta de vértice mínima, entonces hay $v\in V(G)\setminus I$ tal que $(V(G)\setminus I) - v$ es una cubierta de vértices. Esto significa que todos los vértices en la vecindad $N(v)$ de $v$ están en $V(G)\setminus I$ Es decir, $\{v\}\cup N(v)$ es disjunta con $I$ . Por lo tanto, $I + v$ es también un conjunto independiente, lo que contradice la maximalidad de $I$ .

Answer 2

Aquí hay una prueba alternativa, corrígeme si me equivoco.

primero

• $\alpha(G):=$ tamaño del conjunto máximo independiente.
• $\tau(G):=$ tamaño de la cobertura mínima de vértices.
• $v(G):=$ número de vértices en G.

lo demostramos:

• $\tau(G) + \alpha(G) = v(G) $

con muestra que sí, si empiezas con una cubierta de vértices mínima y tomas todos los vértices que no toma, te quedarás con un conjunto máximo independiente, y viceversa.

es decir, el tamaño de la cobertura máxima de vértices es $v(G)-\alpha(G)$ y viceversa.

prueba $\alpha(G)\geq v(G)-\tau(G)$ :

Supongamos que $S$ es una cubierta de vértices máxima en G. entonces mira $S':=V(G)-S$ primero demostramos $S'$ es un conjunto independiente.

Supongamos que $S'$ no es un conjunto independiente, es decir, existe $u,v\in S'$ , de manera que $uv\in E(G)$ con implica que $u,v\notin S$ , entonces $S$ no cubre el borde $uv$ contradicción.

De ahí que haya concluido que $\alpha(G)\geq v(G)-\tau(G)$ .

prueba : $\tau(G)\leq v(G)-\alpha(G)$ :

Del mismo modo, supongamos ahora $S$ es un conjunto máximo independiente, entonces demostramos que $S':=V(G)-S$ es una cubierta de vértices.

Supongamos por contradicción que no es así. entonces se sostiene que existe $uv\in E(G)$ tal que $u\notin S'$ y $v\notin S'$ por lo que de nuevo concluimos que ambos deben estar en $S$ , entonces observamos que $S$ no es un conjunto independiente.

entonces observamos que: $\tau(G)\leq v(G)-\alpha(G)$ .

movemos el alfa y el tau, y obtenemos que $\alpha(G)\leq v(G)-\tau(G)$ , y de la observación anterior obtuvimos que $\alpha(G)\geq v(G)-\tau(G)$ .

por lo tanto, debe sostener que: $\tau(G) + \alpha(G) = v(G) $

ahora si asumes que hay una cubierta de vértices con menos vértices, entonces la ecuación simplemente no se sostiene.