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

рис. 2.1.4, а). Но тогда граф G будет иметь вид K3,1 = O1 + O3. Легко видеть, что граф K3,2 не является минимальным вершинным 1-расширением графа K3,1. В самом деле, удаление любой вершины степени 2 из графа K3,2 приводит к графу C4, в котором нет вершин степени 3. На рис. 2.1.4 изображен граф K3,2, а также граф K3,1 и его минимальное вершинное 1-расширение.

{3,2}: С учетом леммы 2.1.4 граф G* будет являться кубическим графом. Любой максимальный подграф графа G* изоморфен графу G, то есть граф G* является точным вершинным 1-расширением графа G. Получаем пункт 2 из формулировки теоремы.

{3,2,1}: Аналогично степенному множеству {3,1} приходим к выводу, что граф G* должен иметь степенное множество {3,2}. Рассмотрим удаление вершины v степени 3 из графа G*. Получившийся граф будет иметь столько же ребер, сколько и граф G, следовательно, граф G* – v изоморфен графу G.

В силу произвольности выбора вершины v это означает, что каждая вершина степени 3 в графе G* соединена с одинаковым количеством вершин степени 2: с 0, 1, 2 или 3 вершинами. Первый случай можно исключить из рассмотрения, так как если вершины степени 3 не смежны ни с одной вершиной степени 2, то граф G* будет несвязным. Рассмотрим оставшиеся случаи. Обозначим для определенности через m1 количество вершин степени 3 в графе G*.

По теореме о четности числа вершин нечетной степени число m1 – четно. Через v обозначим произвольную вершину степени 3 в графе G*, а через u – произвольную вершину степени 2. Как было отмечено выше, граф G* – v изоморфен графу G.

Случай I. Рассмотрим случай, когда каждая вершина степени 3 графа G* смежна с 3 вершинами степени 2. Предположим, что в графе G* есть вершина u степени 2, смежная с двумя вершинами степени 3 (рис. 2.1.5, а). Но тогда в графе G* – v (а значит, и в графе G) будет m1 – 1 вершин степени (см. рис. 2.1.5, б), а в графе G* – u будет m1 – 2 вершин степени 3 (см.

рис. 2.1.5, в), то есть граф G не будет вкладываться в граф G* – u, что противоречит предположению.

Рис. 2.1.5. Иллюстрация к случаю I: есть вершина степени 2, смежная с двумя Итак, в графе G* каждая вершина степени 2 смежна не более чем с одной вершиной степени 3 (рис. 2.1.6, а). Это означает, что вершины степени соединены цепями, состоящими из вершин степени 2. Обозначим кратчайшее расстояние между вершинами степени 3 через d3:

Так как вершины степени 3 несмежны между собой, то d3 > 1. Более того, как было установлено ранее, в графе G* нет вершин степени 2 смежных с двумя вершинами степени 3, поэтому d3 > 2. Не ограничивая общности, будем считать, что расстояние между вершинами v1 и v2 равно d3:

Рассмотрим граф G* – v1. В этом графе будет m1 – 1 вершин степени 3, из вершины v2 будет выходить цепь длины d3 – 1 и это будет самая короткая по длине цепь (см. рис. 2.1.6, б).

Рассмотрим граф, получающийся удалением из графа G* первой вершины степени 2 в цепи, соединяющей вершину v1 с v2. В этом графе также будет m1 – 1 вершин степени 3, а из вершины v2 будет выходить цепь длины d3 – 2 (см. рис. 2.1.6, в). Очевидно, что этот граф не может содержать в себе граф G* – v1.

Рис. 2.1.6. Иллюстрация к случаю I: вершины степени 2 смежны не более чем с одной вершиной степени Случай II. Пусть каждая вершина степени 3 смежна с 2 вершинами степени 2. Рассмотрим пару вершин u1, u2 степени 2 смежных с вершиной v степени 3. Если вершины u1 и u2 смежны, то граф G* – v будет несвязный.

Следовательно, граф G* представляет собой m1/2 пар смежных вершин степени 3. С каждой вершиной степени 3 смежна пара несмежных вершин степени 2 (рис.

m1/2 – 1 пар смежных вершин степени 3 и 2 вершины степени 1, смежные с вершинами степени 2. Таким образом, расстояние от вершины степени 1 до ближайшей вершины степени 3 будет не менее 2 (см. рис. 2.1.7, б).

Рассмотрим граф G* – u, где u – произвольная вершина степени 2 (см.

рис. 2.1.7, в). Этот граф должен допускать вложение графа G (или изоморфного ему графа G* – v) и отличаться от него на одно дополнительное ребро. В графе G* вершина u смежна с одной вершиной степени 3 и с одной вершиной степени 2. Для определенности, обозначим эти вершины u1 и w. В графе G* – u, следовательно, будет m1/2 – 1 пар смежных вершин степени 3 и еще одна вершина u2 степени 3, смежная только с вершинами степени 2. Вершина w в графе G* – u1 будет единственной вершиной степени 1, причем вершина w будет смежна с вершиной степени 3. Предположим, что вложение графа G в граф G* – u построено. Тогда вершине u2 может соответствовать только вершина степени 2, и лишнее ребро – ребро, инцендентное вершине u2. Обозначим через H граф, получающийся из графа G* – u после удаления этого ребра.

Тогда граф H должен быть изоморфен графу G* – v, но в графе H вершина степени 1 смежна с вершиной степени 3, а в графе вершины степени 1 смежны вершинам степени 2. Получаем противоречие.

Случай III. Остается последняя возможность. Пусть каждая вершина степени 3 смежна с одной вершиной степени 2 и, соответственно, с 2 вершинами степени 3. Но тогда в графе G* должно быть не менее 4 вершин степени 3, и это число должно быть четным. Рассмотрим граф G* – v, где v – произвольная вершина степени 3. Этот граф должен быть изоморфен графу G. В графе G* – v одна вершина имеет степень 1, а остальные имеют степень 2 или Пусть u – произвольная вершина графа G* степени 2. Вершина u не может быть смежна с двумя вершинами степени 2, так как в этом случае в графе G* – u окажется 2 вершины степени 1, и вложение графа G будет невозможно. Таким образом, каждая вершина степени 2 смежна либо с двумя вершинами степени 3, либо с одной.

Каждая вершина степени 3 графа G* смежна с двумя другими вершинами степени 3, то есть граф, индуцированный всеми вершинами степени 3, представляет собой цикл или объединение нескольких циклов. Покажем, что последнее невозможно. Предположим противное и, для определенности, обозначим через k количество циклов, составленных из вершин степени 3. Будем рассматривать далее только эти циклы. Граф G изоморфен графу, получающемуся из G* удалением любой вершины степени 3. Удалив одну вершину степени 3, мы разомкнем один цикл, составленный из вершин степени 3, и в получившемся графе окажется на один цикл меньше: k – 1.

Относительно вершин степени 2 рассмотрим две возможности.

1. В графе G* есть вершина u степени 2, смежная с двумя вершинами степени 3, принадлежащим различным циклам (рис. 2.1.8, а). Удаление вершины u из графа G* приведет к тому, что циклов останется k – (см. рис. 2.1.8, б). Тогда в граф G* – u нельзя будет вложить граф G (см. рис. 2.1.8, в).

2. В графе G* нет вершины u степени 2, смежной с двумя вершинами степени 3, принадлежащим различным циклам. Это означает, что все вершины степени 2 смежны с одной вершиной степени 3 и с одной вершиной степени 2 (рис. 2.1.9, а). Удаление вершины u степени 2 из графа G* приведет к тому, что циклов останется k – 1, как и в графе G (см. рис. 2.1.9, б). Однако в графе G единственная вершина степени 1 будет смежна с вершиной степени 3, а в графе G* – u расстояние от единственной вершины степени 1 до вершины степени будет равно двум. Очевидно, что в граф G* – u нельзя будет вложить граф G (см. рис. 2.1.9, в).

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

степенное множество {3,2};

количество вершин степени 3 должно быть четным и больше 3;

вершины степени 2 смежны либо с двумя вершинами степени 3, либо с одной вершиной степени 3 и одной вершиной степени 2; то есть вершины степени 3 соединяются цепью, состоящей не более чем из трех ребер;

вершины степени 3 смежны с двумя другими вершинами степени 3, причем граф, индуцированный всеми вершинами степени 3, представляет собой цикл.

Получаем пункт 3 из формулировки теоремы.Теорема доказана.

Следствие. Семейство из 3-го пункта теоремы содержит графы с числом вершин 3k – 1 и 4k – 1, k > 1.

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

Заметим, что для заданного числа вершин всегда можно построить соответствующего представителя семейства. Для этого достаточно построить цикл с числом вершин 2k и каждую пару смежных вершин соединить цепью из одной или двух вершин. Удалив любую вершину степени 3 из получившегося графа, получим искомого представителя семейства. Следствие доказано.

На рис. 2.1.10 представлены все графы и их минимальные вершинные 1-расширения с числом вершин до 8, попадающие под пункт 3 доказанной теоремы.

Рис. 2.1.10. Графы со степенным множеством {3,2,1} и их МВ-1Р З а м е ч а н и е. Полученные результаты удалось перенести и на ориентированные графы (Абросимов, Моденова, 2012, а, б, 2013, а, б). Описание графов, минимальное вершинное 1-расширение которых отличается на 4 и более дополнительных ребер, приводит к рассмотрению слишком большого числа случаев. Интересной представляется задача описания графов, для которых минимальным вершинным 1-расширением является тривиальное 1-расширение. Такие графы существуют, например, почти все предполные графы имеют единственное минимальное вершинное k-расширение, которым является тривиальное k-расширение (см. параграф 2.5).

Интересно было бы установить связь конструкции минимального вершинного k-расширения с алгебраическими операциями над графам, а именно:

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

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

Будем говорить, что граф G обладает свойством дополнительности kрасширения, если дополнение хотя бы одного его минимального вершинного k-расширения является минимальным вершинным k-расширением дополнения графа G. При k = 1 будем говорить, что граф обладает свойством дополнительности расширения. Заметим, что если граф обладает свойством дополнительности k-расширения, то и его дополнение также обладает этим свойством.

Нетрудно видеть, что графы, обладающие свойством дополнительности k-расширения, существуют. Рассмотрим полный n-вершинный граф Kn и его дополнение – вполне несвязный n-вершинный граф On. При любом k > 0 эти графы имеют по теоремам 2.1.1 и 2.1.2 единственные с точностью до изоморфизма минимальные вершинные k-расширения: Kn+k для Kn и On+k для On, которые являются дополнительными графами. Далее этот случай будем называть тривиальным и не будем больше им интересоваться.

Нетривиальным случаем при k = 1 является цепь Pn. В частности, цепь P4 (см. рис. 2.1.11) является самодополнительным графом, причем единственное минимальное вершинное 1-расширение цепи P4 – цикл C5 – k-расширение являются самодополнительными графами. Следующий пример показывает, что не всякий самодополнительный граф обладает самодополнительным минимальным вершинным k-расширением.

На рис. 2.1.12 представлен самодополнительный граф C5, его единственное минимальное вершинное 1-расширение, построенное на основании результатов параграфа 2.4 этой главы, а также дополнение минимального вершинного 1-расширения.

Как будет видно далее, не каждый граф обладает свойством дополнительности расширения. В работе (Абросимов, 2001, б) приводятся все графы с числом вершин до 11, обладающие свойством дополнительности расширения. Далее решается задача описания графов, обладающих свойством дополнительности k-расширения, а потом мы увидим, что такие графы обладают и рядом других интересных свойств.

Пусть отличный от полного и вполне несвязного граф G с вектором степеней (a1, …, an) обладает свойством дополнительности расширения. Дополнение графа G – граф G' – имеет вектор степеней (bn, …, b1), G* – минимальное вершинное 1-расширение графа G из определения дополнительности расширения, а G'* (G*)' – минимальное вершинное 1-расширение графа G', являющееся дополнением для G*. Для компонент векторов степеней справедливо соотношение:

Пусть m* и m'* – число дополнительных ребер в минимальных вершинных 1-расширениях G* и G'* графа G и его дополнения соответственно. Так как G'* является дополнением для G*, то Далее, поскольку a1 и bn – наибольшие степени вершин графов G и G', то по лемме 2.1. откуда Таким образом, графы, обладающие свойством дополнительности расширения, следует искать среди графов, минимальная и максимальная из степеней вершин которых различаются не более чем на единицу. Рассмотрим оба случая.

a1 – an = 0, то есть G – однородный граф порядка a1. Так как G отличен от вполне несвязного графа, то его минимальное вершинное 1-расширение G* отличается от G на некоторое число дополнительных ребер. Из этого следует, что старшая из степеней вершин в G* будет больше a1, тогда минимальная из степеней вершин a* в дополнении графа G* будет откуда Это означает, что в минимальном вершинном 1-расширении графа G' минимальная степень вершины не больше минимальной степени вершины в G', однако в силу леммы 2.1.4 такое возможно, только если G' является вполне несвязным графом. Сформулируем полученный результат в следующем утверждении:

ТЕОРЕМА 2.1.12 (об отсутствии нетривиальных случаев среди однородных графов). Среди всех однородных графов только вполне несвязные и полные графы обладают свойством дополнительности расширения. Причем минимальные вершинные 1-расширения этих графов единственны с точностью до изоморфизма.

Вспоминая, что через «*» мы обозначали унарную операцию получения минимального вершинного 1-расширения в том случае, если оно единственно, утверждение теоремы 2.1.12 для полных графов и вполне несвязных графов можно записать в следующем виде:

a1 – an = 1. В этом случае вектор степеней графа G имеет вид (a,…,a,a – 1,…,a – 1), а графа G': (b,…,b,b – 1,…,b – 1), где b = n – a. Обозначим через k и k2 = n – k1 число вершин степени соответственно a и a – 1 в графе G. Минимальное вершинное 1-расширение графа G должно содержать не менее a дополнительных ребер, а минимальное вершинное 1-расширение графа G' – не менее b, то есть С другой стороны, суммарное число дополнительных ребер в обоих минимальных вершинных 1-расширениях в точности равно n. Тогда неравенства превращаются в точные равенства:

Рассуждая далее, получаем, что любая вершина минимального вершинного 1-расширения графа G не может иметь степень ниже a. Но по лемме 2.1.3 степень любой вершины не больше a. Следовательно, минимальные вершинные 1-расширения для G* и G'* являются однородными графами порядка a и b = n – a соответственно. Более того, из наших рассуждений следует, что эти минимальные вершинные 1-расширения единственны с точностью до изоморфизма, причем число вершин степени a – 1 в графе G в точности равно a. Аналогично для дополнения, с той разницей, что в графе G' число вершин степени b – 1 в точности равно b. Сосчитаем сумму степеней вершин графа G:

По теореме о необходимой четности суммы степеней вершин графа получаем, что при нечетном a число вершин графа должно быть также нечетным. Таким образом, можно сформулировать два необходимых условия существования нетривиального решения задачи.

ТЕОРЕМА 2.1.13 (Первое необходимое условие дополнительности расширения для графа, отличного от полного и вполне несвязного). Пусть граф G отличен от вполне несвязного и полного графов. Тогда для того, чтобы граф G обладал свойством дополнительности расширения, необходимо, чтобы граф G имел степенное множество вида {a,a – 1}, причем число вершин степени a – 1 должно в точности равняться a.

ТЕОРЕМА 2.1.14 (Второе необходимое условие дополнительности расширения для графа). Пусть G – некоторый граф, а G* – его минимальное вершинное 1-расширение. Тогда для того, чтобы граф G обладал свойством дополнительности расширения, необходимо, чтобы граф G* был однородным.

Очевидно, что второе необходимое условие не является достаточным (см. рис. 2.1.12). Однако и первое необходимое условие не является достаточным, что показывает следующий пример.

6-вершинный граф G615 с вектором степеней (2,2,2,2,1,1), удовлетворяющий условию теоремы 2.1.13, имеет три неизоморфных минимальных вершинных 1-расширения, отличающихся от графа G615 на пять дополнительных ребер, причем ни одно из них не является однородным графом. Дополнение графа G615 – граф G6107 с вектором степеней (4,4,3,3,3,3) имеет единственное с точностью до изоморфизма минимальное вершинное 1-расширение с шестью дополнительными ребрами (см. табл. 2.1.2).

Итак, из того, что граф удовлетворяет первому необходимому условию, не следует, что дополнение его минимального вершинного 1-расширения является минимальным вершинным 1-расширением дополнения, более того, не следует и что граф удовлетворяет второму необходимому условию, то есть имеет минимальным вершинным 1-расширением однородный граф. Очевидно, что обратное тоже верно: не всякий граф, минимальное вершинное 1-расширение которого является однородным графом, удовлетворяет первому необходимому условию. Оказывается, что объединение обоих необходимых условий является достаточным условием для определения нетривиального решения.

ТЕОРЕМА 2.1.15 (Критерий существования нетривиального решения задачи). Для того чтобы граф G обладал свойством дополнительности расширения, необходимо и достаточно, чтобы граф G имел степенное множество вида {b,b – 1}, причем число вершин степени b – 1 в точности равнялось b, а его минимальное вершинное 1-расширение было однородным графом порядка b. При этом и граф G, и его дополнение имеют единственные с 1-расширения, поэтому справедлива запись:

Доказательство. Достаточность. Обозначим через G* однородный граф, являющийся минимальным вершинным 1-расширением графа G. Заметим, что по n-вершинному графу G из условия однородный (n + 1)-вершинный граф порядка b можно построить единственным образом, а именно, добавив новую вершину и соединив ее с каждой вершиной порядка b – 1. По условию полученный граф является минимальным вершинным 1-расширением для графа G. Тогда удаление любой его вершины приводит к удалению в точности b дополнительных ребер, то есть каждый максимальный подграф графа G* изоморфен графу G.

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

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

Покажем, что и граф G, и его дополнение имеют единственные минимальные вершинные 1-расширения. В силу симметрии достаточно рассмотреть граф G.

По рассмотренному выше, никакое минимальное вершинное 1-расширение G* графа G не может иметь вершин со степенью ниже b. Однако вершин со степенью выше b граф G* также иметь не может, поскольку отличается от G в точности на b ребер. Наконец, только один однородный граф порядка b является минимальным вершинным 1-расширением для графа G, что и доказывает теорему.

Необходимость была доказана ранее.

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

Доказательство. Утверждение справедливо для полных и вполне несвязных графов. Для всех остальных графов, обладающих свойством дополнительности расширения, справедливость утверждения следует из доказательства теоремы 2.1.15.

Следствие 2. Каждый граф, обладающий свойством самодополнительности расширения, имеет 4k вершин и степенное множество вида {2k,2k – 1}.

Доказательство. Пусть n-вершинный граф G обладает свойством самодополнительности расширения. Тогда по теореме 2.1.15 его степенное множество имеет вид {b,b – 1}, причем в точности b вершин имеют степень b – 1. Поскольку граф G самодополнительный, то n 1 b = b 1, откуда n = 2b. Таким образом, b вершин графа G имеют степень вершин b, а остальные b вершин имеют степень b – 1. Поскольку либо b, либо b – 1 нечетно, а число нечетных вершин графа должно быть четно, то из этого следует, что b – четное, то есть b = 2k.

З а м е ч а н и е. Из теоремы 2.1.15 следует очевидный алгоритм для поиска всех n-вершинных графов, обладающих свойством дополнительности расширения. В работе (Абросимов, 2001, б) приводятся все графы с числом ширения.

ТЕОРЕМА 2.1.16. При k > 1 только полный и вполне несвязный графы обладают свойством дополнительности k-расширения.

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

Предположим противное. Пусть отличный от полного и вполне несвязного граф G имеет вектор степеней (a1,…,an), дополнение G – граф G' – имеет вектор степеней (bn,…,b1). Далее пусть Gk* и G'k* – минимальные вершинные k-расширения для графов G и G', являющиеся дополнениями друг друга, а их вектора степеней обозначим ( a1k,..., a nk+ k ) и (bn + k,..., b1 ). Для компонент векторов степеней справедливо соотношение:

аналогично Минимальная степень вершины в графе G равна an, тогда по лемме 2.1.4 минимальная степень вершины в графе G* должна быть не меньше an + k. Откуда старшая степень вершины в G'* То есть старшая степень вершины в минимальном вершинном k-расширении графа G' (аналогично и для графа G) равна старшей степени вершины в его минимальном вершинном k-расширении. Далее получаем:

то есть минимальная степень вершины в минимальном вершинном k-расширении в точности на k больше минимальной степени вершины графа.

Обозначим через m и m' число дополнительных ребер минимальных вершинных k-расширений Gk* и G' k *. Оценим число дополнительных ребер минимального вершинного k-расширения графа G. Поскольку старшая степень вершины и в G, и в Gk* равна a1, то число дополнительных ребер по лемме 2.1.3 для Gk* не может быть менее a1k: m a1k. Аналогично для дополнения графа G оценим снизу число дополнительных ребер: m' bnk. Поскольку общее число дополнительных ребер должно быть в точности равно то получаем:

далее откуда Последнее неравенство выполняется только при k = 1. Полученное противоречие доказывает утверждение теоремы.

Понятие точного вершинного k-расширения было введено Харари и Хейзом в работе (Harary, Hayes, 1996). Там же приводятся следующие примеры графов, обладающих точным вершинным k-расширением: минимальное вершинное k-расширение полного n-вершинного графа Kn – полный (n + k)вершинный граф Kn+k – является его точным вершинным k-расширением;

1-расширением для n-вершинной цепи Pn. Однако точное вершинное k-расширение есть не у каждого графа. Например, при n > 3 минимальное вершинное 1-расширение цикла Сn не является его точным расширением. Очевидно, что только однородный граф может являться точным вершинным k-расширением, но, как показывает случай с циклом, это условие не является достаточным. Далее в работе (Harary, Hayes, 1996) Харари и Хейз ставят вопрос описания точных вершинных k-расширений графов. Из результатов, полученных Раджави и Розенталем (Radjavi, Rosenthal, 1972), можно сделать вывод, что для неориентированных графов никакой граф кроме On и Kn не может быть точным вершинным k-расширением при k > 1. Для ориентированных графов ситуация оказывается более интересной, это будет подробнее рассмотрено в параграфе 2.7. Неожиданным является обнаруженное в ходе вычислительного эксперимента (Абросимов, Долгов, 2007, 2008) и описанное затем А. А. Долговым в работе (Долгов, 2010) семейство турниров, которое обладает особым свойством. Неориентированный граф может иметь точное вершинное k-расширение либо только при k = 1, либо при всех натуральных значениях k (полные и вполне несвязные графы). Турниры из описанного А. А. Долговым семейства имеют точное вершинное 1- и 2-расширение, но не имеют точного вершинного k-расширения при k > 2.

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

ТЕОРЕМА 2.1.17. Граф G тогда и только тогда имеет точное вершинное k-расширение, когда он обладает свойством дополнительности kрасширения.

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

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

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

При k = 1 имеем следствие 1 из теоремы 2.1.15, согласно которому минимальное вершинное 1-расширение графа со свойством дополнительности 1-расширения является и его точным вершинным 1-расширением.

При k > 1 только полные и вполне несвязные графы по теореме 2.1. обладают свойством дополнительности k-расширения. Как уже было отмечено, эти графы имеют и точное k-расширение.

Следствием из теорем 2.1.15, 2.1.16 и 2.1.17 является следующее утверждение:

ТЕОРЕМА 2.1.18. Если n-вершинный граф G имеет точное вершинное k-расширение G*, то при n > 1 граф G* является единственным с точностью до изоморфизма минимальным вершинным k-расширением графа G.

Заметим, что если бы существовал граф, имеющий неизоморфные точные вершинные 1-расширения, то он не был бы вершинно реконструируемым, то есть его нельзя было бы с точностью до изоморфизма восстановить по списку максимальных подграфов. Теорема 2.1.18 сформулирована для неориентированных графов, а для орграфов подобный результат пока неизвестен. Удалось показать (Абросимов, Долгов, 2011), что все известные семейства орграфов, имеющих точные вершинные 1-расширения, удовлетворяют теореме 2.1.18. Более того, все семейства Стокмейера нереконструируемых орграфов (Stockmeyer, 1981) не являются точными вершинными 1-расширениями.

ТЕОРЕМА 2.1.19. Граф G является точным вершинным 1-расширением тогда и только тогда, когда он является вершинно-симметрическим.

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

Достаточность. Пусть граф G является точным вершинным 1-расширением. Тогда для любых двух вершин u и v графы G – u и G – v изоморфны.

В общем случае из того, что G – u изоморфен G – v, не следует, что вершины u и v подобны (Харари, 2009). Покажем, что в случае точных вершинных 1расширений это выполняется.

Так как G является точным вершинным 1-расширением, то граф G – однородный некоторого порядка d. Граф G – u изоморфен G – v, и пусть f подходящий изоморфизм. Пусть u1,…,ud – вершины степени d – 1 графа G – u, а v1,…,vd соответственно подобные им вершины в графе G – v. Вершина u смежна с вершинами u1,…,ud в графе G и только с ними, а вершина v смежна с вершинами v1,…,vd и только с ними. Обозначим множество вершин u1,…,ud через (u), а множество вершин v1,…,vd через (v).

Покажем, что вершины u и v подобны. В самом деле, рассмотрим отоv, x = u нозначным отображением. Покажем, что f * – автоморфизм графа G. Рассмотрим пару вершин w1 и w2 графа G. Рассмотрим три случая:

1) w1 и w2 отличны от u. Тогда (w1, w2) (f *(w1), f *(w2)) ;

2) одна из вершин – u (пусть для определенности w1 = u), а другая (то есть w2) смежная с ней в графе G вершина, то есть w2 (u). Тогда и в этом случае выполняется (w1, w2) (f *(w1), f *(w2)) ;

3) одна из вершин – u (пусть опять для определенности w1 = u), а другая (то есть w2) не смежная с ней в графе G вершина, то есть w (u). Тогда (w1, w2), однако f *(u) = v, а f *(w2) (v), а поскольv, f *(w2)), Итак, f * является изоморфизмом, следовательно, вершины u и v подобны.

Таким образом, всякий вершинно-симметрический граф является точным вершинным 1-расширением, однако не всякий такой граф является точным реберным 1-расширением. На рис. 2.1.13, а приведен минимальный по числу вершин вершинно-симметрический граф, не являющийся точным реберным 1-расширением. Интересно, что этот граф также является минимальным вершинным 1-расширением цикла Рис. 2.1.13. Графы ТВ-1Р: не являющийграф K3,3 является минимальным реберся (а) и являющийся (б) ТР-1Р является минимальным вершинным 1-расширением цикла C5.

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

Как мы уже обсуждали в параграфе 1.4, при анализе сложности рассматриваются задачи распознавания свойств, а задача поиска будет иметь не меньшую сложность.

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

или «нет».

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

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

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

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

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

Покажем, что задача ВЕРШИННОЕ 1-РАСШИРЕНИЕ NP. Для этого нужно показать, что с помощью алгоритма полиномиальной сложности можно убедиться в правильности решения, которое было найдено с помощью некоторого недетерминированного алгоритма.

Пусть граф G содержит n, а граф H содержит m вершин, очевидно, что если G является вершинным 1-расширением, то n m + 1. Обозначим вершины графа G через v1, …, vn. Тогда недетерминированному алгоритму необходимо угадать n последовательностей Vi по m вершин из множеств V – vi, для каждой из которых далее за полиномиальное время можно проверить, что определяемая этой последовательностью биекция является вложением. В общем случае, для произвольного k необходимо будет указать C nk последовательностей для всех возможных наборов из k удаляемых вершин графа G: для фиксированного k эта величина будет полиномом от n и может быть оценена как O(nk).

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

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

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

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

Рассмотрим далее оптимизационный вариант задачи.

НЕПРИВОДИМОЕ k-РАСШИРЕНИЕ

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

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

Задача НЕПРИВОДИМОЕ k-РАСШИРЕНИЕ является, очевидно, не менее трудной, чем задача ВЕРШИННОЕ k-РАСШИРЕНИЕ: для проверки того, что граф G является неприводимым вершинным k-расширением графа H, необходимо установить, что 1) G является вершинным k-расширением графа H (NP-полная задача) и 2) никакая часть G, получающаяся удалением одного ребра, не является вершинным k-расширением H (задача из co-NPC).

В некоторых случаях можно избежать проверки пункта 2, используя аналитические оценки на минимальное количество дополнительных ребер в k-расширении графа. Так, например, леммы из параграфа 2.1 позволяют получить такую оценку в некоторых случаях.

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

Это означает, что задача НЕПРИВОДИМОЕ k-РАСШИРЕНИЕ NP. Легко увидеть, что и обратная задача также не допускает полиномиальной проверки, поэтому задача НЕПРИВОДИМОЕ k-РАСШИРЕНИЕ co-NP. Аналогичные рассуждения применимы и к задаче МИНИМАЛЬ-НОЕ kРАСШИРЕНИЕ. Заметим, что для проверки, является ли заданный граф неприводимым или минимальным расширением, достаточно полиномиального объема памяти, то есть эти задачи принадлежат классу сложности PSPACE.

2.3. Неизоморфные расширения Могут ли графы иметь неизоморфные минимальные вершинные k-расширения?

Как было показано в параграфе 2.1, все 2-, 3- и 4-вершинные графы имеют единственное с точностью до изоморфизма минимальное вершинное 1-расширение. Цепи, полные и вполне несвязные графы также имеют единственное минимальное вершинное 1-расширение. Однако для многих графов такая ситуация, как мы увидим в дальнейшем, не характерна. Так уже среди 5-вершинных графов 9 графов имеют более одного минимального вершинного 1-расширения. В следующем параграфе будут описаны различные схемы 1-расширений циклов.

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

ТЕОРЕМА 2.3.1. Графы G*1 и G*2, изображенные на рис. 2.3.1, б, в, являются неизоморфными минимальными вершинными 1-расширениями 5-вершинного несвязного графа G0,3 с двумя ребрами и двумя изолированными вершинами, изображенного на рис. 2.3.1, а.

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

По лемме 2.1.3 число дополнительных ребер любого минимального вершинного 1-расширения графа G0,3 не может быть меньше 2, следовательно, G*1 и G*2 являются неизоморфными минимальными вершинными 1-расширениями графа G0,3. Нетрудно убедиться, что других минимальных вершинных 1-расширений у графа G0,3 нет.

ТЕОРЕМА 2.3.2. Графы G*1 и G*2, изображенные на рис. 2.3.2, б,в, являются неизоморфными минимальными вершинными 1-расширениями 5-вершинного несвязного графа G2,3 с тремя ребрами, изображенного на рис. 2.3.2, а.

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

Покажем, что они отвечают условию 3.

Граф G2,3 не имеет изолированных вершин, следовательно, по лемме 2.1.1 степень любой вершины в некотором его минимальном вершинном 1-расширении G* не может быть меньше 2, и, значит, количество ребер G* не меньше (2 + 2 + 2 + 2 + 2 + 2)/2 = 6. Исследуемые графы имеют в точности указанное количество ребер.

ТЕОРЕМА 2.3.3. Графы G*51, G*52, G*53 и G*54, изображенные на рис. 2.3.3, б, в, г, д, являются неизоморфными минимальными вершинными 1расширениями связного графа G5 с четырьмя ребрами и вектором степеней (3,2,1,1,1), изображенного на рис. 2.3.3, а.

Доказательство. Заметим, что граф G5 является сверхстройным деревом с вектором цепей (2,1,1). Непосредственной проверкой можно убедиться, что все четыре графа G*51, G*52, G*53 и G*54 отвечают условиям 1 и 2 из определения минимального вершинного 1-расширения, кроме того, они неизоморфны. В самом деле, вектора степеней графов G*51, G*52, G*53 и G*54 имеют вид соответственно (4,4,2,2,2,2), (4,3,3,2,2,2), (3,3,3,3,2,2) и (3,3,3,3,2,2). У графа G*53 обе вершины степени 3, смежные с одной вершиной степени 2, смежны между собой, а у графа G*54 – нет. Покажем, что все эти графы отвечают и условию 3. Пусть G* – минимальное вершинное 1-расширение G5.

Граф G5 не имеет изолированных вершин, а одна его вершина – степени 3, следовательно, степень любой вершины графа G* должна быть по лемме 2.1. не ниже 2, и по лемме 2.1.2 как минимум две вершины должны иметь степень не ниже 3. Граф G5 не удовлетворяет условию теоремы 2.1.11, поэтому граф G* не может отличаться от графа G на три дополнительных ребра. Дадим прямое доказательство этому утверждению без использования упомянутой теоремы.

Пусть G* отличается от графа G5 на 3 дополнительных ребра. Из вышесказанного получается, что единственно возможным вектором степеней графа G* может быть вектор (3,3,2,2,2,2). Предположим, что вершины со степенью 3 смежны. Тогда максимальный подграф, получающийся при удалении из G* одной из этих вершин, не будет содержать ни одной вершины степени выше 2, и поэтому вложение в него графа G5 невозможно. Итак, вершины степени 3 в графе G* несмежны. Каждая из них смежна с тремя вершинами степени 2. Всего таких вершин четыре и, значит, существуют две вершины степени 2, каждая из которых является смежной с обеими вершинами степени 3. Тогда максимальный подграф, получающийся из G* удалением одной из этих вершин, не будет содержать вершин степени выше 2, и, следовательно, граф G5 в него вкладываться не будет.

Таким образом, не существует графа G* с 7 ребрами, который бы являлся минимальным вершинным 1-расширением графа G5, и, следовательно, графы G*51, G*52, G*53 и G*54 являются минимальными вершинными 1-расширениями графа G5.

ТЕОРЕМА 2.3.4. Граф G0,3 из теоремы 2.3.1 является минимальным среди всех графов, содержащих одну или более изолированных вершин, имеющих неизоморфные минимальные вершинные 1-расширения, в том смысле, что не существует графа из указанного класса с меньшим числом вершин или меньшим числом ребер, обладающего рассматриваемым свойством.

Доказательство. Как мы уже видели, любой граф с числом вершин меньшим 5 имеет единственное с точностью до изоморфизма минимальное вершинное 1-расширение.

Истинность второго утверждения теоремы о том, что не существует графа с одним ребром и обладающего указанным свойством, очевидна.

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

Доказательство. Как мы уже видели, любой граф с числом вершин меньшим 5 имеет единственное с точностью до изоморфизма минимальное вершинное 1-расширение.

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

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

Доказательство. Как мы уже видели, любой граф с числом вершин меньшим 5 имеет единственное с точностью до изоморфизма минимальное вершинное 1-расширение. Так как граф G5 является деревом, то не существует связного 5-вершинного графа с меньшим числом ребер, чем у G5, однако следует рассмотреть другие 5-вершинные деревья, которые имеют такое же число ребер, как и G5. Это цепь P5 и звезда K1,4.

По теореме 2.1.4 цепь P5 имеет единственное с точностью до изоморфизма минимальное вершинное которым является цикл C6.

Звезда K1,4 также имеет единственное с точностью до изоморфизма минимальное вершинное 1-расширение, которым является ее тривиальное 1расширение. В этом можно убедиться непосредственно, а общее доказательство для любых звезд можно посмотреть в параграфе 2.6.

Следствие. Граф G0,3 из теоремы 2.3.1 является минимальным среди всех графов, имеющих неизоморфные минимальные вершинные 1-расширения, в том смысле, что не существует графа с меньшим числом вершин или меньшим числом ребер, обладающего неизоморфными минимальными вершинными 1-расширениями.

Заметим, что вершинные 1-расширения дерева из теоремы 2.3.3, изображенные на рис. 2.3.3, б и 2.3.3, г, являются Т-неприводимыми. По каталогу Т-неприводимых 1-расширений С. Г. Курносовой (Курносова, 2003) можно убедиться, на рис. 2.3.4, а показан минимальный по числу вершин и ребер граф K 2 O1, имеющий неизоморфные Т-неприводимые 1-расширения. Легко видеть, что 1-расширение, изображенное на рис. 2.3.4, в, также является минимальным вершинным 1-расширением с 1 дополнительным ребром.

В работе (Hayes, 1976) Хейз предложил процедуру для построения минимального вершинного k-расширения цикла. В работе (Harary, Hayes, 1996) Харари и Хейз поставили вопрос о существовании минимальных вершинных 1-расширений, 1-расширениям, предложенным ранее Хейзом. Расширениям циклов посвящено достаточно много работ: (Paoli et al., 1984, 1986 ; Mukhopadhyaya, Sinha, 1992 ; Sung et al., 1998, 2000, 2001 ; Wang et al., 1998, 2000 ; Hung et al., 1999, 2000, 2001 ; Абросимов, 2000, а, 2001, а; Tsai, Li, 2007 ; Hsu, Lin, 2009).

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

ТЕОРЕМА 2.4.1 (Hayes, 1976). Минимальное вершинное 1-расширение n-вершинного цикла Cn содержит не менее дополнительных ребер.

Доказательство. Пусть G* = (V*, *) является минимальным вершинным 1-расширением n-вершинного цикла Cn. Согласно лемме 2.1.4 степень каждой вершины в G* не ниже 3, а при четном значении n степень одной из вершин в силу теоремы о необходимой четности суммы степеней вершин будет строго больше 3. Таким образом, можно записать Поскольку число ребер n-вершинного цикла равно n, то, объединяя оба случая, получаем требуемую оценку снизу для числа дополнительных ребер минимального вершинного 1-расширения цикла.

ТЕОРЕМА 2.4.2 (Hayes, 1976). Гамильтоновы графы, изображенные на рис. 2.4.1, представляют собой минимальные вершинные 1-расширения nвершинного цикла при n четном (рис. 2.4.1, а) и n нечетном (рис. 2.4.1, б).

Доказательство. Обозначим n-вершинный граф, построенный по рассматриваемым схемам, через H(n). В графе, построенном по схеме, представленной на рис. 2.4.1, а, одна вершина имеет степень 4, а все остальные – степень 3. В графе, построенном по схеме, представленной на рис. 2.4.1, б, все вершины имеют степень 3. Таким образом, число дополнительных ребер расn + сматриваемых графов в точности равно. Непосредственной проверкой можно убедиться в том, что изображенные на рисунке графы являются вершинными 1-расширениями соответствующих циклов.

Следствие 1. Минимальное вершинное 1-расширение n-вершинного цикла имеет вектор степеней (4, 3, 3, …, 3) при четном n и (3, …, 3), при нечетном n.

Следствие 2. Минимальное вершинное 1-расширение n-вершинного цикла Cn содержит в точности ребер или дополнительных ребер.

На рис. 2.4.2, а–е представлены минимальные вершинные 1-расширения циклов, построенные по схемам Хейза.

Рис. 2.4.2. МВ-1Р циклов C4 (а), C5 (б), C6 (в), C7 (г), C8 (д) и C9 (e) Задача поиска минимальных вершинных k-расширений циклов вызвала большой интерес, обусловленный практической значимостью, и был предложен ряд альтернативных схем их построения. Граф называется k-вершинно-гамильтоновым1, если он является гамильтоновым после удаления любых k вершин и инциндентных им ребер. Граф называется k-реберно-гамильтоновым2, если он является гамильтоновым после удаления любых k ребер. Граф называется k-гамильтоновым3, если он является гамильтоновым после удаления любых k вершин и/или ребер. (Вершинно-, реберноk-гамильтонов граф называется оптимальным, если он имеет минимально k-гамильтоновых графов с тем же числом вершин. Очевидно, что следующие пары понятий являются синонимами:

k-вершинно-гамильтонов – вершинное k-расширение цикла;

оптимальный k-вершинно-гамильтонов – минимальное вершинное k-расширение цикла;

k-реберно-гамильтонов – реберное k-расширение цикла;

оптимальный k-реберно-гамильтонов – минимальное реберное k-расширение цикла;

k-гамильтонов – комбинированное k-расширение цикла;

оптимальный k-гамильтонов – минимальное комбинированное k-расширение цикла.

В этом параграфе мы рассмотрим вершинные k-расширения циклов, а реберные будут рассмотрены в параграфе 3.4 следующей главы.

Махопадхья и Синха в работе (Mukhopadhyaya, Sinha, 1992) предложили собственную схему построения 1-гамильтоновых графов M(k), то есть минимальных вершинных и реберных 1-расширений циклов. Пусть k и t натуральные числа, причем k 4. Определим семейство графов B(i, t) (рис. 2.4.3):

k-vertex-hamiltonian.

k-edge-hamiltonian.

k-hamiltonian.

четного k строится следующим образом (при t = 0 для удобства будем писать yi = xil,0 = xir, 0 ).

1. При k = 6t + 4 – граф M(k) строится влением вершин z0, z1, z2 в вершину z 2. При k = 6t + 6 – граф M(k) строится из B(0, t + 1), B(1, t) и B(2, t) отождествлением вершин z0, z1, z2 в вершину z и добавлением ребер {x0l,t +1, x1r,t },{x1l,t, x2r,t },{x2,t, x0r,t +1}.

3. При k = 6t + 8 – граф M(k) строится из B(0, t + 1), B(1, t + 1) и B(2, t) отождествлением вершин z0, z1, z2 в вершину z и добавлением ребер {x0l,t +1, x1r,t +1},{x1l,t +1, x2r,t },{x2,t, x0r,t +1}.

Граф M(k) для нечетного k 5 строится следующим образом.

1. При k = 8t + 5 – граф M(k) строится из четырех B(i, t) для i = 0, 1, 2, отождествлением вершин z0, z1, z2 и z3 в вершину z и добавлением ребер {x0,t, x1r,t },{x1l,t, x2,t },{x2,t, x3r,t },{x3,t, x0r,t }.

t + 1) отождествлением вершин z0, z1, z2 и z3 в вершину z и добавлением ребер {x0,t +1, x1r,t },{x1l,t, x2r,t },{x2,t, x3r,t },{x3,t, x0r,t +1}.

двух B(j, t) для j = 2, 3 отождествлением вершин z0, z1, z2 и z3 в вершину z и добавлением ребер {x0, t +1, x1r, t +1}, {x1l,t +1, x2,t }, {x2, t, x3, t }, 4. При k = 8t + 11 – граф M(k) строится из трех B(i, t + 1) для i = 0, 1, 2 и B(3, t) отождествлением вершин z0, z1, z2 и z3 в вершину z и добавлением ребер {x0,t +1, x1r,t +1},{x1l,t +1, x2r,t +1},{x2,t +1, x3r,t },{x3l,t, x0r,t +1}.

ТЕОРЕМА 2.4.3 (Mukhopadhyaya, Sinha, 1992). Графы M(k) являются минимальными вершинными и реберными 1-расширениями соответствующего цикла при k 4.

На рис. 2.4.4 и 2.4.5 представлены минимальные вершинные 1-расширения циклов, построенные по схемам Махопадхья и Синха.

Рис. 2.4.4. МВ-1Р циклов C4 (а), C5 (б), C6 (в), C7 (г), C8 (д) и C9 (е) Рис. 2.4.5. Графы М(4) (а), М(5) (б), М(18) (в), М(25) (г) Можно заметить, что графы M(4), M(5), M(6) и М(8) изоморфны минимальным вершинным 1-расширениям, построенным по схемам Хейза. А при больших значениях справедлива ТЕОРЕМА 2.4.4. Графы M(k) и H(k) при k = 7 и k > 8 неизоморфны.

Доказательство. Для четного n = 2k мы имеем графы H(2k) и M(2k). В графе H(2k) при k > 2 содержится ровно два 3-вершинных цикла, а в графе M(2k) при k > 4 – не менее трех.

Рассмотрим нечетное n = 2k + 1. Видно, что в графе H(2k + 1) вершины, смежные с вершиной степени 4, разбиваются на пары смежных вершин, а в графе M(2k + 1) такое возможно лишь при k = 2.

Ванг, Хунг и Хсу (Wang et al., 1998) предложили еще одно семейство W(k) минимальных вершинных и реберных 1-расширений циклов при натуральных значениях k. Семейство W(k) строится из 2k + 1 графов B(i, k) для 0 i 2k соединением вершин zi по циклу и добавлением ребер {x2 k,k, x0r,k } и {xil,k, xir+1,k } для всех 0 i 2k – 1.

Таким образом, семейство W(k) дает минимальные вершинные 1-расширения цикла Cn при n = 11, 29, 55, 89, … Последнее семейство CT(s), которое мы рассмотрим, называется «рождествеские елки»4. Это семейство предложили Хунг, Хсу и Санг (Hung et al., 1999).

Определим сначала вспомогательное семейство ST(s) = (V,, u, l, r), где V множество вершин, – множество ребер, u V – корневая вершина, l V – левый узел, r V – правый узел и s 2:

1) ST(2) – полный граф K3 с вершинами u, l, r;

2) при s 2 ST(s) строится из корня u и двух копий ST(s – 1) в качестве левого и правого поддеревьев: STl (s – 1) = (V1, 1, u1, l1, r1) и STr (s – Граф семейства CT(s) строится из графа STl(s) = (V1, 1, u1, l1, r1) и STr(s + 1) = (V2, 2, u2, l2, r2). CT(s) = (V, ), где 2 {{u1, u 2 }, {l1, r2 }, {r1, l 2 }}. Количество вершин в графе CT(s) равно 2 – 1 + 2s+1 – 1 = 32s – 2. Граф CT(2) имеет 10 вершин и изоморфен графуM(10).

На рис. 2.4.8 приведен граф CT(3).

ТЕОРЕМА 2.4.6 (Хунг, Хсу и Санг, 1999). Графы CT(k) являются минимальными вершинными и реберными 1-расширениями цикла при k 1.

Таким образом, семейство CT(k) дает минимальные вершинные 1-расширения цикла Cn при n = 9, 21, 45, 93, … ТЕОРЕМА 2.4.7 (Абросимов, 2000, а). Гамильтоновы графы, изображенные на рис. 2.4.9, представляют собой минимальные вершинные 1-расширения n-вершинного (n > 3) цикла при n четном (рис. 2.4.9, а) и n нечетном (рис. 2.4.9, б).

Доказательство. Обозначим через A(n) n-вершинный граф, построенный по рассматриваемым схемам. Покажем, что графы A(n) являются расширениями соответствующих циклов. Достаточно проверить, что для любой не входит.

Рассмотрим случай, когда n – четно.

Изучим удаление вершин v1,…,vn/2. При удалении v1, vn или vn+1 циклы очевидны. Для vi, 1 < i < n/2 + 1 цикл получается обходом графа «змейкой», начиная с v1 и заканчивая vn+1:

• v1v2vn/2+1vn/2+2v3…vi-1vn/2+i-1vn/2+ivn/2+i+1vi+1…vn/2vn-1vnvn+1, когда i и n/2 нечетные;

v1v2vn/2+1vn/2+2v3…vi-1vn/2+i-1vn/2+ivn/2+i+1vi+1…vn-1vn/2vnvn+1, когда i нечетное, n/2 – четное;

• v1vn/2+1 v2v3vn/2+2…vi-1vn/2+i-1vn/2+ivn/2+i+1vi+1…vn/2vn-1vnvn+1, когда i и n/2 четные;

v1vn/2+1 v2v3vn/2+2…vi-1vn/2+i-1vn/2+ivn/2+i+1vi+1…vn-1vn/2vnvn+1, когда i четное, n/ – нечетное.

Аналогично строятся циклы для вершин vi, n/2 < i < n.

Рассмотрим случай, когда n – нечетно. Пусть удалена вершина vi. Начинаем строить цикл с вершины v1 или v2, дальше идем «змейкой» по всем вершинам графа, обходя vi, до vn-1 или v(n+1)/2.

Оканчивается цикл одной из следующих цепочек:

• vn-1vnv(n+1)/2vn+1v1, если начинали из v1 и дошли до vn-1, • vn-1vn+1v(n+1)/2vn v2, если начинали из v2 и дошли до vn-1, • v(n+1)/2vn vn-1vn+1v1, если начинали из v1 и дошли до v(n+1)/2, • v(n+1)/2vn+1vn-1vnv2, если начинали из v2 и дошли до v(n+1)/2.

Рассматриваемые графы имеют такое же количество ребер, что и соответствующие графы из теоремы 2.4.2, следовательно, они также являются минимальными вершинными 1-расширениями.

Видно, что при четном n предлагаемое минимальное вершинное 1-расширение является гамильтоновым графом.

Для случая, когда n нечетно, минимальное вершинное 1-расширение также является гамильтоновым графом. В самом деле, начнем строить цикл с вершины v1 и пойдем змейкой: v1,v(n+1)/2+1,v3,v4,v(n+1)/2+2,…, окончанием цикла будет либо v(n+1)/2,vn+1,vn-1,vn,v2,v1, либо vn-1,vn+1,v(n+1)/2,vn,v2,v1.

Заметим, что при n 5 предлагаемые построения изоморфны построениям Хейза. На рис. 2.4.10 изображены некоторые минимальные вершинные 1-расширения циклов, построенные по описанной схеме.

Рис. 2.4.10. МВ-1Р циклов C4 (а), C5 (б), C6 (в), C7 (г), C8 (д) и C9 (е) ТЕОРЕМА 2.4.8. Графы A(n) и H(n) при n > 6 неизоморфны.

Доказательство. Для нечетного n = 2k + 1 имеем графы A(2k + 1) и H(2k + 1). Видно, что единственная вершина степени 4 в графе A(2k + 1) является вершиной двух треугольников с общей стороной: vn/2vn+1vn и vn/2vn-1vn, а в графе H(2k + 1) такое возможно лишь при n = 5.

Для четного n = 2k имеем графы A(2k) и H(2k). Видно, что граф H(2k) содержит два цикла длины 3: vn/2+1v1v2 и vnvn+1v(n+1)/2, что возможно в графе A(2k) лишь при n = 4 и n = 6.

ТЕОРЕМА 2.4.9. Графы A(n) и M(n) при n > 7 неизоморфны.

Доказательство. Для нечетного n = 2k + 1 имеем графы A(2k + 1) и H(2k + 1). Видно, что единственная вершина степени 4 в графе A(2k + 1) является вершиной двух треугольников с общей стороной: vn/2vn+1vn и vn/2vn-1vn, а в графе M(2k + 1) такое возможно лишь при n = 5 и n = 7.

Для четного n = 2k имеем графы A(2k) и M(2k). Видно, что граф M(2k) содержит циклы длины 3, а граф A(2k) при n >6 циклов длины 3 не содержит.

ТЕОРЕМА 2.4.10. Любой цикл Cn при n > 5 имеет, по крайней мере, два неизоморфных минимальных вершинных 1-расширения.

Доказательство. Как следует из теорем о неизоморфности графов семейств A(n), H(n) и M(n), циклы C6 и C7 имеют, по крайней мере, по два неизоморфных минимальных вершинных 1-расширения – графы H(7) и A(7) или изоморфный M(7) и графы A(8) и H(8) или изоморфный ему M(8). А при n > 8 цикл Cn имеет, по крайней мере, три неизоморфных минимальных вершинных 1-расширения – графы A(n + 1), H(n + 1) и M(n + 1).

Таким образом, получен принципиальный ответ на вопрос, касающийся единственности предложенных Хейзом минимальных вершинных 1-расширений для цикла. Следствие 1 из теоремы 2.4.2 позволяет использовать алгоритм 2.1.2 для построения всех минимальных вершинных 1-расширений nвершинного цикла. Это особенно актуально для циклов с нечетным числом вершин, так как известны алгоритмы, которые позволяют относительно эффективно строить кубические графы (Brinkmann, 1996 ; Brinkmann, 2011).

Следует отметить, что количество неизоморфных минимальных вершинных 1-расширений цикла возрастает при росте n. Так, например, если циклы C6 и С7 имеют лишь по два неизоморфных минимальных вершинных 1-расширения, то уже для 8-вершинного цикла их известно 10. Существенно возрастает и число графов, перебираемых в алгоритме 2.1.2 для поиска минимального вершинного 1-расширения. Так, при нечетном n минимальным вершинным 1-расширением n-вершинного цикла является кубический граф, то есть однородный граф порядка 3. Согласно Риду (Read, 1958) число M всех помеченных кубических графов с 2n вершинами выражается следующей асимптотической формулой:

Точное число кубических (2n)-вершинных графов для n = 2,…,15 составляет: 1, 2, 6, 21, 94, 540, 4207, 42110, 516344, 7373924, 118573592, 2103205738, 40634185402, 847871397424 5. Так как минимальное вершинное 1-расширение будет связным графом, то интерес представляют только связные кубические графы. Их число для n = 2,…,15 составляет: 1, 2, 5, 19, 85, 509, 4060, 41301, 510489, 7319447, 117940535, 2094480864, 40497138011, 845480228069 6. Заметим, что известны алгоритмы (Brinkmann, 1996; Brinkmann, 2011), которые позволяют на персональном компьютере построить все такие кубические графы. Для векторов степеней вида (4, 3, …, 3) подобные алгоритмы и данные не известны. На основе вычислительного эксперимента начало последовательности для числа неизоморфных реализаций вектора См. последовательность A005638: http://oeis.org/A См. последовательность A002851: http://oeis.org/A степеней (4, 3, …, 3) имеет вид: 1, 4, 27, 208, 1958, 21879 (Абросимов, Кузнецов, 2012).

Минимальные вершинные 1-расширения циклов, построенные в теоремах 2.4.2, 2.4.3, 2.4.5, 2.4.6 и 2.4.7, являются гамильтоновыми. Возникает вопрос о существовании у циклов негамильтоновых минимальных вершинных 1-расширений. Этот вопрос тесно связан с исследованиями гипогамильтоновых графов и кубических графов, то есть однородных графов порядка 3. Дадим два определения (см. (Aldred et al., 1997)).

Граф, каждый максимальный подграф которого является гамильтоновым, называется гипоциклическим. Негамильтонов граф, каждый максимальный подграф которого является гамильтоновым, называется гипогамильтоновым.

Очевидно, что любое минимальное вершинное 1-расширение цикла является гипоциклическим графом, а любое негамильтоново минимальное вершинное 1-расширение цикла будет гипогамильтоновым графом. Поскольку n-вершинный цикл содержится в любом n-вершинном гамильтоновом графе, то каждый гипогамильтонов и гипоциклический граф является вершинным 1-расширением цикла, не обязательно минимальным.

В работе (Абросимов, 2001, а) приводятся все минимальные вершинные 1-расширения для циклов с числом вершин до 11. В табл. 2.4.1 указано число неизоморфных минимальных вершинных 1-расширений для циклов с числом вершин до 17 (в 1999–2000 гг. автором были обработаны циклы с числом вершин до 13, последующие результаты получены в 2012 г.

Н. А. Кузнецовым (Абросимов, Кузнецов, 2012)).

Вектор степе- Число реализаций Количество неизоней МВ-1Р Cn вектора степеней морфных МВ-1 Cn Вопрос о существовании гипогамильтоновых графов был поставлен Сусельером в работе (Sousselier, 1963). Годин, Херц и Росси показали (Gaudin et al., 1964), что наименьшим гипогамильтоновым графом является граф Петерсена (см. рис. 2.4.11). Позднее исчерпывающий компьютерный поиск показал, что не существует гипогамильтоновых графов с числом вершин 11, (Herz et al., 1967), 14 (Collier, Schmeichel, 1978) и 17 (Aldred et al., 1997). С другой стороны, были найдены гипогамильтоновы графы с числом вершин n = 10, 13, 15 и 16, а также для всех n 18 (см. (Herz et al., 1967 ; Lindgren, 1967 ; Bondy, 1972 ; Chvatal, 1973 ; Thomassen, 1974, 1981; Doyen, van Diest, 1975 ; Holton, Sheehan, 1993). Более подробный обзор вопроса можно найти в книге Холтона и Шихана (Holton, Sheehan, 1993). Интересным представляется тот факт, что, несмотря на то что почти все кубические графы являются гамильтоновыми (см. (Robinson, Wormald, 1992)), для любого n > 8 существует 2n-вершинный гипогамильтонов кубический граф. В книге (Басакер, Саати, 1973) можно найти доказательство утверждения, что граф Петерсена является гипогамильтоновым графом и не существует других гипогамильтоновых графов с числом вершин n 10. Оказалось, что граф Петерсена является минимальным вершинным 1-расширением 9-вершинного цикла. Следовательно, среди циклов с числом вершин меньшим 10 только 9-вершинный цикл имеет негамильтоново минимальное вершинное 1-расширение.

ТЕОРЕМА 2.4.11. Граф Петерсена, изображенный на рис. 2.4.11, является негамильтоновым минимальным вершинным 1-расширением Доказательство. Заметим, что граф Петерсена – кубический граф, следовательно, имеет такое же количество ребер, что и минимальное вершинное 1-расширение цикла С9. Доказательство того, что граф Петерсена является гипогамильтоновым, то есть негамильтоновым расширением Рис. 2.4.11. Граф Петерсена З а м е ч а н и е. На рис. 2.4.12 изображены все гипогамильтоновы графы с числом вершин до 18 по работе (Aldred et al., 1997). Заметим, что 13- и 15-вершинные гипогамильтоновы графы содержат по 3 вершины степени 4.

Каждый из 16-вершинных гипогамильтоновых графов содержит не менее одной вершины степени 5. Таким образом, среди гипогамильтоновых графов с числом вершин до 18 только граф Петерсена является минимальным вершинным 1-расширением цикла. Для большего числа вершин доказано (Aldred et al., 1997) существование кубических гипогамильтоновых графов, а поскольку любой кубический гипогамильтонов граф является минимальным вершинным 1-расширением цикла, то это дает и ответ на вопрос о существовании негамильтоновых минимальных вершинных 1-расширений у циклов с числом вершин n > 16.

Алгоритм 2.1.2 можно использовать для поиска гипогамильтоновых минимальных вершинных 1-расширений. Однако при количестве вершин n > 13 перебор оказывается слишком большим (например, при нечетном n нужно перебрать все кубические графы, а их число очень велико (Read, 1958)). Следующее очевидное утверждение позволяет существенно увеличить эффективность поиска негамильтоновых минимальных вершинных 1-расширений с помощью соответствующей модификации алгоритма 2.1.2.

ТЕОРЕМА 2.4.12. Минимальное вершинное 1-расширение цикла, содержащее 3-вершинный цикл, является гамильтоновым.

Доказательство. Пусть граф G* – минимальное вершинное 1-расширение цикла Cn, а вершины v0, v1, v2 образуют в G* 3-вершинный цикл. Не ограничивая общности, будем считать, что d(v1) = d(v2) = 3. Рассмотрим граф G* – v0. По условию этот граф содержит гамильтонов цикл. Поскольку степени смежных вершин v1 и v2 в графе G* – v0 равным двум, то они являются соседними вершинами гамильтонова цикла. Таким образом, гамильтонов цикл в графе G* – v0 может быть записан в виде v1, v2, vi 3,…, vin, v1.

Тогда цикл v1, v0, v2, vi4,…, vin, v1 является гамильтоновым в графе G*.

Соответствующие изменения алгоритма 2.1.2 позволяют исследовать случай с числом вершин до 16. Однако для большего числа вершин модификация алгоритма 2.1.2 также перестает быть эффективной. В работах Вормальда (Wormald, 1978, 1981) даются асимптотические оценки числа кубических графов, содержащих цикл длины 3. На основании теоремы 2.4.12 число исключаемых из рассмотрения графов для цикла с четным числом вершин несколько выше, однако бльшим является и объем пространства поиска.

2.5. Предполные графы Назовем предполным граф вида K1 + G, где G – произвольный граф.

Поскольку O1 изоморфен K1, то можно записать предполный граф и как O1 + G. В предполном графе есть хотя бы одна вершина, смежная со всеми остальными. Будем называть такие вершины полными. Предполным графом, очевидно, является и полный граф. В полном графе каждая вершина является полной. Заметим, что любой предполный граф является связным.

Пусть в предполном n-вершинном графе G есть p полных вершин. Тогда его можно представить в виде Kp + Gn-p, где Gn-p обозначает (n – p)-вершинный граф, причем такое представление единственно. Среди предполных графов имеются деревья – графы вида O1+On, причем только они. Графы такого вида называются звездными. В некоторых работах (например, (Кабанов, 1997)) эти графы называются колесами. Там же доказывается, что тривиальное 1-расширение звездного графа является его минимальным вершинным 1-расширением. Далее мы покажем, что при больших значениях k тривиальное k-расширение звездного графа не является его минимальным вершинным k-расширением (см. теорему 2.5.2). Следующее утверждение показывает, что количество предполных графов с заданным числом вершин достаточно велико.

Утверждение. Число всех неизоморфных n-вершинных предполных графов равно числу всех неизоморфных (n – 1)-вершинных графов.

Доказательство. Предполный граф содержит хотя бы одну полную вершину. Рассмотрим все неизоморфные (n – 1)-вершинные графы. Каждому (n – 1)-вершинному графу G соответствует единственный с точностью до изоморфизма предполный граф, получающийся добавлением полной вершины: K1 + G. И наоборот, каждому предполному n-вершинному графу K1 + G соответствует единственный с точностью до изоморфизма (n – 1)-вершинный граф G, получающийся удалением любой полной вершины. В силу установленного взаимно однозначного соответствия между всеми (n – 1)-вершинными графами и n-вершинными предполными графами получаем доказываемое утверждение.

ЛЕММА 2.5.1. Однородный n-вершинный граф порядка n – 2, где n – чётное, является униграфом.

Доказательство. Пусть G – однородный n-вершинный граф порядка n – 2, а G' – дополнение графа G. Граф G' – однородный n-вершинный граф порядка 1, его вектор степеней имеет вид (1,…,1). Очевидно, что такой вектор степеней определяет униграф, следовательно, униграфом является и граф Обозначим однородный n-вершинный униграф порядка n – 2 (n – четное) через Rn,n-2. Заметим, что граф дополнение представлены на рис. 2.5.1.

– 2,…,n – 2) определяет n-вершин-ный униграф.

Доказательство. Пусть G – некоторый граф с вектором степеней (n – 1,n – 2,…,n – 2). Вершина v степени n – 1 смежна со всеми остальными вершинами графа G. Граф G – v является (n – 1)-вершинным однородным графом Rn-1,n-3, причем униграфом по лемме 2.5.1, то есть G = Rn 1, n 3 + K1. Поскольку единственным способом можно получить граф Rn-1,n-3 из G и единственным способом можно получить G из Rn-1,n-3, то G является униграфом.

Следствие 2. При n 2 любой n-вершинный граф со степенным множеством {n – 1,n – 2} является униграфом.

{n –1,n – 2}. Рассуждаем аналогично предыдущему случаю. Пусть F – множество вершин из V(G) степени n – 1. Рассмотрим однородный граф G – F.

По лемме 2.5.1 он является униграфом. Положим p = n – |F|. Поскольку единственным способом можно получить граф Rp,p-2 из G и единственным способом можно получить G из Rp,p-2, то G является униграфом.

Два предыдущих следствия можно объединить в Следствие 3. Граф вида G = Rn 1, n 3 + K p является униграфом.

2.5.1. Минимальные вершинные 1-расширения Результаты относительно минимальных вершинных 1- и k-расширений был впервые представлен автором в работе (Абросимов, 2000, в), а затем в работе (Абросимов, 2003). Независимо аналогичный результат был представлен в работе (Choudum, Sivagurunathan, 2000).

ТЕОРЕМА 2.5.1. Относительно предполных графов справедливы следующие утверждения.

1. При четном n любой n-вершинный предполный граф K1 + G имеет единственное с точностью до изоморфизма минимальное вершинное 1-расширение – тривиальное, то есть 2. При нечетном n:

а) при n 3 существует один и только один n-вершинный предполный граф Gnp1, для которого тривиальное расширение не является минимальным. Граф Gnp1 может быть представлен в виде O1 + O2 +... + O2. При этом граф Gnp1 имеет единственное с точностью до изоморфизма минимальное вершинное 1-расширение и оно содержит n – 1 дополнительных ребер:

б) при n 5 существует один и только один n-вершинный предполный граф Gnp2, имеющий два неизоморфных минимальных вершинных 1-расширения: вида O2 + O2 +... + O2 и тривиальное O1 + Gnp 2.

Причем граф Gnp2 получается из графа Gnp1 удалением любого ребра, соединяющего две вершины степени n – 2;

в) любой n-вершинный предполный граф G, не изоморфный Gnp1 и Gnp2, имеет единственное с точностью до изоморфизма минимальное вершинное 1-расширение – тривиальное:

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

I. Пусть граф G* имеет хотя бы одну полную вершину, например v.

Удаление такой вершины приводит к удалению n ребер, следовательно, граф G* отличается от G на n ребер. Значит, граф G* – v изоморфен графу G. Следовательно, граф G* есть тривиальное 1-расширение графа G. Таким образом, 1-расширение, причем других неизоморфных G* минимальных вершинных 1расширений с полными вершинами граф G иметь не может.

II. Пусть G* не имеет полных вершин, тогда максимальная степень его вершин есть n – 1. Пусть вершина v графа G* имеет степень n – 1. Вершина v соединена со всеми вершинами G*, кроме одной. Тогда в графе G* – v может быть единственная вершина степени n – 1, а именно вершина, не смежная с v. Обозначим ее через u. Итак, удаление одной из вершин минимального вершинного 1-расширения G* предполного графа G дает предполный граф с единственной полной вершиной. Вывод: если G и имеет минимальное вершинное 1-расширение без полных вершин, то в G есть только одна полная вершина.

В графе G* несмежные вершины u и v смежны со всеми остальными вершинами, степени которых не выше n – 1. Тогда удаление любой вершины G*, кроме u или v, например вершины u1, приведет к уменьшению степени вершин u и v в графе G* – u1 на единицу. Следовательно, в графе G* существует еще одна вершина степени n – 1 – вершина, не смежная с u1. Повторяя предыдущее рассуждение относительно этой вершины, получим, что степень u1 тоже должна быть n – 1. Однако мы произвольно выбрали вершину u1.

Значит, степень любой вершины графа G* есть n – 1. Итак, некоторый граф G, про который известно, что он имеет только одну полную вершину, может иметь минимальное вершинное 1-расширение без полных вершин, и если он (n – 1)(n + 1) – нечетно и в силу теоремы о необходимой четности суммы степеней вершин графа получаем, что при четном n ни для какого предполного n-вершинного графа G нельзя построить минимальное вершинное 1-расширение без полных вершин, следовательно, единственное минимальное вершинное 1-расширение графа G – тривиальное. Это доказывает первое утверждение теоремы.

Итак, n нечетное, вектор степеней (n + 1)-вершинного графа G* есть (n – 1, …, n – 1), и, в силу леммы 2.5.1, граф G* является униграфом. Удаление любой его вершины дает граф с вектором степеней (n – 1,n – 2,…, n – 2) и числом ребер на n – 1 меньшим, чем в графе G*. С другой стороны, граф G* отличается от графа G по лемме 2.1.3 не менее чем на n – 1 и не более чем на n ребер. Рассмотрим каждый из этих случаев.

1. Пусть граф G отличается от графа G* на n – 1 ребро. Тогда вектор степеней графа G должен иметь вид (n – 1,n – 2,…,n – 2). По следствию 1 из леммы 2.5.1 граф G является униграфом. Итак, если и существует предполный граф, имеющий минимальное вершинное 1-расширение с числом дополнительных ребер меньшим, чем у тривиального 1-расширения, то этот граф имеет вектор степеней (n – 1,n – 2,…,n – 2), а его минимальное вершинное 1расширение имеет n – 1 дополнительное ребро и вектор степеней (n – 1,…,n – 1). Последний вектор степеней по лемме 2.5.1 определяет униграф, и удаление любой его вершины приводит к униграфу с вектором степеней (n – 1,n – 2,…,n – 2). Следовательно, этот вектор степеней определяет граф Gnp1, что доказывает утверждение 2а теоремы.

2. Пусть граф G отличается от графа G* на n ребер. Тогда вектор степеней графа G при n > 3 должен иметь вид (n – 1,n – 2,…,n – 2,n – 3,n – 3), а при n > 4 – вид (n – 1,n – 2,…,n – 2,n – 4).

Удаление любой вершины графа G* дает граф Gnp1. Следовательно, такой и только такой граф среди всех графов с рассматриваемыми векторами степеней, который вкладывается в граф Gnp1, будет иметь G* своим минимальным вершинным 1-расширением. Определим, сколько таких графов существует. Все вершины графа G* имеют степень n – 1 и могут быть разбиты на пары несмежных вершин, смежных со всеми остальными. Удаление одной из вершин пары дает граф Gnp1, в котором оставшаяся вершина пары является полной. Удаляем и эту вершину, получаем однородный (n – 1)-вершинный граф G1 порядка n – 3. Полную вершину можно добавить единственным способом, поэтому число неизоморфных графов с указанным вектором степеней, для которых G* является минимальным вершинным 1-расширением, есть число неизоморфных графов, которые можно получить удалением одного ребра графа G1. Следовательно, мы должны определить, сколько неизоморфных графов можно получить удалением одного ребра графа G1. Рассмотрим пары несмежных вершин. Удалим ребро, инцидентное одной из вершин некоторой пары. Очевидно, что таким образом мы получим единственный с точностью до изоморфизма граф Gnp2 с вектором степеней (n – 1,n – 2,…,n – 2,n – 3,n – 3) (отсюда получается ограничение n > 3 в формулировке пункта 2б теоремы), для которого G* и будет являться расширением.

Это доказывает с учетом пункта I утверждения 2б и 2в теоремы.

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

Алгоритм 2.5.1.

На входе: n-вершинный граф G.

На выходе: все минимальные вершинные 1-расширения, если граф G – предполный.

Определить по вектору степеней, является ли граф G предполным. Если нет, ВЫХОД.

Если n четное, то минимальное вершинное 1-расширение имеет вид K1 + G. ВЫХОД.

Если граф G имеет вектор степеней (n – 1,n – 2,…,n – 2), то G является графом типа Gnp1 – минимальное вершинное 1-расширение имеет вид O2 + O2 +... + O2. ВЫХОД.

Если граф G имеет вектор степеней (n – 1,n – 2,…,n – 2,n – 3,n – 3) и вершины степени n – 3 не смежны, то G является графом типа Gnp2 и два его минимальных вершинных 1-расширения имеют вид O2 + O2 +... + O2 и K1 + G.

ВЫХОД.

Минимальное вершинное 1-расширение имеет вид K1 + G.

Обоснование. Корректность алгоритма обусловлена теоремой 2.5.1.

Определим сложность алгоритма. Пусть граф G имеет n вершин и m ребер.

Для представления графа удобно использовать список ребер. Тогда определение вектора степеней на шаге 1 потребует O(m) действий. Построение графа на шагах 2 и 5 состоит в добавлении одной вершины и n ребер – сложность O(n). Определение типа графа по вектору степеней на шаге 3: O(n).

Определение типа графа на шаге 4 по вектору степеней и проверка смежности вершин степени n – 3: O(n + m). Построение графа на шагах 4 и 5: O(n) действий. Таким образом, общая сложность алгоритма составляет O(n + m).

Следствие 1. Единственным с точностью до изоморфизма минимальным вершинным 1-расширением звездного графа с числом вершин большим трех является его тривиальное 1-расширение.

Следствие 2. Наименьший граф Gnp1 из пункта 2а теоремы есть цепь P3, а ее минимальное вершинное 1-расширение – цикл C4.

Следствие 3. Доказательство теоремы позволяет построить наименьший граф Gnp2 пункта 2б теоремы. Это 5-вершинный униграф с вектором степеней (4,3,3,2,2), изображенный на рис. 2.5.2.

Следствие 4. Граф Gnp1 (при нечетном n) и полный Kn – единственные предполные n-вершинные графы, имеющие точное вершинное 1-расширение.

Доказательство. Пусть G – предполный граф, G* – его минимальное вершинное 1-расширение, G' – дополнение G, а G'* – минимальное вершинное 1-расширение G'. Пусть число ребер графа G равно m, тогда его дополнеn(n 1) ние содержит графа G отличается от G либо на n – 1, либо на n ребер. Тогда число ребер графа G*' есть либо первом случае минимальное вершинное 1-расширение дополнения должно отличаться только на одно ребро, что возможно лишь для графа Gnp1, так как любая его часть, отличная от него самого, содержит хотя бы одну вершину степени большей единицы. Во втором случае минимальное вершинное 1-расширение дополнения содержит столько же ребер, сколько и дополнение, что возможно только для вполне несвязного графа, который является дополнением полного графа. Непосредственно видно, что минимальные вершинные 1расширения графов Gnp1 и Kn являются точными.

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

Доказательство. Пусть G = K r + Gn. При r > 1 граф G имеет не менее r полных вершин, следовательно, по теореме 2.5.1 граф G имеет единственное минимальное вершинное 1-расширение G* вида G + K1. Откуда получаем 2.5.2. Минимальные вершинные k-расширения ЛЕММА 2.5.2. Минимальное вершинное k-расширение любого предполного n-вершинного графа либо содержит хотя бы одну вершину степени n + k – 1, либо не содержит вершин со степенью ниже n + k – 2.

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

Пусть это не так и, например, d(v) < n + k – 2, где v V(G*).

Докажем более сильное утверждение: (n + k)-вершинный граф G* без полных вершин, но с вершиной, степень которой отличается от степени полной вершины более чем на единицу, не может являться вершинным k-расширением никакого предполного графа.

Рассмотрим дополнение G*' графа G*. В G* нет полных вершин, значит, в G*' нет изолированных вершин. Покажем, что каким бы ни был граф G*, всегда можно выбрать набор F V (G ) из k вершин так, чтобы подграф G F не содержал ни одной полной вершины, а следовательно, его дополнение G ' F не содержало изолированных вершин.

Пусть G*' содержит m компонент связности S1, …, Sm с числом вершин n1, …, nm. Число вершин в той компоненте, в которой находится вершина v, больше 2. Не ограничивая общности, будем считать, что это компонента S1.

Будем выбирать вершины по следующим правилам:

1. Если существует i = 2, …, m: ni k, тогда удаляем все вершины компоненты Si, k := k – ni.

2. Если существует i = 2, …, m: ni 3, тогда удаляем min{ni – 2, k} вершин 3. Если k = 0, то ВЫХОД.

4. Если была проведена редукция по одному из правил 1 или 2, то переход на шаг 1, иначе ВЫХОД.

Нетрудно видеть, что действия алгоритма не приводят к появлению изолированных вершин. Из алгоритма можно выйти в одном из двух случаев:

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

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

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

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

Следствие 2. Минимальное вершинное k-расширение любого предполного n-вершинного графа является либо предполным графом, либо однородным графом порядка n + k – 2.

ЛЕММА 2.5.3. Если минимальное вершинное k-расширение некоторого (не обязательно предполного) графа G содержит полную вершину, то оно является тривиальным 1-расширением некоторого минимального вершинного (k – 1)-расширения графа G.

Доказательство. Пусть G* – минимальное вершинное k-расширение из условия теоремы с полной вершиной v V (G * ). Граф G* – v является вершинным (k – 1)-расширением графа G. Предположим, что G* – v не является минимальным вершинным (k – 1)-расширением графа G. Обозначим через G минимальное вершинное (k – 1)-расширение G. Тогда граф G1 + K1 является вершинным k-расширением графа G, причем с меньшим числом ребер, чем у минимального вершинного k-расширения G* графа G. Полученное противоречие доказывает утверждение.

ЛЕММА 2.5.4. Граф Gnp2 не является минимальным вершинным k-расширением никакого предполного графа ни при каком натуральном значении k.

Доказательство. Пусть граф Gnp2 является минимальным вершинным k-расширением некоторого предполного графа G. Как было показано в лемме 2.5.2, минимальное вершинное k-расширение любого предполного графа либо содержит полную вершину и в силу леммы 2.5.3 является тривиальным 1расширением минимального вершинного (k – 1)-расширения графа G, либо является однородным графом Rm,m-2.

Граф Gnp2 содержит единственную полную вершину, но подграф, получающийся после ее удаления, не является ни предполным, ни однородным.

ЛЕММА 2.5.5. Для четного n однородный n-вершинный граф порядка n – 2 – граф Rn,n-2 – имеет единственное минимальное вершинное 1-расширение – тривиальное, причем это минимальное вершинное 1-расширение есть граф G(n+1)p1.

Доказательство. Пусть G* – минимальное вершинное 1-расширение графа Rn,n-2. Если в G* есть полная вершина, то G* является по лемме 2.5. тривиальным 1-расширением.

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

Однако удаление любой смежной с ней вершины приведет к графу с вершиной степени n – 3, что противоречит предположению о том, что граф G* является минимальным вершинным 1-расширением графа Rn,n-2.

Так как при четном n имеем (Rn,n-2)* = G(n+1)p1, и (G(n-1)p1)* = Rn,n-2, то имеет место ЛЕММА 2.5.6. Каждое минимальное вершинное k-расширение G*k любого предполного графа G при четном k есть минимальное вершинное 1-расширение некоторого минимального вершинного (k – 1)-расширения G*k-1 графа G, причем это минимальное вершинное 1-расширение единственно с точностью до изоморфизма и является тривиальным 1-расширением графа G*k-1.

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

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

Все вершины графа G*k образуют пары, так что вершины одной пары несмежны друг с другом, но смежны со всеми остальными вершинами. Удалим k/2 таких пар вершин. Удаление одной пары вершин приводит к уменьшению степеней всех остальных вершин на два, следовательно, в результате получим однородный n-вершинный граф порядка n – 2. Итак, один из подграфов графа G*k, полученный удалением его k вершин, не является предполным графом, а следовательно, и никакой предполный граф G не имеет при четном k минимальных вершинных k-расширений без полных вершин, поэтому любое минимальное вершинное k-расширение графа G является тривиальным некоторого его минимального вершинного (k – 1)-расширения.

Следствие. Любой предполный граф при четном k имеет столько же неизоморфных минимальных вершинных k-расширений, сколько и неизоморфных минимальных вершинных (k – 1)-расширений.

ЛЕММА 2.5.7. Каждое минимальное вершинное k-расширение G*k любого предполного графа G с четным числом вершин есть минимальное вершинное некоторого минимального вершинного (k – 1)-расширения G*k-1 графа G, причем это минимальное вершинное 1-расширение единственно с точностью до изоморфизма и является тривиальным расширением графа G*k-1.

Доказательство. При четном k утверждение теоремы следует из леммы 2.5.6.

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

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

Доказательство. При k = 1 минимальное вершинное 1-расширение любого предполного графа G с четным числом вершин в силу теоремы 2.5. есть тривиальное 1-расширение. Рассуждая по индукции, докажем утверждение.

ЛЕММА 2.5.8. При нечетном n для любого предполного n-вершинного графа G, являющегося частью графа Gnp1, существует нечетное число k1, такое, что справедливы следующие утверждения:

а) для любого k < k1 граф G имеет единственное минимальное вершинное k-расширение, являющееся тривиальным k-расширением;

б) граф G имеет два неизоморфных минимальных вершинных k1-расширения: тривиальное k1-расширение и граф Rn+ k1,n +k12 ;

в) граф G имеет два неизоморфных минимальных вершинных (k1 + 1)расширения, каждое из которых является тривиальным 1-расширением одного из двух неизоморфных минимальных вершинных k1-расширений;

г) для любого нечетного k > k1 граф G имеет единственное с точностью до изоморфизма минимальное вершинное k-расширение – однородный граф R n + k,n + k 2 ;

д) для любого четного k > k1 + 1 граф G имеет единственное с точностью до изоморфизма минимальное вершинное k-расширение – тривиальное 1-расширение графа Rn + k 1,n + k 3.

Доказательство. Пусть при нечетном n предполный n-вершинный граф G с m ребрами является частью графа Gnp1 и отличается от него на m' ребер. Очевидно, что минимальное вершинное k-расширение графа Gnp1 является вершинным k-расширением графа G, и, если оно не является минимальным вершинным k-расширение графа G, то тогда таковым является тривиальное k-расширение графа G. Определим число ребер в минимальном вершинном k-расширении графа Gnp1 и в тривиальном k-расширении графа G.

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

Минимальное вершинное k-расширение графа Gnp1 при нечетном k по следствию из леммы 2.5.5 есть граф Rn+k,n+k-2. Тогда число ребер минимального вершинного k-расширения графа Gnp1 есть (n + k )(n + k 2) / 2, а число ребер тривиального k-расширения графа G есть nk + (k 1)k / 2 + m, где Определим разность между числом ребер этих графов: m'. Приравнивая к нулю, находим k1: k1 = 2m' – 1. Таким образом, при k < k1 меньшее число ребер у тривиального k-расширения графа G, при k > k1 + 1 меньшее число ребер имеет минимальное вершинное k-расширение графа Gnp1, а при k = k1 и при k = k1 + 1 число ребер в этих графах одинаково. Что и требовалось показать.

Следствие 1. Для любого предполного n-вершинного графа G, являющегося частью графа Gnp1, существует нечетное число k, такое что граф G имеет два неизоморфных минимальных вершинных k- и (k + 1)-расширения, причем при всех остальных значениях k граф G имеет единственное с точностью до изоморфизма минимальное вершинное k-расширение.

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

Следствие 3. Для любого k и нечетного n, таких что n2 – 4n + 2 k, всегда можно указать предполный граф, имеющий два неизоморфных минимальных вершинных k-расширения.

Доказательство. Из леммы 2.5.8 следует, что среди всех n-вершинных предполных графов только граф, являющийся частью графа Gnp1, может иметь два неизоморфных минимальных вершинных k-расширения, причем только при k = 2m' – 1 и k = 2m' + 1, где m' – разница в числе ребер графов G и Gnp1. Число ребер графа Gnp1 есть Максимальное значение m' будет достигнуто, если G – звездный граф, число ребер которого есть n – 1. Тогда откуда получаем неравенство, которому должны удовлетворять числа n и k, чтобы можно было построить граф с требуемым свойством:

ТЕОРЕМА 2.5.2. Относительно предполных графов справедливы следующие утверждения.

1. При четном n и любом натуральном k каждый n-вершинный предполный граф G имеет единственное с точностью до изоморфизма минимальное вершинное k-расширение – тривиальное k-расширение.

2. При нечетном n:

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

i) если предполный граф G является частью графа Gnp1 и отличается от него на m ребер, то – при k < 2m – 1 граф G имеет единственное с точностью до изоморфизма минимальное вершинное k-расширение – тривиальное k-расширение;

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

– при k > 2m – 1 граф G имеет единственное минимальное вершинное k-расширение – граф Rn+k,n+k-2;

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

Доказательство. Лемма 2.5.7 и следствие из неё дают доказательство утверждения 1.

Лемма 2.5.6 и следствие из неё дают доказательство утверждения 2а.

Лемма 2.5.8 доказывает утверждения i пункта 2б.

Истинность утверждения ii пункта 2б следует из того, что если предполный граф G не является частью графа Gnp1, то граф R(n+k),(n+k-2) ни при каких k не является его минимальным вершинным k-расширением, следовательно, любое его минимальное вершинное k-расширение содержит полную вершину, то есть является тривиальным 1-расширением его минимального вершинного (k – 1)-расширения, а значит, оно является и тривиальным k-расширением, причем это минимальное вершинное k-расширение единственно с точностью до изоморфизма.

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

На входе: число k > 0 и n-вершинный граф G с n вершинами и m ребрами.

На выходе: все минимальные вершинные k-расширения, если граф G – предполный.

Определить по вектору степеней является ли граф G предполным. Если нет, ВЫХОД.

Если n четное, то минимальное вершинное k-расширение имеет вид Kk + G. ВЫХОД.

Если k четное: построить все (одно или два) минимальные вершинные (k – 1)-расширения G: Gi. Минимальные k-расширения будут иметь вид K1 + Gi. ВЫХОД.

Если G допускает вложение в граф Gnp1, то шаг 5, иначе минимальное вершинное k-расширение имеет вид Kk + G. ВЫХОД.

Определяем разницу по числу ребер между графом G и Gnp1:

Если k < 2s – 1, то минимальное вершинное k-расширение имеет вид Kk + G. ВЫХОД.

Если k = 2s – 1, то минимальные вершинные k-расширения имеют вид Kk + G и граф Rn+k,n+k-2. ВЫХОД.

Если k > 2s – 1, то минимальное вершинное k-расширение имеет вид Rn+k,n+k-2.

Обоснование. Корректность алгоритма следует из теоремы 2.5.2.

Оценим сложность алгоритма: T(n, k).

Пусть G – n-вершинный граф. Удобно представлять заданный граф в виде списка ребер.

При четном k согласно с пунктом 3 имеем: T(n, k) = T(n, k – 1). Далее рассматриваем нечетные значения k.

Определение на шаге 1, является ли граф G предполным, потребует O(n + m) действий.

Построение графа вида Kk + G на шагах 2, 4 и 6 потребует добавления k вершин и Самым сложным с вычислительной точки зрения является определение вложения на шаге 4. В общем случае не известен алгоритм полиномиальной сложности для определения вложения одного графа в другой. Однако особенности графа Gnp1 позволяют существенно упростить эту задачу.

Итак, пусть n нечетно. Требуется определить, является ли граф G частью графа Gnp1. Дадим два определения.

Паросочетанием называется произвольное подмножество попарно несмежных ребер графа. Паросочетание называется максимальным, если оно не содержится в паросочетании с бльшим числом ребер, и наибольшим, если число ребер в нем наибольшее среди всех паросочетаний графа. Паросочетание называется совершенным, если любая вершина графа принадлежит некоторому ребру этого паросочетания. Наиболее эффективными алгоритмами построения паросочетаний являются (см. (Ловас, Пламмер, 1998)) алгоритмы Бартника, Карива, Ивена и Карива со сложностью O(n5/2) и алгоритм Майкели и Вазирани со сложностью O(mn1/2).