Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Число Рамсея для дерева и полного графа
Loading...
Из курса от партнера Moscow Institute of Physics and Technology
Теория графов
287 оценки
Из урока
Теория Рамсея
На заключительной лекции мы поговорим про теорию Рамсея. Вы узнаете много нового о знакомствах, о том, сколько раз можно в одном доказательстве применить принцип Дирихле и о том, что доказать существование графа и привести пример такого графа - это зачастую совсем разные по сложности задачи.
Познакомьтесь с преподавателями
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавскийкандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
Так, друзья, давайте позанимаемся теорией Рамсея.
На лекциях у нас уже было достаточно много весьма нетривиальных и забавных
утверждений.
Сейчас мы попробуем на примерах различных задач понять,
как еще могут быть устроены рамсеевские результаты, рамсеевские соображения.
Давайте обозначим буквой T произвольное конкретное дерево на 5 вершинах.
Произвольное дерево на 5 вершинах.
И введем по аналогии с обычным числом Рамсея
такую вот величину, обозначим ее R (T, K4).
Ну вот, что такое обычное число Рамсея?
Все помнят, конечно, определение.
Какое-нибудь там R (S, T), да?
Это минимальное количество вершин, такое, что для любого
графа с таким количеством вершин либо в нем есть копия полного графа KS,
либо в его дополнении, то есть мы все его ребра стерли,
а все, которых не было, провели, вот в его дополнении есть копия графа KT.
Ну вот здесь вместо KS мы рассматриваем дерево T.
А вместо KT рассматриваем K4.
Давайте так и напишем.
Это есть по определению минимальное натуральное число N,
такое, что для любого G = (V,
E), у которого мощность V = n,
то есть для любого графа на n вершинах.
Либо в G есть дерево
T, либо в G с чертой есть полный граф на 4 вершинах.
Ну, это то же самое, конечно, либо в G в самом
есть независимое множество,
независимое множество на 4-х вершинах.
Давайте еще раз.
Либо в самом графе есть копия дерева T,
либо в его дополнении есть копия полного графа K4.
Но в его дополнении есть копия полного графа K4, это то же самое,
что в нем самом есть независимое множество на 4-х вершинах.
Я думаю, что это понятно.
Вот минимальное количество вершин, которые гарантируют, что какой бы граф мы не
взяли, в нем есть либо это дерево, либо четырехвершинное независимое множество,
минимальное такое n и обозначает наше нынешнее R (T, K4).
Вот интересно, чему это равняется.
Значит задача состоит в том, чтобы доказать, что R (T,
K4) = 13.
Ну, действительно, давайте, во-первых, докажем, что R (T,
K4) больше, либо равняется 13.
Для того чтобы это обосновать, нужно просто привести
пример такого графа на 12 вершинах, в котором нету ни дерева T,
ни независимого множества на 4-х вершинах.
Если мы такой пример приведем,
тогда минимальное n с вот этой альтернативой уж точно не меньше, чем 13,
раз на 12 вершинах бывает гнусный граф, который ни того,
ни другого не содержит, ни T, ни независимого множества на 4-х вершинах.
Ну пример очень простой.
Давайте рассмотрим три копии графа K4,
три копии графа K4, между которыми никаких ребер нету.
То есть вот здесь вот полный граф на 4-х вершинах,
здесь полный граф на 4 вершинах, и здесь полный граф на 4 вершинах,
и вот это все вместе — некоторый граф с 3 компонентами связности,
каждый из которых является полным графом на 4-х вершинах.
У него, естественно, 12 вершин и у него число
независимости, конечно, не превосходит 3.
Ну это как турановский результат.
Помните?
Ну, это в общем совершенно понятно.
Из каждого полного графа на 4-х вершинах мы больше одной вершинки-то в независимое
множество все равно взять не сможем.
Как только мы берем 2, там сразу возникает ребро,
поэтому число независимости этого графа заведомо не превосходит 3.
Ну и стало быть, смотрите, может в нем возникнуть дерево на 5 вершинах?
Нет, конечно.
Потому что это граф на 4 вершинах, это граф на 4 вершинах,
и это граф на 4 вершинах.
Дерево на 5 вершинах никак не возникнет.
Дерево на 5 вершинах — это связный граф.
Ему взяться неоткуда.
Значит дерева на 5 вершинах там нет, а α (G) не превосходит 3, это значит,
что независимого множества на 4 вершинах в этом замечательном примере тоже нет.
То есть пример очень простой, очень простой.
Но вот теперь нам предстоит доказать,
что R (T, K4) точно не превосходит 13,
то есть теперь мы берем произвольный граф на 13 вершинах,
произвольный абсолютно, и пытаемся доказать, что либо в нем найдется копия
нашего конкретного дерева, либо уж если этого не случится,
то точно найдется независимое множество на 4-х вершинах.
Ну, давайте рассуждать более или менее в стандартном духе.
Вот у нас G.
Вот у него 13 вершин.
Давайте предположим для начала,
предположим, что
для любой вершины нашего графа,
который мы зафиксировали, для любой его вершины степень
больше либо равняется 4.
Помните, как мы с вами когда-то очень давно, еще там в первом семинаре,
наверное, разбирали такую задачку.
Если степень каждой вершины графа, ну или там минимальная степень
вершины графа не меньше n или равняется n, где n больше,
либо равно 1, тогда этот граф точно содержит цепь с не менее,
чем n ребрами, ну и, соответственно, с менее чем n + 1 вершиной.
Смотрите, здесь мы знаем, что минимальная степень не меньше 4.
Но, значит, мы можем гарантировать,
что в таком графе поймается цепь, содержащая, как минимум 5 вершин.
Но если вы вспомните то рассуждение, с помощью которого мы доказали,
что поймается цепь, содержащая не менее 5 вершин,
а оно было совершенно элементарным, мы просто брали произвольную вершину,
выводили из нее какое-то ребро, удаляли эту вершину вместе со всеми смежными
ребрами, смотрели на оставшиеся вершины, замечали, что у них там степень уже,
соответственно, не меньше, чем n − 1 и дальше продолжали эту процедуру.
Так вот, если вы посмотрите на это рассуждение, то вы поймете,
что не только цепь на 5 вершинах, но и любое дерево на 5 вершинах эта процедура
нам обеспечивает, любое дерево на 5 вершинах.
То есть, если мы предполагаем,
что у каждой вершины нашего графа степень не меньше 4-х, то не только дерево,
представляющее собою цепь на 5 вершинах, но и наше конкретное дерево T,
которое сейчас у нас зафиксировано, мы тоже можем гарантировать в нашем графе.
То есть в этом случае за счет идей очень простых,
которые я сейчас произнес заново, изложенных еще в первом семинаре,
в этом случае мы гарантируем наличие T,
дерева T в нашем графе.
И все замечательно.
Наличие дерева T в нашем графе.
И все, конечно, совершенно замечательно, вы в героях.
Ну ладно, давайте предположим, что нам не повезло.
Пусть наоборот.
Пусть, наоборот,
существует такая вершина из множества вершин нашего графа, которая,
к несчастью, имеет маленькую степень, то есть степень, не превосходящую 3.
Тогда у нас нет ресурса для того,
чтобы гарантировать наличие дерева T в нашем графе.
Но у нас же есть альтернатива.
Мы можем попытаться в этом случае попробовать поискать независимое
множество на 4-х вершинах.
Ну, сразу-то мы его не найдем.
Вот давайте предположим, что есть вершина степени не больше, чем 3.
Вот какая-то эта вершина, V.
У нее степень не больше 3.
Но я нарисую, как будто бы она равняется 3, а так это в общем не очень важно.
Давайте удалим эту вершину из нашего графа вместе со всеми ребрами,
которые из нее выходят.
Сколько вершин таким образом удалится?
Давайте напишем.
Удалим V вместе со всеми смежными ребрами из исходного графа G.
Удалится, понятное дело, не больше 4-х вершин.
То есть останется граф с не менее чем 9 вершинами.
Не забывайте, что исходный граф по условию имеет 13 вершин.
Значит, вот если мы удаляем вершину с вот такой маленькой степенью и все выходящие
из нее ребра, тогда мы получаем на выходе граф, у которого не менее 9 вершин.
Дальше мы можем снова рассмотреть такую же точно альтернативу.
Давайте граф обозначим как-нибудь, G'.
И я еще раз для него произведу эту альтернативу,
чтобы было совершенно понятно.
Значит альтернатива такая.
Предположим, существует какая-то W из V (G') Ой, почему же существует.
Предположим, для любой W (извините, конечно, так же точно,
как было до сих пор).
Так вот, предположим, для любой W из V (G') deg W ≥ 4.
Ну, в этом случае, я вот так вот напишу, в этом случае (только
здесь G' надо писать) мы гарантируем наличие дерева T, но уже в графе G'.
Поэтому, если мы все время пытаемся избежать наличия T,
как-то вот привести к противоречию то, что у нас должно было получиться,
обмануть самих себя, то мы, конечно,
должны опять предполагать, что существует W из V (G'),
у которой снова степень не превосходит 3.
Ну и проделаем с ней ту же самую процедуру, которая вот здесь.
То есть вот она — W, из нее выходят 3 ребра или там меньше,
удалим W из G', удалим W из G'.
Останется какой-то там граф G'', если хотите,
G'' с не менее чем 5 вершинами.
Понятно, да?
То есть мы уже удалили,
то есть либо мы нашли дерево T в нашем графе, либо мы удалили вершину.
Либо снова нашли дерево T, и тогда мы в героях,
либо опять удалили вершину, но даже после того, как мы удалили 2 вершины,
у нас остался граф, который имеет не менее 5 вершин.
И следующая альтернатива точно такая же.
Ну, либо мы заловим дерево, либо мы еще раз покоцаем граф,
останется 1 вершина как минимум.
И вот смотрите, мы удаляем еще какую-то X.
То есть V, W, X.
После удаления X остается хотя бы 1 вершина.
Берем вот эту вершину, называем ее Y,
и либо на каком-то из шагов до удаления у нас образовалось дерево T и тогда все
замечательно, либо в конце концов мы набрали 4 вершины, V, W, X и Y.
И они по построению ребрами в исходном графе не соединены.
Потому что когда мы брали V, мы ведь удаляли всю ее окрестность.
W не могла в ней находиться.
W — это вершина несмежная с вершиной V.
И точно так же X заведомо несмежна ни с V, ни с W.
И, наконец, Y несмежна ни с X, ни с W, ни с V.
То есть если на каком-то этапе мы не изловили дерево,
то в конце концов мы заловим 4 вершины, которые попарно несмежны,
то есть, товарищи, образуют независимое множество на 4-х вершинах.
И задача полностью решена.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
