Главная
Новости
Строительство
Ремонт
Дизайн и интерьер

















Яндекс.Метрика





Граф Винера — Арайи

Граф Винера — Арайи — это граф с 42 вершинами и 67 рёбрами. Он гипогамильтонов, что означает, что сам по себе он не имеет гамильтонова цикла но любой граф, образованный удалением отдельной вершины, гамильтонов. Он также планарен.

История

Гипогамильтоновы графы первым изучал Сусилье в статье Problèmes plaisants et délectables (1963). В 1967 году Линдгрен построил бесконечную последовательность гипогамильтоновых графов. Он указал на Годена, Герца и Росси, а затем на Басакера и Саати как пионеров данной области.

С самого начала наименьший гипогамильтонов граф известен — это Граф Петерсена. Однако охота на наименьший планарный гипогамильтонов граф продолжается. Вопрос первым поставил Вацлав Хватал в 1973 году. Первый ответ дал в 1976 году Карстен Томассен, который представил построение графа со 105 вершинами, 105-граф Томассена. В 1979 году Хатцель улучшил этот результат, найдя планарный гипогамильтонов граф с 57 вершинами — граф Хатцеля. Эта граница была понижена в 2007 году 48-графом Замфиреску.

В 2009 году граф, построенный Габором Винером и Макото Арайи, (с 42 вершинами) стал наименьшим известным планарным гипогамильтоновым графом. В своей статье Винер и Арайа высказали гипотезу, что их граф является оптимальным аргументом, почему число (42) появилось как ответ на главный вопрос жизни, вселенной и всего такого из Автостопом по галактике, романа Дугласа Адамса.