Лемма о безопасном ребре

Дан неориентированный взвешенный граф $G=(V, E)$.

Остовным деревом в $G$ называется граф $ST=(V, E')$ такой что $E' \subset E$ и $ST$ является деревом. Говоря простым языком, мы оставляем в графе только некоторые рёбра, чтобы оставшийся граф был деревом (или, ещё говорят, скелетом).

Весом графа мы будем называть суммарный вес всех рёбер, входящих в него.

Безопасным остовом мы будем называть подграф(возможно, несвязный) без циклов, который можно дополнить, добавляя (но не удаляя!) в него рёбра, до некоторого минимального остовного дерева (миностова).

Безопасным ребром для безопасного остова мы будем называть ребро, добавление которого сохраняет безопасность.

Лемма о безопасном ребре

Пусть $S=(V, E') ~-$ безопасный остов. Пусть $E_{intercomp} ~-$ множество всех рёбер из $E$, концы которых лежат в разных компонентах связности S. Тогда все рёбра минимального веса из $E_{intercomp}$ являются безопасными.

Доказательство

Пусть минимальное ребро в $E_{intercomp} ~-$ $(u, v)$.

Поскольку $S ~-$ безопасный, дополним его (каким-нибудь образом) до миностова $MST$. Если этот миностов содержит ребро $(u, v)$, то утверждение доказано. Если же нет, то добавление $(u, v)$ в $MST$ приведёт к появлению цикла $C$ (поскольку $MST ~-$ дерево). Поскольку $(u, v)$ соединяет вершины из разных компонент относительно $S$, то в $C$ найдётся ребро $(u', v')$, соединяющее $2$ вершины из разных компонент относительно $S$ (начнём идти по $C$ от $u$ в сторону $v$, если мы не найдём такого ребра, то $u$ и $v$ лежат в одной компоненте).

По предположению леммы $(u, v)$ было самым лёгким ребром между компонентами относительно $S$. $\implies w(u, v) \leq w(u', v') \implies (u, v)$ можно добавить в $C$, убрав оттуда $(u', v')$, не увеличив вес остова. Значит, получившийся остов является минимальным $\implies$ ребро $(u, v) ~-$ безопасное.

---

Автор конспекта: Александр Гришутин

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