Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Сравнение двух оценок хроматического числа
Loading...
Do curso por Moscow Institute of Physics and Technology
Случайные графы
62 ratings
Na lição
Хроматическое число случайного графа
Оценки хроматического числа случайного графа G(n,p) при различных p=p(n).
Conheça os instrutores
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Максим Жуковскийпреподаватель
кафедра дискретной математики МФТИ
Добрый день, друзья!
Ну что, в прошлый раз мы разобрались с такой совершенно удивительной темой,
которая поставила много вопросов, на самом деле,
о раскрасках и о характеристиках случайных графов, которые с ними связаны.
Так вот, начнем мы сегодня с того,
что ответим все-таки на поставленный на прошлой лекции вопрос.
Какая из двух оценок лучше?
Голосования я, к сожалению, провести не мог, ну,
хотя, кто знает — можно устроить онлайн голосование, это я не думал.
Ну хорошо.
Давайте, значит, давайте все-таки ответим на вопрос.
Давайте ответим на поставленный вопрос.
А вопрос был поставлен такой.
Вот есть оценка хроматического числа кликовым числом графа,
то есть размером самого большого полного подграфа в этом графе,
совершенно очевидное, и есть другая оценка,
которая получается как отношение числа вершин графа к его числу независимости,
то есть к размеру самого большого пустого подграфа, самого большого независимого
множества, множества, которое свободно от ребер.
[ВЗДОХ] Ну и какая же из двух оценок лучше?
Вопрос-то ставился так.
Мы берем все возможные графы на n вершинах — их 2 в степени c из n по два,
ну и спрашивается, каких графов больше.
Тех, для которых эта оценка сильнее, чем вторая, или наоборот — тех,
для которых вторая сильнее, чем первая.
При этом результат, который мы получили на прошлой лекции,
он не позволяет ответить на этот вопрос.
Да, действительно, там использовалось второе неравенство, но так, елки-палки,
там нельзя было использовать первое.
Мы как раз хотели избавиться от клика, даже от циклов.
Так что это не ответ.
Ну ладно, томить больше не буду.
Теорема, с которой мы начнем сегодняшнюю лекцию и которая нам в
дальнейшем еще пригодится для очень практических, между прочим, нужд,
значит эта теорема утверждает,
что пусть вероятность ребра случайного графа, это просто 1/2.
То есть каждый граф возникает с одной и той же вероятностью,
равной 1 поделить на 2 в степени c из n по 2.
Все ребра равно возможны.
Они как проводятся, так и не проводятся с вероятностью 1/2.
Это такой вот случай классической вероятности для случайного графа.
Тогда асимптотически почти наверное,
ну, то есть, как обычно — с вероятностью, которая стремится к единице,
коль скоро n стремится к бесконечности, α(j) не превосходит
два двоичных логарифма n.
Более того, одновременно выполнено и вот такое
неравенство: ω(j) не превосходит два двоичных логарифма n.
Ну, на самом деле, товарищи,
которые хорошо чувствуют теорию вероятности, они должны понимать,
что коль скоро мы проводим ребро, каждое ребро случайного графа,
с вероятностью 1/2 и не проводим его с такой же вероятностью, то вот эти
случайные величины α(j) и ω(j) конечно должны иметь одинаковое распределение.
Ну просто отсутствие ребер и присутствие ребер имеет одну и ту же вероятность.
Поэтому какая разница на что смотреть?
На независимое множество, в котором ребер нет, или на клику, в которой, наоборот,
все ребра есть?
Ясно, что с точки зрения вот такой вероятности ребра, это одно и то же,
но если в нашей замечательной виртуальной аудитории присутствуют люди, которые,
ну может быть еще не до такой степени осознали эту тонкость, то бог бы с ним.
Я сейчас, когда буду доказывать этот результат, я, конечно, продемонстрирую и
вот это, и вот это, и просто по ходу дела станет понятно, что я имею в виду.
Другой разговор, что прежде чем доказывать эту теорему,
давайте сделаем из нее далеко идущий вывод.
Что она означает с точки зрения сопоставления вот этих двух наших оценок?
Ну смотрите, раз почти наверное, ну то есть с высокой вероятностью,
α(j) не превосходит удвоенного двоичного логарифма, то вот отсюда,
конечно, следует, что асимптотически почти наверное
хроматическое число нашего случайного графа не меньше,
чем n поделить на два двоичных логарифма n.
Понятно.
То есть вторая оценка, с высокой вероятностью,
это оценка величиной n поделить на всего лишь удвоенный двоичный логарифм.
В то время как первая оценка, в почти всяком случае,
то есть с вероятностью близкой к 1, это оценка величиной,
которая скорее всего меньше, чем два двоичных логарифма n.
То есть оказывается,
что с высокой вероятностью вот эта оценка гораздо лучше вот этой.
В этом случае у нас оценка едва-едва,
дай бог чтобы достигала удвоенного двоичного логарифма.
В то же время вот в этом случае она точно достигает величины,
которая равна n поделить на столь медленно растущую функцию.
Да, я ничего не говорю про маленькие значения n в этом рассуждении,
то есть утверждение касается только тех, больших значений n,
при которых соответствующие вероятности уже достаточно близки к единице, но и это,
по-моему, довольно впечатляюще.
То есть мы демонстрируем тем самым, что как правило на случайном графе
правильнее использовать вот этот результат, а не вот этот.
Это очень важно с практической точки зрения,
потому что когда вы на практике пытаетесь как-то оценить хроматическое число,
и даже не пробуете использовать, например, вот это неравенство,
а обращаетесь только к такому, потому что, дескать, вот его в каком-то
смысле принято чаще использовать, то это, как минимум, мягко говоря очень странно.
Все-таки с очевидной точки зрения первое неравенство ω(j),
оно гораздо слабее, чем второе.
Заметьте это, и мы сейчас это продемонстрируем.
Если на практике будете что-то такое использовать,
обязательно используйте и второе неравенство тоже.
Накрутить можно каждое из них.
Ошибиться можно и здесь, и здесь, но второе неравенство на случайном графе,
то есть в средней ситуации, работает гораздо-гораздо лучше.
Видите?
Вот такая величина, она куда как больше, чем логарифм.
Да ω к тому же еще и не превосходит этой величины, то есть нельзя даже утверждать,
что первое неравенство дает такую оценку.
Вот. Такой вот замечательный важный результат.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
