Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Модификация графа
Loading...
來自 Moscow Institute of Physics and Technology 的課程
Случайные графы
65 個評分
從本節課中
Вероятностный метод
Хроматическое число, число независимости и кликовое число. Обхват графа. Теорема о существовании графа с большим обхватом и большим хроматическим числом.
與講師見面
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Осталось сделать один совершенно гениальный шаг — поправить граф G.
Мы доказали, что он существует.
Давайте исправим граф G, перейдем от него к некоторому новому графу G'.
Сейчас объясню, как.
Итак, мы нашли граф G с очень-очень большим, вообще говоря,
количеством вершин, который одновременно имеет маленькое число независимости и в
котором мало вредоносных циклов.
Ну давайте сделаем так: удалим из
каждого вредоносного цикла...
Я напишу просто «вред.
цикла».
Из каждого вредоносного цикла любую какую-нибудь вершину,
какую-нибудь вершину, совершенно произвольную.
Какую-нибудь вершину.
То есть вот был граф G, давайте я нарисую картину,
в нем было несколько коротких циклов, каждый из которых вредил.
Ну, если эти циклы пересекались, вообще говоря,
мы могли постараться и, удалив одну вершину, разрушить сразу несколько циклов.
Но мы плюем на эту возможность.
Мы говорим так: давайте наобум лазаря выкинем вершину из первого плохого цикла.
Опять наобум лазаря выкинем вершину из второго плохого цикла,
из третьего и так далее.
Но мы точно знаем, что в нашем исходном графе G плохих циклов мало,
меньше, чем n / 2.
Поэтому как бы много вершин мы ни удаляли, но больше,
чем n / 2 вершин мы точно не удалим.
То есть это означает, что...
Давайте я вот здесь буду писать уже.
Что у G' не менее или даже более строго n / 2 вершин.
Мы из каждого вредного цикла в графе G удалили вершину,
но у графа G было n вершин, а вредных циклов было меньше, чем n / 2.
Поэтому, удаляя даже по вершине по отдельной из каждого цикла,
мы все равно получаем, что на выходе остается граф, у которого не меньше никак,
чем n / 2 вершин.
Это-то уж точно.
При этом понятно, что обхват
этого нового графа больше, чем l, потому что в исходном
графе было мало вредоносных циклов, а в новом графе их просто нет.
Мы же разрушили каждый вредоносный цикл.
Мы из каждого вредного цикла удалили вершину,
новые вредные циклы появиться никак не могли в результате этой процедуры.
Значит у нового графа по-прежнему достаточно много вершин,
но обхват, слава богу, уже такой, как нам хотелось бы, то есть >, чем l.
Теперь.
Очевидно, что α (G') не могло вырасти по отношению к α (G).
Мы удаляли вершины.
Естественно...
вот здесь вот мы удаляли вершины, да?
Естественно, вместе со всеми ребрами, которые к ним примыкали.
Поэтому число независимости вырасти никак не могло.
α (G') не превосходит α (G), которое, как мы знаем, < x.
Замечательно.
Но отсюда, в свою очередь, следует, и я уже об этом фактически говорил,
что χ (G') ≥ количество вершин в этом графе поделить на его число независимости,
а это, в свою очередь, ≥ (n/2) / x, потому что α < x.
Можно даже строго > написать в этом месте.
Потрясающе!
Это асимптотически равно...
Мы же знаем, чему асимптотически равен x.
n / 2x, где x — это (3 логарифм n) / p.
Правильно?
Это асимптотика для x.
То есть мы получаем np / 6 * логарифмов n.
Вспоминаем, что p выбиралось как n в степени (θ − 1),
то есть получаем n в степени θ.
p — это n в степени (θ − 1), поэтому произведение — это как раз n в степени θ.
Поделить на 6 логарифмов n.
θ у нас равняется 1 / 2l.
Вот тут еще очень важный момент.
l — это может быть огромнейшее число.
Но оно от n никак не зависит.
Это заранее зафиксированная константа.
Поэтому тут у нас стоит функция в числителе,
которая растет как n в степени «некоторое фиксированное положительное число»,
а в знаменателе стоит 6 логарифмов n.
Я думаю, слушатели знакомы с анализом до такой степени,
чтобы понимать, что вот эта функция, сколь бы маленьким фиксированным θ ни было,
растет быстрее все-таки, чем логарифм.
Поэтому вот это вот стремится к бесконечности,
коль скоро n неограниченно возрастает.
Вот это отношение стремится к бесконечности,
каким бы мы заранее ни зафиксировали l.
Пусть огромным, но стремление к бесконечности все равно будет.
Это означает, что существует такое n3,
что для любого n ≥ максимума из n1,
n2, n3 g (G'),
конечно, больше, чем l, это мы уже получили по построению.
Но более того, χ (G'), которое стремится к бесконечности,
после вот этого n3 >, чем заданное наперед k.
Ведь повторяю, k — это была константа, а тут у нас рост к бесконечности.
Значит, начиная с некоторого момента,
бесконечно большая функция превзойдет наперед заданное k.
И наступает полный катарсис.
Мы совершенно никак не описали конструкцию графа, тем не менее, мы точно знаем,
что его можно найти.
Он существует, есть такой граф на очень большом количестве вершин,
у которого одновременно нету коротких циклов и большое хроматическое число.
Теорема полностью доказана.
