Образец для цитирования:

Абросимов М. Б., Долгов А. А. О РЕКОНСТРУИРУЕМОСТИ МАЛЫХ ТУРНИРОВ // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2009. Т. 9, вып. 2. С. 94-98. DOI: https://doi.org/10.18500/1816-9791-2009-9-2-94-98

Язык публикации: 
русский
Рубрика: 
Информатика
УДК: 
519.17

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

Авторы: 
Абросимов Михаил Борисович , ФГБОУ ВПО Саратовский государственный университет имени Н.Г. Чернышевского, Россия, г. Саратов, ул. Астраханская, 83 , mic@rambler.ru
Долгов Александр Алексеевич , ФГБОУ ВПО Саратовский государственный университет имени Н.Г. Чернышевского, Россия, г. Саратов, ул. Астраханская, 83 , Dolgov.A.A@gmail.com
Аннотация: 

В работе рассматриваются вопросы, связанные с реконструируемостью турниров. Приводятся известные результаты по реконструируемости ориентированных графов и описывается схема построения семейств Стокмейера нереконструируемых направленных графов. Рассматривается техника компьютерного поиска нереконструируемых турниров и соответствующие алгоритмы. Приводятся все нереконструируемые турниры с числом вершин до 12.
 

Ключевые слова: 
граф, турнир, реконструируемость графов
DOI: 
https://doi.org/10.18500/1816-9791-2009-9-2-94-98
Библиографический список

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

2. Харари Ф. Теория графов. М.: УРСС, 2003.

3. Stockmeyer P. My quest for non-reconstructable graphs // Congressus Numerantium. 1988. V. 63. P. 188– 200.
4. Долгов А.А. Турниры и гипотеза вершинной реконструируемости // Наука и образование: проблемы и перспективы: Материалы 9-й региональной научнопрактической конференции аспирантов, студентов и учащихся (Бийск, 13–14 апреля 2007г.). 2007. С. 171– 176.
 

Полный текст в формате PDF:
скачать
52