Теорема Гринберга

Базовые определения

Определение:

Подграф (англ. 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], и граф [math] G - 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]\triangleleft[/math]

Определение:

Подграфы [math]V_1[/math] и [math]V_2[/math] из предыдущей леммы называются торцевыми графами.

Также стоит отметить, что если граф [math] G [/math] несвязен, то его бонд определим как бонд какой-либо его компоненты, а всякий мост графа образует однореберный бонд. Торцевые графы моста являются торцевыми графами соответствующего бонда.

Определение:

Гамильтоновым бондом (англ. hamiltonian bond) называется бонд графа [math] G [/math], торцевыми графами которого являются деревья.

Теорема Гринберга

Теорема (Гринберг):

Пусть связный граф [math] G [/math] имеет гамильтонов бонд [math] H [/math] с торцевыми графами [math] X [/math] и [math] Y [/math]. Пусть [math] f_n^{X} [/math] и [math] f_n^{Y} [/math] — число вершин в графов [math] X [/math] и [math] Y [/math] соответственно, имеющих в [math] G [/math] степень [math] n ~ (n = 1, ~ 2, ~ 3, ~ \ldots) [/math]. Тогда: [math] \sum\limits_{n=1}^{\infty} (n - 2) (f_n^{X} - f_n^{Y}) = 0 ~~~ \bf{(1)} [/math].

Доказательство:

[math]\triangleright[/math]

Так как торцевые графы являются деревьями, то количество их вершин на единицу больше количества ребер: [math] \sum\limits_{n=1}^{\infty} f_n^{X} = |V(X)| = |E(X)| + 1 ~~~ \textbf{(2)} [/math]. Посчитаем [math] \sum\limits_{n=1}^{\infty} n f_n^{X} [/math], то есть количество всех исходящих ребер из [math]X[/math]. По лемме о рукопожатиях ребер, с обоих сторон прикрепленных к [math]X[/math], будет [math]2|E(X)|[/math]. Количество ребер, прикрепленных и к [math]X[/math], и к [math]Y[/math], по определению бонда — количество ребер в бонде [math]H[/math], то есть [math]|E(H)|[/math]. Отсюда: [math] \sum\limits_{n=1}^{\infty} n f_n^{X} = |E(H)| + 2|E(X)| ~~~ \textbf{(3)} [/math]. Вычитаем дважды из формулы [math]\textbf{(3)}[/math] формулу [math]\textbf{(2)}[/math] и получаем: [math]\sum\limits_{n=1}^{\infty} (n - 2) f_n^{X} = |E(H)| - 2 ~~~ \textbf{(4)} [/math]. Полученная формула в правой части не зависит от подграфа, поэтому вычитая вариант для [math] Y [/math] из [math]\textbf{(4)}[/math], приходим к [math]\textbf{(1)}[/math].

[math]\triangleleft[/math]

Использование теоремы

Рис. 1

• Сам Гринберг использовал свою теорему для того, чтобы искать негамильтоновы кубические (все вершины имеют степень [math]3[/math]) полиэдральные графы с высокой циклической связностью. Например он нашел граф с [math]46[/math] вершинами, [math]25[/math] гранями и циклической рёберной связностью пять, показанный на рисунке [math]1[/math].
• Теорема Гринберга — необходимое условие для планарного графа, чтобы граф содержал гамильтонов цикл, основанное на длинах циклов граней.
• Теорема Гринберга используется также для поиска планарных гипогамильтоновых графов путём построения графа, в котором все грани имеют число рёбер, сравнимых с [math]2[/math] по модулю [math]3[/math].

Рис. 2

• Теорему Гринберга можно иногда использовать для доказательства отсутствия гамильтонова бонда в графе. Пусть, например, все вершины связного графа [math] G [/math], кроме одной, имеют степени, сравнимые с [math]2[/math] по модулю [math]3[/math]. Тогда левая часть формулы [math]\textbf{(1)}[/math] не делится на [math]3[/math] и, следовательно, гамильтонова бонда в графе [math] G [/math] не существует. Рисунок [math]2[/math] иллюстрирует этот простой пример.

См. также

• Гамильтоновы графы
• Разрез, лемма о потоке через разрез
• Лемма о рукопожатиях
• Дерево, эквивалентные определения

Источники информации

• У. Татт. Теория графов. М.: "Мир", 1988. с. 304. ISBN 5-03-001001-7
• Д.В. Карпов. Теория графов. c. 301