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

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

Версия 00:22, 24 декабря 2013

Теорема Гринберга(англ. Grinberg) - необходимое условие содержания гамильтонова цикла планарным графом.

Теорема (Гринберга):
Пусть [math]G[/math] плоский граф без петель с гамильтоновым циклом [math]C[/math], который делит плоскости на две области [math]R[/math] и [math]R'[/math]. Пусть [math]k_i[/math] и [math]k'_i[/math] — количества граней размера [math]i[/math] в [math]R[/math] и [math]R'[/math] соответственно. Тогда [math]\sum_{i=3}^{V(G)}(i-2)(k_i-k'_i)=0[/math]
Доказательство:
[math]\triangleright[/math]

Отметим, что в гамильтоновом графе [math]G[/math], очевидно, нет мостов и граница любой грани — простой цикл. Поэтому размер границы каждой его грани не более [math]V(G)[/math]. Пусть [math]e[/math] и [math]e'[/math] — количества рёбер графа [math]G[/math], лежащих внутри областей [math]R[/math] и [math]R'[/math] соответственно. Так как [math]C[/math] — гамильтонов цикл графа [math]G[/math], то область R разбита на [math]e + 1[/math] граней. а область [math]R'[/math] — на [math]e' + 1[/math] граней. Получаем соотношения:

(1) [math]\sum_{i=3}^{V(G)}k_i=e+1[/math], [math]\sum_{i=3}^{V(G)}k'_i=e'+1[/math]

Каждое внутреннее ребро области [math]R[/math] входит в границы двух внутренних граней области [math]R[/math], а каждое ребро цикла [math]C[/math] — в границу одной внутренней грани этой области. Аналогичное соотношение верно и для [math]R'[/math]. Следовательно,

(2) [math]\sum_{i=3}^{V(G)}i*k_i=2e+E(C)[/math], [math]\sum_{i=3}^{V(G)}i*k'_i=2e'+E(C)[/math]

Из соотношений (1) и (2) получаем:

[math]\sum_{i=3}^{V(G)}i(k_i-k'_i)=2(e - e')=\sum_{i=3}^{V(G)}2(k_i-k'_i)[/math]

откуда немедленно следует доказываемое утверждение.
[math]\triangleleft[/math]