RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика // Архив

Изв. Сарат. ун-та. Нов. сер. Сер.: Математика. Механика. Информатика, 2013, том 13, выпуск 2(1), страницы 100–105 (Mi isu402)

Информатика

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

Д. Ю. Осипов

Факультет компьютерных наук и информационных технологий, Саратовский государственный университет им. Н. Г. Чернышевского

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

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

УДК: 519.17

DOI: 10.18500/1816-9791-2013-13-2-1-100-105



Реферативные базы данных:


© МИАН, 2024