Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Алгоритм покраски
Loading...
From the course by Moscow Institute of Physics and Technology
Случайные графы
63 ratings
From the lesson
Хроматическое число случайного графа
Оценки хроматического числа случайного графа G(n,p) при различных p=p(n).
Meet the Instructors
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Итак, давайте сформулируем собственно ключевое утверждение,
из которого в итоге будет вытекать результат Балабаша.
Ключевое утверждение можно назвать леммой, но можно, вообще говоря, и теоремой,
потому, что это абсолютно нетривиальный, очень красивый самостоятельный факт.
Утверждение такое.
Давайте попробуем посчитать вероятность того, что любое
множество вершин случайного графа...
V — это множество вершин случайного графа всех, а S — это некоторое подмножество,
произвольное в данном случае, всего множества вершин случайного графа.
Так вот вероятность того, что любое подмножество,
имеющее мощность, равную m… Помните, да,
у нас есть m — это n поделить на логарифм в квадрате n, загадочная величина?
Значит, вероятность того, что любое подмножество множества вершин,
имеющая мощность, в точности равную m,
устроено так, что число независимости графа G,
ограниченного на это подмножество, то есть ну вот мы просто смотрим кусок графа,
который попал в это подмножество вершин.
Сейчас я нарисую картинку, будет всё совершенно понятно.
Вот что α ≥ k₁, где k₁ — это та самая величина,
которую мы ввели только что, в предшествующей части лекции.
Вероятность того, что в любом m-элементном,
m-вершинном множестве содержится независимое подмножество мощности k₁,
вот эта вероятность стремится к единице при n, стремящемся к бесконечности.
Ну, давайте я нарисую картинку, так будет понятнее.
Вот у нас есть множество V, в нём всего n вершин.
В нём есть куча самых разнообразных
подмножеств, каждое из которых имеет мощность m.
Я специально их нарисовал довольно-таки жирными, потому что m — это, как вы,
может быть, помните, n / логарифм в квадрате n.
Это величина относительно маленькая, конечно, в сравнении с n,
но не настолько маленькая, чтоб рисовать вот эти подсардельки совсем уж крошечными.
Маленькой является величина k₁, k₁ у нас, напоминаю,
асимптотически ведёт себя как 2 log двоичный n,
и утверждение теоремы фактически говорит следующее.
Если мы возьмём случайный граф, возьмём случайный граф, то,
скорее всего, какое подмножество из вот этих вот, нарисованных здесь на картинке,
их всего C из n по m штук,
какое из этих подмножеств ни возьми, но у нашего случайного графа внутри этого
подмножества есть независимое множество размера как минимум k₁.
То есть и вот в этой подсардельке есть независимая дырочка, дырочка,
в которой отсутствуют рёбра.
И вот в этой подсардельке есть независимая дырочка,
и вот в этой подсардельке есть независимая дырочка.
И какую подсардельку, какое подмножество из вот этого огромнейшего числа их,
подмножеств этих, какое подмножество ни возьми,
а с высокой вероятностью оно содержит маленькую, но дырочку независимую.
Знаете, как в известной рекламе — даже в маленьком кусочке есть лесной орех.
Вот куда ни ткни, а там такой вот лесной орешек — независимое множество.
Почему это фантастически удивительно?
Потому что вспомните утверждение, которое мы доказали в самом начале,
в самом начале нашей сегодняшней лекции.
Оно состояло в том, что если мы возьмём вот такую вот величину,
целая часть от удвоенного двоичного логарифма n, которое, конечно,
асимптотически ведёт себя как два двоичных логарифма n,
вот если мы возьмём такую величину, то с высокой вероятностью независимых
множеств этого размера в случайном графе вообще не будет.
Однако, едва мы берём другую величину, которая тоже асимптотически
равняется 2 логарифма двоичных n, но чуть-чуть поменьше, конечно, чем эта.
Помните, она поменьше?
Вроде мы берём с той же самой асимптотикой величину,
и не только мы можем утверждать, что уже такие независимые множества с
высокой вероятностью есть в случайном графе, но, более того, они не просто есть,
а они есть в каждом его m-вершинном подмножестве.
Вот это вот совершенно удивительно.
В каждом m-вершинном подмножестве есть независимое множество такого размера.
Такого размера нет вообще во всём графе, чуть-чуть уменьшили,
но сохранили асимптотику,
и асимптотически почти наверное в каждом m-вершинном найдётся такое независимое.
По-моему, это очень впечатляет.
Это, конечно, совершенно нетривиальная лемма.
Вот. Ну, лемму мы доказывать не будем,
а исходя из утверждения леммы, очень легко получить алгоритм раскраски нашего графа,
доказывающей основное утверждение Балабаша о том, что лучше оценки, чем n
поделить на α, на самом деле в среднем-то и нет, в случайном графе-то и нет.
Значит, алгоритм такой.
Берём наш граф,
который обладает вот этим свойством, такой,
что для любого S из его множества вершин, мощности m маленькое,
α (G), ограниченного на s, больше либо равняется k₁.
Вот берём произвольный такой граф.
Понятно, что это почти всякий граф, потому что мы знаем, что вероятность
этого свойства стремится к единице при n, стремящемся к бесконечности.
Вот берём любой такой граф из множества почти всех графов.
Замечательно.
Рисуем его множество вершин — опять ту же самую сардельку,
вот она, вот в ней n элементов.
Ну, раз граф обладает вот этим свойством, значит в нём самом,
уж во всяком случае, есть независимое множество мощности k₁.
В нём самом.
Нет, я не говорю, что оно есть в каждом, оно есть в каждом,
но уж в нём-то самом точно есть.
Ну раз это независимое множество мощности k₁,
то давайте его покрасим просто тупо в первый цвет.
Возьмём и все вершины этого независимого множества, которое у нас есть,
покрасим в первый цвет.
Хорошо, удалим из множества вершин покрашенное подмножество
— останется ещё куча вершин.
Эта куча, скорее всего, имеет мощность большую, чем m,
но тогда опять воспользуемся этим свойством,
и в оставшейся части графа найдём подмножество мощности k₁,
которое спокойно, раз оно независимое, можно покрасить во второй цвет.
Отлично!
Покрасим его во второй цвет и тоже удалим из нашего графа.
Снова останется, вообще говоря, больше, чем m вершин,
снова за счёт вот этого свойства найдём третье независимое множество мощности k₁,
покрасим все его вершины в третий цвет.
Сколько раз мы можем так делать?
Сколько таких выкидываний мы можем осуществить?
Ну, понятное дело, мы можем осуществить столько таких выкидываний,
чтобы в итоге у нас осталось хотя бы m вершин.
Значит, количество таких цветов,
количество таких цветов, очевидно,
равняется целой части от (n − m) / k₁.
Каждый цвет имеет мощность k₁, и вот если мы возьмём ровно столько цветов,
ровно столько вот этих вот маленьких дырочек,
которые есть в каждом лесном орехе, понимаете?
Вернее, в каждом маленьком кусочке есть лесной орех, это я уже заболтался,
не то говорю.
Значит, возьмём каждый такой лесной орех, который есть в каждом маленьком кусочке,
он мощности k₁, возьмём их столько,
в сумме получится как раз n − m вершин на все эти орехи,
и вне этих орехов останется m свободных, m свободных вершин.
Значит, столько цветов мы задействовали,
остаётся незадействованных, непокрашенных, остаётся непокрашенных...
непокрашенных не более m вершин.
Покрасим каждую из этих вершин в свой отдельный цвет,
отличный от вот этих первых, получится, что хроматическое
число графа G не превосходит целая часть от
(n − m) / k₁ + еще m, m отдельных цветов,
которые задействованы на оставшиеся непокрашенными вершины.
Их мы тупо покрасим каждый в свой цвет.
Ну теперь смотрите, это асимптотически равно (n −
m) / k₁, целую часть я легко снимаю, прибавить m,
это асимптотически равно n − n / логарифм в квадрате n,
я m заменил просто на свою асимптотику,
поделить на 2 log двоичных n.
k₁ у нас имеет асимптотику 2 log двоичный n.
Так, и + опять же n / логарифм в квадрате n.
Это равняется n / 2 log двоичный
n − n / 2 двоичных логарифма n,
помноженных на логарифм натуральный в квадрате, + n / логарифм в квадрате.
Ну потрясающе!
Каждое из этих слагаемых, очевидно, бесконечно мало в сравнении с первым,
потому что первое делится в них ещё на какую-то степень логарифма,
то ли на квадрат, то ли на первую степень.
Здесь видите логарифм в квадрате,
он отличается от логарифма примерно в логарифм раз.
Но, естественно, асимптотика этого выражения — это и есть n / 2
log двоичных n, что и требовалось доказать.
То есть за счёт того, что в каждом маленьком кусочке есть
независимое множество, есть лесной орех, а кусочек достаточно маленький,
чтобы утонуть в асимптотике главного члена, мы действительно показываем,
что любой граф, обладающий вот этим свойством, а это почти любой граф,
он красится в асимптотически нужное количество цветов.
И по модулю вот этой потрясающей, конечно, леммы теорема доказана.
Ну давайте на этом, наверное, на сегодня угомонимся.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
