78
правок
Изменения
→Базовые определения
<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>G(V_1) \text{ и } G(V_2)</tex> связны. Рассмотрим отдельно подграф <tex>G(V_1)</tex>, если он не связный, то имеет <tex>2</tex> компоненты <tex>O_1 \text{ и } O_2</tex>, но <tex>\forall e \in E = E(V_1, V_2)</tex> граф <tex>G - E + e</tex> связен, а также <tex>e = (u, v) \text{ при } u \in G(V_1), v \in G(V_2)</tex> то есть <tex>e</tex> не связывает <tex>O_1 \text{ и } O_2</tex> между собой, и в графе <tex> G - E + e</tex> остается <tex>2</tex> компоненты, что противоречит условию связности. Так же доказывается связность <tex>G(V_2)</tex>.
<tex>e \in E </tex> можно также представить как <tex>e = (u, v) \text{ при этом } u \in G(V_1), v \in G(V_2)</tex>, то есть <tex>u \in O_1 \mid u \in O_2</tex>, и граф <tex> G - E + e </tex> состоит из <tex>2</tex> компонент <tex>(O_1 \cup G(V_2)), O_2 \mid (O_2 \cup G(V_2)), O_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> этот разрез непуст, то есть, является бондом.
}}
Подграфы <tex>V_1</tex> и <tex>V_2</tex> из предыдущей леммы называются '''торцевыми графами'''.
}}
Также стоит отметить, что если граф <tex> G </tex> несвязен, то его '''бонд''' определим как бонд какой-либо его компоненты, а всякий перешеек [[мост | Мост,_эквивалентные_определения]] графа образует однореберный бонд. Торцевые графы перешейка моста являются торцевыми графами соответствующего бонда.
{{Определение
