|
Информатика
Т-неприводимое расширение для объединения цепей и циклов
Д. Ю. Осипов Факультет компьютерных наук и информационных технологий, Саратовский государственный университет им. Н. Г. Чернышевского
Аннотация:
Расширением $n$-вершинного графа $G$ называется граф $H$ с $n+1$ вершинами такой, что граф $G$ вкладывается в каждый максимальный подграф графа $H$. Тривиальное расширение графа $G$ – соединение графа $G$ с одноэлементным графом (т.е. к графу $G$ добавляется вершина, которая соединяется ребром с каждой вершиной графа $G$). Т-неприводимым расширением графа $G$ называется расширение графа $G$, получаемое из тривиального расширения данного графа удалением максимально возможного набора добавленных при построении тривиального расширения ребер. В данной работе описано одно из ТНР для произвольного объединения цепей и циклов.
Ключевые слова:
граф, Т-неприводимое расширение, объединение цепей и циклов.
Образец цитирования:
Д. Ю. Осипов, “Т-неприводимое расширение для объединения цепей и циклов”, Изв. Сарат. ун-та. Нов. сер. Сер.: Математика. Механика. Информатика, 13:2(1) (2013), 100–105
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/isu402 https://www.mathnet.ru/rus/isu/v13/i3/p100
|
Статистика просмотров: |
Страница аннотации: | 200 | PDF полного текста: | 72 | Список литературы: | 40 |
|