Сравнение достаточных условий гамильтоновости графа, основанных на степенях вершин

Абросимов, Михаил Борисович

Сравнение достаточных условий гамильтоновости графа, основанных на степенях вершин

Дата публикации: 2019

Дата публикации в реестре: 2020-03-03T19:12:26Z

Аннотация:

Для всех графов с числом вершин до 12 сравниваются наиболее популярные достаточные условия гамильтоновости, основанные на степенях вершин графа: теоремы Дирака, Оре, Поша, Хватала и Бонди — Хватала. Для каждого условия подсчитано число графов, ему удовлетворяющих. Наилучшие результаты показывает достаточное условие гамильтоновости, предложенное Бонди и Хваталом в 1976г., — этому условию удовлетворяют около 90 % гамильтоновых графов.

Ключевые слова:
гамильтоновы графы, Дирака теорема, Оре теорема, Поша теорема, Хватала теорема, Бонди-Хватала теорема

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2019. № 45. С. 55-63