В теории графов Граф Винера — Арайи — неориентированный планарный гипогамильтонов граф с 42 вершинами и 67 рёбрами, названный в честь Габора Винера и Макото Арайи, впервые описавших его в 2009 году в публикации The ultimate question (2009).
История Гипогамильтоновы графы впервые были исследованы Сусилье в статье Problèmes plaisants et délectables (1963). В 1967 году Линдгрен построил бесконечную последовательность гипогамильтоновых графов. Он указал на Годена, Герца и Росси, а затем на Ба́сакера и Саати как пионеров данной области.
Минимальный по числу вершин гипогамильтонов граф был известен давно — это Граф Петерсена. Однако поиска наименьшего планарного гипогамильтонова граф продолжаются. Впервые вопрос был поставлен Вацлавом Хваталом в 1973 году. Первым попытался предоставить ответ Карстен Томассен в 1976 году, его 105-граф Томассена содержал 105 вершин. В 1979 году Хатцель улучшил этот результат, найдя планарный гипогамильтонов граф с 57 вершинами — граф Хатцеля. Эта граница была понижена в 2007 году 48-графом Замфиреску.
В 2009 году граф, построенный Габором Винером и Макото Арайи, (с 42 вершинами) стал наименьшим известным планарным гипогамильтоновым графом. В своей статье Винер и Арайа предположили, что существование их графа делает возможным, что главный вопрос жизни, вселенной и всего такого в романе Дугласа Адамса Автостопом по галактике, мог звучать как "каков размер минимального планарного гипогамильтонова графа?"
Однако уже в 2013 году был обнаружен меньший планарный гипогамильтонов граф (40 вершин).
Свойства Граф Винера — Арайи планарен. Его можно нарисовать на плоскости без пересечения рёбер.
Граф Винера — Арайи гипогамильтонов. Сам по себе граф не содержит гамильтонова цикла, однако удаление любой одной вершины приводит к графу, содержащему гамильтонов цикл.
Хроматическое число графа равно 3, хроматический индекс равен 4, обхват равен 4, радиус равен 5, диаметр равен 7.
Примечания
Литература
Ссылки
Категория:Планарные графы Категория:Графы, имеющие собственные названия