Изменения

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

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

63 байта убрано, 15:12, 8 октября 2018
Использование теоремы
* Теорему Гринберга можно иногда использовать для доказательства отсутствия гамильтонова бонда в графе. Пусть, например, все вершины связного графа <tex> G </tex>, кроме одной, имеют степени, сравнимые с <tex>2</tex> по модулю <tex>3</tex>. Тогда левая часть формулы <tex>\textbf{(1)}</tex> не делится на <tex>3</tex> и, следовательно, гамильтонова бонда в графе <tex> G </tex> не существует. Рисунок <tex>2</tex> иллюстрирует этот простой пример.
* Теорема Гринберга {{---}} необходимое условие для планарного графа, чтобы Чтобы планарный граф существовал и содержал гамильтонов цикл, основанное на длинах циклов гранейнеобходимо выполнение теоремы Гринберга.
* Теорема Гринберга используется также для поиска планарных гипогамильтоновых графов<ref>[https://ru.wikipedia.org/wiki/%D0%93%D0%B8%D0%BF%D0%BE%D0%B3%D0%B0%D0%BC%D0%B8%D0%BB%D1%8C%D1%82%D0%BE%D0%BD%D0%BE%D0%B2_%D0%B3%D1%80%D0%B0%D1%84 Википедия {{---}} Гипогамильтонов граф]</ref> путём построения графа, в котором все грани имеют число рёбер, сравнимых с <tex>2</tex> по модулю <tex>3</tex>.
78
правок

Навигация