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

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

Язык публикации:

русский

Рубрика:

Информатика

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

Авторы:

Осипов Дмитрий Юрьевич, ФГБОУ ВПО Саратовский государственный университет имени Н.Г. Чернышевского, Россия, г. Саратов, ул. Астраханская, 83 , st_hill@mail.ru

Аннотация:

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

Ключевые слова:

: граф, Т-неприводимое расширение, объединение цепей и циклов.

DOI:

https://doi.org/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. Абросимов М. Б. Минимальные расширения объ-

единения некоторых графов // Теоретические пробле-