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

Осипов Д. Ю. Т-неприводимое расширение для объединения цепей и циклов // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2013. Т. 13, вып. 2. С. 100-?.


Рубрика: 

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

Аннотация: 

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

Библиографический список

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.

 

Краткое содержание (на английском языке):