uzluga.ru
добавить свой файл

РЕКОНСТРУИРУЕМОСТЬ МАЛЫХ ТУРНИРОВ


А.А.Долгов


Саратовский государственный университет, Саратов, Россия


Турниром называется полный направленный граф без петель. Турнир называется сильным, если любые две его вершины взаимно достижимы. Здесь и далее определения даются по работе [1].

Говорят, что граф является реконструируемым, если он может быть однозначно с точностью до изоморфизма восстановлен по списку своих максимальных подграфов.

Для неориентированных графов известная гипотеза Келли-Улама (1945 г.) утверждает, что если два графа G и H с числом вершин большим двух имеют одинаковые максимальные подграфы, то G и H изоморфны. Для малых графов гипотеза проверена с помощью компьютерного поиска (см. [2]).

Для ориентированных графов гипотеза в общем виде не верна. Особый интерес представляют результаты, полученные в 70-80-х годах Стокмейером. В обобщающей работе [3] приводится схема построения пар сильных n-вершинных турниров, имеющих одинаковые списки максимальных подграфов, то есть являющихся исключением из гипотезы Келли-Улама, для n = 2m + 2k, 0 ≤ m < k (3, 5, 6, 9, 10, 12, 17, 18, 20, 24, ...). Реконструируемость несильных турниров была доказана Харари и Палмером в работе [4]. С помощью компьютерных вычислений Стокмейер проверил все турниры с числом вершин до 8 в поиске нереконструируемых турниров.

Была разработана система распределенных вычислений для поиска нереконструируемых турниров. Разработав ряд алгоритмов, позволяющих сократить и ускорить перебор, при помощи системы удалось получить все турниры с числом вершин до 10, а затем, используя их проверить реконструируемость турниров с числом вершин до 11. Таким образом, были перепроверены результаты Стокмейера для турниров с числом вершин до 8, а также было проведено более глубокое исследование реконструируемости турниров.

Некоторые результаты исследований были ранее представлены в работе [5]. На рисунке изображены нереконструируемые 10-вершинные турниры, обнаруженные в ходе вычислений. Для найденных турниров получено аналитическое доказательство их нереконструируемости.



Рис. 10-вершинные нереконструируемые графы


Результаты были получены с помощью расчетов, осуществлявшихся в течение 25 суток на 8 компьютерах Intel Pentium IV 2.4 ГГц.


Список литературы

1. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. М.: Наука. 1997. С. 368

2. McKay B. D., Small graphs are reconstructible // Australasian J. Combinatorics, 1997. Vol. 15. P. 123-126.

3. Stockmeyer P.B. My quest for non-reconstructable graphs // Congressus Numerantium, 1988. Vol. 63. P.188-200.

4. Harary F., Palmer E. M. On the Problem of Reconstructing a Tournament from Subtournaments // Monatsh. Math, 1967. Vol. 71. P. 14-23.

5. Абросимов М.Б., Долгов А.А. Гипотеза Келли-Улама и малые турниры // Актуальные проблемы математики, механики, информатики: матер. Междунар. науч.-метод. конф., посвященной 90-летию высшего математического образования на Урале (Пермь, 9-15 окт. 2006 г.). Пермь: ПГУ, 2006. 300 с. С. 33-34.