Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


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

Осипов Д. Ю. Т-неприводимое расширение для объединения цепей и циклов // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2013. Т. 13, вып. 2. С. 100-105. DOI: https://doi.org/10.18500/1816-9791-2013-13-2-1-100-105

Опубликована онлайн: 
27.02.2013
Язык публикации: 
русский
Рубрика: 
УДК: 
519.17

Т-неприводимое расширение для объединения цепей и циклов

Авторы: 
Осипов Дмитрий Юрьевич, Саратовский национальный исследовательский государственный университет им. Н. Г. Чернышевского
Аннотация: 

Расширением n-вершинного графа G называется граф H с n+1 вершинами такой, что граф G вкладывается в каждый максимальный подграф графа H. Тривиальное расширение графа G – соединение графа G с одноэлементным графом (т.е. к графу G добавляется вершина, которая соединяется ребром с каждой вершиной графа G). Т-неприводимым расширением графа G называется расширение графа G, получаемое из тривиального расширения данного графа удалением максимально возможного набора добавленных при построении тривиального расширения ребер. В данной работе описано одно из ТНР для произвольного объединения цепей и циклов. 

DOI: 
10.18500/1816-9791-2013-13-2-1-100-105
Библиографический список: 
  1. Богомолов А. М., Салий В. Н. Алгебраические осно- вы теории дискретных систем. М. : Наука, 1997. 368 с.
  2. Hayes P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. Vol. 25. P. 875– 884.
  3. Абросимов М. Б. Минимальные расширения объ- единения некоторых графов // Теоретические пробле- мы информатики и ее приложений. Саратов : Изд-во Сарат. ун-та, 2001. Вып. 4. С. 3–11.
  4. Салий В. Н. Доказательства с нулевым разглашени- ем в задачах о расширениях графов // Вестн. Томск. гос. ун-та. 2001. Вып. 6. C. 63–65.
  5. Курносова С. Г. Т-неприводимые расширения для некоторых классов графов // Теоретические проблемы информатики и ее приложений. Саратов : Изд-во Сарат. ун-та, 2004. Вып. 6. С. 113–125.
  6. Осипов Д. Ю. Т-неприводимые расширения для объ- единения цепей и циклов // Компьютерные науки и информационные технологии. Саратов : Издат. центр «Наука», 2012. С. 245–246.  
Краткое содержание:
(downloads: 6)
Полный текст в формате PDF:
(downloads: 11)