The upper and lower bounds for the number of additional arcs in a minimal edge 1-exten-sion of oriented cycle.pdf Введение Рассмотрим неориентированные и ориентированные графы, основные определения даются согласно работам [1-3]. Неориентированным циклом (далее - просто циклом) Cn называется n-вершинный граф, состоящий из единственного цикла, содержащего все вершины. Очевидно, что число вершин любого цикла n 3. Цикл Cn является связным однородным графом порядка 2. Для нас представляют интерес ориентации цикла Cn, которые получаются заменой каждого ребра цикла на дугу. Простые циклические пути в ориентированном графе называются контурами. Особым случаем ориентации цикла Cn является контур Cn, то есть ориентированный граф, состоящий из единственного контура, содержащего все вершины. В контуре Cn все вершины имеют степени исхода и захода, равные 1. Граф G* = (V*, а*) называется минимальным вершинным k-расширением (МВ-kP) n-вершинного графа G = (V, а), если выполняются следующие условия: 1) граф G* является вершинным k-расширением графа G, то есть G вкладывается в каждый подграф графа G*, получающийся удалением любых его k вершин; 2) граф G* содержит n + k вершин, то есть |V*| = |V| + k; 3) а* имеет минимальную мощность при выполнении условий 1 и 2. Понятие минимального вершинного k-расширения появилось в работе [1] как модель для исследования отказоустойчивости элементов дискретных систем. Позднее в [2] введена модель для исследования отказов связей между элементами. Граф G* = (V*,а*) называется минимальным рёберным k-расширением (МР-кР) n-вершинного графа G = (V, а), если выполняются следующие условия: 1) граф G* является рёберным k-расширением графа G, то есть G вкладывается в каждый граф, получающийся из G* удалением любых его k рёбер (дуг); 2) граф G* содержит n вершин, то есть |V*| = |V|; 3) а* имеет минимальную мощность при выполнении условий 1 и 2. Задача поиска минимального вершинного или рёберного k-расширения для произвольного графа является вычислительно сложной [4], и в общем виде решение удалось получить лишь для некоторых классов графов. Обзор основных результатов можно найти в [3]. В работе [2] предлагаются схемы построения минимальных рёберных 1-расширений для циклов. Теорема 1. Графы, представленные на рис. 1, являются минимальными рёберными 1-расширениями для цикла Cn при чётном числе вершин (а) и нечётном числе вершин (б). а Рис. 1. МР-1Р цикла Cn из теоремы 1 Заметим, что число дополнительных рёбер в этих расширениях равно |"n/2"|. В [3] предлагаются другие схемы построения минимальных рёберных 1-расширений циклов и доказывается, что при n > 5 построенные по ним расширения неизоморфны расширениям из теоремы 1. Теорема 2. Графы, представленные на рис. 2, являются минимальными рёберными 1-расширениями для цикла Cn при чётном числе вершин (а) и нечётном числе вершин (б ); при n > 5 они неизоморфны расширениям, построенным по теореме 1. а Рис. 2. МР-1Р цикла Cn из теоремы 2 1. Ориентации циклов Рассмотрим ориентации цикла. Ранее были получены оценки для числа дополнительных дуг в МВ-1Р ориентации цикла, а также схемы построения для двух ориентаций цикла, на которых достигается нижняя оценка. Напомним, что расширение (вершинное или рёберное) G* графа G называется неприводимым, если никакая его собственная часть не является расширением (вершинным или рёберным) графа G. Заметим, что неориентированный цикл можно рассматривать как ориентированный граф, в котором каждое ребро является парой встречных дуг. Теорема 3. Цикл Cn является неприводимым рёберным 1-расширением для произвольной ориентации Cn цикла Cn. Теорема 1 даёт оценку сверху для числа дополнительных дуг в минимальном рёберном 1-расширении ориентации цикла. Следующая теорема показывает, что оценка является достижимой. Теорема 4. Цикл Cn является минимальным рёберным 1-расширением контура -п. Отметим, что в общем случае цикл Cn является не единственным минимальным рёберным 1-расширением контура C n. Для получения нижней оценки заметим, что в цикле каждая вершина имеет степень 2, соответственно в ориентации цикла в каждой вершине будет две дуги (входящие или исходящие). Тогда в минимальном рёберном 1-расширении в каждой вершине будет не менее трёх дуг [3]. Это даёт нижнюю оценку числа дополнительных дуг |"n/2"|. Получаем итоговую оценку: Теорема 5. Для числа дополнительных дуг минимального рёберного 1-расширения любой ориентации C n цикла C n справедливо следующее неравенство: Pn/2^ < ec(-п) < n. Далее представлены схемы построения минимальных рёберных 1-расширений для некоторых ориентаций циклов, которые показывают, что нижняя оценка также является достижимой. С этой целью рассмотрим возможность ориентации минимальных рёберных 1-расширений циклов из теоремы 2. 2. Циклы с чётным числом вершин Рассмотрим цикл Cn с чётным числом вершин, который ориентируем по схеме «сток - источник». Обозначим такую ориентацию CSTn. Очевидно, что в минимальном рёберном 1-расширении орграфа CSTn все вершины, в которых есть три дуги, могут быть также только источниками или стоками. По этой причине минимальное рёберное 1-расширение для CSTn не может быть получено никакой ориентацией минимального рёберного 1-расширения цикла из теоремы 1. Можно заметить, что это расширение имеет два цикла длины 3. Любая его ориентация приведёт к тому, что появится вершина, не являющаяся ни стоком, ни источником. Граф из теоремы 2 не имеет циклов длины 3 и для него подобную ориентацию построить возможно. Теорема 6. Граф, представленный на рис. 3, является минимальным рёберным 1-расширением для ориентации CSTn при n = 4k + 2. Рис. 3. МР-1Р ориентации цикла из теоремы 6 Пунктирными линиями на рис. 3 показаны дополнительные дуги. Заметим, что в ориентации направление дуг выбирается естественным образом, чтобы сохранить источники и стоки. Очевидно, что такая ориентация невозможна при n = 4k, так как в этом случае вершины в противоположных углах прямоугольника будут иметь одинаковый тип (сток - сток или источник - источник). Любая ориентация диагонали не сможет сохранить источники и стоки. 3. Циклы с нечётным числом вершин Рассмотрим цикл Cn с нечётным числом вершин. Его нельзя ориентировать по схеме «сток - источник», поэтому предложим другую ориентацию. В одной вершине ориентируем рёбра так, чтобы одно ребро было исходящим, а другое - входящим. Остальные вершины ориентируем по схеме «сток - источник». Обозначим такую ориентацию CSTNn. Для неё можно ориентировать минимальные рёберные 1-расширения как из теоремы 1, так и из теоремы 2. Теорема 7. Граф, представленный на рис. 4, является минимальным рёберным 1-расширением для ориентации CSTNn. Рис. 4. МР-1Р ориентации цикла из теоремы 7

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