Unabhängigkeitszahl in LaTeX (\alpha(G))

Verwendung

Unabhängigkeitszahl von G: die Größe der größten Menge paarweise nicht adjazenter Knoten.

Die Unabhängigkeitszahl erfüllt \alpha(G) \cdot \chi(G) \geq |V(G)|, da jede Farbklasse eine unabhängige Menge ist, und \alpha(G) = \omega(\overline{G}). Die Identität von Gallai verknüpft sie mit der Knotenüberdeckungszahl: \alpha(G) + \tau(G) = |V(G)|. Ihre Berechnung ist im Allgemeinen NP-schwer, auf bipartiten Graphen aber mit dem Satz von Kőnig einfach. Verwenden Sie den griechischen Buchstaben \alpha, der sich in den meisten Schriften deutlich von a unterscheidet. Kantenanaloga sind \alpha'(G) oder \nu(G), die Matchingzahl. Die Schranke von Caro und Wei liefert \alpha(G) \geq \sum_v 1/(\deg(v)+1).

Minimales kompilierbares Beispiel

Fügen Sie dies in eine leere .tex-Datei ein und kompilieren Sie mit pdfLaTeX, XeLaTeX oder LuaLaTeX.

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

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

Verwandte Symbole

• MatchingM
• Cliquenzahl\omega(G)
• Planarer GraphG \hookrightarrow \mathbb{R}^2
• Chromatische Zahl\chi(G)
• WaldF
• BaumT

Häufige Fragen

Wie schreibe ich Unabhängigkeitszahl in LaTeX?

Schreiben Sie \alpha(G) im Mathematikmodus, zum Beispiel $\alpha(G) \geq \sum_{v \in V} \frac{1}{\deg(v) + 1}$. Es funktioniert in Standard-LaTeX, ohne ein Paket zu laden.

Welches Paket brauche ich für \alpha(G)?

Keines. \alpha(G) gehört zum Standardumfang von LaTeX und kompiliert ohne weitere Angaben in der Präambel außer der Dokumentklasse.

Kann ich \alpha(G) im Textmodus verwenden oder nur im Mathematikmodus?

Nur im Mathematikmodus. Außerhalb von $...$ bricht LaTeX mit "Missing $ inserted" ab, schreiben Sie im Fließtext also $\alpha(G)$.