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