Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Хроматическое число случайного графа без ребер
Loading...
審閱
4.9（67 個評分）
- 5 stars60 ratings
- 4 stars6 ratings
- 2 stars1 ratings
從本節課中
Хроматическое число случайного графа
Оценки хроматического числа случайного графа G(n,p) при различных p=p(n).
教學方
Андрей Райгородский
профессор, доктор физико-математических наук
Максим Жуковский
преподаватель
Так, друзья, давайте этот факт запомним, запомним,
что α(G) у нас почти наверняка не превосходит удвоенного двоичного
логарифма, и мы обязательно этим еще воспользуемся в дальнейшем,
когда будем обсуждать алгоритмические аспекты отыскания чисел независимости,
кликовых чисел и хроматических чисел графа.
Мне кажется, это одна из очень важных, в том числе прикладных тем,
о которых мы обязательно здесь поговорим, но это не на сегодняшней лекции.
Сейчас я хочу с вами обсудить, а, вообще, все-таки как устроены числа
независимости и хроматические числа случайных графов при различных p?
Так, давайте, наверное,
обратимся прежде всего к хроматическому числу, и я попробую
пробежаться по каким-то ситуациям, которые ну достаточно просты, которые можно,
в общем, обсуждать как, если угодно, упражнения на теорию случайных графов.
Значит, следующая тема, которую я сейчас хочу осветить,
после того как мы разобрались с этими оценками, это тема, собственно,
«Хроматическое число хроматическое
число случайного графа».
Это безумно красивая тема, про которую можно рассуждать исключительно долго,
но я думаю, что мы сделаем так: в рамках такого общечеловеческого курса,
который, я считаю, ну вот всякому полезно прослушать абсолютно,
я расскажу только какие-то наиболее значимые вещи,
касающиеся хроматического числа случайного графа.
А вот в рамках какой-то модификации этого курса, в который, возможно,
я расскажу более глубокие теоремы, нежели те, которые удастся уложить вот в такой
общечеловеческий курс, я докажу некоторые из тех результатов, которые сегодня
исключительно заявлю и, может быть, как-то прокомментирую, а вот там я их докажу.
Но давайте вот в нашем нынешнем курсе просто пробежимся по тем ситуациям,
в которых легко разобраться, и потом как-то чиркнем по поверхности,
затронем суть того, что происходит в более сложных ситуациях.
Но повторяю, тема безумно красивая,
и тут есть чем заниматься и исследователю, и практику.
Значит, ну давайте рассмотрим совсем простую первую ситуацию.
Предположим, что у нас вероятность ребра
p маленькое от n — это очень быстро стремящаяся к нулю функция,
совсем крошечная вероятность у каждого ребра.
Давайте предположим, что она вообще o малое от 1/n².
Ну или, что то же самое, если p(n) умножить на n²,
то даже такое произведение будет стремиться к нулю с ростом n.
Что тогда?
Как будет устроено хроматическое число?
А? Ну я надеюсь, что слушатели,
которые сейчас задумаются, они легко сообразят.
Ну, действительно, давайте обозначим X(G) — просто число ребер,
просто число ребер в случайном графе G.
У этой величины
совершенно легко с помощью линейности посчитать математическое ожидание.
Математическое ожидание X — это просто C из n по 2 умножить на p.
Понятно: всего C из n по 2 ребер, и каждое тестируем на попадание в случайный граф.
Естественно, эта величина ведет себя как n²/2 × p.
Ну и мы только что сказали, что p устроено таким образом,
что едва ты его умножишь на n² и ты получишь функцию,
которая все равно стремится к нулю при n, стремящемся к бесконечности.
Но это означает согласно нашему любимому и уже ставшему совершенно стандартным
неравенству Маркова, что с вероятностью,
стремящейся к нулю, X больше либо равняется единице,
а стало быть с вероятностью стремящейся к единице, X равняется нулю.
Ну то есть в случайном графе с высокой вероятностью нету ребер вовсе.
Но если в случайном графе вовсе нету ребер, то он сам из себя представляет
независимое множество, ну которое, естественно, можно покрасить одним цветом.
Таким образом, мы можем сказать, что вот в этой ситуации асимптотически
почти наверное хроматическое число случайного графа не
превосходит единицы, ну а стало быть ей равняется.
То есть это совсем простенькая ситуация.
Вот давайте, покуда я буду перемещаться на чистую доску,
вы на мгновение задумайтесь (для вас-то это будет мгновение, вам ничего стирать
не надо), вы на мгновение задумаетесь и попробуете ответить на вопрос заранее,
на тот, на который я отвечу на чистой доске: а что будет...
Давайте здесь будет второй пункт.
Я его потом перепишу снова.
Что будет, если p(n) чуть-чуть помедленнее стремится к нулю,
а именно ведет себя как o маленькое от 1/n.
Конечно, в эти ситуации укладывается и это тоже.
То есть хроматическое число может равняться единице.
Но, как видите, все-таки p уже не столь быстро, вообще говоря, стремится к нулю.
Мы лишь знаем, что если p умножить на n, то у нас получится стремление к нулю,
но мы не утверждаем, что если p умножить на n²,
то непременно стремление к нулю появится.
Вот подумайте пока, какое будет хроматическое число.
