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