Изменения

Перейти к: навигация, поиск

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

24 байта добавлено, 21:07, 28 января 2016
м
Теорема Гринберга
|statement=
Пусть связный граф <tex> G </tex> имеет гамильтонов бонд <tex> H </tex> с торцевыми графами <tex> X </tex> и <tex> Y </tex>. Пусть <tex> f_n^{X} </tex> и <tex> f_n^{Y} </tex> {{---}} число и вершин в графов <tex> X </tex> и <tex> Y </tex> соответственно, имеющих в <tex> G </tex> валентность <tex> n ~ (n = 1, ~ 2, ~ 3, ~ \ldots) </tex>. Тогда:
<center> <tex> \sum\limits_{n=1}^{\infty} (n - 2) (f_n^{X} - f_n^{Y}) = 0 ~~~ \bf{(1)} </tex>. '''(1)''' </center>
|proof=
Используя теорему '''1.37''', находим, что:
<center> <tex> \sum\limits_{n=1}^{\infty} f_n^{X} = |E(X)| + 1 ~~~ \textbf{(2)} </tex>. '''(2)''' </center>
Ясно также, что:
<center> <tex> \sum\limits_{n=1}^{\infty} n f_n^{X} = |E(H)| + 2|E(X)| ~~~ \textbf{(3)} </tex>. '''(3)''' </center>
Поэтому:
<center> <tex> \sum\limits_{n=1}^{\infty} (n - 2) f_n^{X} = |E(H)| - 2 ~~~ \textbf{(4)} </tex>. '''(4)''' </center>
Аналогичную формулу получаем для графа <tex> Y </tex>. Вычитая ее из '''(4)''', приходим к '''(1)'''.
}}
39
правок

Навигация