Building edge extensions of star-like trees.pdf Для минимальных вершинных 1-расширений графов существуют хорошие верхние и нижние оценки для количества дополнительных рёбер. Так, например, тривиальное вершинное 1-расширение для произвольного графа может выступать в качестве верхней оценки. Для рёберных же расширений произвольного графа в качестве верхней оценки можно взять лишь полный граф, учитывая при этом, что в общем случае не для всех графов существуют рёберные расширения. В [1] рассмотрены вопросы, связанные с нижней оценкой числа дополнительных рёбер минимального рёберного 1-расширения произвольного сверхстройного дерева. В данной работе рассматривается верхняя оценка. Графом (неориентированным) называется пара G = (V, а), где V - конечное множество вершин, а а - симметричное и антирефлексивное бинарное отношение на V (множество рёбер). Определения в основном даются по работе [2]. Назовём граф G* рёберным k-расширением графа G, если граф G вложим в каждый граф, получающийся из G* удалением любых его k рёбер. Граф G* = (V*,а*) называется минимальным рёберным k-расширением графа G = (V, а), если выполняются следующие условия: 1) граф G* является рёберным k-расширением G; 2) |V*| = |V|; 3) а* имеет минимальную мощность при выполнении условий 1 и 2. Сверхстройным деревом называется корневое дерево, где степень всех вершин, кроме корня, не превосходит 2, а степень корня более 2. Будем задавать сверхстройное дерево с помощью вектора (а1,..., as), где ai - количество цепей длины i, при этом s -длина максимальной цепи. Теорема 1. Пусть граф G является объединением s (s > 2) цепей длин m1, ..., ms с общей концевой вершиной, и это сверхстройное дерево задаётся вектором (k, 0, а3,..., at), k = 0. Тогда существует граф G* -рёберное 1-расширение графа G с количеством дополнительных рёбер F, вычисляемым по формуле F = k + £ (m - 1). i=1 Теорема 2. Пусть граф G является объединением s (s > 2) цепей длин m1, ... , ms с общей концевой вершиной и не все m1,..., ms равны 1. Назовём ребро цепи Pi проблемным, если при его удалении цепь Pi разбивается на две цепи длин ki и /i (ki + Zi + 1 = mi), причём среди длин m1,... , ms нет ни ki, ни li, и ki = 0, li = 0. Назовём началом проблемного ребра вершину, инцидентную этому ребру, находящуюся ближе к корневой вершине. Тогда граф G*, построенный из графа G путём соединения каждой вершины степени 1 из цепи длины больше 1 со всеми вершинами степени 1 других цепей, корневой вершиной и началами всех проблемных рёбер цепи, которой принадлежит эта вершина, является рёберным 1-расширением графа G (рис. 1). О О Рис. 1. Пример для схемы из теоремы 2

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