Задача Конвея о 99 графах
В теории графов проблема 99 графов Конвея — это нерешенная проблема, спрашивающая, существует ли неориентированный граф с 99 вершинами , в котором каждые две смежные вершины имеют ровно одного общего соседа и в котором каждые две несмежные вершины имеют ровно двух общих соседей. . Эквивалентно, каждое ребро должно быть частью уникального треугольника, а каждая несмежная пара должна быть одной из двух диагоналей уникального 4-цикла. Джон Хортон Конвей предложил за это решение приз в размере 1000 долларов. [1]
Если бы такой граф существовал, то он обязательно был бы локально линейным графом и сильно регулярным графом с параметрами (99,14,1,2). Первый, третий и четвертый параметры кодируют постановку задачи: в графе должно быть 99 вершин, каждая пара смежных вершин должна иметь 1 общего соседа, а каждая пара несмежных вершин должна иметь 2 общих соседа. Второй параметр означает, что граф является обычным графом с 14 ребрами на вершину. [2]
Если этот граф существует, он не может иметь симметрии, переводящие каждую вершину в любую другую вершину. [3] Известны дополнительные ограничения на его возможные группы симметрий. [4] [5]
Возможность графа с этими параметрами уже была предложена в 1969 году Норманом Л. Биггсом [6] , и его существование было отмечено другими до Конвея как открытая проблема. [3] [7] [8] [9]Сам Конвей работал над этой проблемой еще в 1975 году, [7] но предложил награду в 2014 году как часть набора задач, поставленных на конференции DIMACS по проблемам идентификации целых чисел. Последовательности. Другие проблемы в наборе включают гипотезу тракла , минимальное расстояние между наборами Данцера и вопрос о том, кто выиграет после 16-го хода в игре с серебряной чеканкой . [1]
В более общем смысле существует только пять возможных комбинаций параметров, для которых мог бы существовать строго регулярный граф с каждым ребром в уникальном треугольнике и каждым неребром, образующим диагональ уникального четырехугольника. Известно только, что графы существуют с двумя из этих пяти комбинаций. Эти два графа представляют собой девятивершинный граф Пэли (граф дуопризмы 3-3 ) с параметрами (9,4,1,2) и граф Берлекампа–ван Линта–Зейделя с параметрами (243,22,1,2). ). Параметры, для которых графики неизвестны: (99,14,1,2), (6273,112,1,2) и (494019,994,1,2). Задача 99 графов описывает наименьшую из этих комбинаций параметров, для которых неизвестно существование графа. [4]
