Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Определение жадного алгоритма
Loading...
From the course by Moscow Institute of Physics and Technology
Случайные графы
62 ratings
From the lesson
Алгоритмы на случайном графе
Жадный алгоритм раскраски. Жадное хроматическое число, жадное число независимости и жадное кликовое число. Теорема о жадном хроматическом числе и жадном числе независимости случайного графа.
Meet the Instructors
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Добрый день!
Давайте продолжим сегодня заниматься той тематикой,
которой мы занимались уже довольно долго, а именно продолжим обсуждать вот эти вот
замечательные характеристики графов: такие как хроматические числа,
числа независимости, кликовые числа.
Но сегодня обсудим алгоритмический аспект этой проблематики, который,
мне кажется, имеет достаточно прикладной характер,
и с этой точки зрения особенно может быть интересен многим слушателям.
Впрочем, красивой математики будет не меньше, чем обычно.
Итак, мы по-прежнему рассматриваем вот эти замечательные величины: χ(G),
α(G), ω(G), но на сей раз нас интересует сложность
подсчета этих величин на произвольном графе или на почти произвольном графе,
в зависимости от того, как мы поставим задачу.
Ну с одной стороны, я вынужден просто постулировать некий факт,
который не имеет отношения к текущему курсу, а именно тот факт,
что в каком-то смысле вычислительная сложность каждой из трех упомянутых сейчас
на доске задач, то есть вычислительная сложность отыскания хроматического числа,
а равно вычислительная сложность отыскания числа независимости и кликового числа,
каждая из этих вычислительных сложностей очень высокая, по-видимому.
То есть...
Ну вот для тех, кто знает, эти задачи NP-трудные.
Задачи отыскания таких величин на произвольном графе NP-трудные.
Для тех, кто не знает, смысл такой: скорее всего,
быстрого алгоритма подсчета этих величин не существует.
Быстрого — это значит такого, чтобы он работал за полином от количества ребер,
ну или, если угодно, от количества вершин нашего графа, за полином операций.
Причем полином-то может быть какой угодно степени,
и даже такого алгоритма, скорее всего, нет.
Это вот важный постулат, с которого стоит начинать.
Ну тогда возникает вопрос: быть может мы можем хотя бы приближенно подсчитать эти
характеристики, придумать какие-нибудь алгоритмы, которые искали бы аппроксимацию
хроматического числа, числа независимости и кликового числа в произвольном случае?
Оказывается, что и эта задача тоже трудная.
То есть приблизить каждое из этих чисел, например, в 100 раз,
то есть ошибиться не более чем в 100 раз, это уже очень тяжелая задача,
опять-таки с трудом, по-видимому, решаемая с помощью каких-либо алгоритмов.
И тут на помощь замечательным образом приходят случайные графы.
Вот в этом пафос сегодняшнего мероприятия, сегодняшней лекции.
Оказывается, что если взять случайный граф, то даже самый банальный жадный
алгоритм, который я сейчас опишу, уже работает, ну, очевидно,
работает быстро (жадный-то алгоритм — это вещь очень простая и легко реализуемая,
сейчас я напомню, что это такое), но мало того, что он работает быстро, на почти
всяком графе он дает очень хорошую аппроксимацию нужной нам характеристики.
То есть если вы допускаете возможность какой-то ошибки, но при этом вероятность
этой ошибки хотите чтоб стремилась к нулю, то у вас есть замечательная альтернатива
каким-то сложным продвинутым алгоритмам — банальный жадный алгоритм.
Значит, давайте я опишу, что такое жадный алгоритм раскраски,
жадный алгоритм раскраски графа.
Давайте считать, что у нас, как обычно, как это, например,
в случайном графе бывает, зафиксировано множество вершин,
которое как-то изначально занумеровано числами от 1 до n,
ну и на этом множестве вершин дан, в общем-то, совершенно произвольный граф.
Пока не случайный, а просто произвольный граф с этим множеством вершин и
некоторым множеством ребер E.
Как можно банально осуществлять покраску этого графа алгоритмически?
Ну можно сделать так: вершине 1 по определению присвоить цвет с номером 1,
потом посмотреть на вершину 2 и сказать: ну хорошо,
если она не соединена ребром с единицей, то есть никакого конфликта по цветам не
возникает, то, конечно, мы ее покрасим в первый цвет, а если она соединена ребром,
ну тут уж ничего не попишешь, давайте ее красить в цвет номер 2.
Вот делаем такую простую альтернативу.
Ну и вообще, вот мы двигаемся так по списку вершин,
доходим до вершины с номером i и смотрим минимальный номер цвета,
в который можно покрасить эту вершину i,
чтобы не возникло конфликтов с какими-либо цветами из предшествующих вершин.
Ну что значит «конфликтов»?
Это значит, что нету ребер, которые шли бы в вершины этого цвета из нашей вершины i.
То есть красим i — давайте я это прямо явно зафиксирую
— в цвет с минимальным номером,
в цвет с минимальным номером,
с которым нет конфликта по ребрам, нет конфликта.
Не возникает ребер, идущих из вершины i в какую-либо вершину i-того цвета.
То есть это абсолютно банальный и, конечно,
очень быстро работающий жадный алгоритм.
Такой вот банальнее некуда.
Мы даже не пытаемся как-то специально занумеровать вершины, мы просто их заранее
занумеровали, наплевать как, и дальше чешем по этой нумерации для каждого графа.
Конечно, это очень быстрый алгоритм.
Другой вопрос в том, что, казалось бы,
ну как можно такую ерунду применять на практике?
Наверняка же она очень сильно ошибается?
Да, совершенно верно.
Она может очень сильно ошибаться.
Но пафос в том, что почти никогда она сильно не ошибается тем не менее.
Давайте обозначим χ с индексом ж от G то количество цветов,
которое на данном графе найдет вот такой вот простенький жадный алгоритм.
Естественно, это будет некоторая аппроксимация для реального хроматического
числа, и покуда я точную теорему не сформулировал, слушатели, наверное,
должны пребывать в некотором все-таки недоумении от того,
как это вот такая вот тривиальность может сработать.
Но вот случайные графы они на то и замечательная наука,
что позволяют оценивать такого рода вероятности.
Вот. Давайте за счет вот этой покраски сделаем
еще некоторую аппроксимацию числа независимости графа, а именно просто...
Ну как вот?
Мы взяли граф, покрасили его с помощью жадного алгоритма и давайте
найдем в нем самый большой цвет, который получился в результате этой покраски.
Понятно, что самый большой цвет — это будет самое большое независимое множество,
которое сумел найти наш жадный алгоритм.
Это тоже будет некоторая аппроксимация для величины α(G).
Берем αж от G — это
число вершин в самом
большом одноцветном множестве,
в самом большом одноцветном множестве,
которое получено за счет жадной покраски.
В самом большом одноцветном множестве, которое получено за счет жадной покраски.
Ну про ω с индексом ж от G я особенно говорить не собираюсь,
но смысл тоже очень понятный.
Мы можем вместо графа G рассмотреть граф G с чертой, то есть провести ребра там,
где их у графа не было, а там, где они были, их, наоборот, стереть.
И уже на этом новом, дополнительном таком, двойственном графе запустить тот же самый
жадный алгоритм, отыскать α с индексом ж от этого дополнительного графа,
и у нас получится вполне естественная аппроксимация для исходного ω,
для кликового числа.
Понятно, что кликов в двойственном графе, вот в таком G с чертой — это то же самое,
что независимое множество в исходном и наоборот.
Ну это понятно.
Давайте говорить только про хроматическое число и число независимости.
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.
