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