Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Введение вспомогательного события
Loading...
Из курса от партнера Moscow Institute of Physics and Technology
Случайные графы
63 оценки
Из урока
Алгоритмы на случайном графе
Жадный алгоритм раскраски. Жадное хроматическое число, жадное число независимости и жадное кликовое число. Теорема о жадном хроматическом числе и жадном числе независимости случайного графа.
Познакомьтесь с преподавателями
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Так, доказательство вот этого неравенства.
Угу, но мы же с вами кое-что знаем!
Мы это сделали и применяли неоднократно.
Ну, наверное, все-таки правильно сказать, на прошлой лекции, да?
А именно мы знаем, давайте это прям так и напишем: мы знаем,
что асимптотически почти наверное числитель в той дроби,
которую мы желаем сейчас оценить, ɑ(G) не превосходит 2 log двоичное n.
Вот видите, как это неравенство сыграет сейчас.
Увидите очень скоро.
То оно было просто ну какой-то игрушкой, в каком-то смысле.
Мы его...
мы с помощью этого неравенства сравнивали две оценки хроматического числа и вроде
как уж большого прикладного смысла за этим неравенством не усматривали.
А сейчас это неравенство поможет нам действительно получить такой
вот замечательный результат во вполне прикладной задаче.
Итак, мы знаем, что асимптотически почти наверное ɑ(G) не превосходит удвоенного
двоичного логарифма.
Что же нам остается доказать,
коль скоро мы желаем установить вот такое неравенство?
Наверное, достаточно теперь доказать...
Давайте это напишем, и станет понятно,
что это действительно так: достаточно доказать,
что Для любого, давайте δ, большего 0,
асимптотически почти наверное ɑ с индексом
ж(G) ≥ (1
− δ) * на log двоичный n.
Ну действительно, если мы докажем вот этот результат,
если мы докажем, что жадник на случайном графе находит с высокой вероятностью
независимое множество вот такой вот как минимум величины,
тогда с высокой вероятностью отношение, которое тут написано,
не превосходит 2 log двоичный n поделить на правую часть вот этого неравенства.
log двоичный n благополучно уничтожается, и у нас остается 2 / (1 − δ).
Ну, поскольку δ произвольная,
то 2 / (1 − δ) мы при желании можем сделать в точности равным 2 + Ε.
Здесь Е произвольное, здесь δ произвольное, значит,
едва мы это доказываем, так сразу у нас получается то, что нам нужно.
Ну, асимптотически почти наверное, как обычно, означает, что
вероятность вот этого события стремится к 1 при n, стремящемся к бесконечности.
Мне в данном случае проще будет оценивать вероятности сверху,
потому что я буду их оценивать как вероятности объединения некоторых событий,
и там будет простая оценка суммы.
Давайте я, стало быть, наоборот напишу событие,
состоящее в том, что ɑ жадное на случайном графе меньше,
ну или, если хотите, не превосходит (1 − δ) * на log двоичный n,
и буду доказывать, что вот эта вероятность стремится к 0.
Я пока напишу под вопросом, потому что это нам предстоит доказать,
но это реально наша цель.
Если мы показываем, что эта вероятность стремится к нулю, то мы,
естественно, получаем,
что асимптотически почти наверное справедливо нужное нам неравенство.
Итак, нам нужно каким-то образом оценить вот эту вероятность.
Давайте, для того чтоб было более понятно, чего происходит, я попробую нарисовать
сейчас картинку, которая проиллюстрирует некоторое следствие из вот этого события.
Смотрите, у нас есть событие относительно случайного графа,
состоящего в том, что жадный алгоритм пыхтел-пыхтел,
но допыхтел только до вот такого маленького независимого множества.
Что из этого следует?
Давайте сделаем так.
Во-первых, введем некий параметр,
который обозначим m, а потом уже нарисуем картинку.
Значит, m — это у нас будет целая часть от n / (2
* (1 − δ) * на log двоичный n).
Вот такая вот загадочная, как водится, у нас покамест целая часть.
Вечно мы выбираем какие-то параметры, которые потом — бац!
— и дают нам очень красивый результат.
Вот. А теперь мы нарисуем картину.
Картина эта, как обычно, сарделька, на которой нарисовано множество вершин
случайного графа, коей, разумеется, имеет мощность n.
Так.
смотрите, вот что означает...
Давайте вместе подумаем, что означает,
что жадному алгоритму не удалось найти большого независимого множества?
Ведь жадный алгоритм изначально не стремился искать независимое множество.
Жадный алгоритм занимался раскраской.
И просто в результате раскраски, которую делал жадный алгоритм, оказалось,
что самый большой цвет, самое большое количество вершин, покрашенных в
один цвет, имеет все-таки мощность, не превосходящую вот такой вот величины.
Что отсюда следует?
Я не говорю «чему это равносильно», вот будьте внимательны.
Я сейчас не буду писать равносильное утверждение.
Я хочу вывести некоторое следствие, вероятность которого, в свою очередь,
мне будет удобно оценивать.
Если я докажу, что вот из этого события вытекает некоторое другое событие,
после чего оценю вероятность этого вытекающего, то, естественно,
я получу оценку и для вероятности своего события тоже.
Значит, давайте вот это событие, которое нас интересует, будем обозначать буквой А.
Значит, нас интересует вероятность события А,
и я хочу оценить эту вероятность вероятностью некоторого события В,
где В вот я сейчас на картинке попробую изобразить.
Я докажу, что из А следует некоторое событие В.
Ну, смотрите.
Значит, двигался наш жадный алгоритм по вершинам нашего графа,
нашего конкретного графа на n вершинах, вот он здесь как бы нарисован.
Двигался-двигался, пыхтел-пыхтел, находил какие-то независимые множества,
которые называл цветами.
И в итоге оказалось, что эти все независимые множества маленькие.
Не сумел он найти независимого множества,
размер которого превосходил бы такую величину.
Ну давайте нарисуем какое-то количество тех независимых множеств,
которые он в результате нашел, наш алгоритм.
Понятно, что можно нарисовать С₁,
C₂, ..., C с индексом m,
где m — это в точности вот этот вот замечательный параметр.
Сейчас пока, может быть, не до конца понятно, но скоро будет понятно совсем.
Значит, можно написать, вот...
нарисовать вот такие независимые множества.
Сказать, что мощность каждого из этих независимых множеств не
превосходит следующей замечательной величины,
а именно (1 − δ) * помножить на log двоичный n.
Ну правильно, он же не смог найти независимые множества большего размера?
Вот он нашел m штук независимых множеств,
размер каждого из которых не превосходит (1 − δ) * на log двоичный n.
Товарищи, я понимаю, что он нашел, наверное, еще больше независимых множеств,
потому что смотрите: да, действительно,
размер каждого из них не больше обещанной величины, но при этом их количество m,
вот оно здесь задано формулой, целая часть там какая-то...
Что оно нам говорит?
Оно нам говорит, что если мы посмотрим суммарную мощность вот этого множества С₁,
C₂, Cm — суммарная мощность получится не превосходящей m
помножить на (1 − δ) * log двоичный n.
Повторяю, это оценка сверху суммарной мощности нарисованных на
картинке независимых множеств.
Но m у нас, как целая часть, не превосходит, конечно, как водится,
своего аргумента, то есть величины n / дважды (1 − δ) log двоичный n.
Это я написал оценку для величины m.
Ну и я умножаю ее на вот эту величину, на (1 − δ) * log двоичный n.
Шлеп, шлеп — у меня получается n пополам.
То есть вроде бы я здесь нарисовал только половину потенциальных независимых
множеств, которые наш жадный алгоритм нашел при покраске нашего графа G.
То есть давайте еще раз, вот жадный алгоритм красил наш граф G.
Красил, красил, красил, красил, нашел много цветов.
И мы знаем, что каждый цвет имеет размер не больше, чем вот такая величина.
Ну конечно, из этого знания вытекает тот факт, что он уж заведомо, жадный алгоритм,
нашел m множеств независимых, каждое из которых имеет не больше, чем такой размер.
Повторяю, это именно следствие.
Наверное, он нашел их больше, потому что вместе, как вот мы только что увидели,
эти m множеств занимают не более чем половину от общего числа вершин.
Но ведь граф-то покрашен целиком,
значит там есть еще какие-то независимые множества.
Но вот их мы не упоминаем.
Мы говорим лишь, что если граф покрашен таким образом,
что каждое независимое множество в этой покраске,
каждый цвет содержит не более чем столько вершин, это заведомо, как следствие,
означает, что в графе есть m независимых множеств и, внимание,
вот сейчас будет самое главное: есть не просто m независимых множеств,
а m таких независимых множеств, которые при дальнейшей покраске графа
наш жадный алгоритм не смог никак увеличить.
Они уже сформировались и оказались вот столь маленькими,
что граф не удалось В графе не удалось найти большего независимого множества с
помощью нашего жадного алгоритма.
А что значит не удалось пополнить?
Это значит, что, если мы возьмем произвольную вершину x,
которая находится вне объединения вот этих множеств,
то как ведь строилась наша жадная раскраска: мы смогли бы
добавить эту вершину к какому-нибудь из предшествующих цветов, если бы из этой
вершины внутрь соответствующего цвета ни одного ребро не шло.
Но мы не можем добавить эту вершину.
Алгоритм завершился нахождением маленьких независимых множеств.
Раз не можем, значит, и сюда есть хотя бы одно ребро,
и сюда есть хотя бы одно ребро, и сюда есть хотя бы одно ребро,
и это верно для каждой вершины, расположенной вне вот этих множеств.
Ровно ради этого мы взяли m именно таким, как взяли, чтобы у нас еще как минимум
n пополам вершин осталось вне объединения множеств C1,...,Cm, чтобы для каждой
из них можно было написать условие наличия ребра в каждое из перечисленных множеств.
Ну, я немножко сумбурно или даже скорее бурно говорю.
Я надеюсь, что вот эта картинка сейчас уже стала немножко прояснять то,
что я напишу дальше, а напишу я совершенно аккуратно.
Значит, A влечет событие B,
как я и обещал, так что вероятность A будет не превосходить вероятность B,
где B описывается следующим образом,
давайте я совершенно аккуратно скажу: существуют
числа a1,...,am,
такие, что аi-тое
не превосходит 1−δ на log двоичный n.
Эти числа играют роль вот этих вот правых частей,
мощностей множеств Ci-тое, дальше,
существуют множества C1,...,Cm,
каждое из которых является подмножеством множества вершин графа,
существуют множества, такие,
что для любых i и j Ci-тое, пересеченное с Cj-тым — пусто,
эти множества не пересекаются, ну вот на картинке мы видим — да, конечно,
они не пересекаются, существует m непересекающихся множеств, такие,
что для любого i мощность Ci-того равняется ai-тому,
существуют вот такие ai-элементные множества,
где ai-тое каждое не превосходит вот этой величины,
и самое главное — вот это вот условие на каждую вершину x,
что для любого x, который принадлежит множеству вершин,
не попадающих в объединение C1,...,Cm,
и для любого i, то есть для любого номера множества C1,...,Cm,
для любого i существует вершина y,
принадлежащая Ci-тому, такая,
что пара x-y образует ребро в нашем графе.
Вот, собственно говоря, какое следствие получается.
Я вот долго, бурно, и немножко, может быть, сумбурно объяснял, что именно такое
следствие имеет место, теперь не страшно глядеть на эту формулу, я надеюсь,
потому что если бы я сразу это написал, это, возможно, вызвало бы какие-то ужасы.
А, поскольку я пояснил, откуда такое берется,
то дальше написание, пусть и громоздкой формулы, уже кажется вполне обоснованным.
Значит, давайте я еще раз, спокойно, не особенно куда-то торопясь,
прокомментирую то, что произошло, снова ткнув в картинку.
Итак, смотрите: мы знаем, что жадный алгоритм не сумел найти
сколь-нибудь большого независимого множества.
Ну, стало быть, мы знаем, что найдутся действительно вот такие вот числа, каждое
из которых не очень большое, и найдутся попарно непересекающиеся множества вершин,
каждое из которых имеет вот эту самую, не слишком большую мощность,
найдутся такие множества вершин, что, какую бы вершину
снаружи по отношению к этим множествам мы ни рассмотрели, она обязательно
с каждым таким множеством, с каждым таким множеством соединена ребром.
Это вот на картинке видно.
Иначе, если бы это было не так, как мы сейчас написали,
это бы означало, что жадный алгоритм все-таки может найти большое,
все еще пополняемое множество независимости.
Но это не так — жадный алгоритм не сумел найти больших, и значит,
он нашел достаточно много маленьких, достаточно много — это вот это m,
достаточно много маленьких, каждое из которых ничем уже пополнить не сумел,
какую бы вершину он ни пытался приткнуть к какому-то из этих независимых множеств,
он наталкивался на препятствие, связанное с тем, что для любого i есть некоторая
вершина из Ci-того, которую, которая соединена ребром с x-ом.
Ничего не получается, x ни к какому Ci-тому уже не добавить.
Они маленькие и они непополняемые.
Жадный алгоритм обломался.
Вот если вы осознали эту импликацию, это следствие, то все замечательно, потому что
никакой более сложной логики в дальнейших рассуждениях, конечно, не будет.
Дальше надо просто аккуратно оценить вероятность события A, пользуясь тем,
что квантор существования всегда означает просто объединение каких-то событий,
но это я сейчас аккуратно напишу, когда у меня появится чистая доска.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
