Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Подсчет графов с большими полными подграфами
Loading...
En provenance du cours de Moscow Institute of Physics and Technology
Теория графов
268 notes
À partir de la leçon
Теория Рамсея
На заключительной лекции мы поговорим про теорию Рамсея. Вы узнаете много нового о знакомствах, о том, сколько раз можно в одном доказательстве применить принцип Дирихле и о том, что доказать существование графа и привести пример такого графа - это зачастую совсем разные по сложности задачи.
Rencontrer les enseignants
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавскийкандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
Давайте, по сути, действовать с помощью вероятностного метода.
Но поскольку как-бы считается, что мы пока как следует вероятностей не знаем,
я предлагаю рассуждать в чисто количественных терминах.
А именно, прежде всего попробуем просто установить
какое-нибудь соотношение между числами n и s,
которое бы в итоге нам гарантировало вот существование такого графа.
Давайте сделаем следующее: всего
графов на n вершинах,
как мы уже хорошо с вами понимаем, всего графов на n вершинах,
конечно же, 2 в степени C из n по 2.
Ну это общее количество графов на n вершинах.
Каждое ребро графа, полного графа на n вершинах, может быть либо проведено,
либо не проведено, всего два способа для каждого ребра, в полном графе C из n по 2
ребер, ну значит 2 в степени C из n по 2 у нас есть различных графов.
Ну это мы хорошо знаем, это я просто на всякий уж случай,
из соображений занудства, повторил.
Да, всего графов на n вершинах 2 в степени C из n по 2.
Теперь давайте фиксируем произвольные s вершин,
фиксируем произвольные s маленькое
вершин и зададимся таким вопросом...
s маленькое из n маленького, то есть фиксируем произвольные s
маленькое вершин из тех n маленькое вершин, которые есть в нашем распоряжении.
Любые s вершин отсюда, из вот этого множества V.
Фиксируем и давайте зададимся таким вопросом:
а сколько есть графов, в которых
эти конкретные
s маленькое вершин образуют
полный граф, полный подграф?
Вот сколько есть всего графов,
в которых эти конкретные s маленькое вершин образуют полный подграф?
Ну можно нарисовать такую «сардельку», любимую картинку.
Значит у нас всего n вершин, мы зафиксировали какие-то s маленькое из
них и хотим посчитать, сколько есть всего различных графов на n вершинах,
у которых здесь образуется клика — полный подграф на s вершинах.
Здесь все ребра проведены.
Ну, товарищи, если здесь все ребра проведены,
тогда в рамках этого «островка», так сказать, мы никакой воли уже не имеем.
Такая ли свободная воля бывает?
Нет, здесь, конечно, у нас никаких возможностей нету.
Мы можем проводить любые оставшиеся ребра, кроме тех,
которые присутствуют в этом полном подграфе.
Ну сколько остается ребер?
Всего ребер C из n по 2, как мы знаем,
в полном графе на n вершинах, и C из s по 2 из них уже зафиксированы.
Мы точно знаем, что в этом «островке» все они присутствуют.
Но значит ребер, которые еще не проведены, но потенциально проведены могут быть,
их, конечно, вот такая разность (C из n по 2 минус C из s по 2).
Ну и соответственно, каждое из них может быть как проведено, так и не проведено,
поэтому ответом на поставленный вопрос, сколько есть графов,
в которых эти s вершин образуют полный подграф,
служит вот эта величина — 2 в степени (C из n по 2 минус C из s по 2).
Полный подграф уже зафиксировался, а дальше какие угодно ребра.
И те, которые здесь, и те, которые так идут — любые совершенно.
2 в степени (C из n по 2 минус C из s по 2).
Смотрите, я могу задать другой вопрос: а сколько есть графов,
в которых эти s вершин образуют пустой подграф, то есть независимое множество?
Образуют полный подграф.
А здесь я добавлю второй вопрос: независимое множество,
сколько таких графов, у которых вот этот «островок», наоборот, ничем не заполнен?
Ну очевидно, вроде.
Столько же.
Правда же?
Либо все заполнено,
и тогда у нас остается выбор вот этих ребер, либо ничего не заполнено,
там независимое множество, но у нас все равно остается выбор ровно стольких ребер.
И это можно сделать вот таким количеством способов.
Значит, в этом вопросе ответ точно такой же.
Ну значит число графов,
для которых
данный «островок»,
как я это называл, данная «подсарделька»,
данный кусочек мощности s маленькое, для которых данный «островок»
либо является полным подграфом,
полным подграфом,
либо является независимым множеством,
либо является независимым множеством,
вот число таких графов равно 2 умножить на
2 в степени (C из n по 2 минус C из s по 2).
Ну просто сложили две одинаковых величины.
С одной стороны, это количество графов, для которых «островок» служит
полным подграфом, с другой стороны, это количество графов,
для которых он служит пустым подграфом, то есть независимым множеством.
Поэтому в сумме получаем дважды это количество.
А теперь смотрите, смотрите.
Число графов,
для которых — внимание!
— не данный «островок»,
а хотя бы один «островок», хотя бы один «островок»,
хотя бы один (сейчас я еще раз прокомментирую) «островок»,
и дальше все те же самые слова:
либо является полным подграфом,
либо является независимым множеством.
Вот «множеством» я еще перерисую вот так,
«равно» не скажу, а скажу «не превосходит»,
не превосходит C из n по s — числа всевозможных «островков»,
помножить на 2, ну и на 2 в степени C из n по 2 минус C из s по 2.
Сейчас давайте переведем дух и еще раз осознаем, что происходит.
Смотрите, вот в этом утверждении мы зафиксировали конкретное подмножество
множества вершин, имеющее мощность s маленькое.
Его мы и назвали «островком».
«Островок» — это просто некое подмножество множества вершин.
Ну понятно,
что всего различных подмножеств мощности s в аккурат C из n по s штук.
Это все возможные количества всех возможных подмножеств,
каждое из которых может служить вот в этом утверждении «островком».
И теперь мы говорим: число графов, для которых хотя бы один такой «островок» — то
есть хотя бы одно подмножество мощности s — либо является полным подграфом,
либо является независимым множеством, не превосходит вот этой величины.
Ну как это можно изобразить графически, чтобы было совершенно понятно?
Вот нарисуем тоже какую-нибудь такую условную «сардельку»,
только не путайте ее вот с этой.
Эта «сарделька» обозначает — внимание!
— множество тех графов,
для которых данный конкретный «островок» и дальше прямо по тексту.
А дальше нарисуем другое множество графов, другую «сардельку».
Эта «сарделька» состоит, эта «сарделька»,
да, состоит из графов, для которых уже не вот тот «островок»,
а какой-то другой s-вершинный «островок» и дальше прямо по тексту: либо является
полным подграфом, либо является независимым множеством, ну и так далее.
Всего вот таких вот множеств, таких сарделек C из n по s штук.
Для каждого потенциального «островка» мы рисуем множество тех графов,
в которых именно этот «островок» служит либо полным, либо пустым подграфом.
Ну эти множества графов они, конечно, как-то пересекаются,
поэтому я нарисовал такую кашу.
Я не знаю, чему равна мощность объединения этих множеств, но я точно знаю, что эта
мощность объединений не превосходит суммы мощностей каждого из этих множеств.
Но мощность каждого из этих множеств такая, мы ее посчитали для данного
«островка», а количество вот этих вот «сарделек» оно равно C из n по s.
А объединение этих «сарделек» — это и есть то, что нам нужно.
Это и есть множество графов, для которых хотя бы один «островок»...
и дальше по тексту.
Объединение вот этих «сарделек» — это есть множество графов,
для которых хотя бы один «островок» служит либо полным, либо пустым подграфом.
Вот. Ну мощность объединения она не превосходит
суммы мощностей — очевидный комбинаторный факт.
Ну вот я, собственно, это и написал.
А теперь смотрите.
Наступает, собственно, опять же, катарсис.
Предположим, предположим,
вот эта величина C из n по s × 2 × 2 в
степени (C из n по 2 минус C из s по 2) меньше,
чем 2 в степени C из n по 2.
То есть число графов, для которых хотя бы один «островок» и так далее,
строго меньше, чем число всех графов на n вершинах.
Вот давайте предположим.
Что тогда?
Ну тогда?
если бы это случилось, тогда положительным
является число тех графов, для которых вот это не выполнено.
То есть тогда существуют графы,
существуют графы, хотя бы один граф,
для которых (и дальше пишем отрицание вот этого свойства) ни
один «островок» не является ни полным подграфом, ни независимым множеством.
Ни один «островок»,
ни одно подмножество множества вершин, имеющее мощность s,
не является ни полным,
ну давайте я так напишу, ни пустым, чтоб покороче было,
ни пустым, то есть независимым, подграфом.
Ни один «островок».
Но это же в точности означает существование графов,
в которых нету ни s-вершинных полных подграфов,
ни s-вершинных независимых множеств, потому что ни одно множество мощности s,
множество вершин мощности s в таких графах не служит ни полным подграфом для них,
ни независимым вот таким вот пустым множеством.
Существуют такие графы, если общее количество таких графов строго меньше,
чем общее количество графов.
Значит, существуют те графы,
в которых вообще нету ни s-вершинных полных, ни s-вершинных пустых.
Но это ровно то, чего нам хотелось.
И нам лишь остается теперь проверить, что вот это неравенство действительно
выполнено, коль скоро в качестве n мы возьмем такую целую часть.
Все, что осталось сделать, по сути, для завершения лекции.
Нам нужно вместо n подставить вот такую величину и убедиться в том,
что это соотношение имеет место.
Тогда мы докажем, что на n вершинах, как нам того и хотелось, есть граф, в котором
нет ни полного подграфа на s вершинах, ни независимого множества мощности s.
Сейчас мы это сделаем.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
