Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Замкнутый маршрут
Loading...
Do curso por Moscow Institute of Physics and Technology
Теория графов
268 ratings
Na lição
Введение. Базовые понятия теории графов
В первую неделю курса мы познакомимся с понятием графа, научимся отличать граф от его изображения, поговорим о разных видах графов. Мы вспомним, с чего началась теория графов, научимся представлять в виде графа структуру интернета. Мы обсудим такие важные понятия, как маршруты в графах, степень вершины, связность, а также начнем говорить про важный класс графов - деревья.
Conheça os instrutores
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавскийкандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
Ну давайте, наверное, последнюю задачку по первой лекции разберем.
Тоже на то, как устроены маршруты в графах.
И утверждение этой задачи, оно такое: в любом, связном графе, ну нетривиальном,
конечно, то есть состоящим больше, чем из одной вершины, есть замкнутый маршрут,
замкнутый маршрут, который стартует из произвольной вершины, в нее же,
естественно, возвращается и при этом проходит по каждому ребру ровно два раза.
Давайте это запишем.
В любом связном графе
есть замкнутый
маршрут, маршрут,
который стартует с произвольной вершины,
[ПИШЕТ НА ДОСКЕ]
с произвольной
вершины и проходит
по каждому ребру графа, по каждому
ребру ровно два раза.
[ПИШЕТ НА ДОСКЕ] Друзья,
в этом месте очень важно понимать, что я ни в коем случае не говорю о цикле.
То есть я не утверждаю, что у меня получится именно цикл с точки зрения тех
определений, которые я давал на лекции.
У меня получится просто какой-то маршрут.
То есть там можно болтаться туда-обратно, например, по ребру.
Это никак не возбраняется.
Ну давайте докажем утверждение индукции по количеству ребер в графе.
Докажем индукции по количеству ребер.
Ну поскольку граф нетривиальный, то есть состоящий не из одной
вершины и при этом связный, то в графе одно ребро.
Это просто означает, что граф из себя представляет вот это вот одно ребро.
Если ребер 1, самое маленькое количество, какое только может быть,
то граф из себя представляет, собственно, вот это самое одно ребро.
Знаете, несвязный граф мог бы быть там как-то погано устроен.
Ну так понятно, что в несвязном графе маршрута нету априори.
Граф связный состоит из одного ребра.
Мы стартуем из произвольной вершины.
Хоть отсюда, хоть отсюда.
Понятно, что мы сначала пройдем по ребру в одну сторону.
Например вот так.
Ну а потом просто вернемся по этому ребру в изначальную вершину и у нас благополучно
получится тот самый маршрут, который, повторяю, никаким циклом не является,
но который проходит по каждому ребру этого простенького графа ровно два раза.
По этому единственному ребру он проходит ровно два раза.
Никаких проблем, и при этом нам совершенно плевать с какой вершины стартовать.
Таким образом база индукции очевидна.
Значит, база индукции очевидна.
Здесь никаких вопросов.
Ну давайте предположим, что для всех связных графов с
числом ребер не превосходящим какого-нибудь там n, наше утверждение
доказано и рассмотрим произвольный связный граф, у которого на единичку больше ребер.
Рассмотрим произвольный связный граф, у которого n + 1 ребро.
Произвольный связный
граф уже с n + 1 ребром.
То есть хотим совершить шаг индукции.
Ну давайте, действительно,
стартуем с совершенно произвольной вершины этого графа.
То есть возьмем произвольную его вершину.
Возьмем его произвольную вершину, которую как-нибудь назовем, ну как водится, — V.
[Неразборчиво] Возьмем произвольную вершину этого графа, которую назовем V.
Так, ну поскольку граф является связным,
то у этой вершины есть хотя бы одна соседка.
В связном графе не может быть, понятное дело, изолированных вершин.
Значит, рассмотрим ребро, которое заведомо
есть какое-нибудь совершенно произвольное (V,W).
Я повторяю: V не может быть изолированной вершиной, потому что граф связен.
Ну давайте я нарисую соответствующую картинку: V и W.
Вот рассмотрим такую ситуацию.
И теперь, товарищи, возможны два случая.
Значит первый случай, он вот какой.
Давайте представим себе,
что мы удалили вот это вот ребро из нашего связного графа.
Удалили ребро с вершинами V и W.
Вот что возможно?
Возможно, что граф потеряет связность, а возможно, что не потеряет.
Ну давайте в первом случае будем считать, что при удалении,
при удалении вот этого ребра
(V,W) граф не теряет связность.
Не теряет связность, то есть остается связным.
Но смотрите, вот мы удалили это ребро.
Мы его удалили.
Граф связность не потерял, а количество ве...
а, извините, не вершин, а ребер.
Количество ребер в новом графе, который по прежнему связен, оно на 1 меньше.
То есть — равняется n.
Для такого графа введу предположение индукции.
Интересующий нас маршрут заведомо существует,
стартующий из совершенно произвольной вершины.
Ну давайте, например, считать, что мы стартуем как раз из вершины V.
Вот в этом новом графе, который получился из исходного удалением вот этого ребра,
мы его вычеркнули, мы знаем по предположению индукции, что существует
замкнутый маршрут, стартующий из V и возвращающийся в эту вершину,
который проходит по каждому ребру оставшегося графа ровно два раза.
Но при этом, конечно, он не шел по этому ребру, потому что оно было удалено.
В оставшемся графе ровно этого ребра-то и нету, а другие есть,
и по каждому мы прошли ровно по два раза.
Ну как совершить шаг индукции?
Понятно, мы проводим вот этот вот маршрут,
который по предположению индукции существует.
Он все-все-все ребра исходного графа обходит.
Обходит ровно по два раза.
Но единственное ребро, которое он не прошел, это вот это.
Ну замечательно.
Пройдем в одну сторону, как в базе индукции, вернемся.
У нас получится опять же замкнутый маршрут, который стартовал с
совершенно произвольной вершины V, вот так вот прошел, он прошел сюда, прошел сюда,
вернулся в эту же самую вершину V и при этом как здесь по предположению
индукции прошел по каждому ребру дважды, так и на вот этом единственном,
которое не было учтено в предположении индукции, тоже побывал туда и обратно.
То есть все в порядке.
Первый случай, таким образом, полностью разобран.
Ну давайте еще рассмотрим второй случай.
Второй случай...
я предлагаю немножко сместиться вот сюда...
второй случай, это что при удалении,
при удалении вот этого ребра (V и W) образуются
две компоненты связности, то есть граф разваливается на две связных компоненты.
Давайте так и напишем: граф разваливается на
две компоненты.
Картинка вот такая: есть одна компонента — в ней находится вершина V,
есть какая-то другая компонента — в ней находится вершина W, и вот между
ними идет такой мостик, удаление которого как раз и привело к образованию вот
этих двух половинок, вот этих двух частей нашего графа, что мы удалили.
Образовались две половинки.
Совершенно очевидно, товарищи, я думаю, что это совершенно очевидно,
что в каждой из этих половинок количество ребер, разумеется, не превосходит n.
Вот здесь не больше, чем n ребер, ну если изначально их было n + 1 и мы одно
удалили, то понятно, что в каждой из половинок не больше, чем n ребер.
То есть к каждой из половинок мы можем применить предположение индукции.
А именно — вот в этой левой половинке мы стартуем из вершины V.
Так?
Обходим все ребра по предположению индукции,
так чтобы каждое ребро было пройдено ровно два раза,
возвращаемся в эту вершинку V, идем по удаленному ребру,
возвращаем его как бы в исходный граф, идем по нему в исходном графе,
пока что только единожды по направлению слева направо,
дальше, в правой части мы тоже применяем предположение индукции,
то есть мы спокойно можем стартовать с вершины W, как-то там все это дело обойти,
чтобы каждое ребро было пройдено ровно два раза, это заведомо можно, потому что не
больше, чем n ребер, а дальше просто берем и идем обратно по этому ребру.
То есть мы стартовали с V, прошли все вот эти ребра, каждое по два раза,
потом прошли сюда, здесь прошли все ребра, каждое по два раза, и вернулись назад,
поэтому даже изначально удаленное ребро мы действительно прошли и туда и обратно.
Все ребра пройдены по два раза и шаг индукции завершен.
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.
