Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


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

Осипов Д. Ю. Т-неприводимые расширения для сверхстройных деревьев // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2015. Т. 15, вып. 3. С. 330-339. DOI: https://doi.org/10.18500/1816-9791-2015-15-3-330-339

Опубликована онлайн: 
11.09.2015
Язык публикации: 
русский
Рубрика: 
УДК: 
519.17

Т-неприводимые расширения для сверхстройных деревьев

Авторы: 
Осипов Дмитрий Юрьевич, Саратовский национальный исследовательский государственный университет им. Н. Г. Чернышевского
Аннотация: 

Рассматривается один из способов построения оптимального расширения графа — Т-неприводимое расширение (ТНР). До сих пор остается нерешенной следующая задача: построить одно из ТНР для произвольного сверхстройного дерева. Данная задача была решена С. Г. Курносовой для подкласса сверхстройных деревьев –- пальм. Для несложных сверхстройных деревьев данная задача была решена М. Б. Абросимовым. Приводится контрпример для схемы из статьи Харари и Хурума «One node fault tolerance for caterpillars and starlike trees», которая описывает построение одного ТНР для произвольного сверхстройного дерева. Приводится схема построения ТНР для сложных сверхстройных деревьев с числом вершин k > 4 и доказывается её корректность. Рассматриваются различные семейства сложных сверхстройных деревьев с k = 3 и строится ТНР для каждого из семейств.

DOI: 
10.18500/1816-9791-2015-15-3-330-339
Библиографический список: 
  1. Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М. : Наука, 2009.
  2. Курносова С. Г. Т-неприводимые расширения для некоторых классов графов // Теоретические проблемы информатики и ее приложений. Саратов : Изд-во Сарат. ун-та, 2004. Вып. 6. С. 113–125.
  3. Harary F., Khurum M. One node fault tolerance for caterpillars and starlike trees // Internet J. Comput. Math. 1995. Vol. 6. P. 135–143.
  4. Осипов Д. Ю. Об одном контрпримере для Т-неприводимых расширений сверхстройных деревьев // Прикладная дискретная математика. 2014. № 3(25). С. 98–102.
  5. Абросимов М. Б. Графовые модели отказоустойчивости. Саратов : Изд-во Сарат. ун-та, 2012. 192 с.
Полный текст в формате PDF:
(downloads: 12)