Число независимости в LaTeX (\alpha(G))

Где используется

Число независимости G: размер наибольшего множества попарно несмежных вершин.

Число независимости удовлетворяет неравенству \alpha(G) \cdot \chi(G) \geq |V(G)|, поскольку каждый цветовой класс — независимое множество, а также \alpha(G) = \omega(\overline{G}). Тождество Галлаи связывает его с числом вершинного покрытия: \alpha(G) + \tau(G) = |V(G)|. В общем случае его вычисление NP-трудно, но для двудольных графов оно просто благодаря теореме Кёнига. Используйте греческую \alpha, которая в большинстве шрифтов хорошо отличается от a. Рёберные аналоги — \alpha'(G) или \nu(G), число паросочетания. Оценка Каро — Вея даёт \alpha(G) \geq \sum_v 1/(\deg(v)+1).

Минимальный компилируемый пример

Вставьте это в пустой файл .tex и скомпилируйте с pdfLaTeX, XeLaTeX или LuaLaTeX.

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

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

Похожие символы

• ПаросочетаниеM
• Кликовое число\omega(G)
• Планарный графG \hookrightarrow \mathbb{R}^2
• Хроматическое число\chi(G)
• ЛесF
• ДеревоT

Частые вопросы

Как написать «Число независимости» в LaTeX?

Наберите \alpha(G) в математическом режиме, например $\alpha(G) \geq \sum_{v \in V} \frac{1}{\deg(v) + 1}$. Команда работает в обычном LaTeX без подключения пакетов.

Какой пакет нужен для \alpha(G)?

Никакой. \alpha(G) входит в стандартный LaTeX, поэтому в преамбуле достаточно класса документа.

Можно ли использовать \alpha(G) в текстовом режиме или только в математическом?

Только в математическом режиме. Вне $...$ LaTeX остановится с ошибкой "Missing $ inserted", поэтому в тексте пишите $\alpha(G)$.