Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Паросочетания и степени вершин
Loading...
來自 Moscow Institute of Physics and Technology 的課程
Теория графов
266 個評分
從本節課中
Паросочетания. Теоремы Холла и Кёнига
На этой неделе мы поговорим про паросочетания. Мы узнаем, что нужно, чтобы переженить всех юношей и девушек по любви. Мы обсудим две классических теоремы, у одной из которых очень изящное доказательство по индукции, а у другой не менее изящное доказательство алгоритмическое. А на семинаре мы узнаем, что эти две теоремы эквивалентны.
與講師見面
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавскийкандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
Давайте рассмотрим еще одну забавную симпатичную задачу на применение
теоремы Холла.
Разумеется, у нас есть двудольный граф.
Так, дан двудольный граф.
Давайте считать, что он не имеет изолированных вершин,
то есть вершин степени 0.
Вершин, которые вообще ни с какими ребрами дело не имеют, в этом графе нет.
Двудольный граф без изолированных вершин,
без изолированных вершин.
И давайте считать, что каждая вершина из верхней доли,
если она соединена ребром с какой-то вершиной из нижней доли,
то она имеет степень не меньшую, чем степень вот этой нижней вершины.
Ну то есть если a из
A, b из B и (a,
b) — ребро,
то степень вершины a больше либо равняется степени вершины b.
Вот давайте так считать.
Ну я надеюсь, что все понимают уже сейчас, что A — это верхняя доля,
B — это нижняя доля.
Утверждается, что в этом случае существует паросочетание в этом графе,
которое покрывает все вершины доли A.
Значит, докажем или докажите, что существует
паросочетание, покрывающее
[БЕЗ_ЗВУКА] все вершины доли A,
верхней доли, нашей условной верхней доли.
Такое паросочетание.
Ну понятно, если мы желаем это доказать, значит, наверное,
нам стоит попробовать проверить условие Холла.
То самое, которое, собственно,
наличие такого паросочетания в теореме Холла как раз и гарантирует.
Значит, почему выполнено условие Холла?
Ну вот давайте это проверим.
Рассмотрим произвольное множество S,
находящееся внутри верхней доли.
Наша цель показать, что количество соседей в нашем графе, которые расположены,
естественно, внутри множества B, никак не меньше, чем мощность этого множества S.
Докажем, что мощность N(S),
то есть количество соседей, находящихся в B, не меньше, чем мощность S.
Введем следующее обозначение: вот пусть у нас
есть какое-то ребро e, пусть у нас есть какое-то ребро e.
Я немножко тороплюсь, на самом деле, прежде чем вводить это обозначение,
давайте сделаем вот что.
Давайте рассмотрим граф G',
который является индуцированным, порожденным подграфом исходного графа G,
и порожден он множествами S и N(S), ну что вполне естественно.
Вот у нас есть верхняя доля, в ней расположено наше произвольное множество S,
и есть множество соседей этого множества S, расположенных в нижней доле N(S).
И вот мы рассматриваем индуцированный подграф нашего исходного графа.
Ну можно это нарисовать, как обычно.
Не знаю, может быть, даже я и не буду сейчас это рисовать, не так важно.
И вот теперь, собственно, введем обещанное обозначение.
Это я, было, поторопился.
Вот у нас есть какое-то ребро этого графа.
Давайте для этого ребра (ребра, идущего из S в N(S),
понятное дело), давайте для этого ребра введем обозначение dS(e)
— это будет степень той вершины этого ребра, которая находится в множестве S.
Степень той вершины ребра e,
которая находится в множестве S.
Ну и аналогично dN(S) от e — это степень той вершины ребра e, которая,
наоборот, находится в нижней доле, то есть в множестве соседей множества S.
Смотрите, что замечательно: понятно,
что d(S) от e просто по определению равняется степени вот этой самой вершины.
Давайте степень той вершины v, которая находится в множестве S.
Степень v имеется в виду в исходном графе G.
В исходном графе G степень этой вершины в точности такая же,
как вот в этом нашем новом индуцированном подграфе.
Просто потому, что в исходном графе изначально из S только в N(S) ребра и шли.
А вот d с индексом N(S) от e эта
величина уже не превосходит степени в
исходном графе той вершины w, которая
была расположена в нижней доле и служила концом и служит концом нашего ребра e.
То есть dS(e) в точности равняется deg v, а вот dN(S) от (e) она может быть меньше.
Ну понятно: в нижней доле могут быть не только соседи вот этого множества,
но и соседи каких-то еще вершин.
Поэтому степени могли понизиться внутри вот этого вот графа,
по сравнению со степенями исходного графа.
Но для нас это только сейчас будет хорошо.
Сейчас вы это увидите.
Давайте сначала распишем величину мощность S.
Очень симпатично ее распишем, воспользовавшись тем, — внимание!
— что в нашем графе по определению нет изолированных вершин.
Я утверждаю, что мощность S можно посчитать следующим образом: мы суммируем
по все ребрам e (ну по всем ребрам, имеется в виду, вот этого графа G',
которые в нем присутствуют) величину 1 поделить на d с индексом S(e).
Вот это выглядит как-то очень неожиданно, на первый взгляд: как это, сумма каких-то
дробей вдруг окажется равной целому числу, которая есть мощность нашего множества S?
Но в действительности все очень просто.
Смотрите, что такое dS от (e) по определению?
Ну давайте я все-таки нарисую какую-то картинку.
Вот у нас есть ребро e из одной доли в другую.
Вот это ребро e.
Вот это вершина v, вот это вершина w.
Давайте подумаем, сколько раз величина dS от (e) встречается в этой сумме?
Величина dS от (e) — это, внимание!
— это степень вот этой вершины v.
То есть эта величина соответствует и нашему ребру e, и еще какому-то ребру e',
которое так же примыкает к вершине v и идет вниз, и еще какому-то ребру.
То есть вот это вот слагаемое, равное 1 поделить на dS от (e),
оно в нашем суммировании встречается столько раз, сколько есть ребер,
выходящих из вершины v, которая служит концом вот именно этого ребра e.
Ну а сколько выходит ребер?
Естественно, степень этой вершины.
То есть это слагаемое встречается в этой сумме столько раз,
какова степень вот этой конкретной вершины.
Ну в знаменателе-то эта самая степень и стоит.
То есть мы складываем вот эту дробь столько раз, чему равен ее знаменатель.
Естественно, мы получаем 1.
И теперь мы единицу, очевидно, получаем столько раз,
сколько у нас есть вершин вот в этой верхней дольке, которую мы обозначаем S.
Ну значит, получается в точности мощность S.
То есть это очень простая вещь, которая на первый взгляд казалось неожиданной.
С другой стороны, смотрите, мы знаем, что dS от (e),
dS от (e)...
так, это величина, которая...
Сейчас секундочку, я пойму.
Которая...
Так, dS от (e) — это степень вот этой вот вершины v.
Отлично!
У нас есть еще одно условие в нашей задаче,
которое меня чуть-чуть затормозило.
Извините, сейчас мы его как раз и используем.
Смотрите, если у нас есть какое-то ребро, то по условию нашей задачи степень верхней
вершины не меньше, чем степень нижней вершины.
Внимание, это в исходном графе.
Но в нашем графе G' неравенство продолжается в нужную сторону.
Степень исходной вершины больше либо равна вот этой вот степени.
То есть мы получаем, мы получаем, что
dS от (e) больше либо
равна d с индексом N от (S) от (e).
Понятно, да?
dS от (e) больше либо равняется dN от (S) от (e).
Потому что dS от (e) — это степень вершины v,
она больше либо равна по условию, чем степень вершины w, которая,
в свою очередь, больше либо равна, нежели dN от (S) от (e).
То есть мы получаем здесь знак неравенства,
поскольку все написано в знаменателе в другую сторону.
Это будет сумма по e 1 поделить на dN от (S) от (e).
А это ровно потому же рассуждению,
которое мы только что провели вот в этом месте, ровно с помощью такого же
рассуждения оказывается равным мощности множества N от (S).
Ну и мы доказали, что мощность множества N от (S) больше либо равна мощности S,
что нам и требовалось.
Все, условие Холла есть, и значит есть паросочетание,
которое покрывает все вершины верхней доли.
