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