On minimal edge k-extensions of oriented stars.pdf Звездой называется полный двудольный граф K 1n, в котором одна вершина смежнас n попарно несмежными вершинами. Направленной звездой назовём диграф,симметризация которого является звездой, то есть направленный граф, получающийсяиз неориентированной звезды заменой каждого ребра дугой. Направленную звездубудем обозначать Zm,n, где m и n - число вершин с одной исходящей и одной входящейдугой соответственно. Вершину, являющуюся концом или началом каждой дугизвезды, будем называть центральной.Граф G* = (V *,а*) называется минимальным реберным k -расширением (к - натуральное)n-вершинного графа G = (V, а), если выполняются следующие условия:1) G* является реберным k-расширением G, то есть граф G вкладывается в каждыйподграф графа G*, получающийся удалением любых его к ребер;2) G* содержит n вершин, то есть |V*| = |V|;3) а* имеет минимальную мощность при выполнении условий 1 и 2.Понятие минимального k-расширения введено на основе конструкции оптимальнойk-отказоустойчивой реализации. Понятие реберной отказоустойчивости было предложеноХейзом совместно с Харари в работе [1]. Было доказано, что задача проверкиk-расширения для произвольного графа является NP-полной (см. [2]).В работе [3] дается полное описание минимальных вершинных и реберных k-расширенийнеориентированных звезд. Удалось получить полное описание минимальныхвершинных k-расширений направленных звезд (см. [4]). Основной результат даннойработы устанавливает для направленных звезд вид их минимальных реберных k-расширений.Обозначим через ZKmn,p семейство графов, получающихся из звезды Zm,n добавлениемp - 1 центральной вершины, соединением их между собой и центральной вершинойзвезды Zm,n парами встречных дуг. Каждая из добавленных центральных вершинсоединяется m входящими и n исходящими дугами с произвольными источниками истоками звезды Zmn. По описанной схеме для заданной звезды в общем случае можетбыть построено много графов.Теорема 1. Относительно минимальных реберных 1-расширений направленныхзвезд Zmn справедливо следующее:1) при m = n = 1 звезда Zi,i имеет единственное с точностью до изоморфизмаминимальное реберное 1-расширение, которым является циклическая тройка;2) при mn > 1 звезда Zmn имеет минимальныереберные 1-расширения видаKi, m+n и графы, построенные по схемам ZKm-1n2 и ZKmn-12;3) при m > 0, n = 0 звезда Zm,n имеет минимальные реберные 1-расширения видаZ K m-1,n,2;4) при m = 0, n > 0 звезда Zmn имеет минимальные реберные 1-расширения видаZK m,n-1,2;5) при m = 2, n = 1 звезда Z2,1 имеет еще одно минимальное реберное 1-расширение- турнир, получающийся из циклической тройки добавлением однойвершины и дуг от нее во все остальные вершины;6) при m = 2, n = 1 звезда Z21 имеет еще одно минимальное реберное 1-расширение- турнир, получающийся из циклической тройки добавлением однойвершины и дуг в нее из всех остальных вершин.Для общего случая результат формулируется следующим образом.Теорема 2. Относительно минимальных реберных k-расширений направленныхзвезд Zm,n при k > 1 справедливо следующее:1) при m = n = k звезда Zm,n имеет минимальным реберным k-расширениемлюбой регулярный (2k + 1)-вершинный турнир и только их;2) при m = n + 1 = k звезда Zm+1,m имеет минимальным реберным k-расширениемлюбой (2k + 2)-вершинный турнир, который получается из регулярного (2k + 1)-вершинного турнира добавлением дополнительной вершины-источника;3) при m + 1 = n = k звезда Zm,m+1 имеет минимальным реберным k-расширениемлюбой (2k + 2)-вершинный турнир, который получается из регулярного (2k + 1)-вершинного турнира добавлением дополнительной вершины-стока;4) кроме случая m = n = k звезда Zmn при k ^ m + n имеет минимальнымреберным k-расширением графы вида ZKmi ni,k+1, гдеm1 + n1 = m + n - k;max{0, m - k} ^ m1 ^ m;max{0, n - k} ^ n1 ^ m.При k > m + n звезда Zm,n не имеет минимальных реберных k-расширений.

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