Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Последовательности степеней
Loading...
From the course by Moscow Institute of Physics and Technology
Теория графов
261 оценки
From the lesson
Введение. Базовые понятия теории графов
В первую неделю курса мы познакомимся с понятием графа, научимся отличать граф от его изображения, поговорим о разных видах графов. Мы вспомним, с чего началась теория графов, научимся представлять в виде графа структуру интернета. Мы обсудим такие важные понятия, как маршруты в графах, степень вершины, связность, а также начнем говорить про важный класс графов - деревья.
Meet the Instructors
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавскийкандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
Давайте попробуем теперь поразбираться, всегда ли возможно
построить граф с заданной последовательностью степеней вершин.
Я взял шпаргалку, потому что на память мне трудно запомнить такие последовательности,
которые мы тут напридумывали.
Ну я сейчас со шпаргалки их спишу.
Значит, смотрите, вот, например, пункт «а».
Рассмотрим такую последовательность чисел: 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?
Вот ровно, как в той задаче.
Ровно, как в той задаче.
Да, такого графа тоже быть не может.
На самом деле, друзья, можно предложить некий очень простой алгоритм,
очень простой алгоритм, который по данной последовательности однозначно после
определенного количества итераций говорит, можно по ней построить граф или нельзя.
Но это все-таки выходит за рамки данного обсуждения,
хотя мне кажется исключительно симпатичным тоже фактом.
И есть общая теорема Эрдеша — Галлаи, которая тоже позваляет даже без алгоритма,
а просто там, сравнивая некоторые числа, посмотреть,
является данная последовательность чисел реализуемой графом с
такими вот степенями вершин или не является.
Это вот известная классическая задача теории графов.
Но в этих конкретных примерах все было просто.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
