Número de independencia en LaTeX (\alpha(G))

Dónde se usa

Número de independencia de G: el tamaño del mayor conjunto independiente, es decir, de vértices no adyacentes dos a dos.

El número de independencia cumple \alpha(G) \cdot \chi(G) \geq |V(G)|, ya que cada clase de color es un conjunto independiente, y \alpha(G) = \omega(\overline{G}). La identidad de Gallai lo relaciona con el número de recubrimiento por vértices: \alpha(G) + \tau(G) = |V(G)|. Calcularlo es NP-difícil en general, pero sencillo en grafos bipartitos gracias al teorema de Kőnig. Use \alpha, la letra griega, que se distingue visualmente de la a en la mayoría de las fuentes. Los análogos para aristas son \alpha'(G) o \nu(G), el número de emparejamiento. La cota de Caro-Wei da \alpha(G) \geq \sum_v 1/(\deg(v)+1).

Ejemplo mínimo compilable

Pégalo en un archivo .tex vacío y compílalo con pdfLaTeX, XeLaTeX o LuaLaTeX.

\documentclass{article}
\begin{document}
Independent Set: $\alpha(G)$

\[ \alpha(G) \geq \sum_{v \in V} \frac{1}{\deg(v) + 1} \]
\end{document}

Símbolos relacionados

• EmparejamientoM
• Número de clique\omega(G)
• Grafo planoG \hookrightarrow \mathbb{R}^2
• Número cromático\chi(G)
• BosqueF
• ÁrbolT

Preguntas frecuentes

¿Cómo escribo Número de independencia en LaTeX?

Escribe \alpha(G) en modo matemático, por ejemplo $\alpha(G) \geq \sum_{v \in V} \frac{1}{\deg(v) + 1}$. Funciona en LaTeX estándar sin cargar ningún paquete.

¿Qué paquete necesito para \alpha(G)?

Ninguno. \alpha(G) forma parte de LaTeX estándar, así que compila solo con la clase de documento en el preámbulo.

¿Puedo usar \alpha(G) en modo texto o solo en modo matemático?

Solo en modo matemático. Fuera de $...$ LaTeX se detiene con "Missing $ inserted", así que en el texto escribe $\alpha(G)$.