Loading AI tools
Из Википедии, свободной энциклопедии
Задача Конвея о 99-вершинном графе — нерешённая задача, которая спрашивает, существует ли неориентированный граф с 99 вершинами, в которых каждые две смежные вершины имеют в точности одного общего соседа и в которых две несмежные вершины имеют в точности два общих соседа. Эквивалентно, любое ребро должно быть частью единственного треугольника, а любая пара несмежных вершин должна быть на диагонали единственного 4-цикла. Джон Хортон Конвей объявил о призе в 1000 долларов тому, кто решит эту проблему[1].
Если такой граф существует, он необходимо будет локально линейным сильно регулярным графом с параметрами (99,14,1,2). Первый, третий и четвёртый параметр кодируют утверждение проблемы — граф должен иметь 99 вершин, каждая пара смежных вершин должна иметь 1 одного общего соседа, а любые несмежные вершины должны иметь 2 общих соседа. Второй параметр означает, что граф является регулярным графом с 14 рёбрами на вершину[2].
Если этот граф существует, он не имеет любых симметрий порядка 11, откуда следует, что его симметрии не могут перевести любую вершину в любую другую вершину[3]. Известны и другие ограничения на возможные группы симметрий[4].
О возможном существовании графа с такими параметрами предполагал уже в 1969 году Норман Л. Биггс[5], а как открытую проблему существования среди прочих поставил Конвей[3][6][7][8]. Конвей сам работал над этой проблемой с 1975 года[6], но объявил приз в 2014 тому, кто решит проблему, как часть набора проблем, представленных на конференции DIMACS по важнейшим проблемам идентификации целочисленных последовательностей. Другие проблемы в этом наборе включает гипотезу о трекле, наименьшего расстояния множеств Данцера и вопрос, кто выигрывает после хода 16 в игре в «чеканку»[англ.][1].
Более обще, существует только пять возможных комбинаций параметров, для которых сильно регулярный граф может существовать со свойством, что каждое ребро принадлежит единственному треугольнику, а каждое не-ребро (отсутствующее ребро двух несмежных вершин) образует диагональ единственного четырёхугольника. Известно только, что графы существуют с двумя из пяти этих комбинаций. Этими двумя графами являются граф Пэли с девятью вершинами (граф 3-3 дуопризмы) с параметрами (9,4,1,2) и граф Берлекэмпа — ван Линта — Зейделя с параметрами (243,22,1,2). Проблема 99-графа спрашивает о наименьшей из этих пяти комбинаций параметров, для которых существование графа неизвестно[4].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.