On minimal vertex 1-extensions of special form superslim trees.pdf Дерево называется сверхстройным, если все его вершины, кроме корня и листьев,имеют степень 2. Сверхстройное дерево можно рассматривать как объединение k цепейРг1, . . . , с общей концевой вершиной. Для однозначного задания сверхстройногодерева достаточно указать длины этих цепей: (/1 - 1 ,... ,/& - 1).Граф G* = (V*,а*) называется минимальным вершинным k -расширением (k -натуральное) n-вершинного графа G = (V, а), если выполняются следующие условия:1) G* является вершинным k-расширением G, то есть граф G вкладывается в каждыйподграф графа G*, получающийся удалением любых его k вершин;2) G* содержит n + k вершин, то есть |V*| = |V| + k;3) а * имеет минимальную мощность при выполнении условий 1 и 2.Понятие минимального k-расширения введено на основе понятия оптимальнойk-отказоустойчивой реализации, которое предложено Хейзом в работе [1], где описанамодель для исследования отказоустойчивости, основанная на графах.Вектор степеней сверхстройного дерева имеет вид (k, 2 ,..., 2 ,1 ,..., 1), причем количестволистьев, то есть вершин степени 1, в точности равно k. Кратко вектор степенейсверхстройного дерева может быть записан в виде (k, 2m, 1k). Среди сверхстройныхдеревьев есть представители других хорошо известных семейств графов.Если k = 1 или k = 2, то сверхстройное дерево является цепью Pn. Единственноеминимальное вершинное 1-расширение цепи Pn есть цикл Cn+1 (см. [1]). Далее исключимцепи из рассмотрения и будем говорить о сверхстройных деревьях, у которыхk > 2.Если m = 0, то сверхстройное дерево является звездой K 1,k. Минимальное вершинное1-расширение звезды K 1,k единственно с точностью до изоморфизма и получаетсядобавлением вершины и соединением ее со всеми вершинами звезды.Пусть граф G* суть минимальное вершинное 1-расширение некоторого сверхстрой-ного дерева T . Очевидно, что G* не может содержать вершин степени меньше двух.В самом деле, если бы некоторая вершина имела степень 1, то удаление смежной с нейвершины привело бы к графу с изолированной вершиной. В такой граф дерево T вкладыватьсяне может. Граф G* должен иметь, по крайней мере, две вершины степени нениже k, причем если эти вершины имеют в точности степень k, то они не могут бытьсмежны. Если бы такая вершина была одна, то ее удаление из графа G* привело бык графу, в который дерево T вкладываться не может. Аналогично, если вершин степениk две и они смежны. Таким образом, граф G* отличается от дерева T не менеечем на k дополнительных ребер. Эту оценку уточняет следующаяТеорема 1. Число дополнительных ребер минимального вершинного 1-расширениялюбого сверхстройного дерева не меньше k + 1.На основании проведенного вычислительного эксперимента были проанализированывсе сверхстройные деревья с количеством вершин до 10 общим числом 67. Большинствоиз них имеют минимальные вершинные 1-расширения с числом дополнительныхребер k + 1. Только у 9 из них минимальные вершинные 1-расширения имеют k + 2дополнительных ребра и у одного дерева - k + 3 (это дерево имеет вид (3, 3, 3)).Легко заметить, что если минимальное вершинное 1-расширение сверхстройногодерева имеет k + 1 дополнительных ребер, то его вектор степеней может иметь вид((k + 1)2, 2m+k), (k + 1, k, 3, 2m+k-1) или (k2, 32, 2m+k-2). В работе [2] удалось полностьюописать минимальные вершинные 1-расширения сверхстройных деревьев, которыеимеют вектор степеней первого вида.Теорема 2. Пусть сверхстройное дерево является объединением k > 2 цепей длины/1,...,/& , где хотя бы одна цепь имеет длину больше единицы. Минимальное вершинное1-расширение этого дерева будет отличаться на k + 1 дополнительных ребери иметь вектор степеней ((k + 1)2, 2m+k) тогда и только тогда, когдаVi G {1,..., k} (li > 1 ^ Vj G {2, ...,li} 3p (1 ^ p ^ к & (lp = j - 1 V lp = li - j ))).Минимальное вершинное 1-расширение из теоремы 2 строится следующим образом:к дереву T добавляется вершина, соединяется ребрами со всеми листьями и с корневойвершиной.Среди 67 сверхстройных деревьев с числом вершин до 10 и имеющих минимальновозможное число дополнительных ребер к + 1 только 3 не подпадают под теорему 2.В частности, все сверхстройные деревья с числом вершин до 7 имеют минимальноевершинное 1-расширение вида, указанного в теореме 2. Самые малые по числу вершинсверхстройные деревья, которые имеют минимальные вершинные 1-расширения,отличные от вида из теоремы 2, - это 8-вершинные сверхстройные деревья (1,1, 5) и(2, 2, 3). Всего 13 сверхстройных деревьев с числом вершин до 10 не подпадают поддействие теоремы 2.Удалось описать одно семейство сверхстройных деревьев, у которых есть минимальноевершинное 1-расширение вида (к + 1, к, 3, 2m+k-1).Теорема 3. Пусть сверхстройное дерево T является объединением к (к > 2) цепейc длинами не более 2, среди которых есть хотя бы одна цепь длины 1 и хотя бы однацепь длины 2. Тогда граф G*, полученный из дерева T добавлением вершины и соединениемее со всеми листьями и любой вершиной степени 2, является минимальнымвершинным 1-расширением дерева T .Непосредственной проверкой можно убедиться, что графы из теоремы 3 подпадаютпод действие теоремы 2 и, таким образом, имеют по крайней мере два минимальныхвершинных 1-расширения. Оказывается, что имеет место более сильное утверждение.Теорема 4. Пусть сверхстройное дерево T является объединением к (к > 3) цепейc длинами не более 2, среди которых есть хотя бы одна цепь длины 1 и хотя бы однацепь длины 2. Тогда дерево T имеет в точности два неизоморфных минимальныхвершинных 1-расширения, которые строятся по схемам из теорем 2 и 3.

Скачать электронную версию публикации