Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
К-регулярный двудольный граф
Loading...
来自 莫斯科物理科学与技术学院 的课程
Теория графов
230 评分
从本节课中
Паросочетания. Теоремы Холла и Кёнига
На этой неделе мы поговорим про паросочетания. Мы узнаем, что нужно, чтобы переженить всех юношей и девушек по любви. Мы обсудим две классических теоремы, у одной из которых очень изящное доказательство по индукции, а у другой не менее изящное доказательство алгоритмическое. А на семинаре мы узнаем, что эти две теоремы эквивалентны.
与讲师见面
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавскийкандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
Давайте поразбираемся с задачами, которые связаны, ну условно говоря,
с паросочетаниями в двудольных графах, то есть с задачами,
которые возникают по сути в связи с теоремами Холла и Кёнига.
Ну первая задача формально с теоремами Холла и Кёнига не связана,
давайте сформулируем её так.
Есть двудольный граф, но не полный.
Просто какой-то двудольный граф.
Давайте как обычно обозначим его доли,
верхнюю, скажем, буквой A, нижнюю буквой B.
Вот есть условная верхняя доля, которую я обозначаю буквой A,
и есть какая-то нижняя доля,
совершенно необязательно равная по мощности верхней, которую мы обозначим B.
Ну я обозначаю, мы с вами вместе обозначим, потому что деваться некуда,
я командую процессом.
Вот хорошо, ввели обозначения для долей и давайте ещё предположим,
внимание, что граф, то что называется, k-регулярный.
Ну этого термина я, может быть, раньше не вводил, поэтому давайте я скажу,
что это значит, это очень просто.
Имеется в виду, что степень каждой вершины в этом графе, каждой вершины,
как верхней так и нижней, равняется k.
Значит, граф k-регулярный, k-регулярный,
то есть любая его вершина имеет степень k,
в точности равную k, такой вот очень хороший граф.
Например, один регулярный граф, один регулярный граф, ну вот если доли
у нас имеют одинаковые размеры, это просто такое вот паросочетание на этих долях.
Это будет один регулярный граф, но если доли неодинакового размера,
тогда там, конечно, появятся вершины степени 0.
Вот. Ну вот мы предполагаем,
что этот двудольный граф не является полным, вообще говоря, полный, конечно,
тоже регулярен, но вот он является k-регулярным.
Предлагается доказать, докажите (ну докажите — это значит я сейчас,
конечно, разберу), значит, предлагается доказать,
что этот граф как минимум двусвязен.
Ну что значит по определению, что он двусвязен?
Это значит, что при удалении любой вершины он связность не теряет.
Он был связным и...
А, я забыл сказать, товарищи.
Да, конечно, я предполагаю, что этот изначальный граф связен.
Этот изначальный граф связен.
Ну хорошо, но я хочу доказать, что этот граф является двусвязным.
То есть при удалении любой вершины, он связность не потеряет.
Ну что ж, давайте предположим противное.
Давайте предположим,
что вопреки нашему утверждению существует какая-то
вершина a из верхней доли A, значит, я выбрал верхнюю долю то что называется
без ограничения общности и из того рассуждения, которое я сейчас приведу,
вы будете понимать, вы поймёте сразу, что можно было с таким же успехом, конечно,
начать с какой-то вершины b из нижней доли.
Ну вот давайте без ограничения общности предположим, что найдётся какая-то вершина
a из верхней доли нашего графа, давайте, например, первая.
Например, первая вершина из этой верхней доли найдётся,
такая, что при её удалении
из нашего исходного графа,
ну как обычно давайте назовём его буквой G, G — это вот этот вот наш исходный
k-регулярный двудольный граф, что при её удалении из графа G связность потеряется,
граф развалится на отдельные компоненты, которых может быть две, может быть больше,
это уж как посчастливится графу, но вот мы предполагаем, что связность утратится,
потеряется, появятся отдельные компоненты.
Давайте рассмотрим какую-нибудь конкретную компоненту связности,
которая получится в результате.
Совершенно произвольную.
Значит, рассмотрим любую связную компоненту,
связную компоненту.
Понятно, что эта связная компонента всё равно представляет собою какой-то
двудольный подграф исходного двудольного графа,
то есть у неё есть долька сверху, некоторое подмножество множества A,
давайте я её здесь изображу условно такой «сарделечкой» и назову A'.
Ну я надеюсь, вы понимаете,
что «сарделечка» не обязана быть прямо вот такой вот связной, компактной,
она может быть как-то разбросана среди вершин из множества A без a, но...
a она, естественно, не содержит, потому что вершину a мы удалили.
И вот мы берём такую конструкцию, такое подмножество здесь,
ну и какое-то подмножество B' берём тут,
это у нас будет вторая доля нашей компоненты связности.
Значит, берём любую связную компоненту, это будет граф G',
натянутый на A' и B', я так это обозначу.
Это тот граф, который индуцируется нашим исходным графом G
на вот этих дольках A' и B' соответственно.
Понятно, что B', конечно, является собственным подмножеством множества B,
совпадать с B не может, потому что иначе у нас бы получилось, что при
удалении вершины a, из которой, конечно, выходили рёбра, их было, по крайней мере,
k, при удалении вершины a не удалилась ни одна вершина из множества B.
Ну понятно, в общем, да, граф развалился на связные компоненты, вот образовался
такой, один из этих, одна из этих связных компонент — подграф на A' и B'.
А теперь смотрите, будет очень красивое арифметическое рассуждение
про количество рёбер, количество рёбер вот в этом графе G'.
Значит, смотрите, вот количество рёбер.
Количество рёбер в графе G'.
С одной стороны, это количество рёбер, разумеется,
равняется сумме степеней вершин из множества A'.
Ну вот отсюда выходит какое-то количество рёбер, правильно?
Отсюда выходит какое-то количество рёбер,
ну и так далее, из последней вершины выходит какое-то количество рёбер.
Какое? Какое количество рёбер выходит из
каждой вершины множества A'?
Ну по-моему, совершенно очевидно, оно, конечно, равняется k.
Мы удалили только вершину a вместе со всеми теми k рёбрами,
которые к ней примыкали.
Но a же не принадлежит множеству A', значит в A' каждая
вершина имеет столько же соседей, сколько их было в исходном графе G.
Значит количество рёбер в графе G', очевидно, делится на k.
Делится на k.
Ещё раз повторяю,
потому что степень каждой вершины внутри множества A' просто равняется k,
ну значит сумма этих степеней, в аккурат равная количеству рёбер внутри графа G',
она делится на k как сумма чисел, делящихся на k, вроде бы всё понятно.
Но с другой стороны, а давайте подумаем,
что у нас происходит с вершинами множества B'?
Ведь можно же посмотреть и по-другому на это же самое количество рёбер.
Можно просуммировать не степени вершин из множества A', но степени,
наоборот, вершин из множества B'.
То есть посмотреть,
вот из этой вершины выходит количество рёбер внутрь множества A' какое-то,
из этой вершины тоже выходит какое-то количество рёбер внутрь множества A'.
Сложим вот эти вот числа, вот эти вот количества рёбер, степени вершин
из множества B' и опять-таки получим количество рёбер в графе G'.
Оно должно бы делиться на k, мы это знаем.
Но мы-то с вами предположили, что это отдельная связная компонента, да,
после удаления вершины a?
Вот я хочу объяснить, что теперь окажется, что оно на k не делится по
каким-то причинам, и это и будет искомым противоречием к нашему, как выяснится,
неверному предположению.
Значит, почему не делится на k?
Ну смотрите, вот есть эта вершина a в изначальном графе G, да?
В изначальном графе G.
Может ли такое случиться,
может ли такое случиться, что все соседи,
все k соседей, все k соседей, их k штук, граф k-регулярный,
все k соседей вершины a в исходном графе G сидят вот в этом множестве B'?
Может ли такое быть, что все k соседей этой вершины a сидят в множестве B'?
Что никаких соседей у вершины a вне множества B' нету.
Вот такого ребра нет, а все её соседи, все их,
все их k штук сидят в множестве B', вот может такое случиться или нет?
Не может, конечно.
Ну давайте я сейчас это зафиксирую.
Значит, не все...
А потом поясню, конечно.
Не все соседи вершины
a в графе G
находятся в B'.
Ну давайте поясню, почему не все соседи находятся в B'.
Если бы оказалось, что все соседи, вот все эти k товарищей, находятся
внутри множества B', тогда оказалось бы, что исходный граф G не является связным.
Смотрите, почему он не является связным, получилось бы так,
что Из вершин множества B', смотрите, ни из какой вершины даже,
я б так сказал, множества B', нельзя добраться, например, вот сюда.
Вот в эту вершинку.
Мы уже с вами заметили, что множество B' — это собственное подмножество множества B.
Поэтому, если граф связный, то Из каждой вершины множества B',
по идее, можно выбраться наружу внутрь этого множества B.
Но граф у нас двудольный, поэтому рёбер внутри самой доли B, конечно,
никаких нету.
Если и можно как-то выбраться, то сперва скакнув куда-то наверх,
а потом переместившись-таки сюда.
Ну или скакнув наверх, потом переместившись вниз, потом снова наверх и,
наконец, сюда.
Но понимаете, куда мы имеем возможность скакать наверх?
А, казалось бы, в этом случае,
когда все соседи в графе G вот этой вершины a, мы можем...
Находятся внутри B'.
Мы можем из B' куда скакать?
Ну мы можем скакать в вершину a, мы можем скакать в вершины из множества A'.
Но ни одна из них не поможет нам попасть в эту вершину, потому что все товарищи,
которые находятся в A', связаны только с B' по определению,
ну и a связано по вот этому предположению только с B'.
Так, конечно, быть не может.
Поэтому, не все соседи вершины a в графе G находятся внутри множества B'.
Их строго меньше, чем k.
Всего соседей k штук, ну значит их строго меньше, чем k.
Значит, соседей a в
B' не больше, давайте напишем, чем k − 1.
Строго меньше чем k — это то же самое, что не больше, чем k − 1.
Всего соседей там не больше, чем k − 1.
С другой стороны, давайте я уж не буду морочить голову,
рассуждение абсолютно такое же, можете проверить.
Конечно же, хотя бы один сосед вершины a, опять-таки, в виду связности
исходного графа G, хотя бы один сосед вершины a находится внутри B'.
Значит, я очень быстро сказал, ну давайте ещё раз повторю.
Вот по той же самой причине связности исходного графа,
их не меньше (этих самых соседей) одного.
Ну то есть в итоге у нас получается так,
что количество соседей вершины a внутри множества B' в
изначальном графе G не меньше 1 и не больше, чем k−1.
Но смотрите, в новом графе G' вершина a вместе
со всеми своими рёбрами, которые из неё выходят, удалена.
То есть вот у тех вершин, которые в изначальном
графе служили концами удалённых рёбер, у них степень уже не k,
как это было в изначальном k-регулярном графе, изначально-то она была равна k.
Она уже не k, она ровно на 1 меньше.
И таких вершин, у которых степень теперь не k, а k−1, теперь это значит в графе G',
вот таких вершин, как мы выяснили, от 1 до k−1 штуки.
От единицы до k−1 штуки.
Есть от 1 до k−1 штуки вершин,
каждая из которых степени k−1.
А все остальные вершины, внимание, товарищи,
все остальные вершины в B' вот в этом графе G' по-прежнему имеют степень k.
Ну давайте я это зафиксирую.
Есть от 1 до k−1
вершины в B' в графе G',
имеющие, в графе G',
имеющие степень ровно k−1,
а все остальные по-прежнему имеют степень k.
А все остальные по-прежнему
степени k.
Ну и какова тогда ж сумма степеней?
Ну те вершины, которые имеют степень k, они суммируются в какое-то число,
их степени суммируются в какое-то число, которое тоже, разумеется, делится на k.
А вот те вершины, у которых степень в точности k−1 и которых не 0 и не k,
а какое-то число в пределах от 1 до k−1,
они в сумме дают какое-то число, которое на k как раз не делится.
То есть, получается, что сумма степеней вершин в графе G',
вершин вот этого множества B', она не делится на k.
Часть слагаемых делится на k, а часть слагаемых не делится на k,
и в сумме получается число, которое на k уже разделить нельзя.
Ну и это, конечно, противоречие, потому что мы только что говорили, что,
если просуммировать степени вершин в A', то есть, опять же,
найти количество рёбер внутри графа G', то получится количество, делящееся на k.
Противоречие, и значит наше предположение неверно, то есть, действительно,
граф является двусвязным, как минимум.
