8.3. Графы с заданными степенями

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

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

Рассмотрим графическую последовательность упорядоченную по убыванию: Пусть — степень вершины «Изъять означает соединить соответствующую вершину с вершинами если или если Последовательность если или

если называется остаточной последовательностью после изъятия или просто остаточной последовательностью.

Хакими [8.4] и Гавел [8.5] предложили алгоритм построения простого графа (если он существует), имеющего заданную последовательность степеней. Этот алгоритм основан на результате, являющемся частным случаем (при ) следующей теоремы, доказанной Вонгом и Клейтманом [8.6].

Теорема 8.7. Если последовательность является последовательностью степеней простого графа, то этим свойством обладает и остаточная последовательность после изъятия

Доказательство. Для доказательства нам необходимо показать, что существует такой граф с последовательностью степеней в котором вершина смежна с первыми d вершинами, отличными от самой вершины Допустим противное. Выберем среди графов с последовательностью степеней простой граф G, в котором вершина смежна с максимальным числом вершин из первых вершин, отличных от Пусть такая вершина, не смежная с вершиной в графе G, что если или 1, если . Другими словами, вершина находится среди первых вершин, не считая саму вершину Поэтому последняя смежна в графе G с некоторой вершиной не входящей в число первых вершин. Тогда (если бы было равенство, и q можно было поменять местами) и, следовательно, вершина смежна с некоторой такой вершиной что вершины не смежны. Теперь, если заменить ребра на соответственно, мы получим граф G, в котором число первых вершин, отличных от вершин и смежных с ней, на 1 больше, что противоречит определению графа

Эта теорема предлагает следующий алгоритм, являющийся обобщением алгоритма Хакими реализации последовательности простым графом.

Выберем произвольное «Изымем» , соединяя вершину с первыми вершинами, не считая саму Определим остаточную последовательность. Переупорядочим вершины так, чтобы остаточные степени в получившейся последовательности были невозрастающими. Повторяем этот процесс до тех пор, пока не возникнет одна из следующих ситуаций:

1. Все остаточные степени равны нулю. В этом случае получившийся граф имеет последовательность степеней

2. Одна из остаточных степеней отрицательна. Это означает, что последовательность D не графическая.

Для иллюстрации описанного алгоритма рассмотрим последовательность

После изъятия (обведенной кружком), получим последовательность

которая после переупорядочения остаточных степеней принимает вид

Затем, изымая степень, соответствующую вершине получим

Переупорядочивая остаточные степени в получим

Теперь, изымая степень, соответствующую вершине получим

Здесь алгоритм заканчивает работу. Поскольку все остаточные степени равны нулю, последовательность (4, 3, 3, 2, 2) графическая.

Рис. 8.5. Граф с последовательностью степеней (4, 3, 3, 2, 2).

Требуемый граф (рис. 8.5) получается в результате выполнения шагов, соответствующих порядку изъятия степеней:

1. Соединяем вершину

2. Соединяем вершину

3. Соединяем вершину

Эрдёш и Галлаи [8.7] определили необходимые и достаточные условия (неалгоритмического типа) того, что последовательность графическая. Их результат описывается также в работе [8.8].

Предположим, что в описанном алгоритме мы изымаем на каждом шаге наименьшую ненулевую остаточную степень. Тогда с помощью индукции легко показать, что получающийся граф связен, если для всех t, (8.8)

Заметим, что выполнение неравенств (8.8) и (8.9) необходимо, чтобы граф был связным. В следующей теореме мы доказываем более

сильный результат. Он получен Эдмондсом [8.9]. Данное здесь доказательство предложили Вонг и Клейтман [8.10].

Теорема 8.8 (Эдмондс). Необходимым и достаточным условием того, что графическая последовательность есть последовательность степеней простого -реберно-связного графа при является выполнение для всех степеней

Доказательство. Необходимость очевидна.

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

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

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

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

Случай 1. Все ненулевые остаточные степени не меньше

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

Докажем полноту описанных случаев. Пусть — вершина, соединяемая с другими на шаге i. Не нарушая общности, будем считать, что вершина находится во множестве А. Покажем, что если случаи 1 и 2 не возникают, то на некотором шаге алгоритма возникнет случай 3.

На шаге 1 вершина полностью связна. Тогда а) наименьшие ненулевые остаточные степени равны поскольку случай 1 не возникал; б) степени ни одной из вершин А не уменьшались на 1 при соединении вершины поскольку случай 2 не возникал. Следовательно, связываемая на шаге 2 вершина должна быть в А. (Все вершины А должны иметь степень, не меньшую k.) Если после соединения вершины не возникает случай 1 и никакое из ребер не связывает А с А, тогда все еще, как и прежде, мы имеем случай а или 6. Следовательно, следующая связываемая вершина будет снова в А.

Так как остаточные степени на каждом шаге процедуры соединения вершин уменьшаются, то рано или поздно будет связана такая лежащая в А вершина что между А и А появится ребро. Если не возникает случай 2, то одна из ненулевых остаточных степеней вершнн, лежащих в и еще не полностью связанных, станет равной Это означает, что вершина должна соединяться с каждой вершиной , поскольку все вершины имеют остаточные степени, равные k, и вследствие того, что мы соединяем вершину с вершинами, имеющими наибольшие остаточные степени. Так как на этом шаге возникает случай 3.

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