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

Абросимов М. Б., Долгов А. А. О БЕСКОНТУРНЫХ ТОЧНЫХ РАСШИРЕНИЯХ // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2010. Т. 10, вып. 1. С. 83-88. DOI: https://doi.org/10.18500/1816-9791-2010-10-1-83-88

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

О БЕСКОНТУРНЫХ ТОЧНЫХ РАСШИРЕНИЯХ

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

Точные расширения неориентированных графов достаточно хорошо исследованы, а о точных расширениях орграфов известно значительно меньше. В данной работе доказывается, что только бесконтурный или сильно связный граф может быть точным 1-расширением орграфа. Более того, бесконтурным точным 1-расширением может быть только транзитивный турнир.

Ключевые слова: 
бесконтурный граф, транзитивный турнир, точное расширение
DOI: 
https://doi.org/10.18500/1816-9791-2010-10-1-83-88
Библиографический список

1. Harary F., Hayes J.P. Node fault tolerance in graphs // Networks. 1996. V. 27. P. 19–23.

2.Абросимов М.Б. Минимальные расширения дополнений графов // Теоретические задачи информатики и ее приложений. Саратов: Изд-во Сарат. ун-та, 2001. Вып. 4. С. 11–19.
3. Абросимов М.Б., Долгов А.А. Точные расширения некоторых турниров // Вестн. Томск. гос. ун-та. Приложение. 2007. № 23. С. 211–216.
4. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997.
 

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