On minimal edge 1-extensions of two special form trees.pdf Ациклический связный граф называется деревом. Дерево называется сверхстрой-ным, если все его вершины, кроме корня и листьев, имеют степень 2. Сверхстройноедерево можно рассматривать как объединение k цепей P^,..., P^fc с общей концевойвершиной. Для однозначного задания сверхстройного дерева достаточно указать дли-ны этих цепей: (Zl - 1,... , Ik - 1).Задача описания минимальных реберных k-расширений для произвольного гра-фа является вычислительно сложной [1], однако среди деревьев есть представителинекоторых хорошо известных семейств графов, для которых известны аналитическиерешения. Например, цепь Pn является частым случаем дерева.Теорема 1 [2]. Единственное минимальное реберное 1-расширение цепи Pn естьцикл Cn.Звезда является частным случаем сверхстройного дерева (звезда - сверхстройноедерево, в котором нет вершин степени 2).Теорема 2 [3]. Минимальное реберное 1-расширение звезды KL,k единственнос точностью до изоморфизма и получается соединением двух листьев звезды со всемиостальными листьями звезды и между собой.Помимо этих двух результатов, на основе проведенного вычислительного экспе-римента, результаты которого были частично описаны в [4], удалось выделить двасемейства деревьев, для которых также возможно аналитически построить минималь-ные реберные 1-расширения. В работе [5] рассматривались деревья, которые представ-ляют собой одинаковые звезды с соединенными центрами. Удалось получить новыйрезультат для деревьев подобного вида.Теорема 3. Пусть граф G = (V, а) состоит из двух звезд с соединенными цен-трами (рис. 1). Построим граф G* = (V*,а*) из G по следующей схеме: выберем двепроизвольные вершины степени 1, расстояние между которыми равно 3; каждую извыбранных вершин соединим со всеми вершинами степени 1, расстояние до которыхот неё равно 3. Полученный граф G* является минимальным реберным 1-расширениемграфа G.Теорема 4. Пусть граф G = (V, а) -сверхстройное дерево, являющееся объеди-нением k цепей длины 2 и n > 1 цепей длины 1 (рис. 2). Построим граф G* = (V*, а*)из G по следующей схеме: соединим с корнем все листья, расстояние от которых докорня равно 2; если n четное, то соединим попарно между собой все листья, рассто-яние от которых до корня равно 1; если n нечетное, то соединим один из листьев,расстояние от которого до корня равно 1, с двумя такими же листьями, а остальныелистья, расстояние от которых до корня равно 1, кроме трёх уже задействованных, со-единим попарно между собой. Полученный граф G* является минимальным реберным1-расширением графа G.Рис. 1. Дерево G и его минимальное реберное 1-расширениеРис. 2. Сверхстройное дерево G и его минимальное реберное 1-расширение

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