1632
правки
Изменения
м
rollbackEdits.php mass rollback
Пусть в графе <tex>G' \setminus S</tex> всего <tex>t</tex> компонент связности, <tex>n</tex> из которых нечётны. Тогда пусть <tex>U_1, \cdots, U_n</tex> {{---}} нечётные компоненты связности <tex>G' \setminus S</tex>, тогда <tex>|odd(G' \setminus S)| = n</tex>, а <tex>U_{n+1}, \cdots, U_t</tex> {{---}} его чётные компоненты связности. Для каждого <tex>i \in [1 \cdots t]</tex> определим три множества:
[[Файл:Плешник 1.png|300px|thumb|right|Чёрные ребра {{---}} рёбра из <tex>A_i</tex>, красные рёбра {{---}} рёбра из <tex>B_i</tex>, синие рёбра {{---}} рёбра из <tex>C_i</tex>. Обратите внимание, что только чёрные рёбра есть в графе <tex>G'</tex>, синие и красные {{---}} рёбра из <tex>F</tex>]]
<tex>A_i</tex> {{---}} рёбра из <tex>E(G')</tex>, соединяющие <tex>U_i</tex> с <tex>S</tex>, <tex>\alpha_i</tex> {{---}} их количество, то есть <tex>\alpha_i = |A_i|</tex>
