497
правок
Изменения
Нет описания правки
Теорема Гринберга(англ. '''Grinberg''') - необходимое условие содержания [[Гамильтоновы графы|гамильтонова цикла]] [[Укладка графа на плоскости|планарным]] графом.
{{Теорема
|about=Гринберга
|statement=
Пусть <tex>G</tex> плоский граф без петель с гамильтоновым циклом <tex>C</tex>, который делит плоскости на две области <tex>R</tex> и <tex>R'</tex>. Пусть <tex>k_i</tex> и <tex>k'_i</tex> {{---}} количества граней размера <tex>i</tex> в <tex>R</tex> и <tex>R'</tex> соответственно. Тогда
<math>\sum_{i=3}^{V(G)}(i-2)(k_i-k'_i)=0</math>
|proof=
Отметим, что в гамильтоновом графе <tex>G</tex>, очевидно, нет мостов и граница любой грани {{---}} простой цикл. Поэтому размер границы каждой его грани не более V(G). Пусть у и e' {{---}} количества рёбер графа G, лежащих внутри областей R и R' соответственно. Так как C {{---}} гамильтонов цикл графа G, то область R разбита на e + 1 граней. а область R' {{---}} на e' + 1 граней. Получаем соотношения:
<math>\sum_{i=3}^{V(G)}k_i=e+1</math> <math>\sum_{i=3}^{V(G)}k'_i=e'+1</math>
}}
