Upper and lower bounds of the number of additional arcs in a minimal edge 1-extension of oriented path.pdf Граф G* = (V*, а*) называется минимальным вершинным к-расширением (МВ-кР) n-вершинного графа G = (V, а), если выполняются следующие условия: 1) граф G* является вершинным k-расширением графа G, то есть G вкладывается в каждый подграф графа G*, получающийся удалением любых его к вершин; 2) граф G* содержит n + к вершин, то есть |V* | = |V| + к; 3) а* имеет минимальную мощность при выполнении условий 1 и 2. Понятие минимального вершинного к-расширения появилось в [1] как модель для исследования отказоустойчивости элементов дискретных систем. Позднее в работе [2] была введена модель для исследования отказов связей между элементами. Граф G* = (V*,а*) называется минимальным рёберным к-расширением (МР-кР) n-вершинного графа G = (V, а), если выполняются следующие условия: 1) граф G* является рёберным к-расширением графа G, то есть G вкладывается в каждый граф, получающийся из G* удалением любых его к рёбер (дуг); 2) граф G* содержит n вершин, то есть |V*| = |V|; 3) а* имеет минимальную мощность при выполнении условий 1 и 2. В [1] доказано, что МВ-1Р n-вершинной цепи является (n + 1)-вершинный цикл, в [2] доказано, что МР-1Р n-вершинной цепи является n-вершинный цикл. Легко показать [3], что эти расширения являются единственными с точностью до изоморфизма. Задача поиска минимального вершинного или рёберного k-расширения для произвольного графа является вычислительно сложной [4], и в общем виде решение удалось получить лишь для некоторых классов графов. Обзор основных результатов можно найти в [3]. Рассмотрим ориентации цепи. Очевидно, что гамильтонова цепь имеет единственное с точностью до изоморфизма МР-1Р - контур с тем же числом вершин. Другой интересной ориентацией является орцепь, состоящая только из источников и стоков, МР-1Р которой при чётном числе вершин является ориентация цикла, состоящая только из источников и стоков. Теорема 1. Среди всех ориентаций цепей при чётном числе вершин МР-1Р с одной дополнительной дугой имеют только гамильтоновы цепи и цепи, состоящие только из источников и стоков. Среди всех ориентаций цепей при нечётном числе вершин только гамильтоновы цепи имеют МР-1Р с одной дополнительной дугой. Теорема 2. Не существует ориентаций цепей с числом вершин n > 5, таких, что МР-1Р имеет две дополнительных дуги. Общих схем, которые бы позволили построить МР-1Р для каких-либо ориентаций цепей Pn, отличных от гамильтоновой и цепи, состоящей из стоков и источников, пока получить не удаётся. В связи с этим большой интерес представляет оценка числа дополнительных дуг МР-1Р. Для МВ-1Р ориентаций цепи удалось получить некоторые такие оценки [5,6]. В данной работе исследуется случай рёберных расширений. Обозначим число дополнительных дуг МР-1Р графа G через ec(G). Тогда оценка из последней теоремы может быть записана следующим образом: Vn > 5 (3 ^ ec(Pra)). Полученный результат удалось улучшить. Очевидно, что концевая вершина ориентации цепи может быть или источником, или стоком. Будем говорить, что концевые вершины цепи одного типа, если они одновременно являются источниками или стоками. В противном случае будем говорить, что концевые вершины имеют разный тип. Рёберное 1-расширение графа G называется неприводимым, если никакая его собственная часть не является рёберным 1-расширением графа G. Заметим достаточно очевидный факт, который можно использовать для получения верхней оценки числа дополнительных дуг: Теорема 3. Неориентированный цикл Cn при n > 2 является неприводимым рёберным 1-расширением для любой ориентации цепи Pn, отличной от гамильтоновой и от ориентации, состоящей из источников и стоков при чётном числе вершин. В неориентированном цикле подразумевается, что ребро представляет собой пару встречных дуг. Из теоремы получается оценка ec(Pra) ^ n + 1. Теорема 4. Число ec(Pn) дополнительных дуг МР-1Р ориентации цепи Pn, имеющей концы разного типа и отличной от гамильтоновой и от ориентации, состоящей из чередующихся источников и стоков, удовлетворяет следующим условиям: n 6 + 1 ^ ec(Pra) ^ n + 1. Теорема 5. Число дополнительных дуг МР-1Р ориентации цепи Pn, имеющей концы одинакового типа, удовлетворяет следующим условиям: n 4+1 ^ ec(Pn) ^ n + 1.

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