Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Первая часть доказательства критерия
Loading...
From the course by Moscow Institute of Physics and Technology
Теория графов
268 оценки
From the lesson
Формула Кэли. Унициклические графы. Эйлеровы циклы
На этой неделе мы перечислим все деревья. Для этого нам потребуется перенять опыт древних по подсчету баранов (или козлов). Не остановившись на этом, перечислим и все леса и унициклические графы. Затем мы вернемся к задаче о Кёнигсбергских мостах и получим полное решение этого вопроса.
Meet the Instructors
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавскийкандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
Так, ну, все, давайте доказывать теорему.
Как обычно, если мы хотим установить эквивалентность каких-то трех утверждений,
то проще всего сначала из утверждения
1 вывести как следствие утверждение 2, потом доказать,
что из 2 следует 3, ну, и наконец пояснить, почему из 3 вытекает 1.
Ну, так, по циклу их доказать, понятно,
что мы тем самым установим их попарную равносильность, эквивалентность.
Ну, и давайте я по пунктам это буду делать.
То, что из 1 следует 2 — это мы уже обсуждали.
Понятно, что если граф эйлеров, то степень каждой вершины графа является
четным числом, это мы только что проговаривали и давайте считать,
что здесь говорить больше не о чем, все доказано.
Вот. Но нам же нужно доказать,
что в обратную сторону тоже верно, поэтому нам нужно реализовать вот эти две
импликации тоже: следствие из 2 – 3 и следствие из 3 – 1.
Давайте, второй пункт доказательства тем самым — это мы
сейчас попробуем вывести из пункта 2 пункт 3.
То есть, мы знаем сейчас,
что степень каждой вершины графа является четным числом, это нам дано,
и мы хотим доказать, что в этом случае множество ребер нашего графа действительно
распадается в объединение попарно не пересекающихся по ребрам простых циклов.
Ну, давайте, возьмем какой-нибудь граф G,
понятное дело, с множеством вершин V и множеством ребер E.
Да, заметьте, что в данном случае, когда я употребляю слово «граф», я предполагаю,
что мультиграфы мы тоже можем рассматривать, потому что иначе получится,
что мы как бы и не находимся в условиях задачи о Кенигсбергских мостах.
Естественно, в этом месте слово «граф» предполагает и «мультиграф» тоже,
кратные ребра разрешены, но не петли и не ориентация,
об этом я сейчас не говорю, там все по-другому немножко.
Ну, хорошо, значит, дан граф, и мы знаем,
что каждая вершина имеет четную степень в этом графе.
Ну вот давайте возьмем какую-нибудь вершину, назовем ее x1.
Граф по определению связен.
Ну это понятно, если бы граф не был связен, то о какой эйлеровости вообще
можно было бы говорить, несвязный граф обойти невозможно.
Значит, из этой вершины выходит хотя бы одно ребро,
она не может быть изолированной, раз граф является связным.
Но если хотя бы одно, то, на самом деле, и хотя бы два, потому что,
повторяю, мы знаем, что степень каждой вершины нашего графа четная.
Ну, да бог с ним, пока достаточно того, что выходит хотя бы одно ребро,
и идет оно в какую-то вершину, которую мы, естественно, можем обозначить x2.
А вот теперь мы уже воспользуемся тем, что x2 имеет четную степень.
То есть помимо ребра x1 x2, который имеет своим концом эту вершину,
есть еще хотя бы одно ребро, которое из этой вершины, условно говоря, выходит.
Ну, ориентации нет, поэтому выходит или входит — это не важно.
Вот. Давайте нарисуем новую вершину x3,
которая таким образом получается, и про нее рассудим точно так же,
как только что мы рассудили относительно вершины x2: у нее четная степень, значит,
есть хотя бы одно ребро, помимо ребра x2 x3, которое смежно с этой вершиной.
Ну, тут уже есть варианты.
Во-первых, это ребро может пойти в вершину x1,
но тогда мы наловили некий простой цикл, это очень хорошо.
Видите, нашелся треугольничек, это простой цикл на трех вершинах.
Значит, уже один из циклов, который мы желаем получить в итоге,
которые будут попарно не пересекаться по ребрам, мы наловили.
Теоретически, конечно, может случиться, что такого счастья не произойдет,
то есть из x3 в x1 никакое ребро не отправится,
а отправится оно в какую-нибудь вершину x4, не присутствующую среди уже найденных.
Значит, получилась такая более длинная цепочка, но относительно вершины x4 можно,
конечно, опять-таки рассудить так: что либо из нее ребро идет в x2,
и тогда мы изловили простой цикл длины 3; либо из нее ребро идет в x1,
и тогда мы изловили простой цикл длины 4; ну,
либо опять не судьба и тогда у нас получается еще более длинная цепочка,
еще более длинный такой бамбук, заканчивающийся вершиной x5.
Но, друзья, понятно совершенно, что так до бесконечности продолжаться не может,
потому что у нас граф конечный, мы все графы рассматриваем, конечно,
только конечные.
Поэтому рано или поздно какая-то там очередная,
энная, скажем, вершина этого графа все-таки не отправит ребро еще дальше,
потому что мы просто исчерпаем все ребра, а отправит...
все вершины, извините, а отправит его куда-нибудь в одну из предшественниц,
и мы, таким образом, наловим первый простой цикл.
Итак, давайте обозначим, скажем, Z1,
тот простой цикл, существование которого в нашем графе мы уже доказали.
Z1 — первый найденный нами в рамках вот этого рассуждения простой цикл.
Теперь сделаем следующее.
Давайте я его нарисую как-нибудь, вот,
естественный пример, что-нибудь вот такое.
Понятно, что я вовсе не утверждаю, будто бы у любого просто цикла,
который мы найдем, будет 6 вершин.
Вы помните, там может быть 3 вершины, 4 вершины — сколько угодно,
но так просто для примера нарисовали.
Ну, и дальше там что-то еще в этом связном графе присутствует,
там могут быть еще какие-то циклы, которые мы сейчас будем ловить и так далее.
Вот тут какой-то такой разлапистый граф сидит на этом цикле.
Давайте возьмем и рёбра этого цикла сотрем, удалим из нашего графа,
не удаляя при этом вершины, которые соединяются этими рёбрами.
Значит, вот эти все рёбра удалим.
Ну, понятно, что граф, который получится на выходе, то есть граф,
который получится в результате удаления этих ребер, он может остаться связным,
потому что вполне не исключено, что здесь есть какие-то другие цепочки,
которые соединяют любые оставшиеся вершины, а может и потерять связность.
Ну, давайте для полноты картины, для общности будем все-таки говорить, что он,
вообще говоря, не связный, и будем рассматривать каждую компоненту
связности вот этого нового графа по отдельности.
Ну, рассмотрим любую
компоненту связности оставшегося в
результате удаления ребер нашего цикла Z1 графа,
оставшегося графа.
[ПИШЕТ НА ДОСКЕ] Ну, понятное дело,
что эта компонента связности просто по своему определению является
связным графом, это вообще очевидно, и, кроме того, коль скоро мы знаем,
что у исходного графа G степень каждой вершины была четным числом,
то в этой компоненте связности степень каждой вершины тоже будет четным числом.
Почему?
Потому что когда мы удаляли вот эти ребра, мы если и меняли какие-то
степени вершин в нашем графе при переходе от исходного графа G к вот этому новому,
с которым мы сейчас работаем, по отдельности рассматривая его компоненты
связности, вот если мы и меняли какие-то степени, то на 2.
Вот у этой вершины степень уменьшилась на 2,
и у этой вершины тоже степень уменьшилась на 2 и так далее.
То есть, если степени и поменялись, то на четное же число.
Поэтому вот в этой произвольной рассмотренной нами
компоненте связности все вершины являются четными числами.
Иными словами, по отношению к этой компоненте связности можно произвести
абсолютно такое же рассуждение, которое вот здесь вот мы
производили для нашего графа G и наловили в итоге цикл Z1.
Ну, давайте так и напишем: произведем в точности,
в точности те же рассуждения,
что и для исходного графа G,
что и для исходного графа G,
и найдем еще один простой цикл,
[ПИШЕТ НА ДОСКЕ] который,
разумеется, обозначим Z2.
Важное и естественное замечание состоит в том, что,
поскольку цикл мы этот нашли в какой-то компоненте связности графа,
у которого нету ни одного из ребер изначального цикла Z1,
то, конечно, ребра цикла Z2 ничего не имеют общего с ребрами цикла Z1.
Откуда им пересекаться, множествам этих ребер?
Вот вершины могут быть общими, пожалуйста: может получиться,
там, какой-нибудь вот такой вот цикл.
Но поскольку мы его рассматривали, повторяю, в графе,
в котором отсутствуют все вот эти вот ребра, то если и есть что-то общее,
то только вершины, ребер, естественно, общих не будет.
Видите, мы нарыли второй цикл, и он благополучно,
действительно, не имеет общих ребер с первым, как нам того и хотелось.
Ну, а дальше делаем все то же самое: удаляем из нашего графа, ну,
уже вот этого нового графа, который был получен удалением первоначального цикла,
удаляем из нашего графа в свою очередь ребра цикла Z2.
Удаляем ребра
цикла Z2 и продолжаем эту процедуру до тех пор,
пока не исчерпаются все ребра исходного графа G.
Понятно, что рано или поздно они исчерпаются просто все,
ребер не останется.
Но каждый раз, исчерпывая их, мы будем находить очередной цикл,
ребра которого ничего не имеют общего с ребрами циклов,
которые были найдены на предыдущих шагах процедуры.
То есть очевидно, что мы действительно понастроим какое-то количество простых
циклов, может быть, большое, может быть, маленькое, может, вообще только один,
которые все будут пересекаться только если по вершинам или вообще не пересекаться,
вот, и таким образом покроем множество всех ребер графа этими циклами.
Все.
Тем самым из 2 мы 3 вывели благополучно, с этим все в порядке.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
