Корневая в задачах на графы

Тяжелые и легкие вершины

Назовем $\textit{тяжелой}$ вершину, имеющую более $\sqrt{E}$ соседей. Все оставшиеся вершины назовем $\textit{легкими}$.

Утверждение:
В графе не более $2 \cdot \sqrt{E}$ тяжелых вершин.

Доказательство:
Пусть в графе более $2 \cdot \sqrt{E}$ тяжелых вершин. Тогда число ребер в графе больше, чем $\frac{2 \cdot \sqrt{E} \cdot \sqrt{E}}{2} = E$, чего не может быть.

Нахождение количества треугольников в графе за $O(E \sqrt E)$

Мысленно разобьем все вершины графа на легкие и тяжелые. Заметим, что треугольников, образованных только тяжелыми вершинами, всего $O(E\sqrt{E})$, как $C^3_{\sqrt{E}}$. Теперь рассмотрим треугольники, которые содержат в себе легкие вершины. В таком треугольнике точно будут два ребра, инцидентных легкой вершине. Сколько таких пар может быть? Всего таких ребер $O(E)$, при этом для каждого ребра парными могут быть только $O(\sqrt{E})$ ребер, в силу степени легкой вершины. Таким образом, \textit{число треугольников в графе равно} $O(E \sqrt{E})$. Каким алгоритмом их искать? Можно явно провести процесс, описанный выше, но это не самое приятное в реализации решение этой задачи.

Можно переориентировать ребра от вершин с меньшей степенью к вершинам с большей. Теперь верно следующее

Утверждение:
Из каждой вершины выходит не более $O(\sqrt E)$ ребер

Доказательство:
Степень легких вершин $O(\sqrt E)$, а из тяжелых вершин ребра идут только в тяжелые, которых всего $O(\sqrt E)$.

Теперь для каждой вершины пометим ее соседей, после чего запустим поиск путей длины 2 и будем фиксировать треугольник при нахождении пометки. Для каждого первого ребра пути мы посмотрим на $O(\sqrt E)$ ребер, поэтому итоговая сложность алгоритма $O(E \sqrt E)$

---

Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s