Número de independência em LaTeX (\alpha(G))

Onde é usado

Número de independência de G: o tamanho do maior conjunto de vértices dois a dois não adjacentes.

O número de independência satisfaz \alpha(G) \cdot \chi(G) \geq |V(G)|, pois cada classe de cor é um conjunto independente, e \alpha(G) = \omega(\overline{G}). A identidade de Gallai o relaciona ao número de cobertura por vértices: \alpha(G) + \tau(G) = |V(G)|. Calculá-lo é NP-difícil em geral, mas fácil em grafos bipartidos graças ao teorema de Kőnig. Use \alpha, a letra grega, que é visualmente distinta de a na maioria das fontes. Os análogos para arestas são \alpha'(G) ou \nu(G), o número de emparelhamento. A cota de Caro-Wei dá \alpha(G) \geq \sum_v 1/(\deg(v)+1).

Exemplo mínimo compilável

Cole isto em um arquivo .tex vazio e compile com pdfLaTeX, XeLaTeX ou 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

• EmparelhamentoM
• Número de clique\omega(G)
• Grafo planarG \hookrightarrow \mathbb{R}^2
• Número cromático\chi(G)
• FlorestaF
• ÁrvoreT

Perguntas frequentes

Como escrever Número de independência em LaTeX?

Digite \alpha(G) no modo matemático, por exemplo $\alpha(G) \geq \sum_{v \in V} \frac{1}{\deg(v) + 1}$. Funciona no LaTeX padrão sem carregar nenhum pacote.

Qual pacote é necessário para \alpha(G)?

Nenhum. \alpha(G) faz parte do LaTeX padrão, então compila só com a classe do documento no preâmbulo.

Posso usar \alpha(G) no modo texto ou só no modo matemático?

Só no modo matemático. Fora de $...$ o LaTeX para com "Missing $ inserted", então no texto escreva $\alpha(G)$.