Изменения

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

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

1 байт добавлено, 20:30, 1 января 2014
Нет описания правки
Левая часть соотношения <math>\sum\limits_{i=3}^{V(G)}(i-2)(k_i-k'_i)=0</math> в таком графе, очевидно, не делится на <tex>3</tex>, так как сравнима по модулю <tex>3</tex> с <tex>(9 - 2)(k_9 - k'_9) = 7</tex>.
[[Файл: Grinberg_Graph_numbers.png|300px|thumb|left| [http://logic.pdmi.ras.ru/~dvk/211/graphs_dk.pdf#259| Граф Гринберга. Проставлено количество ребер в гранях] ]]
Придуманый Гринбергом в 1968 году критерий негамильтоновисти графа, позволил наконец построить контрпримеры к [http://en.wikipedia.org/wiki/Tait%27s_conjecture| гипотизе Тейта](1884г) о том, что любой 3-регулярный трёхсвязный планарный граф имеет гамильтонов цикл. Долгое время единственным контрпримером к этой гипотезе был [http://en.wikipedia.org/wiki/Tutte_graph| граф Татта](1946), негамильтоновость которого доказывалась перебором.
497
правок

Навигация