78
правок
Изменения
→Базовые определения: - Новое определение бонда, лемма
}}
{{Определение
|definition=
}}
{{Лемма
|statement=
Разрез <tex>E(V_1, V_2)</tex> связного графа G является '''бондом''', если и только если оба графа <tex>G(V_1)</tex> и <tex>G(V_2)</tex> связны.
|proof=
Для удобства примем <tex>E = E(V_1, V_2)</tex>.
<tex>\Rightarrow</tex>. Пусть <tex>E</tex> - бонд. Докажем, что для любого ребра <tex>e \in E</tex> граф <tex>G - E + e</tex> связен. Действительно, пусть этот граф несвязен и имеет, скажем, компоненты связности <tex>U_1</tex> и <tex>U_2</tex>. Тогда <tex>E \supsetneq E(U_1, U_2)</tex>, а из связности графа <tex>G</tex> следует, что <tex>E(U_1, U_2) \neq \varnothing</tex>. Противоречие с минимальностью <tex>E</tex>.
Так как для любого ребра <tex>e \in E = E(V_1, V_2)</tex> граф <tex>G − E + e</tex> связен,
оба графа <tex>G(V_1)</tex> и <tex>G(V_2)</tex> связны.
<tex>\Leftarrow</tex>. Если оба графа <tex>G(V_1)</tex> и <tex>G(V_2)</tex> — связны, то добавление любого ребра из <tex>E</tex> даст нам связный подграф графа <tex>G</tex>. Значит, в этом случае разрез <tex>E</tex> минимален по включению. В силу связности <tex>G</tex> этот разрез непуст, то есть, является бондом.
}}
{{Определение
|definition=
Подграфы <tex>V_1</tex> и <tex>V_2</tex> из предыдущей леммы называются '''торцевыми графами'''.
}}
Также стоит отметить, что если граф <tex> G </tex> несвязен, то его '''бонд''' определим как бонд какой-либо его компоненты, а всякий перешеек графа образует однореберный бонд. Торцевые графы перешейка являются торцевыми графами соответствующего бонда.
{{Определение
