Minimal edge extensions of special type palm trees.pdf Ф. Харари и Дж. Хейз в работе [1] рассматривают граф как модель некоторой технической системы. Вершины графа — её элементы, а ребра — связи между ними. Отказ связи системы рассматривается как удаление соответствующего этой связи ребра. При такой интерпретации минимальное рёберное к-расширение графа, моделирующего некоторую систему Е, является моделью оптимальной рёберной к-отказоустойчивой реализации системы Е. Задача нахождения минимального рёберного расширения произвольного графа является NP-полной [2], поэтому представляет интерес нахождение классов графов, для которых можно построить минимальное рёберное расширение аналитически. Определение 1. Назовём граф G* рёберным к-расширением графа G, если G вкладывается в каждый граф, получающийся из G* удалением любых его к ребер. Определение 2. Граф G* = (V*,а*) называется минимальным рёберным к-рас-ширением графа G = (V, а), если выполняются следующие условия: 1) G* является рёберным к-расширением G; 2) |V*| = |V|; 3) а* имеет минимальную мощность при выполнении условий 1 и 2. Определение 3. Сверхстройным деревом называется корневое дерево, где степень всех вершин, кроме корня, не превосходит 2, а степень корня более 2. Альтернативное определение: Граф G называется сверхстройным деревом, если он является объединением s > 2 цепей P1,..., Ps с общей концевой вершиной. Определение 4. Назовем сверхстройное дерево p-листной пальмой высот,ы r, если оно образовано объединением s > 2 цепей P1,..., Ps с общей концевой вершиной, причём длина цепи P1 равна r, а длины остальных цепей равны 1. Определение 5. Назовем рогатым циклом длины n с к рогами граф, полученный из n-звенного цикла и к трёхзвенных циклов таким образом, что каждый из трёхзвенных циклов имеет ровно одно общее ребро с n-звенным циклом и ни один из трёхзвенных циклов не имеет общих рёбер с другими трёхзвенными циклами. При этом назовём n-звенный цикл телом рогатого цикла, а трёхзвенные циклы — его рогами. Определение 6. Назовём разреженностью рогатого цикла длину максимального пути между вершинами, принадлежащими разным рогам, проходящего по рёбрам, не принадлежащим ни одному из рогов. На рис. 1 показаны рогатый цикл длины 6 с тремя рогами и разреженностью 2 (а) и рогатый цикл длины 8 с двумя рогами и разреженностью 3 (б). Рис. 1. Примеры рогатых циклов Теорема 1. Пусть граф G — двулистная пальма высоты n, n > 3. Тогда рогатый 'n — 4" + 2, длиной n1 = n — p + 3 и разреженностью 6 меньше 5 является минимальным рёберным 1-расширением графа G.

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