Numero di indipendenza in LaTeX (\alpha(G))

Dove si usa

Numero di indipendenza di G: la dimensione del più grande insieme di vertici a due a due non adiacenti.

Il numero di indipendenza soddisfa \alpha(G) \cdot \chi(G) \geq |V(G)|, poiché ogni classe di colore è un insieme indipendente, e \alpha(G) = \omega(\overline{G}). L'identità di Gallai lo collega al numero di copertura dei vertici: \alpha(G) + \tau(G) = |V(G)|. Calcolarlo è NP-difficile in generale ma facile sui grafi bipartiti grazie al teorema di Kőnig. Usate \alpha, la lettera greca, che nella maggior parte dei font si distingue bene dalla a. Gli analoghi per gli spigoli sono \alpha'(G) o \nu(G), il numero di accoppiamento. La stima di Caro-Wei dà \alpha(G) \geq \sum_v 1/(\deg(v)+1).

Esempio minimo compilabile

Incollalo in un file .tex vuoto e compilalo 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}

Simboli correlati

• AccoppiamentoM
• Numero di cricca\omega(G)
• Grafo planareG \hookrightarrow \mathbb{R}^2
• Numero cromatico\chi(G)
• ForestaF
• AlberoT

Domande frequenti

Come si scrive Numero di indipendenza in LaTeX?

Scrivi \alpha(G) in modalità matematica, per esempio $\alpha(G) \geq \sum_{v \in V} \frac{1}{\deg(v) + 1}$. Funziona in LaTeX standard senza caricare alcun pacchetto.

Quale pacchetto serve per \alpha(G)?

Nessuno. \alpha(G) fa parte di LaTeX standard, quindi compila con la sola classe del documento nel preambolo.

Posso usare \alpha(G) in modalità testo o solo in modalità matematica?

Solo in modalità matematica. Fuori da $...$ LaTeX si ferma con "Missing $ inserted", quindi nel testo scrivi $\alpha(G)$.