Que el gráfico $G = (V, E)$ $\Rightarrow$ $\alpha(G) \ge \frac{{|V|}^{2}}{2 \times (|E| + |V|)}$ , donde $\alpha(G)$ es el número de independencia del vértice de $G$ .
¡Da alguna pista, por favor!
¡Gracias de todos modos!
Respuesta
¿Demasiados anuncios?
Como esto es una tarea etiquetada, aquí hay un esbozo de una prueba.
Podemos utilizar el algoritmo codicioso para obtener un límite inferior en $\alpha(G)$ . En cada paso elegimos el vértice de menor grado y lo colocamos en nuestro conjunto independiente. A continuación, lo eliminamos, junto con sus vecinos, y repetimos hasta que nos quedemos sin vértices. Si el algoritmo codicioso se ejecuta durante $t$ pasos, entonces $\alpha(G) \geq t$ . Una prueba bastante hábil de que $t \geq |V(G)|/(\overline{d}+1)$ , donde $\overline{d}=\frac{2|E(G)|}{|V(G)|}$ es el grado medio, se dio en:
Halldorsson y Radhakrishnan, Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs ( pdf ), Algorithmica (1997) 18:145-163.
Esta desigualdad se puede reajustar para mostrar que \alpha(G) \geq t \geq \frac{|V(G)|^2}{2(|E(G)|+|V(G)|} siempre que $|E(G)| \geq |V(G)|-1$ .
