78
правок
Изменения
м
→Использование теоремы
== Использование теоремы ==
* Сам Гринберг использовал свою теорему для того, чтобы искать негамильтоновы кубические(все вершины имеют степень 3) [https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D0%B8%D1%8D%D0%B4%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 полиэдральные графы] с высокой циклической связностью.
* Теорема Гринберга - необходимое условие для планарного графа, чтобы граф содержал гамильтонов цикл, основанное а на длинах циклов граней.
* Теорема Гринберга используется также для поиска планарных гипогамильтоноввых графов путём построения графа, в котором все грани имеют число рёбер, сравнимых с 2 по модулю 3.
* Теорему Гринберга можно иногда использовать для доказательства отсутствия гамильтонова бонда в графе. Пусть, например, все вершины связного графа <tex> G </tex>, кроме одной, имеют степени, сравнимые с 2 по модулю 3. Тогда левая часть формулы '''(1)''' не делится на 3 и, следовательно, гамильтонова бонда в графе <tex> G </tex> не существует. Рисунок '''1''' иллюстрирует этот простой пример.
