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

Теорема Гринберга(англ. 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\limits_{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], то область [math]R[/math] разбита на [math]e + 1[/math] граней. а область [math]R'[/math] — на [math]e' + 1[/math] граней. Получаем соотношения: (1) [math]\sum\limits_{i=3}^{V(G)}k_i=e+1[/math], [math]\sum\limits_{i=3}^{V(G)}k'_i=e'+1[/math] Каждое внутреннее ребро области [math]R[/math] входит в границы двух внутренних граней области [math]R[/math], а каждое ребро цикла [math]C[/math] — в границу одной внутренней грани этой области. Аналогичное соотношение верно и для [math]R'[/math]. Следовательно, (2) [math]\sum\limits_{i=3}^{V(G)}i \cdot k_i=2e+E(C)[/math], [math]\sum\limits_{i=3}^{V(G)}i \cdot k'_i=2e'+E(C)[/math] Из соотношений (1) и (2) получаем: [math]\sum\limits_{i=3}^{V(G)}i(k_i - k'_i)=2(e - e')=\sum\limits_{i=3}^{V(G)}2(k_i-k'_i)[/math] откуда немедленно следует доказываемое утверждение.

[math]\triangleleft[/math]

Граф Гринберга

Используя свою теорему, Гринберг построил трёхсвязный кубический плоский граф, в котором ровно одна грань имеет [math]9[/math] рёбер, а все остальные — по [math]5[/math] или [math]8[/math] рёбер. Левая часть соотношения [math]\sum\limits_{i=3}^{V(G)}(i-2)(k_i-k'_i)=0[/math] в таком графе, очевидно, не делится на [math]3[/math], так как сравнима по модулю [math]3[/math] с [math](9 - 2)(k_9 - k'_9) = 7[/math].

Граф Гринберга. Проставлено количество ребер в гранях

Придуманый Гринбергом в 1968 году критерий негамильтоновисти графа, позволил наконец построить контрпримеры к гипотизе Тейта(1884г) о том, что любой 3-регулярный трёхсвязный планарный граф имеет гамильтонов цикл. Долгое время единственным контрпримером к этой гипотезе был граф Татта(1946), негамильтоновость которого доказывалась перебором.

Граф Татта

Источники

• Grinberg's theorem - wikipedia
• Д.В Карпов - теория графов
• теорема Гринберга