Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Вторая часть доказательства критерия
Loading...
Do curso por Moscow Institute of Physics and Technology
Теория графов
278 classificações
Na lição
Формула Кэли. Унициклические графы. Эйлеровы циклы
На этой неделе мы перечислим все деревья. Для этого нам потребуется перенять опыт древних по подсчету баранов (или козлов). Не остановившись на этом, перечислим и все леса и унициклические графы. Затем мы вернемся к задаче о Кёнигсбергских мостах и получим полное решение этого вопроса.
Conheça os instrutores
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавскийкандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
Ну давайте выводить из пункта 3 пункт 1.
Так, это будет, соответственно, пункт 3 (со скобочкой) нашего доказательства.
Первые два мы уже доказали, вот теперь надо вывести из 3 1.
Иными словами, мы про граф G,
который мы рассматриваем, знаем, что для него выполнено условие вот этого пункта.
Давайте напишем G = (V, E).
Он обладает тем свойством, что его множество рёбер распадается в объединение
непересекающихся по рёбрам простых циклов.
Так, давайте запишем, множество рёбер — это
объединение в известном смысле непересекающихся,
непересекающихся простых циклов.
А хотим мы доказать,
что его можно обойти вот ровно так, как хотелось в задаче о
кёнигсбергских мостах, то есть мы хотим доказать, что выполнен пункт,
говорящий о том, что G представляет из себя цикл, эйлеров цикл.
Давайте действовать с помощью математической индукции,
которая будет идти просто по количеству тех простых циклов,
на которые распадается наш граф G.
Индукция, индукция
по числу простых циклов.
[ПИШЕТ НА ДОСКЕ] Ну,
база индукции совершенно очевидна.
Давайте напишем база — это, конечно, случай,
когда количество простых циклов, я прошу прощения, равняется единице.
Ну то есть наш граф представляет собой не что иное,
как ровно один простой цикл и больше ничего.
Очевидно, что такой граф можно обойти, это вообще не вопрос.
База индукции у нас есть, она в кармане.
Ну давайте сделаем предположение индукции, как полагается.
Предположение индукции.
[ПИШЕТ НА ДОСКЕ] Оно состоит в том,
что мы наше утверждение, то есть утверждение о том, что граф можно
обойти эйлеровским маршрутом, мы наше утверждение доказали для числа циклов,
ну какого-то числа циклов n, и вообще для любого меньшего числа.
Предположим, что утверждение, утверждение доказано,
то есть доказано, повторяю, существование эйлеровского обхода,
утверждение доказано для любого k,
не превосходящего некоторого числа n.
Ну вот, например, для любого натурального числа k, не превосходящего единицы,
мы в базе индукции доказали существование такого обхода, значит, мы можем
попытаться перейти к количеству циклов равным двойке, потом к тройке и так далее.
Замечательно.
Ну давайте рассмотрим, стало быть, граф G,
у которого, в свою очередь,
k = n + 1, то есть у которого множество
рёбер распадается в объединение n + 1 непересекающегося простого цикла,
и хотим доказать, что для любого такого графа, какой бы мы ни рассмотрели,
тоже существует эйлеров обход, эйлеров цикл.
Так, давайте зафиксируем какой-нибудь из этих n + 1 циклов.
Зафиксируем любой
цикл Z
из вот этих вот n + 1 циклов, на который распадается граф G.
Ну, давайте я даже условно картинку нарисую,
как всегда вот есть какой-то цикл, мы его обозначили Z,
а весь граф дальше тоже там состоит из каких-то непересекающихся циклов.
Как-то вот так вот это всё устроено.
По вершинам они пересекаться могут, а по рёбрам вот нельзя, не получается.
Ну и так далее.
Z — это, давайте я его так пожирнее выделю, это вот этот цикл.
Но повторяю, за Z можно было взять всё что угодно,
выбрали вот этот и давайте с ним работать.
Всё, вот это вот наш цикл Z.
Понятно, что вся оставшаяся часть графа представляет собою объединение уже n,
n простых циклов.
Другое дело, что если мы сотрём рёбра вот этого вот цикла Z из нашего графа,
то оставшаяся конструкция опять может представлять собою объединение
некоторого количества компонент связности.
То есть, если мы захотим сейчас удалить вот эти вот рёбра из нашего графа,
он, конечно, может развалиться на отдельные связные компоненты.
Ну вот давайте сделаем действительно это,
рассмотрим граф.
Ну как бы его назвать?
Давайте H, который получается из графа G,
получается из графа G удалением рёбер цикла Z,
удалением рёбер цикла Z.
Ну это такой будет вспомогательный граф, и я повторяю, вообще говоря,
он распадается на компоненты связности, то есть связным не является.
Давайте эти компоненты связности как-нибудь обозначим.
H₁ ..., Hm.
Я не знаю, чему равняется m, может быть,
m равняется единице, может быть я неправ, и этот граф окажется связным.
Но на практике может случиться, что он и несвязен,
поэтому просто обозначим буквой m количество связных компонент,
но оно может оказаться равным 1, ничего страшного.
Так, а теперь сделаем следующее.
Вернёмся к рассмотрению нашего графа G и попытаемся доказать,
что в этом графе есть эйлеровский цикл,
что его действительно можно обойти так, как нам того бы хотелось.
Ну что ж, давайте стартуем с произвольной вершины цикла Z.
Сейчас мы это всё напишем.
Стартуем с
произвольной вершины x,
принадлежащей циклу Z, и дальше делаем так.
Смотрите, вот эта вершина x во вспомогательном
графе H принадлежит какой-то из компонент связности.
Так и запишем, вершина x в графе H,
то есть в графе, который получился из графа G удалением рёбер цикла Z,
вершина x в графе H принадлежит какой-то компоненте связности.
Какой-то компоненте.
Ну давайте без ограничения общности, как принято говорить, ну перенумеруем,
если что, считать, что x принадлежит H₁, чтоб не морочить голову.
Без ограничения общности, сокращённо БОО,
x принадлежит компоненте H₁.
Ну, если хотите, мы просто стартовали с вершины, которая принадлежит H₁,
нам ведь всё равно было откуда стартовать, откуда начать маршрут.
Замечательно.
Компонента H₁ является связным
графом, и множество её рёбер, конечно,
распадается в объединение непересекающихся простых циклов.
Причём количество этих простых циклов уже, конечно, не превосходит n,
ведь у исходного графа их было в точности n + 1,
но цикл Z в графе H отсутствует, и, значит, вот эта компонента H₁
разбита на не более чем n непересекающихся простых циклов.
Давайте это тоже запишем.
H₁ разбита на не более чем n
непересекающихся простых циклов.
И, повторяю, она, конечно, является связным графом...
непересекающихся простых циклов.
Иными словами, по отношению к компоненте H₁
мы можем применить предположение индукции и вот эту компоненту обойти так,
как нам того бы хотелось, то есть двигаться по рёбрам,
каждое ребро проходить ровно по одному разу и вернуться в ту же самую вершину x.
То есть вот мы где-то здесь по этой компоненте погуляли, погуляли и,
в конце концов, в вершину x возвратились.
По-моему, понятно.
Всё, применяем предположение индукции, давайте я это зафиксирую на доске,
и обходим
всю компоненту H₁,
возвращаясь в итоге в нашу вершину x.
А дальше делаем очень просто.
Двигаемся по рёбрам цикла Z.
Но как двигаемся?
Дошли до следующей вершины и смотрим,
а она принадлежит какой компоненте связности графа H?
Вот если следующая вершина по-прежнему находится в связной
компоненте H₁, то мы ничего не делаем и двигаемся дальше.
И вот мы так двигаемся по рёбрам цикла Z, покуда не встретим вершину,
которая находится в какой-то другой компоненте связности.
Ну считайте, если угодно, опять без ограничений общности,
что эта связная компонента H2.
Давайте это зафиксируем.
Двигаемся далее в графе G, не в графе H.
В графе H этого цикла нет.
Но вот двигаемся в графе G по рёбрам Z,
пока не наткнёмся на вершину,
которая принадлежит другой компоненте связности графа H,
не встретим вершину y,
просто так её обозначим, которая
принадлежит другой
компоненте графа H.
Ну вот дошли до какой-то вершины, она принадлежит
другой компоненте графа H, опять эта компонента связный граф,
и опять к ней можно применить предположение индукции.
Дальше всё понятно, обходим эту компоненту согласно предположению индукции,
возвращаемся в нашу условную вершину y и снова двигаемся по рёбрам цикла Z,
покуда не встретим очередную ещё не встречавшуюся нам до сих пор компоненту.
Ну понятно, что, в конце концов, мы вернёмся в точку x,
обойдя все компоненты H₁ Hn последовательно,
им неоткуда просто больше взяться, и граф будет обойден,
никаких общих рёбер в этом маршруте, который мы построили,
не возникнет, и переход из 3 в 1 полностью доказан.
Я думаю, что здесь уже даже фиксировать ничего не нужно, просто повторяю,
продолжаем описанную процедуру до тех пор,
пока не обойдём все компоненты и не пройдём по всем рёбрам цикла графа,
цикла, извините, Z вплоть до вершины x.
Всё, теорема доказана.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
