«ГРАФОВЫЕ МОДЕЛИ ОТКАЗОУСТОЙЧИВОСТИ ...»

Граф Gnp1 имеет в точности одну полную вершину, удаление которой приводит к однородному подграфу Rn-1,n-3. Следовательно, вложение возможно, только если граф G также имеет в точности одну полную вершину, причем граф G будет частью граф Gnp1 тогда и только тогда, когда его подграф G1, получающийся из G удалением полной вершины, является частью однородного графа Rn-1,n-3. Рассмотрим дополнения графов G1 и Rn-1,n-3: G1' и Rn-1, соответственно. Граф G1 допускает вложение в Rn-1,n-3 тогда и только тогда, когда дополнение графа Rn-1,n-3 – однородный граф Rn-1,1 допускает вложение в дополнение графа G1 – граф G1'. Однако граф Rn-1,1 вложим в G1' тогда и только тогда, когда в графе G1' есть совершенное паросочетание. С помощью одного из указанных выше алгоритмов это можно проверить за O(n5/2) или O(mn1/2) действий.

Построение графа Rn + k, n + k 2 = O2 +... + O2 на шагах 7 и 8 потребует порядка O(n2 + k2) действий.

Таким образом, теоретическая сложность алгоритма построения минимальных вершинных k-расширений для n-вершинного предполного графа с m ребрами определяется в основном сложностью алгоритма проверки наличия совершенного паросочетания в графе и составляет O(n5/2 + nk + k2) или O(mn1/2 + nk + k2).

Следствие 1. Число дополнительных ребер минимального вершинного k-расширения предполного графа G есть Gnp1 и отличается от него на m ребер.

Доказательство. По теореме 2.5.2, если предполный n-вершинный граф G не является частью графа Gnp1, тогда G имеет единственное минимальное вершинное k-расширение – тривиальное k-расширение. Очевидно, что тривиальное k-расширение является тривиальным 1-расширением тривиального (k – 1)-расширения. Поскольку каждое последующее тривиальное 1расширение получается добавлением одной полной вершины, то число дополнительных ребер в тривиальном k-расширении есть Пусть предполный n-вершинный граф G является частью графа Gnp1 и отличается от него на m ребер. Тогда по теореме 2.5.2 любое его минимальное вершинное k-расширение при k < 2m – 1 является тривиальным k-расширением и число ребер определяется по предыдущему случаю, то есть nk +. Очевидно, формула остается справедливой и при k = 2m – 1, хотя граф G имеет уже два неизоморфных минимальных вершинных k-расширения. Рассмотрим k 2m. В зависимости от четности или нечетности k граф G имеет минимальным вершинным k-расширением либо граф G(n+k)p1, либо граф R(n+k),(n+k-2). Можно заметить, что если тривиальное k-расширение отличается от тривиального (k – 1)-расширения на n + k – 1 ребро, то есть при увеличении k на единицу разница между ними увеличивается также на единицу, то при k 2m при увеличении на единицу k число дополнительных ребер минимального вершинного k-расширения возрастает на единицу только при четном k (см. пункт 2а теоремы 2.5.2). То есть с каждым четным k после k = 2m разница в числе ребер между минимальным вершинным k-расширением и тривиальным k-расширением графа G увеличивается на единицу.

Запишем эту идею:

Объединяя случаи для k < 2m и k 2m, получаем искомую формулу.

Следствие 2. Для любого n-вершинного графа Gn и r > 1 справедливо утверждение:

Доказательство. Пусть G = K r + Gn. При r > 1 граф G имеет не менее r полных вершин, следовательно, по теореме 2.5.2 граф G имеет единственное минимальное вершинное k-расширение G*k вида G*k = G + K k. Откуда получаем В терминах «почти все» результаты относительно предполных графов могут быть сформулированы следующим образом:

Почти все предполные графы имеют единственное с точностью до изоморфизма минимальное вершинное (Т-неприводимое) k-расширение, которым является тривиальное k-расширение.

2.5.3. Гипотеза о соединении В работах (Абросимов, 2000, в, г) исследовалась связь конструкции вершинного расширения и алгебраических операций над графами. В частности, имеет место такое интересное утверждение, связывающее операции дополнения, соединения и конструкцию вершинного 1-расширения:

ТЕОРЕМА 2.5.3. Пусть G – граф, обладающий свойством дополнительности 1-расширения, а G* – его точное вершинное 1-расширение. Тогда граф G+ = G + G* +... + G* = G + (G* ) m также обладает свойством дополнительности 1-расширения, причем его точное вершинное 1-расширение имеет вид G+ = G* + G * +... + G * = (G* ) m +1 :

Доказательство. Пусть n-вершинный граф G обладает свойством дополнительности 1-расширения, граф G* – его точное вершинное 1-расширение, а граф G+ получается соединением графа G и m графов G*.

Заметим, что максимальный подграф графа G+ = G* + G* +... + G* есть граф G+ = G + G* +... + G*, поэтому граф G+ является точным вершинным 1расширением графа G+, а по теореме 2.1.18 и единственным его минимальным вершинным 1-расширением, что доказывает корректность формулы в условии теоремы.

Следующий результат, являющийся усилением предыдущей теоремы, связывает операции соединения и дополнения с конструкцией минимального вершинного 1-расширения.

ТЕОРЕМА 2.5.4. Граф G+ = G + G* +... + G* = G + (G* ) m, где G – произвольный граф, а G* – минимальное вершинное 1-расширение графа G, тогда и только тогда обладает свойством дополнительности 1-расширения, когда G* является точным вершинным 1-расширением графа G. При этом граф G+ = G* + G * +... + G * = (G* ) m +1 является точным вершинным 1-расширением графа G+.

Доказательство. Необходимость. Пусть G – n-вершинный граф, G* – + G * +... + G * = G + (G * ) m обладает свойством дополнительности 1-рас ширения.

Введем обозначения:

b * = min d (v ) для графов G и G соответственно.

Определим наибольшие и наименьшие степени вершин в графе G+.

Вершины, имеющие в графе G степени a и b, в графе G+ будут иметь степени a + m(n + 1) = a + mn + m и b + m(n + 1) = b + mn + m соответственно.

Вершины, имеющие в графе G* степени a* и b*, в графе G+ будут иметь степени По условию граф G+ обладает свойством дополнительности 1-расширения, тогда по теореме 2.1.12 либо граф G+ является однородным и в этом случае он является вполне несвязным или полным и то есть либо или Рассмотрим четыре случая.

1. a = a *, b = b*. Тогда из соотношения (1) получаем a = a* = b = b*, что возможно лишь тогда, когда G и G* являются вполне несвязными графами, то есть G* является точным вершинным 1-расширением графа G.

2. a = a *, b < b*. Из соотношения (1) получаем a 1 = b* 2 > b 2, откуда a > b 1, что возможно лишь при a = b. Поскольку a = a*, то согласно лемме 2.1.4 граф G содержит изолированные вершины, значит, a = b = 0 и граф G является вполне несвязным. Однако минимальное вершинное 1-расширение вполне несвязного графа является по теореме 2.1.2 также вполне несвязным графом, то есть a = a *, b < b *. Следовательно, случая 2 быть не может.

3. a < a *, b = b*. Из соотношения (1) получаем, что a = b 1. Далее a* > a = b 1 = b* 1, но поскольку a* b*, то a* = b*. Таким образом, Обозначим через n1, n 2 число вершин степени a, b графа G и степени a*, b* графа G*. Очевидно, что граф G+ имеет степенное множество {a + mn + m, b + mn + m}, причем число вершин степени a + mn + m равно нию граф G+ обладает свойством дополнительности 1-расширения, причем a + mn + m = b + mn + m 1. По теореме 2.1.15 число вершин степени Таким образом, граф G имеет степенное множество вида {b – 1, b}, число вершин степени b – 1 в точности равно b и его минимальное вершинное 1-расширение – граф G* – является однородным графом порядка b. По теореме 2.1.15 граф G обладает свойством дополнительности 1-расширения, а граф G* является его точным вершинным 1-расширением.

4. a < a *, b < b*. Этот случай возможен лишь тогда, когда G и G* являются полными графами.

Таким образом, в каждом из возможных случаев 1, 3 и 4 граф G* является точным вершинным 1-расширением графа G, что доказывает необходимость.

Достаточность следует из теоремы 2.5.3.

На основании предыдущих рассуждений представляется разумным высказать предположение:

Пусть G – произвольный граф, а G* – некоторое его минимальное вершинное 1-расширение. Тогда граф вида G + G* +... + G * = G + (G* ) m всегда имеет единственное минимальное вершинное 1-расширение, и оно может быть представлено в виде G* + G* +... + G* = (G* )m +1, то есть справедлива запись:

Однако оказалось, что ситуация является более сложной и удалось найти два контрпримера к этому предположению.

ТЕОРЕМА 2.5.5. Пусть G – граф вида Rn, n – 2, а G* – его минимальное вершинное 1-расширение. Тогда минимальное вершинное 1-расширение графа G + G* единственно с точностью до изоморфизма и имеет вид R2n + 2, 2n.

O 2 +... + O 2. По лемме 2.5.5 граф Rn, n – 2 имеет единственное минимальное вершинное 1-расширение G*, которым является его тривиальное 1-расширение:

Таким образом, граф G + G* будет иметь вид и будет являться графом вида Gnp1. По теореме 2.5.1 получаем требуемое утверждение.

ТЕОРЕМА 2.5.6. Пусть G – предполный граф вида Gnp2, а G* – его минимальное вершинное 1-расширение вида O 2 +... + O 2. Тогда граф G + G* имеет два неизоморфных минимальных вершинных 1-расширения, одно из которых имеет вид G* + G*, а второе имеет вид O 2 +... + O 2.

Доказательство. По теореме 2.5.1 граф Gnp2 имеет два неизоморфных минимальных вершинных 1-расширения: тривиальное 1-расширение и расширение вида O2 +... + O2. Если рассматривать первое минимальное вершинное 1-расширение, то утверждение предположения, как несложно заметить, будет справедливым. Мы рассматриваем соединение графа Gnp2 со вторым минимальным вершинным 1-расширением: O2 +... + O2.

Легко увидеть, что это соединение снова будет являться предполным графом вида G(2n+2)p2 и, следовательно, по теореме 2.5.1 будет иметь два неизоморфных минимальных вершинных 1-расширения. Теорема доказана.

Таким образом, в общем виде предположение является ошибочным.

Однако для большого числа графов его утверждение является справедливым, что в дополнении к предыдущим теоремам показывает и следующая ТЕОРЕМА 2.5.7. Пусть G – граф, неизоморфный графу вида Rn, n – 2, а его тривиальное 1-расширение G* является и его минимальным вершинным G + G* единственно с точностью до изоморфизма и имеет вид G * + G *, то есть справедливо соотношение:

Доказательство. Так как G* является тривиальным 1-расширением графа G, то и в G* есть хотя бы одна полная вершина. Граф также является предполным. По теореме 2.5.1, если граф G + G* не будет являться графом вида Gnp1 или Gnp2, то он будет иметь единственное минимальное вершинное 1-расширение, которым будет являться его тривиальное 1-расширение, то есть мы получим утверждение теоремы. В самом деле, тривиальное 1-расширение графа G + G* можно будет записать так:

Вспомним, что граф вида Gnp1 – это граф вида K 1 + O 2 +... + O 2, и поэтому мы должны исключить графы G изоморфные Rn, n – 2.

Граф вида Gnp2 – это граф вида K 1 + (O 2 +... + O 2 e ), где e – некоторое ребро. В нашем случае граф G + G* не может быть изоморфен графу Gnp2, так как, исключив из рассмотрения полную вершину, мы должны подобрать граф G таким образом, чтобы G + G = O 2 +... + O 2 e, что невозможно. Теорема доказана.

Много ли графов попадает под действие доказанной теоремы? Как мы докажем следующим утверждением, это почти все предполные графы, но и кроме них многие графы имеют минимальное вершинное 1-расширение, которое является их тривиальным 1-расширением. Так, например, по материалам работы (Абросимов, 2000, в), для 7-вершинных графов: из 1044 графов 405 графов (из них 156 предполных) имеют минимальным вершинным 1-расширением тривиальное 1-расширение. Для 6-вершинных: 65 (34 предполных) из 156, для 5-вершинных: 10 (все предполные) из 34.

Следствие. Пусть G – произвольный предполный граф не вида Gmp2, а G* – его минимальное вершинное 1-расширение. Тогда граф вида G + G * имеет единственное минимальное вершинное 1-расширение и оно может быть представлено в виде G * + G *, то есть справедливо соотношение:

Доказательство. По теореме 2.5.1 все предполные графы, кроме графов вида Gmp1 и Gmp2, имеют минимальным вершинным 1-расширением тривиальное 1-расширение и, таким образом, попадают под условие теоремы 2.5.7. Остается рассмотреть предполные графы вида Gmp1. По следствию 4 из теоремы 2.5.1 минимальное вершинное 1-расширение графов вида Gmp1 является точным вершинным 1-расширением, и по теореме 2.5.4 получаем требуемое утверждение.

Древесные структуры являются чрезвычайно распространенными в различных практических областях. В работе (Hayes, 1976) отмечается важность задачи определения минимального вершинного 1-расширения для деревьев. В той же работе была предложена процедура построения минимального вершинного 1-расширения для одного частного случая – дерева с метками. Кван и Тойда (Kwan, Toida, 1982) предложили конструкцию минимального 2-расширения для симметричного неоднородного дерева (вершины равноудаленные от корня имеют одинаковые метки). Для звезд полное описание минимальных вершинных 1-расширений было найдено в (Farrag, Dawson, 1989). Харари и Хуррум (Harary, Khurum, 1995) предложили схему построения минимальных вершинных 1-расширений для двух частных случаев деревьев: «гусениц» и звездоподобных деревьев. М. А. Кабанов в (Кабанов, 1997) предложил процедуру построения для одного частного случая дерева n-вершинных звездных графов («колес») с отождествлением вершин таким образом, что центры колес образуют цепь. В той же работе указывается, что цепи колес могут иметь неизоморфные минимальные вершинные расширения, а также приводится соответствующий пример. В общем виде задача построения минимального вершинного k-расширения дерева (с метками или без) остается нерешенной. В работе (Dutt, Hayes, 1990) Дат и Хейз вводят понятие оптимального минимального вершинного 1-расширения» и предлагают процедуру его построения для дерева с метками или без. С. Г. Курносовой удалось описать Т-неприводимые расширения полных бинарных деревьев (Курносова, 2006). Последующие далее результаты позволяют построить минимальное вершинное 1-расширение еще для одного частного случая дерева – сверхстройного дерева.

В табл. 2.6.1 представлены минимальные вершинные 1-расширения для малых деревьев с числом вершин до 5.

2.6.1. Звезды Звезда является частным случаем предполного графа и может быть записана в виде Km + On, где On – вполне несвязный граф. В работе (Farrag, Dawson, 1989) рассматривалась отказоустойчивость систем с выделенным сервером, который связан с клиентами. Клиенты между собой не связываются. Очевидно, что графом такой системы будет являться звезда.

На основании результатов предыдущего параграфа легко получить полное описание минимальных вершинных k-расширений звезд.

ТЕОРЕМА 2.6.1. Единственным минимальным вершинным 1-расширением звездного графа является тривиальное K1 + K1,n = K2 + On.

Заметим, что звездный граф K1,n с нечетным числом вершин является частью графа Gnp1 и отличается от него на [n + n(n – 1)]/2 – n = (n2 – 2n)/2 ребер. С учетом этого из теоремы 2.5.2 следует ТЕОРЕМА 2.6.2. Относительно звездного графа K1,n справедливы следующие утверждения.

1. При нечетном n и любом натуральном k звезда K1,n имеет единственное с точностью до изоморфизма минимальное вершинное k-расширение – тривиальное k-расширение.

а) при четном k число минимальных вершинных k-расширений звезды K1,n в точности равно числу ее неизоморфных минимальных вершинных (k – 1)-расширений, причем каждое из минимальных вершинных k-расширений есть тривиальное 1-расширение соответствующего минимального вершинного (k – 1)-расширения;

б) при нечетном k выделяются три случая:

– при k < n2 – 2n звезда K1,n имеет единственное с точностью до изоморфизма минимальное вершинное k-расширение – тривиальное k-расширение;

– при k = n2 – 2n звезда K1,n имеет два с точностью до изоморфизма минимальных вершинных k-расширения: тривиальное kрасширение и граф Rn+k+1,n+k-1;

– при k > n2 – 2n звезда K1,n имеет единственное минимальное вершинное k-расширение – граф Rn+k+1,n+k-1.

2.6.2. Сверхстройные деревья дополнительных ребер. Напомним, что через ec(G, k) мы обозначали количество дополнительных ребер минимального вершинного k-расширения графа G. При k = 1 будем записывать просто ec(G):

Нижняя оценка Покажем, что минимальное вершинное 1-расширение сверхстройного ных ребер.

ТЕОРЕМА 2.6.3. Минимальное вершинное 1-расширение любого сверхстройного дерева T вида (m1,…,mk) отличается от него более чем на k дополнительных ребер:

Доказательство. Пусть T – сверхстройное дерево с вектором цепей (m1,…,mk) и k > 2. Обозначим через T* некоторое минимальное вершинное 1-расширение дерева T. По определению после удаления любой вершины из графа T* дерево T должно вкладываться в получившийся граф. Следовательно, граф T* должен содержать вершину степени k или выше и будет отличаться от дерева T не менее чем на k дополнительных ребер. Таким образом, для доказательства леммы достаточно показать, что T* не может отличаться на k дополнительных ребер.

Предположим, что это не так, и T* отличается от T на k дополнительных ребер. Так как в T есть одна вершина степени k, то в T* должно быть не менее двух вершин степени k или выше. Действительно, если бы это было не так, и в T* была бы только одна вершина v степени k или выше, то вложение дерева T в граф T* – v было бы невозможно. Рассуждая далее, убеждаемся, что в T* не может быть вершин степени меньше 2. В самом деле, если бы степень некоторой вершины v в графе T* была бы равна 1, то, удалив смежную с v вершину, мы бы получили граф с изолированной вершиной, в который дерево T вкладываться не будет. Наконец, в T* не может быть вершины степени выше k, так как удаление такой вершины привело бы к удалению более k ребер. По предположению в получившийся граф должно вкладываться дерево T, однако оно отличается от T* на k ребер.

Итак, делаем вывод, что если T* – некоторое минимальное вершинное 1-расширение дерева T, которое отличается от T на k дополнительных ребер, то T* имеет вектор степеней (k,k,2,…,2). Обозначим через v1 и v2 вершины степени k графа T*. Удаление одной из этих вершин приводит к удалению k ребер, следовательно, графы T* – v1, T* – v2 и T изоморфны. С учетом того, что степени остальных вершин графа T* равны 2, это означает, что вершины v1 и v2 соединены k цепями, длины которых есть m1 + 1, m2 + 1,…, mk + 1.

Предположим, что минимальная из длин этих цепей равна 1, то есть mk = 1. Это означает, что в T* есть вершина v, смежная и с v1, и с v2. Но тогда в графе T* – v старшая степень вершины будет k – 1 и вложение дерева T будет невозможно. Следовательно, длины всех цепей m1, …, mk должны быть больше 1, в частности, и минимальная из длин цепей mk > 1.

Пусть u – вершина цепи минимальной длины mk, смежная с вершиной v1. Рассмотрим удаление вершины u. В графе T* – u вершина v1 будет иметь степень k – 1, а d(v2) = k. Следовательно, только вершина v2 может быть образом корневой вершины дерева T при вложении. Из вершины v2 выходит k цепей, однако минимальная из них будет иметь длину mk – 1. Таким образом, дерево T не может вкладываться в граф T* – u. Полученное противоречие показывает, что дерево T не может иметь минимального вершинного 1-расширения с k дополнительными ребрами.

Итак, любое минимальное вершинное 1-расширение сверхстройного дерева T вида (m1,…,mk) при k > 2 должно отличаться от T не менее чем на k + 1 дополнительное ребро, должно иметь две вершины степени не ниже k, а степени остальных вершин не могут быть меньше 2. Звезды имеют минимальные вершинные 1-расширения как раз с таким числом дополнительных ребер. Существуют ли минимальные вершинные 1-расширения сверхстройных деревьев, кроме звезд, с числом дополнительных ребер k + 1, какими они могут быть и для каких сверхстройных деревьев это возможно?

Утверждение. Пусть T – сверхстройное n-вершинное дерево с вектором цепей (m1,…,mk) и k > 2, такое, что m1 = 2, а mk = 1. Тогда граф T*, полученный из этого дерева добавлением вершины и соединением ее со всеми листьями и корнем, является минимальным вершинным 1-расширением дерева Доказательство. Заметим, что граф T*, построенный по схеме из доказываемого утверждения, будет иметь вектор степеней ((k + 1)2,2n–1) и отличается от дерева T на k + 1 дополнительных ребер. Покажем, что граф T* является вершинным 1-расширением дерева T, тогда минимальность будет следовать из теоремы 2.6.3.

В графе T* все вершины делятся на три группы подобных вершин: вершины v1 и v2 степени k + 1, вершины смежные и с v1, и с v2 (вершины из цепей длины 1) и вершины смежные либо с v1, либо с v2 (вершины из цепей длины 2).

При удалении вершины v1 или v2 получаем граф, изоморфный T, и вложение очевидно.

При удалении вершины u, смежной и с v1, и с v2, вложение строится следующим образом: вершина v1 – корень, вершина v2 – заменяет удаленную вершину u и образовывает цепь длины 1, а остальные вершины остаются без изменений.

При удалении вершины v, смежной либо с v1, либо с v2, вложение строится следующим образом. Пусть для определенности вершина v смежна с вершиной v2, а w – другая смежная с v вершина: вершина v1 – корень, вершина v2 заменяет удаленную вершину v и образовывает цепь v1, v, w длины 2, а остальные вершины остаются без изменений.

Таким образом, существуют сверхстройные деревья с вектором степеней вида (k,2m,1k), которые имеют минимальные вершинные 1-расширения с k + 1 дополнительным ребром и вектором степеней ((k + 1)2,2m+k). На основании проведенного вычислительного эксперимента (Абросимов, Комаров, 2010, б) были проанализированы все 67 сверхстройных деревьев с количеством вершин от 4 до 10. Большинство из них (57) имеют минимальные вершинные 1-расширения с числом дополнительных ребер k + 1. Только у 9 минимальные вершинные 1-расширения имеют k + 2 дополнительных ребра (это деревья (5,1,1), (6,1,1), (3,3,2), (5,1,1,1), (6,1,1,1), (7,1,1), (5,3,1), (3,2,2,2), (5,2,2)), и у одного дерева – k + 3 (это дерево имеет вид (3,3,3)). Дерево (5,3,1) примечательно тем, что у него 117 неизоморфных минимальных вершинных 1-расширений.

Определим, какие еще вектора степеней могут быть у минимальных вершинных 1-расширений сверхстройных деревьев с k + 1 дополнительным ребром. Любой такой вектор с учетом рассмотренных выше ограничений на степени вершин минимального вершинного 1-расширения должен мажорировать вектор (k,k,2m+k), который описывает граф, отличающийся от заданного дерева на k дополнительных ребер. Это означает, что мы можем добавить две единицы к компонентам такого вектора. Таким образом, кроме вектора степеней ((k + 1)2,2m+k) возможны еще три: (k + 1,k,3,2m+k–1), (k2,32,2m+k–2) и (k2,4,2m+k–1). При k = 3 первый и последний вектора совпадают. На рис. 2.6. представлены все минимальные вершинные 1-расширения сверхстройного дерева (2,1,1) с векторами степеней трех оставшихся видов: (4,4,2,2,2), (4,3,3,2,2) и (3,3,3,3,2).

Покажем, что никакое сверхстройное дерево при k > 3 не может иметь минимальное вершинное 1-расширение с векторами степеней (k2,4,2m+k–1) и (k2,32,2m+k–2).

Вектор (k2,4,2m+k-1) (m1,…,mk) и k > 3, минимальное вершинное 1-расширение которых имеет вектор степеней вида (k2,4,2m+k–1).

Доказательство. В самом деле, предположим, что T – сверхстройное дерево вида (m1,…,mk) и k > 3, а T* – его минимальное вершинное 1-расширение с вектором степеней (k2,4,2m+k–1). Обозначим для определенности через v1 и v2 вершины степени k, а через v – вершину степени 4 в графе T*. Рассмотрим граф T* – v1. Вместе с вершиной v1 удаляется k ее ребер, поэтому граф T* – v1 допускает вложение дерева T и отличается от него на одно ребро. Добавление одного ребра к дереву T с вектором степеней (k,2m,1k) не может привести к появлению отличной от корневой вершины степени 4. При вложении дерева T в граф T* – v1 образом корневой вершины дерева T может быть или вершина v2, или при k = 4 вершина v.

Рассмотрим сначала случай k > 4. Образом корневой вершины дерева T может быть только вершина v2, а вершина v должна иметь степень меньше 4.

Это означает, что вершины v и v1 в графе T* должны быть смежны. Аналогично рассмотрев граф T* – v2, приходим к выводу, что вершины v и v2 в графе T* также должны быть смежны. Но тогда в графе T* – v все вершины будут иметь степень меньше k, и вложение дерева T будет невозможно.

Остается рассмотреть случай k = 4. Граф T* будет иметь вектор степеней (43,2m+k–1). Обозначим через v1, v2 и v3 вершины степени 4. Рассмотрим удаление одной из этих вершин, например v1. Так как T* является минимальным вершинным 1-расширением дерева T, то в графе T* – v1 должна остаться хотя бы одна вершина степени 4, следовательно, вершина v1 не может быть T* – v1, как было установлено ранее, не может остаться две вершины степени 4. Это означает, что вершина v1 должна быть смежна либо с v2, либо с v3.

Пусть для определенности вершина v1 смежна с v2 и несмежна с v3. Повторяя рассуждения для графа T* – v3, мы приходим к выводу, что вершины v2 и v должны быть смежны, то есть вершина v2 будет смежна и с v1, и c v3. Но тогда в графе T* – v2 не будет вершин степени выше 3, и вложение исходного дерева T будет невозможно.

При k = 3 вектор (k2,4,2m+k–1) совпадает с вектором (k + 1,k,3,2m+k–1), поэтому с учетом теоремы 2.6.4 вектор (k2,4,2m+k–1) не представляет интереса деревьев.

Вектор (k2,32,2m+k–2) (m1,…,mk) и k > 3, минимальное вершинное 1-расширение которых имеет вектор степеней вида (k2,32,2m+k–2).

Доказательство. В самом деле, предположим, что T – сверхстройное дерево вида (m1,…,mk) и k > 3, а T* – его минимальное вершинное 1-расширение с вектором степеней (k2,32,2m+k–2). Обозначим для определенности через v1 и v2 вершины степени k в графе T*.

Очевидно, что вершины v1 и v2 не могут быть смежными. Если бы это было так, то в графе T* – v2 не было бы вершин степени k. Аналогично в графе T* не может быть вершины, смежной одновременно с v1 и v2. Если бы была такая вершина w, то в графе T* – w вершины v1 и v2 имели бы степень k – и вложение дерева T было бы невозможно.

Рассмотрим граф T* – v2. Вместе с вершиной v2 удаляется k ее ребер, поэтому граф T* – v2 допускает вложение дерева T и отличается от него на одно ребро. Рассмотрим, какой вид может иметь граф T* – v2 (рис. 2.6.2, а).

Возможны три случая, схематично представленные на рис. 2.6.2, б–г. В графе T* – v2 может быть k, k – 1 или k – 2 вершин степени 1 и, соответственно, 2, или 0 вершин степени 3.

Рис. 2.6.2. Граф T* – v2 (а) и три случая для вектора (k2,32,2m+k–2) (б–г) Исследуем каждый случай.

Случай 1 (см. рис. 2.6.2, б). Обозначим через l1, …, lk длины цепей, выходящих из вершины степени k (это вершина v1) и заканчивающихся вершиной степени 1. Так как дерево T* вкладывается в граф T* – v2, то, не ограничивая общности, получаем, что m1 = l1 – 1, …, mk = lk – 1. Как было установлено ранее lk > 2, а следовательно, mk > 1, то есть в сверхстройном дереве T не может быть цепи длины 1.

Обозначим через v вершину, смежную с вершиной v2 в цепи длины l k (то есть в кратчайшей цепи, соединяющей вершины v1 и v2). Рассмотрим граф граф T*– v. Однако в графе T* – v вершина v2 имеет степень k – 1 и, следовательно, образом корневой вершины дерева T при вложении может быть только вершина v1. Однако из неё выходит цепь длины mk – 1, которая меньше любой цепи в дереве T. Таким образом, этот случай исключается.

Случай 2 (см. рис. 2.6.2, в). Обозначим через l1, …, lk–1 длины цепей, выходящих из вершины степени k (это по-прежнему вершина v1) и заканчивающихся вершиной степени 1. Через lk обозначим длину последней цепи, выходящей из вершины v1 и заканчивающейся вершиной, смежной с единственной вершиной степени 3. Далее, повторяя рассуждения первого случая, приходим к выводу, что и этот случай не возможен.

Случай 3 (см. рис. 2.6.2, г). Заметим, что в этом случае вершина v2 в графе T* смежна с двумя вершинами степени 3. В силу отмеченного свойства графа T* вершина v1 тогда не может быть смежна ни с одной из вершин степени 3, то есть граф T* – v1 будет попадать под случай 1, и случай 3 также должен быть исключен.

Таким образом, были рассмотрены все три возможных случая, и оказалось, что ни в одном из них граф T* не является вершинным 1-расширением дерева T.

Полученный результат означает, что если сверхстройное дерево вида (m1,…,mk) и имеет минимальное вершинное 1-расширение с вектором степеней вида (k2,32,2m+k–2), то это возможно только при k = 3. Такие сверхстройные деревья существуют, и далее одно из них будет использовано в качестве контрпримера.

Вектор ((k + 1)2,2m+k) Как мы уже убедились, существуют сверхстройные деревья, у которых минимальные вершинные 1-расширения имеют вектор степеней вида такой вид.

ТЕОРЕМА 2.6.6. Пусть T – сверхстройное дерево вида (m1,…,mk) и k > 2. Дерево T тогда и только тогда имеет минимальное вершинное ней ((k + 1)2,2m+k), когда выполняется условие Доказательство. Заметим, что если в сверхстройном дереве длины всех цепей равны 1, то есть дерево является звездой, то условие (*) выполняется. Обозначим через T сверхстройное дерево вида (m1,…,mk) и k > 2 с корневой вершиной v, а через T* – граф, получающийся добавлением к дереву T вершины и соединением ее с вершиной v и всеми листьями T. Граф T* будет иметь вектор степеней ((k + 1)2,2m+k). Обозначим две смежные вершины степени k + 1 через v1 и v2.

Необходимость. Пусть граф T* является минимальным вершинным 1расширением дерева T. Покажем, что высказывание (*) истинно. Рассмотрим одну из ветвей дерева T – цепь Pmi. Перенумеруем ее вершины: v1, vi1, …, vir.

В графе T* вершина vir соединена ребром с вершиной v2 по построению. Рассмотрим удаление некоторой вершины vij. Граф T* – vij имеет в точности две вершины степени не ниже k: v1 и v2. Следовательно, только одна из них может быть корнем дерева. Из вершины v1 выходит начальный фрагмент цепи Pmi – цепь длины j – 1. Из вершины v2 выходит концевой фрагмент цепи Pmi – цепь длины mi – j. Если v1 будет корнем дерева, изоморфного T, тогда из неё выходит цепь длины j – 1, а если v2 – то mi – j. Следовательно, цепь одной из этих длин должна существовать в дереве T. Так как цепь Pmi и ее вершина vij выбраны произвольно, то и получается формула (*).

Достаточность. Пусть высказывание (*) верно. Покажем, что T* является минимальным вершинным 1-расширением дерева T. Убедимся в том, что T* является вершинным 1-расширением. Очевидно, что T вкладывается в T* – v1 и T* – v2. Рассмотрим удаление вершины vij некоторой цепи Pmi. Не ограничивая общности, будем считать, что i = 1. Покажем, что дерево T вкладывается в T* – v1j. Граф T* – v1j имеет в точности две вершины степени не ниже k: v1 и v2. Следовательно, только одна из них может быть корнем дерева. Из вершины v1 выходит начальный фрагмент цепи Pm1 – цепь длины j – 1.

Из вершины v2 выходит концевой фрагмент цепи Pm1 – цепь длины m1 – j.

Кроме того, вершины v1 и v2 соединены k – 1 цепями, длины которых m2 + 1, …, mk +1.

Если j = 1, тогда вложение получается следующим образом: v1 – корень, цепь v1, v2, v1m,..., v12 – цепь длины m1. Остальные цепи составляются из вершин цепей Pm,..., Pm.

Если j = m1, то аналогично предыдущему случаю вложение получается так: v2 – корень, цепь v2, v1, v12,..., v1m1 – цепь длины m1. Остальные цепи составляются из вершин цепей Pm2,..., Pmk, начиная от v2, в обратном порядке.

Пусть j 1 и j m1. По условию существует цепь, например Pm, такая что ее длина равна или j – 1 или m1 – j. В первом случае v1 – корень, начало цепи Pm1 – цепь длины j – 1, а цепь v1, v21, v2( j 1), v2, v1m,..., v1( j +1) имеет длину m1. Остальные цепи составляются из вершин цепей Pm,..., Pm. Во втором случае v2 – корень, конец цепи Pm, начиная с вершины v2 – цепь длины m1 – j, а цепь v2, v2 m,..., v21, v1, v11,..., v1( j 1) имеет длину m1. Остальные цепи составляются из вершин цепей Pm2,..., Pmk, начиная от v2, в обратном порядке.

Таким образом, граф T* является вершинным 1-расширением дерева T, причем отличается от дерева T на k + 1 дополнительное ребро. По теореме 2.6.3 дерево T не может иметь расширения с k дополнительными ребрами и, 1-расширением дерева T.

З а м е ч а н и е. Условие в формулировке теоремы означает, что если мы занумеруем, начиная от корня, все вершины цепи с длиной mi сверхстройного дерева, то для каждой вершины с номером j в этой цепи должна найтись или цепь длины j – 1, или цепь длины mi – j. При этом считаем, что цепь длины 0 в дереве есть, поэтому достаточно рассмотреть все вершины цепи, кроме первой и последней. Например, рассмотрим сверхстройное дерево с вектором цепей (4,1,1). Проверим, что условие выполняется для большей цепи:

j = 2: цепь длины 1 в дереве есть;

j = 3: цепи длины 2 в дереве нет, но цепь длины 4 – 3 = 1 в дереве есть.

Таким образом, деревья (2,1,1), (3,1,1) или (4,1,1) подходят под условие теоремы. А вот сверхстройное дерево (5,1,1) – не подходит, так как для вершины v13 с номером j = 3 цепи длины 5 в дереве нет подходящей цепи длины 2 (рис. 2.6.3, а). Из 67 сверхстройных деревьев с числом вершин до 10 включительно 57 имеют минимальное вершинное 1-расширение, отличающееся на k + 1 дополнительное ребро. Из них только 3 дерева не попадают под действие теоремы 2.6.6. Это сверхстройные деревья с векторами цепей (5,1,1), (3,2,2) и (4,3,2).

По построению минимального вершинного 1-расширения с вектором степеней ((k + 1)2, 2m+k) очевидно Следствие. Пусть T – сверхстройное дерево вида (m1,…,mk) и k > 2. Если дерево T имеет минимальное вершинное 1-расширение с k + 1 дополнительным ребром и вектором степеней ((k + 1)2,2m+k), то оно имеет только одно минимальное вершинное 1-расширение с таким вектором степеней.

Вектор (k + 1,k,3,2m+k–1) Полного описания данного семейства пока не известно. Рассмотрим некоторые общие идеи построения минимального вершинного 1-расширения по данной схеме. Пусть T – сверхстройное дерево вида (m1,…,mk), а T* – минимальное вершинное 1-расширение дерева T с вектором степеней (k + 1,k,3,2m+k–1). Граф T* отличается от дерева T на k + 1 дополнительных ребер. Обозначим через u вершину степени k + 1, а через v – вершину степени k.

Рассмотрим граф T* – u. Удаление вершины u приводит к удалению k + 1 ребер, то есть в получившемся графе будет столько же ребер, сколько и в дереве T. По предположению, дерево T должно вкладываться в граф T* – u, а раз количество ребер одинаково, то граф T* – u изоморфен дереву T. Это значит, что построение графа T* можно себе представить следующим образом. Добавляется вершина u, которая соединяется с k листьями дерева T и еще одним ребром с вершиной степени 2. Таким образом, кандидатов на минимальное вершинное 1-расширение n-вершинного сверхстройного дерева T с вектором степеней (k + 1,k,3,2m+k–1) будет менее чем n – k – 1 штук (очевидно, что достаточно рассматривать по одному представителю от цепей одинаковой длины). Предположим, что последнее ребро соединяет вершину u с некоторой вершиной w степени 2 в цепи длины m1. Если назначить номера вершинам этой цепи, начиная с вершины, смежной с вершиной v, то пусть номер вершины w будет j. Тогда вершины u и v соединены k – 1 цепью длины mi + 1, i = 2,…,n. Помимо этих цепей из вершины v выходит цепь длины j, конец которой смежен с вершиной u, и кроме ребра {u,w}, вершины u и w соединены цепью длины m1 – j. Рассмотрим удаление вершины vi1, смежной с вершиной v в некоторой цепи mi. По предположению дерево T вкладывается в получившийся граф. Образом корневой вершины может быть только вершина u, которая имеет в графе T* – vi1 степень k + 1. Из вершины u в графе T* – vi1 выходит цепь длины mi – 1, следовательно, в дереве T также должна быть цепь такой длины. Проведенные рассуждения позволяют предложить одно семейство сверхстройных деревьев, представители которого имеют минимальные вершинные 1-расширения с вектором степеней (k + 1,k,3,2m+k–1).

ТЕОРЕМА 2.6.7. Пусть T – сверхстройное дерево вида (m1,…,mk) и k > 2 такое, что m i m i +1 1, i = 1,..., k 1. Тогда граф, получающийся из дерева T добавлением одной вершины, соединением ее с листьями дерева T и одной вершиной, смежной с листом, будет являться минимальным вершинным 1-расширением дерева T.

при построении графа T* добавленная вершина была соединена с предпоследней вершиной цепи ml > 1: vl ( ml 1) (см. рис. 2.6.3, б).

Убедимся, что при удалении любой вершины графа T* дерево T можно и T* – v вложение дерева T очевидно. Далее исследуем удаление произвольной вершины vij цепи длины m i. Как и ранее, j – это номер вершины в цепи, начиная от вершины, смежной с вершиной v.

Рассмотрим удаление вершины vimi цепи mi = 1, то есть вершины цепи длины 1. Вложение строится следующим образом. Ребро {vlml, u} соответствует цепи mk длины 1. Цепи ml будет соответствовать цепь u, vlml 1,..., vl1, v. Все остальные цепи, выходящие из вершины u, будут соответствовать цепям исходного дерева T. Вложение построено.

Рассмотрим удаление вершины vi1 цепи mi > 1, i l, смежной с вершиной v. Вложение строится следующим образом. Вершина u соответствует корню дерева T. Остаток цепи mi будет иметь длину mi – 1 и соответствовать цепи подходящей длины дерева T. Цепи длины mi дерева T будет соответствовать цепь длины mi – 1 с вершиной v. Все остальные цепи, выходящие из вершины u, будут соответствовать цепям исходного дерева T. Вложение построено.

Рассмотрим удаление вершины vimi цепи mi > 1, i l, смежной с вершиной u. Вложение строится следующим образом. Вершина u соответствует корню дерева T. Ребро {vlml, u} соответствует цепи mk длины 1. Цепь mk вместе с ребром {vk1,u} и остатком цепи mi от вершины v длины mi – 2 образуют цепь длины mi. Цепи ml будет соответствовать цепь u, vlml 1,..., vl1. Все остальные цепи, выходящие из вершины u, будут соответствовать цепям исходного дерева T. Вложение построено.

Рассмотрим удаление вершины vlml цепи ml, смежной с вершиной u.

Вложение очевидно и строится следующим образом. Вершина u соответствует корню дерева T. Цепи ml будет соответствовать цепь u, vlml 1,...,vl1, v. Все остальные цепи, выходящие из вершины u, будут соответствовать цепям исходного дерева T. Вложение построено.

Рассмотрим удаление вершины vl ( ml 1) цепи ml, смежной с вершиной u.

Вложение очевидно и строится следующим образом. Вершина u соответствует корню дерева T. Ребро {vlm, u} соответствует цепи mk длины 1. Цепи ml буl дет соответствовать цепь, оставшаяся часть цепи ml до вершины v длины ml – 2, цепь mk длины 1 с ребром, соединяющим конец цепи с вершиной u. Все остальные цепи, выходящие из вершины u, будут соответствовать цепям исходного дерева T. Вложение построено.

Рассмотрим удаление произвольной вершины vij цепи mi, не относящейся ни к одному из рассмотренных ранее случаев. Вложение строится следующим образом. Вершина v соответствует корню дерева T. Остаток цепи mi от вершины v будет иметь длину j – 1 и соответствовать цепи подходящей длины дерева T. Цепь длины j – 1 вместе с вершиной u и остатком цепи mi от вершины u будет соответствовать цепи mi. Все остальные цепи, выходящие из вершины u, будут соответствовать цепям исходного дерева T. Вложение построено.

Таким образом, граф T*, построенный по описанной схеме, действительно является вершинным 1-расширением сверхстройного дерева T из условия теоремы, а в силу теоремы 2.6.3 и его минимальным вершинным 1-расширением.

Следствие 1. Пусть T – сверхстройное дерево вида (m1,…,mk) и k > такое, что mi mi+1 1, i = 1,..., k 1. Тогда дерево T имеет, по крайней мере, m1 различных минимальных вершинных 1-расширений, отличающихся от T на k + 1 дополнительное ребро.

Доказательство. Из теоремы 2.6.7 следует, что различных минимальных вершинных 1-расширений с вектором степеней (k + 1,k,3,2m+k–1) будет, по крайней мере, столько, сколько есть различных цепей длины отличной от 1, то есть m1 – 1. Заметим, что дерево из условия также попадает и под действие теоремы 2.6.6, что дает еще одно минимальное вершинное 1-расширение с вектором степеней ((k + 1)2,2m+k). Итого получается, что количество минимальных вершинных 1-расширений не менее чем m1.

Рассмотрим сверхстройное дерево T, являющееся объединением цепей длины 1 и 2, среди которых есть хотя бы одна цепь длины 1 и хотя бы одна цепь длины 2. Такое дерево попадает под условие и теоремы 2.6.6, и теоремы 2.6.7. А с учетом теоремы 2.6.5 получается Следствие 2. Пусть сверхстройное дерево T является объединением k (k > 3) цепей длинами не более 2, среди которых есть хотя бы одна цепь длины 1 и хотя бы одна цепь длины 2. Тогда дерево T имеет в точности два неизоморфных минимальных вершинных 1-расширения, которые строятся по схемам из теорем 2.6.6 и 2.6.7.

Верхняя оценка Вспомним, что любой граф имеет тривиальное k-расширение: добавим к данному графу k вершин и соединим их ребрами между собой и со всеми вершинами графа. Число дополнительных ребер тривиального k-расширения любого графа G составит k(k – 1)/2 + nk, где n – число вершин графа G. Тривиальное вершинное k-расширение позволяет получить простейшую верхнюю оценку для числа дополнительных ребер минимального вершинного kрасширения произвольного графа. При k = 1 получаем, что число дополнительных ребер минимального вершинного 1-расширения произвольного nвершинного графа не более n.

В работе (Harary, Khurum, 1995) было высказано более сильное утверждение по сравнению с теоремой 2.6.6. Прежде чем перейти к его формулировке, дадим одно определение. Вершина vij сверхстройного дерева T называется сложной, если среди длин цепей дерева T нет цепи длины j – 1 или mi – j.

В теореме 2.6.6 рассматриваются сверхстройные деревья без сложных вершин. Сверхстройное дерево (5,1,1) из предыдущего примера имеет одну сложную вершину – вершину v13.

1-расширение сверхстройного дерева с k цепями и p сложными вершинами содержит в точности k + p + 1 дополнительных ребер.

При p = 0 приведенное утверждение совпадает с теоремой 2.6.6. Однако при p > 0 cхема доказательства в работе (Harary, Khurum, 1995) исследует вариацию вершинного 1-расширения с вектором ((k + 1)2,2m+k). Пусть vij – сложная вершина, тогда предлагается добавить ребро из вершины старшей степени в вершину vi(j–1). Далее авторы статьи утверждают, что построенный граф будет являться минимальным вершинным 1-расширением заданного сверхстройного дерева. Однако ниже будет показано, что в общем случае построенный граф будет являться вершинным 1-расширением, но не обязательно минимальным.

Как было указано ранее, из 67 сверхстройных деревьев с числом вершин до 10 есть деревья, которые не попадают под действие теоремы 2.6.6, но имеют k + 1 дополнительное ребро. Оказывается, что все они являются контрпримерами к утверждению (Harary, Khurum, 1995).

Сверхстройное дерево (5,1,1) имеет одну сложную вершину, но имеет единственное минимальное вершинное 1-расширение вида (k2,32,2m+k–2), отличающееся на 4 дополнительных ребра.

Сверхстройное дерево (3,2,2) также имеет одну сложную вершину, но имеет 2 минимальных вершинных 1-расширения вида (k2,32,2m+k–2) и одно вида ((k + 1),k,3,2m+k–1), отличающиеся на 4 дополнительных ребра.

Наконец, сверхстройное дерево (4,3,2) имеет одну сложную вершину, но имеет 4 минимальных вершинных 1-расширения вида (k2,32,2m+k–2), отличающиеся на 4 дополнительных ребра.

Еще один интересный пример представляет собой сверхстройное дерево (5,2,2). Можно заметить, что оно имеет 2 сложные вершины, но его 37 минимальных вершинных 1-расширений отличаются на 5, а не на 6 дополнительных ребер. Аналогичная ситуация с деревьями (6,1,1) или (3,3,2), у которых также по две сложные вершины, но минимальные вершинные 1-расширения отличаются на 5 дополнительных ребер.

Самое большое отклонение среди всех сверхстройных деревьев с числом вершин до 10 наблюдается на сверхстройном дереве (7,1,1). Непосредственной проверкой можно убедиться, что оно имеет 3 сложные вершины, но его 8 минимальных вершинных 1-расширений отличаются на 5, а не на 7 дополнительных ребер. Можно предположить, что на сверхстройных деревьях вида (t,1,1) (количество сложных вершин в таких деревьях составляет t – 3, при t > 3) при увеличении t отклонение будет возрастать.

Каждый из этих контрпримеров показывает ошибочность утверждения в общем случае. Исследуем первый контрпример более подробно.

Пример. Рассмотрим сверхстройное дерево T с вектором цепей (5,1,1).

На рис. 2.6.4, а изображено это дерево. Непосредственной проверкой убеждаемся, что единственной сложной вершиной является вершина v13 – вершина цепи длины 5. Действительно, в дереве T нет цепи длины 2 (j – 1 = 3 – 1-расширение, по предлагаемой в работе (Harary, Khurum, 1995) схеме.

Это расширение отличается на 5 дополнительных ребер.

На самом деле это вершинное 1-расширение 2.6.4, в изображено единст- Рис. 2.6.4. Сверхстройное дерево (5,1,1) (а) и два венное минимальное вершин- его вершинных 1-расширения (б, в) ное 1-расширение дерева T с вектором степеней (34,25), которое отличается на 4 дополнительных ребра. Пунктирными линиями обозначаются добавленные вершина и ребра.

Убедимся, что граф на рис. 2.6.4, в действительно является вершинным 1-расширением сверхстройного дерева (5,1,1). В силу очевидной симметрии достаточно рассмотреть графы, получающиеся при удалении верхней вершины и вершин, расположенных слева от неё. На рис. 2.6.5 показано вложение рассматриваемого дерева при удалении соответствующих вершин. Толстой линией выделена вершина, являющая образом корневой вершины, а лишние ребра обозначаются пунктирными линиями. Доказательство минимальности следует из теоремы 2.6.3.

Ошибка в работе (Harary, Khurum, 1995) состояла в том, что исследовалась лишь схема ((k + 1)2,2m+k), а другие возможности не рассматривались. То есть исследовалась схема, в которой добавляется одна вершина и соединяется ребрами с остальными. Напомним, что вершинное k-расширение графа G называется Т-неприводимым, если оно является частью тривиального k-расширения графа G, но никакая его собственная часть не является вершинным k-расширением графа G. По сути, авторы работы (Harary, Khurum, 1995) описали Т-неприводимые 1-расширения сверхстройных деревьев, однако с точки зрения минимальных вершинных 1-расширений этот результат может использоваться лишь как верхняя оценка. Следует отметить, что существуют сверхстройные деревья с p > 0, на которых эта верхняя оценка достигается.

Например, сверхстройное дерево (5,1,1,1) имеет одну сложную вершину и минимальных вершинных 1-расширений, отличающихся на 6 дополнительных ребер. Одно из этих расширений имеет указанный в работе (Harary, Khurum, 1995) вид. Аналогичная ситуация для сверхстройного дерева (6,1,1). Таким образом, нижняя и верхняя оценки для числа дополнительных ребер минимального вершинного 1-расширения произвольного сверхстройного дерева с k цепями и p сложными вершинами являются достижимыми, и можно сформулировать полученный результат:

2.7. Орграфы Основные определения, связанные с расширениями графов, которые были сформулированы в первом параграфе этой главы для неориентированных графов, без изменений могут быть перенесены и на ориентированные графы. Леммы 2.1.1–2.1.5 можно применять и к орграфам, кроме этого докажем леммы, специфические для орграфов.

ЛЕММА 2.7.1. Если минимальная из полустепеней исхода (захода) вершин графа G есть d > 0, то его минимальное k-расширение не содержит вершин с полустепенью исхода (захода) ниже d + k.

ЛЕММА 2.7.2. Если орграф имеет s петель, то его вершинное k-расширение имеет не менее k + s петель.

Доказательство. Пусть дан орграф G из условия соответствующей леммы, а G* – некоторое его минимальное вершинное k-расширение.

1. Пусть G* имеет вершину v со степенью исхода (захода) ниже d + k.

Рассмотрим подграф, получающийся из G* удалением k смежных с v вершин (если d(v) < k, то в этом случае можно удалить все смежные с ней вершины и подходящее количество любых других вершин, кроме v). Он будет содержать вершину со степенью исхода (захода) ниже d и в него нельзя будет вложить граф G.

2. Если бы число вершин с петлями в G* было бы меньше k + s, то, удалив k из них, был бы получен граф, содержащий менее s вершин с петлями, и в него нельзя было бы вложить орграф G.

Следующая лемма устанавливает интересную связь между минимальными вершинными k-расширениями неориентированных и ориентированных графов. Напомним, что симметризацией ориентированного графа G = (V, ) называется неориентированный граф G = (V,*), получающийся заменой дуг ребрами и удалением петель:

ЛЕММА 2.7.3. Пусть G * – минимальное вершинное k-расширение орграфа G. Тогда симметризация орграфа G * является вершинным k-расширением симметризации орграфа G.

k-расширение орграфа G = (V, ). Обозначим через H * = (V *, * ) симметризацию орграфа G *, а через H = (V, ) – симметризацию орграфа G. Выберем произвольный набор F, состоящий из k вершин орграфа G *. По определению орграф G * F, который получается удалением из G * всех вершин, входящих в F вместе с дугами, допускает вложение орграфа G. Это означает, что существует биекция f : V V * F, такая что:

По определению симметризации наличие дуг (u,v) и (f(u),f(v)) в орur графах G и G * означает наличие ребер {u,v} и {f(u),f(v)} в соответствующих симметризациях H и H*, но тогда то есть граф H вкладывается в граф H F.

Следствие 1. Число дополнительных дуг минимального вершинного kрасширения орграфа G не менее числа дополнительных ребер минимального вершинного k-расширения симметризации орграфа G.

Следствие 2. Пусть граф G* является минимальным вершинным k-расширением графа G, диграф H есть некоторая ориентация графа G, а диграф H* есть некоторая ориентация графа G*. Тогда если H* является вершинным k-расширением диграфа H, то H* является и минимальным вершинным k-расширением диграфа H.

Лемма 2.7.3 и два следствия из неё оказываются очень полезными при изучении минимальных вершинных k-расширений орграфов. В частности с их помощью были перенесены теоремы 2.1.8-2.1.11 на случай орграфов, и получены описания орграфов, имеющих не более трех дополнительных дуг в минимальном вершинном 1-расширении (Абросимов, Моденова, 2013 а, б).

ТЕОРЕМА 2.7.1. Пусть G * = (V *, * ) – точное вершинное k-расширение орграфа G = (V, ). Тогда отношения смежности и * являются одновременно либо рефлексивными, либо антирефлексивными.

Доказательство. Пусть G * = (V *, * ) – точное вершинное k-расшиur рение орграфа G = (V, ). Предположим, что отношение смежности * оргuur рафа G* не является ни рефлексивным, ни антирефлексивным. Это означает, что в G* существуют две вершины u и v такие, что в вершине u есть петля, а в вершине v – нет. Но тогда орграфы G * u и G * v содержат различное количество вершин с петлями, а значит, не могут быть изоморфны одному и тому же орграфу G.

З а м е ч а н и е. Из теоремы следует, что точное вершинное k-расширение любого графа либо не содержит петель, либо содержит петлю в каждой вершине. Пусть G* – точное k-расширение орграфа G без петель. Построим новые орграфы H * и H, добавив петли в каждой вершине орграфов G* и G. Очевидно, что получившийся орграф H * будет являться точным вершинным k-расширением орграфа H. С учетом этого замечания далее, если без петель.

ТЕОРЕМА 2.7.2. Пусть G* – точное вершинное k-расширение орграфа G. Тогда симметризация G* является точным вершинным k-расширением симметризации G.

Доказательство. Пусть G * = (V *, * ) – точное вершинное k-расширение орграфа G = (V, ). Обозначим через H * = (V *, * ) симметризацию орграфа G*, а через H = (V, ) – симметризацию G. Выберем произвольный набор F, состоящий из k вершин орграфа G*. По определению орграф G * F изоморфен орграфу G : G * F G. Это означает, что существует изоморфизм f : V * F V, сохраняющий отношение смежности:

По определению симметризации наличие дуг (u,v) и (f(u),f(v)) в орграфах G* и G означает наличие ребер {u,v} и {f(u),f(v)} в соответствующих симметризациях H* и H, но тогда Теорема 2.7.2 означает, что точные вершинные k-расширения при k > могут иметь только такие орграфы, симметризацией которых является полный граф (или вполне несвязный граф, однако этот случай не представляет интереса).

Для неориентированных графов было показано, что дополнение графа, имеющего точное вершинное k-расширение, также имеет точное вершинное k-расширение.

орграфов.

ТЕОРЕМА 2.7.3. Пусть G* – точное вершинное k-расширение орграфа G. Тогда дополнение G* является точным вершинным k-расширением дополнения G.

Доказательство. Пусть G * = (V *, * ) – точное вершинное k-расширение орграфа G = (V, ). Обозначим через H * = (V *, * ) дополнение орграфа G*, а через H = (V, ) дополнение G. Выберем F – k произвольных вершин орграфа G*. Орграф G * F изоморфен G : G * F G. Это означает, что существует изоморфизм f : V * F V, сохраняющий отношение смежности:

откуда Обратным орграфом или обращением орграфа G = (V, ) называется H = (V, ), получающийся заменой ориентации всех дуг G :

орграф = 1 = {(u, v ) V V : (v, u ) }. Граф называется самообратным, если он изоморфен своему обращению.

ТЕОРЕМА 2.7.4. Пусть G* – точное вершинное k-расширение орграфа G. Тогда обращение G* является точным вершинным k-расширением обращения G.

Доказательство. Пусть G * = (V *, * ) – точное вершинное k-расширение орграфа G = (V, ). Обозначим через H * = (V *, * ) дополнение орграфа G*, а через H = (V, ) дополнение G. Выберем F – k произвольных вершин орграфа G*. Орграф G * F изоморфен G : G * F G. Это означает, что существует изоморфизм f : V * F V сохраняющий отношение смежности:

откуда заданием ориентации ребер соответствующих точных неориентированных расширений. На рис. 2.7.1 показаны ориентированная цепь P3, ее точное вершинное 1Рис. 2.7.1. Орцепь P3, ее точное веррасширение – ориентированный цикл C4 и шинное 1-расширение С4 и их дополих дополнения (с учетом замечания о петнения совпадает с дополнением).

ТЕОРЕМА 2.7.5. Пусть G – диграф с числом вершин большим 1, тогда его точное вершинное k-расширение, если оно есть, также будет диграфом.

Доказательство. Пусть n-вершинный диграф G, n > 1, имеет точное вершинное k-расширение G*. Предположим, что G* не является диграфом.

Тогда в G* существует пара встречных дуг (u,v) и (v,u). Число вершин в G* есть n + k k + 2. Выберем набор F, состоящий из k произвольных вершин G*, отличных от u и v. Орграф G* – F по-прежнему содержит пару встречных дуг (u,v) и (v,u) и таким образом не является диграфом, однако по предположению он должен быть изоморфен диграфу G.

Следствие. Из теоремы следует, что точное вершинное k-расширение турнира, если оно существует, также является турниром.

Очевидно, что точное вершинное k-расширение графа с числом вершин большим 1 является и его минимальным вершинным k-расширением. Для неориентированных графов точное вершинное k-расширение в этом случае и единственно. Для ориентированных графов в общем случае это не так. Одновершинные орграфы O1 и K1 имеют по одному единственному минимальному 1-расширения – O2, T2 и K2 для графа O1 (рис. 2.7.2) и те же орграфы с петлями для K1.

Рис. 2.7.2. Граф O1 и три его точных вершинных 1-расширения Турнир T2 с петлями и без имеет два минимальных вершинных 1-расширения, каждое из которых является точным (рис. 2.7.3): циклическую и транзитивную тройки. Заметим, что турниры T2 с петлей лишь в одной 1-расширению, но не имеют точного.

Рис. 2.7.3. Турнир T2 и два его точных вершинных 1-расширения 2.7.1. Турниры ТЕОРЕМА 2.7.6. Единственным минимальным вершинным k-расширением транзитивного турнира Tn при n > 2 является транзитивный турнир Tn+k. Причем это расширение является и его точным вершинным k-расширением.

Доказательство. Рассмотрим правильную нумерацию вершин в графах Tn+k и Tn. Напомним, что нумерация вершин орграфа называется правильной, если для любой дуги орграфа (vi, vj) имеет место i j. При правильной нумерации вершин матрица смежности будет состоять из всех единиц выше главной диагонали. Удаление любых k вершин приведет к удалению соответствующих k строк и столбцов из матрицы смежности. В результате получится матрица смежности n-вершинного транзитивного турнира Tn при правильной нумерации его вершин. Таким образом, транзитивный турнир Tn+k является вершинным k-расширением транзитивного турнира Tn, причем точным.

Покажем, что турнир Tn+k является и единственным минимальным вершинным k-расширением турнира Tn.

Пусть граф G* – минимальное вершинное k-расширение транзитивного турнира Tn. Степень каждой вершины Tn есть в точности n – 1. По лемме 2.1. степень любой вершины в орграфе G* должна быть не ниже n – 1 + k. Заметим, что в графе Tn+k степень каждой вершины в точности равна n – 1 + k, следовательно, Tn+k является минимальным вершинным k-расширением турнира Tn, причем любое другое его минимальное вершинное k-расширение также должно иметь все вершины степени n – 1 + k. Заметим, что поскольку степень каждой вершины на единицу меньше числа вершин, то при удалении любой вершины удаляется именно такое число дуг.

Покажем, что граф G* является направленным. Пусть это не так, и в нем есть встречные дуги (u,v) и (v,u). Рассмотрим подграф, получающийся из G* удалением любых k вершин, отличных от u и v. Он содержит столько же дуг, сколько и Tn, однако не изоморфен ему из-за встречных дуг (u,v) и (v,u), следовательно, Tn и не вкладывается в него.

Аналогично показывается, что G* является и полным направленным графом. Если бы это было не так, то можно было бы найти две вершины u и v в G*, между которыми нет дуги. Тогда подграф, получающийся из G* удалением любых k вершин, отличных от u и v, очевидно, не допускал бы вложения Tn.

Таким образом, любое минимальное вершинное k-расширение турнира Tn является (n + k)-вершинным турниром, причем оно является и его точным вершинным k-расширением. Покажем, что оно должно быть бесконтурным графом.

Пусть это не так, и в графе G* существует контур. Пусть s – минимальная из длин всех контуров в графе G*, и vi1,..., v is, vi1 – один из таких контуров. Рассмотрим два случая.

1) s n, в этом случае любой n-вершинный подграф G*, состоящий из всех вершин этого контура, будет не изоморфен Tn.

2) s > n. Рассмотрим подграф, образованный вершинами v i1,..., v in. Поскольку G* является точным k-расширением, то этот подграф изоморфен Tn, а значит, в силу транзитивности в Tn и в G* есть дуга (v i1, v in ). Тогда при n > 2 можно построить контур длины, меньшей чем s: vi1, vin,..., v is, v i1, что противоречит предположению о минимальности.

Таким образом, транзитивный турнир Tn+k является единственным минимальным вершинным k-расширением транзитивного турнира Tn+k при n > 2, причем точным.

Доказанная теорема означает, что кроме полных и вполне несвязных графов существует еще одно бесконечно семейство графов, имеющих точные вершинные k-расширения при любом натуральном k. А. А. Долгову удалось доказать, что других семейств не существует (Долгов, 2010, а). Однако оказалось, что существуют орграфы, которые имеют точное вершинное k-расширение только при k = 1 и при k = 2.

Рассмотрим p-вершинный граф G = (V, ), где p – простое и p > 2.

Пусть V = {v0, v1, …, vp–1} – множество вершин G. Из вершины vi в вершину vj есть дуга только в том случае, когда (j – i) – квадратичный вычет по модулю p, то есть по теореме Эйлера (j – i)(p – 1)/2 1 (mod p). Известно, что при p = 4n + 3 полученный граф будет являться турниром, он называется турниром квадратичных вычетов QT(p) (Morris, 2006).

Например, при p = 7 квадратичными вычетами по модулю 7 будут являться числа 1, 2 и 4. Значит, матрица смежности графа QT(7) будет иметь вид:

Турнир QT(7) изображен на рис. 2.7.4.

Рис. 2.7.4. Турнир QT(7) и его точные вершинные 1- и 2-расширения Оказывается (Долгов, 2010, б), что граф QT(p) является точным вершинным 1-расширением, а если p – простое число вида 4n + 3, то QT(p) является точным вершинным 1- и 2-расширением для подходящих турниров.

Таким образом, турниры, которые являются точными 2-расширениями, существуют при числе вершин 7, 11, 19, 23, 31, … Соответственно, существуют турниры с числом вершин 5, 9, 17, 21, 29, …, которые имеют точные вершинные k-расширения только при k = 1 и k = 2, а при k > 2 не имеют точных вершинных k-расширений.

З а м е ч а н и е. Минимальные и точные вершинные 1-расширения турниров Tn при n = 1 и n = 2 показаны на рис. 2.7.2 и 2.7.3 соответственно.

ТЕОРЕМА 2.7.7. Пусть G – турнир и G* – его точное вершинное 1-расширение. Тогда если G* имеет сток или источник, то и G, и G* являются транзитивными турнирами.

Доказательство. Пусть G – n-вершинный турнир и G* – его точное вершинное 1-расширение. Не теряя общности, предположим, что вершина v является источником в G*. Пусть v ' – произвольная вершина G*, отличная от v. Рассмотрим орграф G* – v '. В этом графе вершина v является источником.

Рассмотрим орграф G* – v. По условию эти графы изоморфны, следовательно, граф орграф G* – v имеет источник, обозначим его через u. Выберем вершину u ', отличную от v и u. В орграфе G* – u две вершины имеют полустепени исхода n – 1 и n – 2. Но такие вершины должны быть и в орграфе G* – v.

Следовательно, в G* должна быть вершина w с полустепенью исхода n – 3.

Продолжая рассуждения, получаем, что G* оказывается транзитивным турниром, следовательно, и является транзитивным турниром.

2.7.2. Ориентации звезд Ориентированной звездой будем называть орграф, симметризацией которого является звезда. Ориентированную звезду будем обозначать Zm, n, p, где m и n – число вершин с единственной соответственно исходящей и входящей дугой, а p – число вершин с одной входящей и одной исходящей дугой. Направленной звездой будем называть ориентированную звезду, являющуюся диграфом, и обозначать Zm, n (у направленной звезды p = 0). Вершину, являющуюся концом или началом каждой дуги звезды, будем называть центральной.

звезды Zm,n добавлением k = p – 1 копий центральной вершины и соединением их друг с другом по схеме транзитивного турнира, является вершинным kрасширением орграфа Zm,n.

Доказательство. Рассмотрим граф ZTm,n,p. Его вершины можно разделить на три группы:

1-я группа состоит из p центральных вершин, соединенных по схеме транзитивного турнира;

2-я группа состоит из m вершин источников, от каждой из которых исходят дуги ко всем вершинам 1-й группы. Очевидно, что все вершины этой группы подобны и имеют полустепени исхода и захода (p,0);

3-я группа состоит из m вершин стоков, в каждую из которых заходят дуги от каждой вершины 1-й группы. Очевидно, что все вершины этой группы подобны и имеют полустепени исхода и захода (0,p).

Рассмотрим орграф G, получающийся из ZTm,n,p удалением k произвольных вершин. Обозначим через p1, m1 и n1 количество удаленных вершин 1, 2 и 3-й групп соответственно:

Покажем, что направленная звезда Zm,n вкладывается в орграф G.

При p1 = k (все удаленные вершины – вершины 1-й группы) орграф G изоморфен звезде Zm,n и, таким образом, допускает вложение.

Пусть p1 < k. По теореме 2.7.6 транзитивный турнир Tn+k является точным вершинным k-расширением транзитивного турнира Tn (n > 1). В нашем случае после удаления p1 центральных вершин 1-й группы оставшиеся p – p1 > 1 вершины будут по-прежнему образовывать транзитивный турнир Tp-p1.

При этом Вершины транзитивного турнира, как известно, могут быть упорядочены по отношению достижимости. Обозначим оставшиеся центральные вершины в соответствующем порядке через u1, …, um1+n1+1. Таким образом, из любой вершины с меньшим индексом идет дуга в любую вершину с большим индексом.

Укажем соответствие вершин звезды Zm,n вершинам орграфа G которое определяет вложение:

а) m вершинам-источникам соответствуют m – m1 оставшихся вершин 2-й группы и m1 вершин u1,…,um1;

б) n вершинам-стокам соответствуют n – n1 оставшихся вершин 3-й группы и n1 вершин um1+2,…,u m1+n1+1;

в) вершина um1+1 соответствует центральной вершине звезды Zm,n.

Видно, что из каждой вершины типа а) идет дуга в вершину um1+1, а из вершины um1+1 идет дуга в каждую вершину типа б); таким образом, звезда Zm,n действительно вкладывается в орграф G.

С учетом леммы 2.7.3, утверждения 1 и теоремы 2.6.1 получается ТЕОРЕМА 2.7.8. Пусть Zm,n направленная звезда, причем m + n > 1 и mn 1. Диграф ZTm,n,2, получающийся из направленной звезды Zm,n добавлением копии центральной вершины и соединением их друг с другом дугой, является единственным с точностью до изоморфизма минимальным вершинным 1-расширением орграфа Zm,n.

З а м е ч а н и е 1. Направленная звезда Z1,1 является направленной цепью P3, и ее единственное минимальное вершинное 1-расширение, являющееся также и ее точным вершинным 1-расширением, – направлен-ный цикл C4.

З а м е ч а н и е 2. Направленная звезда Z1,0 изоморфна звезде Z0,1 и имеет два неизоморфных минимальных вершинных 1-расширения, каждое из которых является и точным вершинным 1-расширением – транзитивную и циклическую тройки (см. рис. 2.7.3).

С учетом леммы 2.7.3, утверждения 1 и теоремы 2.6.2 получается ТЕОРЕМА 2.7.9. Диграф ZTm,n,p, получающийся из направленной звезды Zm,n добавлением k = p – 1 копий центральной вершины и соединением их друг с другом по схеме транзитивного турнира, является единственным с точностью до изоморфизма минимальным вершинным k-расширением орграфа Zm,n, если выполняется любое из двух условий:

1) m + n нечетно;

Далее необходимо рассмотреть случай, когда m + n четно, так как в этом случае, согласно теореме 2.6.2, могут появиться минимальные вершинные k-расширения с меньшим числом дополнительных дуг.

Рассмотрим схему ориентации однородного (2n)-вершинного графа R2n,2n-2. Напомним, что граф R2n,2n-2 может быть представлен в виде Рис. 2.7.5. Схема ориенпервой пары направим дуги в обратном порядке, так тации ребер в графе вершины второй пары, то ориентируем дуги следующим образом: (u1,u2), (v1,v2), (v2,u1), (u2,v1). Продолжаем ориентацию описанным способом по всем парам вершин. Обозначим построенный диграф через D2n,2n-2.

Отметим некоторые достаточно очевидные свойства диграфа D2n,2n-2.

1. Отображение ui vi, vi ui, i = 1, …, n, является автоморфизмом.

2. Отображение ui ui+1, vi vi+1, i = 1, …, n – 1, un v1, vn u1 является автоморфизмом.

3. Все вершины диграфа D2n,2n-2 подобны и имеют полустепени исхода 4. D2n,2n-2 является вершинно-симметрическим графом (следует из 3).

5. При удалении любой пары несмежных вершин ui и vi диграфа D2n,2n- получается диграф D2n-2,2n-4.

6. Все максимальные подграфы диграфа D2n, 2n-2 изоморфны. Обозначим граф, получающийся удалением любой вершины диграфа D2n,2nчерез TD2n-2,2n-4.

Утверждение 2.7.2. Диграф D2n+k+1, 2n+k-1 при нечетном k является вершинным k-расширением направленной звезды Zn, n.

Доказательство. Обозначим число вершин диграфа D2n+k+1, 2n+k-1 через 2p: 2p = 2n+k+1. Как и ранее, вершины диграфа D2n+k+1, 2n+k-1 обозначим через ui и vi, i = 1, …, p.

Рассмотрим граф, получающийся из D2n+k+1, 2n+k-1 удалением произвольных k вершин: ui 1,…, uik и vi 1,…, vik : k1 + k2 = k. Обозначим этот граф через G.

Так как k нечетное, то k1 k2. Пусть для определенности 0 k1 < k2 k. На рис. 2.7.6 для наглядности оставлена только часть дуг: дугами соединяются вершины одной горизонРис. 2.7.6. Граф G: иллюстрация тали от вершины с меньшим индексом к верк доказательству шине с большим и вершины разных горизонталей от вершины с большим индексом к вершине с меньшим. Удаленные вершины на рисунке помечены черным (при p = 4 этот рисунок соответствовал бы случаю поиска вершинного 3-расширения для 5-вершинной звезды Z2,2). Для краткости будем называть удаленные вершины черными, а оставшиеся белыми. Количество белых и черных вершин очевидно: 2n + 1 и k штук соответственно.

Чтобы доказать, что диграф D2n+k+1, 2n+k-1 является вершинным k-расширением звезды Zn,n, достаточно показать, что в G есть вершина с n входящими и n исходящими дугами. Кандидатами для такой вершины могут быть только такие вершины, у которых парная была удалена, так как только они соединены дугами со всеми остальными вершинами. Искомых вершин может быть и несколько. Для каждой вершины w введем в рассмотрение индекс, состоящий из пары чисел d + (w) и d (w) :

d (w) равно числу белых вершин слева от w в ее ряду плюс число белых вершин справа от w в другом ряду;

d + (w) равно числу белых вершин справа от неё в ее ряду плюс число белых вершин слева от неё в другом ряду.

По построению видно, что для вершин одной пары выполняются соотношения: d + (ui ) = d (vi ) и d (ui ) = d + (vi ). Значения индексов d + (w) и d (w) для белой вершины соответственно равны полустепеням исхода и захода. Искомая вершина, очевидно, должна удовлетворять условию:

Покажем, что такая вершина найдется. На рис. 2.7.7 представлены возможные конфигурации парных вершин.

Рис. 2.7.7. Конфигурации пардля пар типа (б) и (в) (рис. 2.7.7, б, в):

d + (w) + + d ( w) = 2n (единственная белая вершина пары не участвует в подсчете индексов);

– для пары типа (г) (рис. 2.7.7, г): d + ( w) + d ( w) = 2n + 1 (все белые вершины участвуют в подсчете индексов).

Для удобства будем считать, что пары типа (г), если они есть, располагаются справа, а пары типа (а), если они есть, по свойству 5 диграфа можно расположить слева. Таким образом, представляющие для нас интерес пары типа (б) и (в) располагаются между парами типа (а) и (г). Обозначим для определенности номер первой пары интересующего интервала через l, а номер последней пары – через r.

Для каждой вершины пар (б) и (в) рассчитаем индекс. Вершина ul первой пары получит индекс (n – k2,n – k1 – 1), если пара имеет тип (в) или (n – k2 – 1,n – k1), если пара имеет тип (б). Вершина ur последней пары получит (n – k1 – 1,n – k2), если пара имеет тип (в). Так как k1 < k2, то у вершины первой пары d + (ul ) d (ul ), а у последней пары d + (ur ) d (ur ).

Рассмотрим, как изменяется индекс при переходе от одной пары к другой при просмотре слева направо:

Таким образом, при переходе от одной пары к другой компоненты индекса либо не изменяются, либо изменяются на 1. У первой пары:

d + (ul ) d (ul ), а у последней пары наоборот: d + (ur ) d (ur ). Следовательно, существует пара, у которой компоненты окажутся равными. Белая вершина из такой пары и будет искомой вершиной.

Пример. На рис. 2.7.8 представлена схема, иллюстрирующая доказательство – поиск вложения звезды Z2,2 в её 3расширение. Рассчитаем индексы для верхнего ряда вершин: u1: (2,1), u2: (2,2), u3: (2,2), u4:

(2,2).

Таким образом, любая из вершин u2, v или u4 является искомым образом для центральной вершины звезды.

Утверждение 2.7.3. Диграф TD2n+k, 2n+k-2 при четном k является вершинным k-расширением направленной звезды Zn,n.

Доказательство. Следует из предыдущего утверждения, свойства 6 и очевидного замечания, что максимальный подграф вершинного k-расширения некоторого графа является для него вершинным (k – 1)-расширением.

Утверждение 2.7.4. Пусть натуральные m, n, k таковы, что m n, m + n четно, а k нечетно. Никакой диграф, получающийся ориентацией однородного (m + n + k + 1)-вершинного графа Rm+n+k+1, m+n+k-1, не является вершинным k-расширением ни для какой направленной звезды Zm,n.

Доказательство. Для доказательства достаточно показать, что утверждение не выполняется уже при k = 1. Предположим противное: пусть G – некоторая ориентация графа Rm+n+2, m+n является вершинным k-расширением для направленной звезды Zm,n, причем m n и m + n четно.

Не ограничивая общности, будем считать, что m > n (так как m + n четно, то справедливо даже m > n + 1). При удалении любой вершины v графа Rm+n+2, m+n+k получается граф вида O1 + O2 + … + O2, в котором есть только одна полная вершина u – та, которая была несмежна с удаленной вершиной v.

Следовательно, при удалении любой вершины v графа G соответствующая вершина u должна иметь полустепени захода и исхода не меньше чем m и n соответственно. В силу произвольности выбора v получаем, что любая вершина графа G должна иметь полустепени захода и исхода не меньше чем m и n соответственно. Но тогда в каждую вершину орграфа G должно заходить не менее m дуг, откуда получаем, что общее число дуг будет не менее (m + n + 2)(m + n)/2 < (m + n + 2)(m + m)/2 = m(m + n + 2). Полученное противоречие доказывает утверждение.

С учетом утверждений 2.7.2, 2.7.3 и 2.7.4 можно уточнить теорему 2.7.9:

ТЕОРЕМА 2.7.10. Диграф ZTm,n,p, получающийся из направленной звезды Zm,n добавлением k = p – 1 копий центральной вершины и соединением их друг с другом по схеме транзитивного турнира, является при m n единственным с точностью до изоморфизма минимальным вершинным k-расширением орграфа Zm,n.

ТЕОРЕМА 2.7.11. Диграф TD2n+k, 2n+k-2 при четном k или максимальный подграф диграфа TD2n+k+2, 2n+k при нечетном k являются единственными минимальными вершинными k-расширениями направленной звезды Zn,n.

ГЛ А В А 3. РЕБЕРНЫЕ РАСШИРЕНИЯ

3.1. Основные определения и свойства Назовем граф GR = (VR,R) реберным k-расширением графа G = (V,), если граф G можно вложить в каждый граф, получающийся из GR удалением любых его k ребер. Заметим, что определение не теряет смысла и при k = 0.

Как и в предшествующей главе, мы будем рассматривать преимущественно графы без меток, однако если вершины имеют метки, то подразумевается вложение с учетом меток. Если F – некоторый набор ребер графа G, то есть F, то будем обозначать через G – F граф, получающийся из G удалением всех ребер из F. Очевидно, что число вершин любого реберного kрасширения графа не меньше, чем у самого графа. На рис. 3.1.1, а изображена цепь P4. Графы на рис. 3.1.1, б и д являются ее реберными 1-расширениями. Граф на рис. 3.1.1, в – реберным 3-расширением, а граф на рисунке 3.1.1, г – реберным 2-расширением.

Реберное k-расширение (k – натуральное) графа G = (V,) называется неприводимым, если никакая его собственная часть не является реберным k-расширением графа G. Например, расширения на рис. 3.1.1, б, д являются неприводимыми реберными 1-расширениями цепи P4, а на рис. 3.1.1, в, г – неприводимыми реберными 3- и 2-расширениями соответственно.

Граф H называется точным реберным k-расширением графа G, если любой граф, получающийся удалением произвольных k ребер графа H, изоморфен графу G.

Граф G* = (V*,*) называется минимальным реберным k-расширением (иногда будем использовать сокращение МР-kР) n-вершинного графа G = (V,), если выполняются следующие условия:

1. граф G* является реберным k-расширением графа G, то есть граф G допускает вложение с учетом меток вершин в каждый граф, получающийся из графа G* удалением любых его k ребер;

2. граф G* содержит такое же количество вершин, как и в графе G;

3. * имеет минимальную мощность при выполнении условий 1) и 2).

Как и в предыдущей главе, будем считать, что граф является минимальным реберным 0-расширением для самого себя. Не всякий граф имеет минимальное реберное k-расширение. Например, полный граф не имеет минимального реберного k-расширения ни при каком натуральном k.

Заметим, что число ребер минимального реберного k-расширения графа заранее оценить очень сложно, так как граф может вообще не иметь реберного k-расширения с тем же числом вершин, что у него. Если граф имеет минимальное реберное k-расширение с * ребрами, то будем говорить, что это расширение содержит * дополнительных ребер. Для любого графа, кроме вполне несвязного, количество дополнительных ребер больше 0. Из определения следует очевидный переборный (по сравнению с алгоритмом 2.1.1 для минимальных вершинных k-расширений, в этом алгоритме предусматривается случай, когда минимальных реберных k-расширений у графа нет) Алгоритм 3.1.1. Построение всех минимальных реберных k-расширений для заданного графа G, отличного от вполне несвязного.

3. Строим все графы, получающиеся из графа G добавлением m дополнительных ребер.

4. Выбираем среди построенных на шаге 3 графов реберные k-расширения графа G.

5. Если на шаге 4 были найдены графы, то переходим на шаг 8.

6. Если на шаге 4 был построен полный граф, то граф G не имеет минимальных реберных k-расширений, и алгоритм завершает работу.

7. Переход на шаг 2.

8. Среди графов, выбранных на шаге 4, оставляем по одному представителю от изоморфных графов. Полученные графы будут являться минимальными реберными k-расширениями графа G.

Обоснование. В худшем случае, когда граф не имеет минимальных реберных k-расширений, алгоритм завершит свою работу, когда будет построен полный граф. В силу конечности числа ребер графа алгоритм закончит свою работу за конечное число шагов. Алгоритм имеет экспоненциальную сложность, что ограничивает его применение малыми значениями k и числа вершин графа G. В следующем параграфе вычислительная сложность задачи будет обсуждаться более подробно, и станет ясно, что эффективного универсального алгоритма для поиска минимальных реберных k-расширений, повидимому, не существует.

Докажем несколько вспомогательных утверждений о свойствах минимальных реберных k-расширений.

ЛЕММА 3.1.1. Минимальное реберное k-расширение графа без изолированных вершин не содержит вершин со степенью ниже k + 1.

ЛЕММА 3.1.2. Если минимальная степень вершины графа G есть d > 0, то его минимальное реберное k-расширение не содержит вершин степени ниже d + k.

Доказательство. Пусть дан граф G из условия соответствующей леммы, и G* – некоторое его минимальное реберное k-расширение.

Лемма 3.1.1 является частным случаем леммы 3.1.2.

Пусть граф G* имеет вершину v степени ниже d + k. Рассмотрим граф, получающийся из G* удалением k инцидентных вершине v ребер (если d(v) < k, то в этом случае можно удалить все инцидентные вершине v ребра и подходящее количество любых других ребер). Он будет содержать вершину степени ниже d, и в него нельзя будет вложить граф G.

Заметим, что минимальное реберное k-расширение отличается от исходного графа на некоторое количество дополнительных ребер, и только вполне несвязный граф изоморфен любому своему минимальному реберному k-расширению. Далее мы исключаем из рассмотрения вполне несвязные и полные графы.

В табл. 3.1.1 приведены все 2-, 3- и 4-вершинные графы, отличные от вполне несвязных и полных, и их минимальные реберные 1-расширения. Для каждого графа указывается его вектор степеней, а для расширений в скобках приводится число дополнительных ребер.

Минимальные реберные 1-расширения 2-, 3- и 4-вершинных графов (1,1,0,0) (2,2,2,0) (3,3,2,2) В работе (Harary, Hayes, 1993) авторы нашли минимальные реберные kрасширения для некоторых видов графов, в том числе для цепей и циклов.

ТЕОРЕМА 3.1.1 (Harary, Hayes, 1993). Минимальное реберное 1-расширение n-вершинной цепи Pn есть n-вершинный цикл Cn.

Доказательство. В самом деле, нетрудно видеть, что цикл Cn является реберным 1-расширением цепи Pn. Минимальность следует из леммы 3.1.1.

ТЕОРЕМА 3.1.2. Минимальное реберное 1-расширение n-вершинной цепи Pn единственно с точностью до изоморфизма.

Доказательство. Пусть граф G* является минимальным реберным 1-расширением цепи Pn. Очевидно, что G* является связным графом, причем по лемме 3.1.1 степень любой его вершины не меньше двух. По теореме 3.1. цикл содержащий ребер, является минимальным реберным 1-расширением цепи Pn, следовательно, граф G* также содержит n ребер, и, значит, степень любой его вершины в точности равна двум. Заметим, что G* – не дерево и, следовательно, содержит цикл длины k. Если k < n, то нарушается условие связности графа G*, следовательно, k = n, то есть G* изоморфен Для реберных расширений задача описания графов, которые имеют минимальные реберные 1-расширения с малым числом ребер, является более сложной, чем для вершинных 1-расширений. Очевидно, что если граф G имеет минимальное реберное 1-расширение G* с одним дополнительным ребром, то граф G* будет точным реберным 1-расширением графа G.

В отличие от вершинных точные реберные 1-расширения не обязательно являются однородными графами. Так, например, полный двудольный граф Kn, m является точным реберным 1-расширением при любых значениях n > 1, m > 0.

Оказывается, имеет место следующая ТЕОРЕМА 3.1.3. Всякий однородный граф G является точным реберным 1-расширением тогда и только тогда, когда он является реберносимметрическим.

Доказательство. Необходимость. Пусть граф G является реберносимметрическим. Любые два его ребра e1 и e2 подобны, откуда очевидным образом следует, что граф G – e1 изоморфен графу G – e2.

Достаточность. Пусть однородный граф G является точным реберным 1-расширением. Обозначим через k степень вершин графа G. Тогда для любых двух ребер e1 = {u1, v1} и e2 = {u2, v2} графы G – e1 и G - e2 изоморфны.

В графе G – e1 вершины u1 и v1 имеют степень k – 1, а все остальные вершины имеют степень k. Аналогично в графе G – e2 вершины u2 и v2 имеют степень k – 1, а все остальные вершины имеют степень k. Следовательно, при изоморфизме образом вершин u1, v1 могут быть только вершины u2, v2, а это и означает, что ребра e1 и e2 подобны.

Следующая известная теорема (Харари, 2009) устанавливает связь между реберно-симметрическими и вершинно-симметрическими графами:

ТЕОРЕМА 3.1.4. Реберно-симметрический граф без изолированных вершин является или вершинно-симметрическим, или двудольным.

Из этой теоремы с учетом доказанного ранее очевидным образом получается следующая ТЕОРЕМА 3.1.5. Пусть однородный граф G является точным реберным 1-расширением, тогда он является или точным вершинным 1-расширением, или двудольным графом.

Реберно-симметрический граф, не являющийся вершинно-симметрическим, называется полусимметрическим. В книге точным реберным 1-расширением, которое не является точным вершинным 1-расширением) является 20-вершинный граф Фолкмана, изображенный Рис. 3.1.2. Граф Фолкмана В книге (Харари, 2009) приводится ряд утверждений о свойствах симметрических графов, которые с учетом установленных соответствий могут быть сформулированы следующим образом:

ТЕОРЕМА 3.1.6 (ср. Следствие 14.12 (Харари, 2009)). а) Если G – однородное n-вершинное точное реберное 1-расширение и степень d каждой вершины нечетна, то граф G является точным вершинным 1-расширением.

б) Если граф G – однородное n-вершинное точное реберное 1-расширение и степень каждой вершины четна, причем d p/2, то граф G является точным вершинным 1-расширением.

И, наконец, имеет место следующая ТЕОРЕМА 3.1.7 (ср. Теорема 14.13 (Харари, 2009)). Для каждого n 20, кратного 4, существует однородное n-вершинное точное реберное 1расширение, не являющееся точным вершинным 1-расширением.

3.2. Сложность задачи В этом параграфе нас будет интересовать вычислительная сложность задачи описания минимальных реберных k-расширений. Эта задача является поисковой: по заданному графу требуется построить его минимальное реберное k-расширение (или еще более сложная задача – все расширения). Как мы уже обсуждали в параграфе 1.4, при анализе сложности рассматриваются задачи распознавания свойств, а задача поиска будет иметь не меньшую сложность.

Сформулируем задачу о реберном k-расширении, как задачу распознавания свойств, то есть задачу, ответом на которую может быть «да»

или «нет»:

ЗАДАЧА: РЕБЕРНОЕ k-РАСШИРЕНИЕ

УСЛОВИЕ. Даны графы G = (V,) и H = (U,).

ВОПРОС. Верно ли, что граф G является реберным k-расширением графа H?

Прежде чем перейти к основному утверждению, докажем вспомогательное.

ЛЕММА 3.2.1. Граф H вкладывается в граф G тогда и только тогда, когда граф H + K1 вкладывается в граф G + K1.

Доказательство. Пусть даны графы G = (V,) и H = (U,). Графы H + K1 и G + K1 получаются из G и H добавлением одной вершины и соединением со всеми остальными. Обозначим через v и u соответствующие вершины графов G и H.

Необходимость. Пусть граф H вкладывается в граф G и : U V – соответствующая инъекция. Доопределим, положив (u) = v. Очевидно, что построенная инъекция U {u} V {v} определяет вложение графа H + K в граф G + K1.

Достаточность. Пусть граф H + K1 вкладывается в граф G + K1 и : U {u} V {v} – соответствующая инъекция. Покажем, что граф H вкладывается в граф G. Рассмотрим три случая.

1. Пусть v не является образом никакой вершины графа H при отображении. Это означает, что граф H + K1 вкладывается в граф G, но тогда и любая часть H + K1 вкладывается в G, в том числе и граф H.

2. Пусть (u) = v. Тогда очевидно, что отображение : U V будет определять вложение графа H в G.

3. Пусть (u) = v, u u. Для определенности обозначим (u) = v. Так как является вложением, то v v. Построим новое отображение *, определив его следующим образом:

То есть * отличается от только перестановкой образов вершин u и u, а на множестве U \ {u} их значения совпадают. Покажем, что * также определяет вложение графа H в граф G. Очевидно, что * является инъекциx, y U {u}, (x, y) ( *(x), *(y)). Так как определяет вложение графа H в Рассмотрим в графе H + K1 две произвольные смежные вершины x, y U {u}. Тогда вершины (x) и (y) тоже смежны в графе G + K1.

Требуется показать, что в графе G + K1 смежны также вершины *(x) и * (y).

Рассмотрим 4 возможных случая:

а) x, y U \ {u}. Так как на множестве U \ {u} значения функций * и совпадают, то вершины *(x) и * (y) смежны;

б) {x,y} = {u,u}. Так как вершина u полная, то она смежна со всеми остальными вершинами в графе H + K1. По определению отображения * образом вершин u и u являются вершины v и v графа G + K1. Вершина v по условию является полной, и, значит, вершины v и v смежны;

в) одна из вершин x, y есть u, а вторая отлична от u. Пусть для определенности y = u, а x U\ {u}. Аналогично случаю б) образом полной вершины u графа H + K1 является полная вершина v графа G + K1, следовательно, вершины *(x) и v смежны;

г) одна из вершин x, y есть u, а вторая отлична от u. Пусть для определенности y = u, а x U. Так как вложение, то (x) и (y) = v смежны. С другой стороны, в графе H + K1 вершины x и u смежны в силу того, что вершина u полная. Значит, (x) и (u) = v смежны. Однако по определению * (u) = v.

Во всех рассмотренных случаях граф H вкладывается в граф G.

Теперь мы готовы приступить к доказательству основного результата.

ТЕОРЕМА 3.2.1. Задача РЕБЕРНОЕ k-РАСШИРЕНИЕ является NPполной.

Доказательство. По-прежнему доказательство для наглядности будем проводить при k = 1, однако идея доказательства остается справедливой при показать:

1. Задача РЕБЕРНОЕ k-РАСШИРЕНИЕ NP.

2. Некоторая известная NP-полная задача может быть полиномиально сведена к задаче РЕБЕРНОЕ k-РАСШИРЕНИЕ (сводимость по Карпу).

Покажем, что задача РЕБЕРНОЕ 1-РАСШИРЕНИЕ NP. Пусть в графе G n вершин и m ребер, а в графе H p вершин, очевидно, что положительный ответ в задаче возможен лишь при n p. Обозначим ребра графа G через e1, …, em. Тогда недетерминированному алгоритму необходимо угадать m последовательностей Vi по p вершин из множества V, для каждой из которых далее за полиномиальное время можно проверить, что определяемая этой последовательностью инъекция является вложением графа H в граф G – ei. В общем случае, для произвольного k необходимо будет указать C m последоваk тельностей для всех возможных наборов из k удаляемых ребер графа G: для фиксированного k эта величина будет полиномом от n и может быть оценена как O(mk) = O(n2k).

Покажем, что задача ИЗОМОРФИЗМ ПОДГРАФУ сводится к задаче РЕБЕРНОЕ k-РАСШИРЕНИЕ. Для этого необходимо указать функцию f, которая сводит каждую задачу ИЗОМОРФИЗМ ПОДГРАФУ к задаче РЕБЕРНОЕ k-РАСШИРЕНИЕ и удовлетворяет двум условиям полиномиальной сводимости.

Пусть графы G = (V,) и H = (U,) определяют условие задачи ИЗОМОРФИЗМ ПОДГРАФУ. Соответствующая задача РЕБЕРНОЕ k-РАСШИРЕНИЕ строится следующим образом. Первым графом берется граф G + K1 H + K1, а вторым графом берется граф H + K1. Очевидно, что сводимость осуществляется за полиномиальное время. Для проверки второго требования необходимо показать, что G + K1 H + K1 тогда и только тогда является реберным k-расширением графа H + K1, когда граф H вкладывается в граф G. С учетом леммы достаточно доказать, что G + K1 H + K1 тогда и только тогда является реберным k-расширением графа H + K1, когда граф H + K1 вкладывается в граф G + K1.

Необходимость. Если граф G + K1 H + K1 является реберным 1-расширением графа H + K1, то граф H + K1 будет вкладываться в любой граф, получающийся из G + K1 H + K1 удалением произвольного ребра. Если в качестве ребра взять некоторое ребро из компоненты H + K1 графа G + K1 H + K1, то, очевидно, граф H + K1 должен вкладываться в оставшуюся компоненту, то есть в G + K1.

Достаточность. С другой стороны, если граф H + K1 вкладывается в граф G + K1, то граф G + K1 H + K1 является реберным 1-расширением графа H + K1. Действительно, рассмотрим граф G*, получающийся из G + K1 H + K1 удалением произвольного ребра e. Если ребро e входит в компоненту G + K1, то граф G* имеет вид (G + K1 – e) H + K1, а если ребро e входит в компоненту H + K1, то граф G* имеет вид G + K1 (H +K1–e). И в том, и в другом случае граф H + K1 может быть вложен в граф G*– е.

З а м е ч а н и е. Схему сужения задачи реберного k-расширения из доказательства теоремы 3.2.1 также можно использовать и в доказательстве теоремы 2.2.1.

3.3. Неизоморфные расширения Рассмотрим задачу описания минимальных по числу вершин и ребер графов, имеющих неизоморфные минимальные реберные 1-расширения. Рассмотрим три группы графов: 1) все графы, 2) графы без изолированных вершин и 3) связные графы.

В табл. 3.1.1 приведены все 2-, 3- и 4-вершинные графы и их минимальные реберные 1-расширения, построеные с помощью вычислительного эксперимента. В этом параграфе мы приведем аналитическое доказательство минимальности реберных 1-расширений для некоторых из этих графов.

Среди графов с тремя вершинами интерес представляют только два униграфа с векторами степеней (1,1,0) и (2,1,1). Очевидно, что их минимальными реберными являются униграфы и (2,2,2).

Рассмотрим 4-вершинные графы в порядке возрастания числа ребер.

4-вершинный униграф с вектором степеней (1,1,0,0) имеет два неизоморфных минимальных реберных 1-расширения с векторами степеней (2,1,1,0) и (1,1,1,1), таким образом, справедлива ТЕОРЕМА 3.3.1. 4-вершинный униграф с вектором степеней (1,1,0,0) является минимальным графом по числу вершин и ребер среди графов, имеющих неизоморфные минимальные реберные 1-расширения. Минимальность понимается в том смысле, что не существует графа, обладающего 4-вершинные графы с двумя ребрами имеют вектора степеней (1,1,1,1) и (2,1,1,0). Непосредственной проверкой убеждаемся, что минимальное реберное 1-расширение первого есть граф с вектором степеней (2,2,2,2), а второй граф имеет два минимальных реберных 1-расширения с векторами степеней (2,2,2,0) и (3,1,1,1), однако этот граф попадает в группу 1, для которой минимальный граф уже найден.

Все остальные 4-вершинные графы имеют единственное с точностью до изоморфизма минимальное реберное 1-расширение (граф с вектором степеней (2,2,1,1) имеет минимальное реберное 1-расширение с вектором степеней (2,2,2,2), а оставшиеся пять графов имеют своим минимальным реберным 1-расширением полный граф K4).

Продолжим поиски минимальных графов с неизоморфными минимальными реберными 1-расширениями для групп 2) и 3).

5-вершиные графы без изолированных вершин имеют не менее 3 ребер.

Лишь один 5-вершинный граф без изолированных вершин имеет три ребра:

униграф G5,3 с вектором степеней (2,1,1,1,1) можно представить в виде объединения двух цепей: P3 P2. С одной стороны, по лемме 3.1.1 его минимальное реберное 1-расширение не может содержать вершин степени ниже 2, а с другой стороны, нетрудно видеть, что цикл C5 является реберным 1-расширением графа G5,3. Учитывая, что цикл С5 является униграфом, делаем вывод, что С5 является и единственным с точностью до изоморфизма минимальным реберным 1-расширением графа G5,3.

В точности три 5-вершинных графа без изолированных вершин имеют 4 ребра.

1. Граф вида C3 P2 имеет вектор степеней (2,2,2,1,1).

2. Граф P5 также имеет вектор степеней (2,2,2,1,1). По теоремам 3.1.1 и 3.1.2 цикл C5 есть единственное с точностью до изоморфизма минимальное реберное 1-расширение цепи P5.

3. Униграф G5 с вектором степеней (3,2,1,1,1), изображенный на рис. 3.3.1, а, является сверхстройным деревом с вектором цепей (2,1,1).

По лемме 3.1.1, минимальная степень вершины в любом его минимальном реберном 1-расширении не может быть ниже двух, 1расширение графа G5 отличается от него не менее чем на два дополнительных ребра. Непосредственной проверкой убеждаемся, что графы G51 и G52, изображенные на рис. 3.3.1, б, в, являются реберными 1-расширениями графа G5, причем отличаются от него в точности на два дополнительных ребра, а следовательно, являются и его минимальными реберными 1-расширениями.

Таким образом, доказана ТЕОРЕМА 3.3.2. 5-вершинный униграф G5 с вектором степеней (3,2,1,1,1) является минимальным графом по числу вершин и ребер как среди графов без изолированным вершин, так и среди связных графов, имеющих неизоморфные минимальные реберные 1-расширения. Минимальность понимается в том смысле, что не существует графа, обладающего указананным свойством, с меньшим количеством вершин и ребер.

Заметим, что граф G5 является минимальным графом по числу вершин и ребер среди связных графов, имеющих неизоморфные минимальные вершинные 1-расширения (см. теорему 2.3.6).