693
правки
Изменения
→Обобщение задачи для произвольных графов
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Для решения таких задач в каждой компоненте связности выделим [[Остовные деревья: определения, лемма о безопасном ребре|остовные деревья]], которые образуют остовный лес.
Попробуем выполнить операцию удаления ребра.<--- Для этого ---->
[[Файл:Graph.jpg|550px|thumb|left|Граф]] [[Файл:Spanforest.jpg|550px|thumb|right|Остовный лес в графе]]
{{Утверждение
|statement=<tex>l(xy)\leqslant i</tex>
|proof=От противного. Пусть <tex>l(xy)=j</tex> и <tex>j\geqslant i</tex>. Тогда вершины <tex>x</tex> и <tex>y</tex> каким-то образом связаны в <tex>F_j</tex> (либо непосредственно ребром, либо каким-то другим путём). Но <tex>F_j \subseteq F_i</tex>. Значит, в <tex>F_i</tex> между <tex>x</tex> и <tex>y</tex> сохранился путь из рёбер уровня не меньше <tex>j</tex> и появился другой путь через <tex>uv</tex>. Приходим к противоречию, так как в <tex>F_i</tex> все компоненты должны быть деревьями.
}}
