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

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

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

Подграф (англ. subgraph) исходного графа — граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер. По отношению к подграфу исходный граф называется суперграфом.

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

Порождённый подграф (англ. induced subgraph) — подграф, порождённый множеством рёбер исходного графа. Содержит не обязательно все вершины графа, но эти вершины соединены такими же ребрами, как в графе.

Пусть множество вершин графа [math] G [/math] разбито на взаимно дополнительные подмножества [math] X [/math] и [math] Y [/math]. Через [math] J(X, Y) [/math] обозначим множество всех ребер графа [math] G [/math], у каждого из которых один конец лежит в [math] X [/math], а другой — в [math] Y [/math].

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

Если граф [math] G [/math] и порожденные подграфы [math] G[X] [/math] и [math] G[Y] [/math] связны, то множество [math] J(X, Y) [/math] называется бондом графа [math] G [/math]. Подграфы [math] G[X] [/math] и [math] G[Y] [/math] называются торцевыми графами этого бонда. Из приведенного определения следует, что бонд [math] J(X, Y) [/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} = |E(H)| + 2|E(X)| ~~~ \textbf{(3)} [/math]. Поэтому: [math] \sum\limits_{n=1}^{\infty} (n - 2) f_n^{X} = |E(H)| - 2 ~~~ \textbf{(4)} [/math]. Аналогичную формулу получаем для графа [math] Y [/math]. Вычитая ее из (4), приходим к (1).

[math]\triangleleft[/math]

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

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

Рис. 1

См. также

• Гамильтоновы графы

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

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