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