Теорема Грінберга
Зміст
Базові визначення [ред.]
| Визначення: |
| Підграф(англ.subgraph) вихідного графа - граф, що містить деяке підмножина вершин даного графа і деяке підмножина інцидентних їм ребер. По відношенню до подграф вихідний граф називається суперграф. |
| Визначення: |
| Бонд(англ.bond) графа - це мінімальний (за включенням) непустий розріз графа [math]G[/math]. |
| Визначення: |
| Мінімальний (за включенням)(англ.minimal by inclusion) розріз графа [math]G[/math] - розріз, з якого не можна виділити розрізи з меншою кількістю ребер. |
| Лемма: |
| Розріз [math]E(V_1, V_2)[/math] зв'язного графа [math]G[/math] єбондом, якщо і тільки якщо обидва графи [math]G(V_1)[/math] і [math]G(V_2)[/math] зв'язкові. |
| Доказ: |
| [math]\triangleright[/math] |
Для зручності приймемо [math]E = E(V_1, V_2)[/math].
[math]\Rightarrow[/math] . Нехай [math] E [/ math] - бонд. Доведемо, що з будь-якого ребра [math]e \in E[/math] граф [math]G - E + e[/math] зв'язаний. Справді, нехай цей граф незв'язний і має, скажімо, компоненти зв'язності [math]U_1[/math] та [math]U_2[/math]. Тоді [math]E \supsetneq E(U_1, U_2)[/math] , а з зв'язності графа [math]G[/math] випливає, що [math]E(U_1, U_2) \neq \varnothing[/math] . Суперечність із мінімальністю [math]E[/math] .
Тепер доведемо, що підграфи [math]G(V_1) \text < і >G(V_2)[/math] зв'язкові. Розглянемо окремо підграф [math]G(V_1)[/math] , якщо він не зв'язковий, то має як мінімум [math]2[/math] компонентизв'язків, назвемо їх [math]O_1 \text < та >O_2[/math] .
[math]e \in E [/math] можна також уявити як [math]e = (u, v) \text < при цьому u \in G(V_1), v \in G(V_2)[/math] , тобто [math]u \in O_1 \mid u \in O_2[/math] і граф - E + e [/math] складається з [math]2[/math] компонент - [math](O_1 \cup G(V_2), O_2) \mid (O_2 \cup G(V_2), O_1)[/math ] , що суперечить умові зв'язності. Також доводиться зв'язність [math]G(V_2)[/math] .
[math]\Leftarrow[/math] . Якщо обидва графи [math]G(V_1)[/math] і [math]G(V_2)[/math] — зв'язкові, то додавання будь-якого ребра з [math]E[/math] дасть нам зв'язковий підграф графа [math] G[/math] , що містить усі його вершини. Отже, у разі розріз [math]E[/math] мінімальний по включенню. З огляду на зв'язність [math]G[/math] цей розріз непустий, тобто, є бондом.
| Визначення: |
| Підграфи [math]V_1[/math] і [math]V_2[/math] з попередньої леми називаютьсяторцевими графами(англ.end graph). |
Також варто відзначити, що якщо граф [math] G [/math] незв'язний, то його бонд визначимо як бонд будь-якої його компоненти, а всякий міст графа утворює однореберний бонд. Торцеві графи моста є торцевими графами відповідного бонда.
| Визначення: |
| Гамільтоновим бондом(англ.hamiltonian bond) називається бонд графа [math] G [/math] , торцевими графами якого є дерева. |
Теорема Грінберга [ред.]
| Теорема (Грінберг): |
| Доказ: |
| [math]\triangleright[/math] |
Так як торцеві графи є деревами, то їх вершин на одиницю більше кількості ребер: Порахуємо [math] \sum\limits_^ n f_n^ [/math] , тобто кількість вихідних ребер з [math]X[/math] . По лемі про рукостискання ребер, по обидва боки прикріплених до [math]X[/math] , буде [math]2E(X)[/math] . Кількість ребер, прикріплених і до [math]X[/math], і до [math]Y[/math], за визначенням бонда - кількість ребер у бонді [math]H[/math], тобто [math]E( H) [/ math] . Звідси: Віднімаємо двічі з формули [math]\textbf[/math] формулу [math]\textbf[/math] і отримуємо: [math] \ sum \ limits_ ^ (n - 2) f_n ^ = E (H) - 2 |