starlike tree

О НИЖНЕЙ ОЦЕНКЕ ЧИСЛА РЕБЕР МИНИМАЛЬНОГО РЕБЕРНОГО 1-РАСШИРЕНИЯ СВЕРХСТРОЙНОГО ДЕРЕВА

Авторы: Абросимов М. Б.

Граф G∗ называется реберным 1-расширением графа G, если граф G можно вложить в каждый граф, получающийся из графа G∗ , удалением любого его ребра. Реберное 1-расширение G∗ графа G называется минимальным, если графы G и G∗ имеют одинаковое число вершин, а среди всех реберных 1-расширений графа G с тем же числом вершин граф G∗ имеет минимальное число ребер. Дерево называется сверхстройным, если только одна его вершина имеет степень больше двух.

Индексы состояний в динамической системе двоичных векторов, ассоциированных с ориентациями пальм

Авторы: Жаркова А. В.

Рассматривается динамическая система двоичных векторов, ассоциированных с ориентациями пальм. Дерево называется пальмой, если оно является объединением цепей, имеющих общую концевую вершину, причём все эти цепи, за исключением, быть может, одной, имеют длину 1. Данная система в зависимости от размерности состояний разбивается на конечные подсистемы.

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

Авторы: Осипов Д. Ю.

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