Теорема Гринберга — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Базовые определения: определение минимального по включению разреза)
(Теорема Гринберга: пояснения)
Строка 51: Строка 51:
 
Посчитаем <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>. Отсюда:
 
Посчитаем <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>
 
<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> \textbf{(3)} - 2 \times \textbf{(2)} = \sum\limits_{n=1}^{\infty} (n - 2) f_n^{X} = |E(H)| - 2 ~~~ \textbf{(4)} </tex>. </center>
+
<center> <tex>\sum\limits_{n=1}^{\infty} (n - 2) f_n^{X} = |E(H)| - 2 ~~~ \textbf{(4)} </tex>. </center>
 
Аналогичную формулу получаем для графа <tex> Y </tex>. Вычитая ее из <tex>\textbf{(4)}</tex>, приходим к <tex>\textbf{(1)}</tex>.
 
Аналогичную формулу получаем для графа <tex> Y </tex>. Вычитая ее из <tex>\textbf{(4)}</tex>, приходим к <tex>\textbf{(1)}</tex>.
 
}}
 
}}

Версия 02:10, 1 октября 2018

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

Определение:
Подграф (англ. 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]e \in E = E(V_1, V_2)[/math] граф [math]G − E + e[/math] связен, оба графа [math]G(V_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]

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

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

См. также

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