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

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