Добрый день!
Давайте продолжим сегодня заниматься той тематикой,
которой мы занимались уже довольно долго, а именно продолжим обсуждать вот эти вот
замечательные характеристики графов: такие как хроматические числа,
числа независимости, кликовые числа.
Но сегодня обсудим алгоритмический аспект этой проблематики, который,
мне кажется, имеет достаточно прикладной характер,
и с этой точки зрения особенно может быть интересен многим слушателям.
Впрочем, красивой математики будет не меньше, чем обычно.
Итак, мы по-прежнему рассматриваем вот эти замечательные величины: χ(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 с чертой — это то же самое,
что независимое множество в исходном и наоборот.
Ну это понятно.
Давайте говорить только про хроматическое число и число независимости.