Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Завершение доказательства
Loading...
來自 Moscow Institute of Physics and Technology 的課程
Теория графов
268 個評分
從本節課中
Теория Рамсея
На заключительной лекции мы поговорим про теорию Рамсея. Вы узнаете много нового о знакомствах, о том, сколько раз можно в одном доказательстве применить принцип Дирихле и о том, что доказать существование графа и привести пример такого графа - это зачастую совсем разные по сложности задачи.
與講師見面
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавскийкандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
И вот в этом месте, как я уже обещал, когда рассматривал случай R(3, 3),
товарищи, я предлагаю рассмотреть только первый вариант альтернативы,
иначе занудству конца не будет.
Второй вариант — симметричный.
Такой же симметричный по отношению к первому, как второй вариант в случае R(3,
3) был симметричен по отношению к первому варианту в том случае.
Вспоминайте то доказательство,
и там действительно было все абсолютно симметрично.
Хорошо, ну давайте считать,
что A1 имеет
хотя бы R(s − 1,
t) соседей или соседок
вершин среди A2, ..., An.
Повторяюсь, симметричный вариант вы рассмотрите сами, если вдруг не понятно,
почему он симметричный.
Считаем, что вот столько соседок.
Ну давайте нарисуем соответствующую картинку.
Вот есть A1.
Давайте выделим соседок.
Помните, это же не ограничивает никакой общности кого обозвать соседками.
Давайте считать, что без ограничения общности соседки — это
первые вот столько вот вершин.
A с индексом R(s – 1, t) + 1, потому
что здесь нумерация начинается от двойки, стало быть она должна заканчиваться здесь,
чтобы соседок получилось в аккурат R(s – 1, t).
Вот в этом множестве R(s – 1, t) элементов.
И каждая вершина из этого множества в нашем
зафиксированном нами произвольном графе соединена с вершиной A1 ребром.
Ну то есть A1 является соседкой каждой из вот этих вершин.
В такой вот «сардельке».
В этой «сардельке» A1 соединена с каждой вершиной.
Внутри этой «сардельки».
Ну а дальше еще есть какие-то вершины.
Давайте их через многоточие напишем и без ограничения общности опять же считаем,
что с этими вершинами A1 уже ребром не соединена.
Так.
Перевели на секунду дух.
Осознаем, что происходит.
Как?
Понятно?
Мы предположили, что A1 имеет вот столько соседей среди оставшихся.
Какие номера у этих соседей, мы понимаем, что это совершенно не важно.
Поэтому, не ограничивая общности, посчитали, что номера суть вот такие.
То есть мы просто выделили множество вершин, которые являются соседними с A1,
обвели их вот в такую «сардельку» и глядим на эту картинку, радуемся.
Думаем, что же дальше с ней делать.
Что же дальше делать с этой картинкой?
Дорогие наши друзья,
а давайте рассмотрим ту
часть нашего
графа G вместе со всеми ребрами, которые там есть,
ту часть графа G, которая, собственно, находится в пресловутой «сардельке».
Которая находится в «сардельке».
Ну «сарделька», естественно, в кавычках.
Это такая метафора.
Люблю это слово, очень люблю.
Значит, рассмотрим ту часть графа G, которая находится в «сардельке».
Ну то есть вершинами ее служат A2, A3, A вот с таким страшным индексом —
это вершины того графа, той части графа G, которою мы рассматриваем.
И там конечно есть какие-то ребра.
Какие-то ребра там, безусловно, есть.
Ну я так без ограничения общности опять же на картинке какие-то ребра нарисовал.
А может и никаких ребер нет.
Не знаю.
Ну в общем, там живет какой-то граф со своими ребрами и вот с этими вершинами.
Всё. Вот рассмотрели часть нашего графа,
которая туда попала.
Теперь заметим, у этого графа… У этого графа.
У этой части графа.
У этой части графа или просто у этого графа R(s
– 1, t) вершин.
Вот всего столько вершин.
Но ведь мы же знаем определение числа Рамсея.
Что значит, что у какого-то графа столько вершин?
По определению числа Рамсея.
Вот у этого графа, который попал внутрь «сардельки», столько вершин.
Столько вершин.
Что это значит?
Это опять значит некоторую альтернативу.
Это значит, что либо в этой части графа, то есть в «сардельке»…
В этой части графа есть
полный подграф на
(s – 1) вершине,
либо, это просто по определению числа Рамсея,
либо в этой части
есть независимое множество на t вершинах.
Независимое множество на t вершинах.
Ну, либо, либо.
Ничего такого третьего здесь не дано.
Если вдруг это не случилось, то уж это точно произойдет.
И наоборот.
Это мы знаем, потому что R(s – 1) так определялось.
Любой граф, который имеет столько вершин, либо содержит K(s – 1),
либо содержит… Ну такую антиклику, да?
Независимое множество на t вершинах.
Либо его дополнение содержит K с индексом t.
Ну, в общем, как это не определяй, как это не крути, а то, что написано — правда.
Теперь смотрите.
Сейчас будет наступать катарсис.
Полная победа в нашем рассуждении.
Вы уже страдаете, вот сейчас мы будем вас спасать.
Очищать через это страдание.
Значит смотрите, что происходит.
Если выполнен второй вариант написанной альтернативы,
то есть в этой части, внутри «сардельки»,
есть независимое множество на t вершинах, то все — это полная победа.
Это значит во всем графе, а не только в его части,
тем более есть независимое множество на t вершинах.
Давайте это и напишем.
Если выполнен второй вариант,
то есть в «сардельке» есть независимое множество на t вершинах,
если выполнен второй вариант, то, разумеется,
тем более не только в части, но и во всем графе,
во всем графе G,
с которого мы стартовали и который был совершенно произвольным,
есть независимое множество на t вершинах.
Это банальность.
Это как-то совсем не впечатляет.
Обещанного катарсиса нет.
Но понимаете, но вдруг не выполнен этот второй вариант альтернативы.
Вдруг нет независимого множества на t вершинах нашей «сардельки»,
тогда, естественно, мы и во всем графе G существование такого
независимого множества гарантировать не в состоянии.
Но у нас всего два варианта.
Давайте посмотрим, что в первом.
Если наоборот выполнен первый вариант альтернативы.
То вроде как, беда, не хватает.
Давайте я вот здесь еще покажу.
Смотрите, мы хотим доказать, что в графе G, в нашем графе,
либо есть Ks, либо есть независимое множество на t вершинах.
Но вот мы только что показали в рамках второго варианта альтернативы, что да,
независимое множество в этом случае будет.
Но хорошо, если не выполнен этот случай, а выполнен второй, дополнительный к нему?
Тогда же нам хочется изловить Ks.
А мы что изловили?
Мы только изловили только K с индексом (s – 1).
Полный подграф на (s – 1) вершине.
То в «сардельке», в «сардельке»
есть K(s – 1) и вот тут, наконец, наступает просветление.
Потому что смотрите, вот я здесь нарисую.
Вот он.
K с индексом (s – 1).
Где-то тут он внутри «сардельки» есть и в нем присутствуют все
возможные ребра — это полный подграф на (s – 1) вершине.
Но это же только «сарделька», а наш-то граф больше.
В нем еще есть вершинка A1, которую мы специально выделили.
Давайте добавим эту вершину A1 к
найденному нами внутри «сардельки» полному графу на (s – 1) вершине.
Чем характеризуется «сарделька»?
Тем, что A1 с каждым элементом, с каждой вершиной,
сидящей внутри «сардельки» соединена ребром.
Это значит, что в частности A1 имеет среди своих
соседей все вершины внутри вот этого K(s – 1).
Такой «подсардельки» внутри «сардельки».
Да? A1 имеет соседей, соседями,
все вершины из K(s – 1).
Ну значит K(s – 1) вместе с A1, это тоже клика, это тоже полный подграф.
Но на s вершинах, как нам того и хотелось.
Давайте я это напишу.
То в «сардельке» есть K(s – 1), но вместе с вершиной A1,
которой не было в «сардельке», которая есть во всем графе G,
вместе с вершиной A1 этот K(s – 1) образует Ks.
Потому что, повторяю,
A1 по построению соединена ребром с каждой вершиной из «сардельки».
В том числе и из вот этого K(s – 1).
Этот K(s – 1) образует полный граф на s вершинах и теорема полностью доказана.
Либо мы нашли в самом графе G независимое множество на t вершинах,
либо вот путем добавления A1 к вот этому K(s – 1) мы таки
нашли полный подграф на s вершинах в нашем графе.
Всё, теорема доказана полностью.
