Пример (пара близких формулировок и анализ влияния замены):
1) Версия «вершинная» (некоторое стандартное утверждение):
Дан граф $G=(V,E)$ и число $k$. Существует ли подмножество вершин $S\subseteq V$ такого, что $|S|\ge k$ и никакие две вершины из $S$ не смежны (то есть для любых $u,v\in S$, $\{u,v\}\notin E$)?
Это — задача максимального независимого множества (Maximum Independent Set).
2) Версия «рёберная» (замена «вершин» → «рёбра»):
Дан граф $G=(V,E)$ и число $k$. Существует ли подмножество рёбер $M\subseteq E$ такого, что $|M|\ge k$ и никакие два ребра из $M$ не смежны (то есть для любых $e,f\in M$, $e$ и $f$ не имеют общей вершины)?
Это — задача максимального паросочетания (Maximum Matching).
Ключевые различия (как точность формулировки меняет суть):
- Формулировка и эквивалентность через line-граф:
Замена «рёбра» → «вершины» соответствует переходу к line-графу $L(G)$: каждому ребру $e\in E(G)$ соответствует вершина $v_e\in V(L(G))$, и смежность рёбер в $G$ соответствует смежности вершин в $L(G)$. Тогда
максимальное паросочетание в $G$ равно максимальному независимому множеству в $L(G)$: $|M_{\max }(G)|=\alpha (L(G))$.
- Сложность и применимые методы:
- Максимальное независимое множество в общем графе — NP‑полная задача (нельзя ожидать полиномиального алгоритма в общем случае). Применяются комбинаторные умозаключения, сокращения, аппроксимации, эвристики, ветвление и т. п.
- Максимальное паросочетание в общем графе решается полиномиально (алгоритм Эдмондса — «blossom», и его реализации; для двудольных графов — алгоритмы на потоке/аугментационных путях). То есть смена «вершин» на «рёбра» переводит NP‑трудную задачу в полиномиальноразрешимую.
- Примеры, иллюстрирующие, как меняются ответы:
Возьмём звезду $K_{1,n}$. Для неё:
$\alpha (K_{1,n})=n$ (взять все листья), но максимальное паросочетание имеет размер $1$ (все рёбра инцидентны центру). То есть численные значения и структура оптимумов могут сильно отличаться.
- Последствия для теорем и техник:
- Для вершинной задачи полезны теоремы о вершинах, ветвления, разбиении на компоненты и аппроксимации. Для рёберной — алгоритмы на аугментирующих путях, сокращение «blossom», редукция к потоку в двудольном случае.
- В двудольных графах есть связующее утверждение (Кёниг): размер максимального паросочетания равен размеру минимального вершинного покрытия. Это делает обе проблемы взаимосвязанными в особом классе графов; в общем графе такой сильной связи нет, и это подчёркивает, что точная формулировка (вершины vs рёбра) определяет, какие теоремы применимы.
Краткий вывод: замена «смежные вершины» → «смежные рёбра» часто меняет задачу коренным образом: она переводит одну стандартную комбинаторную задачу (MIS, обычно NP‑трудную) в другую (Matching, полиномиальноразрешимую). Точная формулировка определяет, можно ли применить алгоритмы на аугментирующих путях, редукции к потоку, теоремы типа Кёнига или нужно ли использовать общие NP‑полные техники.