Давайте попробуем теперь поразбираться, всегда ли возможно построить граф с заданной последовательностью степеней вершин. Я взял шпаргалку, потому что на память мне трудно запомнить такие последовательности, которые мы тут напридумывали. Ну я сейчас со шпаргалки их спишу. Значит, смотрите, вот, например, пункт «а». Рассмотрим такую последовательность чисел: 5, 4, 3, дальше четыре двойки, 2, 2, 2, 2 и 1. Спрашивается: может ли такая последовательность чисел быть последовательностью степеней вершин некоторого графа? Вообще, это в какой-то мере обобщение той задачи, которую мы решали в самом начале, а именно задачи про совпадение числа знакомых у некоторых двоих людей в произвольной группе товарищей. Ну, действительно, там тоже речь шла о том, что невозможно составить такую последовательность степеней, в которой все бы числа были принципиально различными, попарно различными. Вот здесь предлагается такая последовательность чисел. Сколько их всего? 1, 2, 3, 4, 5, 6, 7. 8. Восемь чисел. Ну, стало быть, спрашивается: существует ли граф, у которого 8 вершин, и у которого какая-то вершина имеет степень 5, какая-то другая вершина имеет степень 4, ну и так далее вплоть до единицы. Возможно ли, в принципе, построить такой граф? Ну, глядя на эту последовательность, можно очень легко сообразить, почему, на самом деле, ответ отрицательный. Действительно, давайте сложим все числа, которые находятся в этой последовательности. У нас получится 5 + 4 + 3 + 2 + 2 + 2 + 2 + 1. Какое это число по четности? Вот здесь у нас четное число. Здесь у нас тоже четное число. Здесь четное. А пятерка нечетное. То есть совершенно неважно, чему равняется эта сумма, но сразу видно, что она является нечетным числом. Но, товарищи, мы же знаем, что сумма степеней вершин графа — это обязательно четное число. Не может быть графа, у которого сумма степеней вершин является нечетным числом. Поэтому здесь ответ — нет, такого графа не существует. Просто это противоречит тому, что сумма степеней вершин равняется удвоенному количеству ребер. Нечетное число не может делиться на два. Стало быть, получаем невозможность. Ну, хорошо. Давайте попробуем посмотреть еще на какую-нибудь последовательность степеней вершин, которую я сейчас срисую со своей шпаргалки: 7, 6, 3, (ну, вернее, не последовательность степеней вершин, а просто последовательность чисел, вот про нее зададимся таким же вопросом: существует ли граф, имеющий такую последовательность степеней вершин?) 1, 1, 1, 1, 1. Ну, давайте опять попробуем сложить. Здесь получится 5 + 3 = 8 Хе! Как интересно! Давайте-ка еще раз поглядим. 3 + 2 = 5. 8. Опять нечетное число получается. Плохую последовательность что ли я срисовал? Что ж такое-то! Не, ну это, конечно, нелепо. Это неинтересная последовательность. Срисовывал-срисовывал со шпаргалки, а срисовал какую-то ерунду. Не, ну давайте я все-таки что-нибудь заменю, а то как-то это неинтересно. Давайте я вот здесь вот... Не, ну вы понимаете, да, товарищи, что я-то старался-старался, нарисовал здесь вот эту тройку, все сложил — опять нечетное число! Ну, конечно, графа с такой последовательностью степеней вершин не бывает. Мы только что этот принцип поняли. Давайте я эту тройку заменю на что-нибудь, чтобы было поинтереснее рассуждать. Вот здесь вот какую-нибудь четверку нарисую, например. Тогда будет, наверное, интереснее, потому что здесь получается 5 + 7 = 12, + 6 + 4 — все, нечетности нет. Сумма, естественно, четная, и это не противоречит тому, что сумма степеней вершин должна равняться удвоенному количеству ребер. Может быть, вообще, такой граф существует. Бог его знает, да? Ну давайте подумаем по-другому. Вот у меня все-таки в голове сидело некоторое готовое решение, и сейчас я его попробую воспроизвести. Смотрите: если бы такой граф существовал, — а я хочу доказать, что его не бывает, — если бы такой граф существовал, то у него заведомо, конечно же, были бы вершины как степени 7, так и степени 6. То есть одна вершина была бы степени 7, другая вершина — давайте я вот так условно нарисую — была бы степени 6. То есть семерка и шестерка — это не номера вершин, а это количество ребер, которые выходят из этих вершин. Ну представьте себе даже, что эти вершины между собою соединены ребром. Даже в этом случае наружу, в оставшиеся вершины из этих двух вершин суммарно выходит 13... Сколько ребер-то выходит? Значит, здесь была степень 6, и в нее входило, допустим, вот это ребро. И здесь была степень 7, и в нее тоже входило, допустим, вот это ребро. То есть суммарно в оставшиеся вершины, даже в случае наличия вот этого промежуточного ребра, выходит 13 минус 2 — 11 ребер. То есть у оставшихся вершин суммарная степень никак не меньше 11-ти. Ну, понятно, друзья, что если бы этого ребра не было, тогда я бы здесь написал вообще 13. Это было бы еще больше. Однако 4 + 1 + 1 + 1 + 1 + 1 — это всего лишь 9. До 11-ти не дотягивает. Так что опять противоречие. Не может такого быть, чтобы были 2 вершины степеней 7 и 6 соответственно, потому что тогда в их окрестности находится как минимум 11 ребер вот здесь вот, вот так вот находятся, а суммарно 11 ребер при таких степенях вершин не наберется. Так что здесь и в этой постановке тоже ответ получается — нет. Ну ладно, выкрутились, что называется, а то как-то было бы неинтересно. Ну давайте пункт «в» я проскачу в какой-то степени. Значит, вот предлагается такая штуковина: 4, 3, 2, 2, 2. 6, 6, 5, 4, 3, 2, 2, 2. Да, вот такая вот замечательная штуковина. Давайте попробуем опять сложить. Да, здесь все в порядке — это четное число. По сумме степеней видно, что никаких противоречий сходу не возникает. Поэтому появляется подозрение, что уж вот этот-то граф можно представить, то есть можно такую последовательность чисел представить графом с вот ровно такими степенями вершин. Ну и ответ здесь действительно — да. Я думаю, что рисовать этот граф ввиду не слишком хороших своих способностей к рисованию я не буду. Ну, поскольку я уж сказал, что — да, нарисуйте его просто. Я не думаю, что это составит какой-то особенный труд. Более интересно именно доказывать, что что-то не получается сделать. Вот давайте еще посмотрим на один замечательный пример. Так. Ну, честно говоря, этот пример, кажись, укладывается тоже в ситуацию пункта «а». Сейчас я его выпишу: 7, 6, 5, 4, 3, 2, 1, 0. Он мне в этом ключе не нравится, потому что смотрите: нечетное число плюс нечетное — четное, да? А нет, здесь все хорошо. Вот здесь никаких проблем нету, потому что смотрите: 7 + 5 — это четное число, 3 + 1 — тоже четное, поэтому сумма этих чисел четная, и такого противоречия, как в пункте «а», которое уже нам неинтересно, потому что мы его изучили, не возникает. Ну, стало быть, надо думать: а может его можно нарисовать? Нет, вот этот нельзя все-таки нарисовать. Ответ — нет. И сейчас я объясню, почему нет. Вот здесь ответ нет получается абсолютно так же, как мы приходили к противоречию в задаче про количество знакомых людей, что в любом графе есть две вершины одинаковой степени. Вот здесь происходит абсолютно то же самое. Здесь всего написано 8 чисел, поэтому самое большое количество соседей, то есть самая большая степень, которая, в принципе, может возникнуть, — это 7. И если мы предполагаем, что такой граф существует, тогда получается, что есть вершина какая-то, которая имеет степень 7, то есть которая соединена со всеми остальными. 5, 6, 7. Вот она соединена просто со всеми оставшимися вершинами этого графа. Но как же тогда может такое быть, что среди этих вершин есть вершина степени 0? Вот ровно, как в той задаче. Ровно, как в той задаче. Да, такого графа тоже быть не может. На самом деле, друзья, можно предложить некий очень простой алгоритм, очень простой алгоритм, который по данной последовательности однозначно после определенного количества итераций говорит, можно по ней построить граф или нельзя. Но это все-таки выходит за рамки данного обсуждения, хотя мне кажется исключительно симпатичным тоже фактом. И есть общая теорема Эрдеша — Галлаи, которая тоже позваляет даже без алгоритма, а просто там, сравнивая некоторые числа, посмотреть, является данная последовательность чисел реализуемой графом с такими вот степенями вершин или не является. Это вот известная классическая задача теории графов. Но в этих конкретных примерах все было просто.
