Number estimation for additional arcs in a minimal 1-vertex extension of tournament.pdf Граф G* = (V*, а*) называется минимальным вершинным k-расширением (k - натуральное, в данной работе k = 1) n-вершинного графа G = (V,а), если выполняются следующие условия: 1) G* является вершинным k-расширением G, то есть граф G вкладывается в каждый подграф графа G*, получающийся удалением любых его k вершин; 2) G* содержит n + k вершин, то есть |V*| = |V| + k; 3) а* имеет минимальную мощность при выполнении условий 1 и 2. Понятие минимального вершинного k-расширения введено на основе понятия оптимальной k-отказоустойчивой реализации, которое предложено Хейзом в [1] при построении модели отказоустойчивости, основанной на графах. Основные определения используются согласно [2]. Через ec(G) обозначим количество дополнительных рёбер (дуг) в минимальном вершинном 1-расширении графа G по сравнению с самим графом G. В работе [3] доказываются некоторые результаты о связи между минимальными вершинными k-расширениями неориентированных и ориентированных графов. Лемма. Пусть орграф G* есть минимальное вершинное k-расширение орграфа G. Тогда симметризация орграфа G* является вершинным k-расширением симметризации орграфа G. Следствие. Число дополнительных дуг минимального вершинного k-расширения орграфа G не меньше числа дополнительных рёбер минимального вершинного k-рас-ширения симметризации орграфа G. Легко убедиться, что единственным минимальным вершинным 1-расширением графа Kn является граф Kn+1, причём ec(Kn) = n. Нижняя оценка Граф G* = (V*,а*) называется точным вершинным k-расширением n-вершинного графа G = (V,а), если граф G изоморфен каждому подграфу графа G*, получающемуся из графа G* путём удаления любых его k вершин и всех связанных с ними дуг (рёбер). Можно заметить, что минимальное вершинное 1-расширение графа Kn является и его точным вершинным 1-расширением. Если ориентировать каждое ребро полного графа Kn, то получим некоторый турнир ^n. Согласно следствию можно сделать следующий вывод: ec(^n) ^ n, то есть число дополнительных дуг минимального вершинного 1-расширения произвольного турнира -n не может быть меньше n, причём в этом случае минимальное вершинное 1-расширение является и точным вершинным 1-расширением. Такие турниры существуют, например транзитивные, вершинно-симметрические и некоторые другие [4], и относительно хорошо изучены. Большинство турниров не имеют точного вершинного 1-расширения, поэтому для них ec(-n) > n. Удалось доказать, что не существует турниров с числом дополнительных дуг в минимальном вершинном 1-расширении равном n +1. Теорема 1. Если минимальное вершинное 1-расширение турнира Tn не является его точным вершинным 1-расширением, то справедливо неравенство ec(^n) > n +1. Данная оценка является достижимой. Теорема 2. Турнир, получающийся из транзитивного заменой ориентации одной дуги из источника в сток, имеет минимальное вершинное 1-расширение с (n + 2) дополнительными дугами. Верхняя оценка Граф Gt = (Vt,at) называется тривиальным k-расширением графа G = (V, а), если Gt получается из G добавлением k вершин, соединением их со всеми вершинами графа G и друг с другом. Граф Gt можно представить как соединение G и полного графа Kk = (Vk, ak): Gt = (Vt,at) = (V U Vk,a U ak U V x Vk U Vk x V). Очевидно, что тривиальное k-расширение графа является и его вершинным k-расширением, что позволяет получить общую верхнюю оценку для числа дополнительных дуг произвольного орграфа: ec (^n) ^ 2n. Оказалось, что для турниров эта оценка является достижимой. Теорема 3. Турнир с числом вершин n = 4k + 2, все вершины которого имеют степени (3k + 1, k) или (k, 3k + 1), имеет минимальное вершинное 1-расширение с 2n дополнительными дугами. Таким образом, получается общий результат. Теорема 4. Если минимальное вершинное 1-расширение турнира не является его точным вершинным 1-расширением, то справедливо неравенство n + 2 ^ ec(^n) ^ 2n, причём верхняя и нижняя оценки являются достижимыми.

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