Изменения
Нет описания правки
Если добавить в множество <tex>A</tex> по очереди все вершины, каждый раз добавляя вершину, наиболее сильно связанную с <tex>A</tex>, то пусть предпоследняя добавленная вершина {{---}} <tex>s</tex>, а последняя {{---}} <tex>t</tex>. Тогда минимальный <tex>s</tex>-<tex>t</tex> разрез состоит из единственной вершины {{---}} <tex>t</tex>
|proof=
Рассмотрим произвольный <tex>s</tex>-<tex>t</tex> разрез <tex>C</tex> и покажем, что его вес не может быть меньше веса разреза, состоящего из единственной вершины <tex>t</tex>:
<tex dpi = '130'>w(\{t\}) \le w(C)</tex>.
Пусть <tex>v</tex> - вершина, которую мы хотим добавить в <tex>A</tex>, тогда <tex>A_v</tex> - состояние множества <tex>A</tex> в этот момент. Пусть <tex>C_v</tex> - разрез множества <tex>A_v \cup v</tex>, индуцированный разрезом <tex>C</tex>. Вершина <tex>v</tex> - активная, если она и предыдущая добавленная вершина в <tex>A</tex> принадлежат разным частям разреза <tex>C</tex>, тогда для любой такой вершины:
<tex dpi = '130'>w(v, A_v) \le w(C_v)</tex>.
<tex>t</tex> - активная вершина, для нее выполняется:
<tex>w(t,A_t) \le w(C_t)</tex>
<tex>w(t,A_t) = w(\{t\}), w(C_t) = w(C)</tex>
Получили утверждение теоремы.
Для доказательства воспользуемся методом математической индукции.
Для первой активной вершины <tex>v</tex> это неравенство верно, так как все вершины <tex>A_v</tex> принадлежат одной части разреза, а <tex>v</tex> - другой. Пусть неравенство выполнено для всех активных вершин до <tex>v</tex>, включая <tex>v</tex>, докажем его для следующей активной вершины <tex>u</tex>.
<tex> w(u,A_u) \equiv w(u,A_v) + w(u,A_u \setminus A_v)</tex> (*)
Заметим, что
<tex>w(u,A_v) \le w(v,A_v)</tex> (**)
вершина <tex>v</tex> имела большее значение <tex>w</tex>, чем <tex>u</tex>, так как была добавлена в <tex>A</tex> раньше.
По предположению индукции:
<tex>w(v,A_v) \le w(C_v)</tex>
Следовательно из (**):
<tex>w(u,A_v) \le w(C_v)</tex>
А из (*) имеем:
<tex>w(u,A_u) \le w(C_v) + w(u,A_u \setminus A_v)</tex>
}}
