78
правок
Изменения
→Использование теоремы
{{Определение
|definition=
'''Минимальный (по включению)''' (англ. ''minimal by inclusion'') разрез графа <tex>G</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 </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> этот разрез непуст, то есть, является бондом.
}}
{{Определение
|definition=
Подграфы <tex>V_1</tex> и <tex>V_2</tex> из предыдущей леммы называются '''торцевыми графами'''(англ. ''end graph'').
}}
Также стоит отметить, что если граф <tex> G </tex> несвязен, то его '''бонд''' определим как бонд какой-либо его компоненты, а всякий перешеек [[Мост,_эквивалентные_определения | мост]] графа образует однореберный бонд. Торцевые графы перешейка моста являются торцевыми графами соответствующего бонда.
{{Определение
Так как торцевые графы являются деревьями, то количество их вершин на единицу больше количества ребер:
<center> <tex> \sum\limits_{n=1}^{\infty} f_n^{X} = |V(X)| = |E(X)| + 1 ~~~ \textbf{(2)} </tex>. </center>
Посчитаем <tex> \sum\limits_{n=1}^{\infty} n f_n^{X} </tex>, то есть количество всех исходящих ребер из <tex>X</tex>. По [[Лемма_о_рукопожатиях | лемме о рукопожатиях]] внутри ребер, с обоих сторон прикрепленных к <tex>X</tex> их , будет <tex>2|E(X)|</tex>. Количество ребер, но мы не посчитали ребра прикрепленные прикрепленных и к <tex>X</tex>, и к <tex>Y</tex>. Количество таких ребер, по определению бонда {{---}} количество ребер в бонде <tex>H</tex>, то есть <tex>|E(H)|</tex>. Отсюда:
<center> <tex> \sum\limits_{n=1}^{\infty} n f_n^{X} = |E(H)| + 2|E(X)| ~~~ \textbf{(3)} </tex>. </center>
Вычитаем дважды из формулы <tex>\textbf{(3)}</tex> формулу <tex>\textbf{(2)}</tex> и получаем:
<center> <tex>\sum\limits_{n=1}^{\infty} (n - 2) f_n^{X} = |E(H)| - 2 ~~~ \textbf{(4)} </tex>. </center>
}}
== Использование теоремы ==
== См. также ==
* [[Лемма о рукопожатиях]]
* [[Дерево, эквивалентные определения]]
== Примечания ==
<references />
== Источники информации ==