Интервальные графы и первое определение путевой ширины
Всем добрый вечер. Обратите внимание, что появилось домашнее задание: как обычно, на него две недели, здесь ничего не поменялось, — не пропустите дедлайн. Задачи там в основном по древесной глубине. У нас с вами началась вторая треть курса, его сердцевина, и пора двигаться к более серьёзным параметрам, чем те, что мы рассматривали до сих пор. Это не значит, что прежние параметры малозначительны, — просто у них меньше интересных взаимосвязей и разных определений. Чем дальше мы будем двигаться, тем больше будет возникать интересных связей, определений, классов графов и вообще новых концептов, и всё это мы с вами поймём.
Сегодня мы займёмся путевой шириной, по-английски она называется pathwidth. Тут возникает хороший вопрос: когда в таких названиях надо ставить дефис, а когда не надо? Ответ на этот вопрос — никакого правила нет. Где-то в названиях параметров дефис ставят, где-то не ставят, где-то пишут слитно, а где-то просто через пробел, так что на это приходится смотреть внимательно для каждого параметра отдельно. Pathwidth пишут обычно слитно; treedepth, кажется, тоже; а про следующий параметр я уже не скажу, как он пишется, — по-моему, тоже слитно. Будет потом и параметр ширины, который часто пишут через дефис.
Чтобы сделать хоть какой-то маленький шажочек от того, что мы уже прошли, вспомним: параметра ширины, который хорошо описывал бы путь, у нас пока нет — хотя один параметр мы с вами всё-таки изобрели. Кажется, был примерно один нормальный параметр, ограниченный у пути. Что это за параметр? Да, да — нужен такой, чтобы у пути он был очень маленьким и с увеличением длины пути не рос.
— (реплика из аудитории неразборчива)
— Да, это был feedback vertex set; здесь, на пути, он равен нулю. На доске это записано сокращённо: .
— Вырожденность.
— А, вырожденность ещё, кстати, была — хорошее замечание, спасибо. Вырожденность этого графа на самом деле равняется единице, на доске это второе обозначение: . Можно посмотреть и на максимальную степень: здесь минимальная степень — единица, а максимальная — двоечка.
Но суть в том, что интересно становится, когда мы начинаем в путь что-то добавлять. Я такую картинку рисовал на прошлой лекции: рядом с самим путём нарисован его «утолщённый» вариант — горизонтальная полоса из пяти четырёхугольных клеток, причём в каждой клетке проведены обе диагонали, так что любые два соседних столбца этой полосы порождают . Хотелось бы, чтобы и здесь параметр оставался ограниченным — и при этом допускал эффективные алгоритмы. Вырожденность тут, понятно, будет ограничена, потому что степени всё ещё ограничены, но мы знаем, что сам по себе параметр вырожденности эффективных алгоритмов не даёт.
Давайте попробуем определить параметр путевой ширины. Определений у нас опять будет много, и обязательно будет определение с грабителем и копами, с полицейскими. Но сначала давайте вспомним — или узнаем — какие-нибудь простые концепты. Один из таких простых концептов — интервальный граф. До сих пор из простых графов у нас были только деревья и клики; этот класс графов немножко посложнее, но определяется он всё равно просто.
Что такое интервальный граф? Граф является интервальным, если каждой вершине можно сопоставить отрезок. Формально: если найдётся отображение из вершин в некоторые отрезки, — какие именно границы, тут совершенно не важно, — такое, что рёбра становятся отношением пересечения этих отрезков: . Понятно такое определение? Ничего формального я тут не накосячил, вроде бы нет. А что за штуки стоят в отрезках — это просто какие-то числа на числовой прямой, любые: можно целые, можно вещественные, целых нам, конечно же, хватит.
Конечно же, такой граф рисуется множеством отрезков. Граф-путь выглядит вот так: шесть отрезков в двух сдвинутых друг относительно друга рядах, каждые два последовательных пересекаются по короткому общему участку — это и есть рёбра пути. А клика выглядит автоматически вот таким вот образом, и никак больше: отрезки уложены друг под другом со сдвигом вправо и все пересекают одну общую вертикальную полосу. То есть это у нас граф , а это — граф . Вопросы, это всё понятно? Все отрезки должны пересекаться; а если отрезки пересекаются попарно, то они пересекаются и в одной общей точке. Вот так у нас здесь и есть — это интервальный граф.
Что ещё интересного можно сделать из интервальных графов? Давайте, например, свяжем интервальные графы с древесной глубиной — связь интервальных графов с древесной глубиной. Древесную глубину мы с вами изучаем уже две лекции, и теперь нам очень легко связать с ней интервальные графы. Каким образом? Если мы возьмём у графа elimination tree — на доске оно подписано сокращением рядом с именем — вот, например, такое, то по нему интервальный граф можно построить согласно временам входа и выхода у этих вершин. Если помните, в поиске в глубину есть время входа и время выхода; по факту это отрезок для вершины, и в этот отрезок вкладываются отрезки всех её сыновей.
Сейчас нарисую, графически это будет совсем понятно, а формально про это легко погуглить: каждой вершинке соответствует отрезок, и отрезок узла-родителя содержит отрезки узлов-дочерних. Вот у меня здесь два дочерних отрезка, а эта штука делится ещё на два дочерних отрезка. Тут можно нарисовать вот такой отрезок, а тут — ещё два отрезка. Левое поддерево, кажется, я нарисовал хорошо; и правое поддерево тоже можно нарисовать хорошо. Make sense?
— Но оно же получается не описывает исходный граф, потому что вершины получаются связаны со всеми предками.
— Это хорошее замечание, мы сейчас ровно эту интуицию и хотим уловить. Во-первых, замечу, что так всегда получится специальный интервальный граф: в нём отрезки либо не пересекаются, либо вкладываются друг в друга. Я не знаю, как это правильно называется, — ламинарная система отрезков, может быть; мне кивают сзади, что да, именно так и называется. Но проще сказать, чем запомнить, что такое ламинарный.
То есть по elimination tree получается некоторый интервальный граф , и на доске между деревом и системой отрезков нарисована двойная стрелка . Причём если я строго задам то, что я сказал, то есть задам ограничение на интервальные графы, что они ламинарные — отрезки могут только вкладываться, а пересекаться по-другому не могут, — то это вообще эквивалентно. Потому что отношение вложения одного отрезка в другой — это как раз отношение «является ли один предком или потомком другого». Согласны?
И вот теперь вопрос: если это elimination tree графа , то чем является вот этот граф для графа ? Смотрите, сам интервальный граф я тут не нарисовал, я нарисовал только его interval representation — изображение в виде системы отрезков. Конечно, — это подграф моего интервального графа, заданного деревом: .
А теперь скажите мне, пожалуйста, как по этой штуке определяется древесная глубина? Да, это цепочка вложенных отрезков. А скажите, с точки зрения теории графов — если бы мы не знали, что граф интервальный, — что из себя представляет в графе цепочка вложенных отрезков?
— Максимальная по включению клика.
— Да, просто максимальная по включению клика, всё так. Формально доказывать, что максимальная по включению клика — это всегда цепочка, то есть просто вертикальный путь вот в этом дереве, мы не будем: это несложно доказать, но мы просто не будем это проводить.
Соответственно, мы можем определить, что на самом деле — древесная глубина — получается вот чем: это минимум по всем таким интервальным графам, которые содержат . Давайте так и напишем: . Это счётчик по всем графам, которые содержат — я просто перебираю такие графы, а elimination tree обозначаю вот так; условие под знаком минимума на доске обведено. И тут я просто смотрю , где — это просто размер максимальной клики в графе.
Я вам обещал новый параметр, а ввёл определение старого — видите, какой я обманщик нехороший. Согласны ли вы с таким определением? Может быть, какой-то формальный переход я здесь не учёл или что-то формально неправильно обозначил; если такое есть, скажите, пожалуйста. А это у нас какое определение древесной глубины? Пятое.
Так вот, мы с вами приходим наконец к путевой ширине. И путевая ширина определяется очень просто: давайте-ка я сниму с этого интервального графа ограничение, что он ламинарный. То есть теперь мне разрешён и вот такой, произвольный интервальный граф. Это и будет первое определение путевой ширины. Давайте я напишу его уже не так неформально — предыдущее было достаточно неформальным, потому что я там определил на словах. На доске помечу его обведённой в кружок пометкой «pw 1», чтобы мы не запутались.
Итак, — это минимум по всем интервальным графам. По-моему, отношение так на самом деле не обозначается — или обозначается, — что является подграфом ; я уже не помню, честно, но кажется, что так обозначать справедливо. Давайте напишу правильно: я беру минимум по всем подграфам (оговорка лектора: имеются в виду надграфы, и на доске отношение записано верно — ) , которые содержат , и где — интервальный. Это как раз , и под условием на доске приписана стрелочка вниз и слово «интервальный». Это совсем простое, вообще суперпростое определение, но пока оно мало что даёт для понимания того, что это за параметр.
Зато мы с вами очень плавно перешли от treedepth к pathwidth. Простите мне такой ломаный русско-английский, но я так всё равно буду говорить — так мы и говорим.
И в частности мы с вами победили путь: у пути получается путевая ширина 2. Но тут я немножко замечу, друзья, что учёным почему-то было очень скучно. И знаете, что они сделали? Они говорят: а почему у пути должна быть путевая ширина 2, я хочу один. И они вычли отсюда единичку: . Вот это правильное определение путевой ширины.
Соответственно, для других определений путевой ширины нужно будет понимать, какая путевая ширина у пустого графа. Можно определить так, что она должна быть один, можно так, что должна быть ноль, — мы с вами это ещё увидим. Но это просто чистая формальность, никому особо сильно не нужная; каноническое определение вот такое. По нему для пустого графа она получается равна нулю — для пустого графа будем отдельно что-то смотреть.
С чего бы начать дальше, точнее — к чему бы перейти? У нас есть, в принципе, такие аспекты: можно ещё накидать определений путевой ширины, а можно взять и показать какое-нибудь применение путевой ширины. Давайте я попробую показать применение и начну с простого примера: рассмотрим какую-нибудь очень искусственную задачу на пути и поймём, откуда же берётся путевая ширина. Точно так же это потом будет работать и на деревьях.
Давайте возьмём задачу о списочной раскраске — на доске я пишу её латинскими заглавными, LIST COLORING. Это по-честному списочная раскраска: у нас есть разные понятия про списки — есть списочное хроматическое число, а есть списочная раскраска, и это совершенно разные задачи. Но давайте напомню, что такое списочная раскраска. Что является входом? Входом у меня является следующая величина — не величина, а функция: граф , и для каждой вершины есть список , некоторое множество цветов. Назову его « красивое»: на доске список — это каллиграфическая , а сама раскраска будет обозначаться маленькой прямой . И вопрос: найти правильную раскраску графа, правильную раскраску — такую, что .
ДП на пути, задача #List Coloring и ширина слоя
Итак, нужно найти правильную раскраску . Что такое правильная раскраска? Это раскраска, в которой концы любого ребра имеют разные цвета; а требование списочной версии состоит в том, что для любой вершины выполнено . Обычной раскраской это было бы, если бы во всех списках стояли числа от до . Условие записано на левой доске под нарисованным путём, от которого отходят две пометки — и (вырожденность; на доске она стоит сокращённо и вслух в этом месте не произносится).
Сейчас объясню, в чём разница между двумя близкими понятиями. Очень часто в теории графов изучают списочное хроматическое число: при какой длине этих списков, какими бы эти списки ни были, граф всегда можно раскрасить. Эта задача довольно сложная, она даже не в находится, насколько мне известно, потому что вам нужно посмотреть, что для каждого возможного набора списков у каждой вершины действительно есть раскраска, — а это довольно сложно представить полиномиальным образом. А здесь задача простая: нужно просто покрасить.
Давайте решать, например, задачу . Кто знает, как меняется задача, если мы дописываем в начале?
— Это значит посчитать количество.
Да, нужно найти количество правильных раскрасок: на доске к заголовку приписывается , а в строку Question вставляется слово «количество». Например, у нас есть классы и — они выписаны справа на левой доске двумя отдельными заголовками. Типичная задача из — найти кратчайший путь, задача из — посчитать число кратчайших путей. Или задача из — найти паросочетание, а задача из — найти количество паросочетаний.
Я специально взял задачу, которая решается не супертривиально. Её можно решать динамическим программированием на пути — давайте мы её на пути и решим. На доске появляется горизонтальная черта и под ней заголовок «На пути » — так он сокращает . Опять, видите, динамическое программирование, но сегодня я постараюсь, чтобы оно было поудобнее, чем было раньше. Кто может предложить, какое динамическое программирование тут будет? На самом деле мы с вами уже рассматривали более сложные конструкции, но в этом курсе мы не хотим разбирать ничего очень суперсложного — скорее уловить все основные концепты и систематизировать их.
Решается это так. Мы берём некоторый префикс нашего пути и хотим посчитать количество списочных раскрасок вот здесь. Давайте назовём вершинки и будем считать величину — количество списочных раскрасок порождённого подграфа на первых вершинах. Все знают, что такое порождённый граф? Никого это не пугает? Я оставил в графе только первые вершин, остальные удалил; рёбра при этом остались те, какие между ними были.
Но давайте вспомним, собственно, зачем нам нужно динамическое программирование. Оно нужно затем, чтобы, когда мы пытаемся красить следующую вершину, она не попадала в конфликт вот с этой вершиной. Поэтому раскраски префикса нам нужно разделить между собой на некоторые классы, чтобы можно было потом красить следующую вершину. А какие это классы будут, друзья?
— Цвет последней вершины.
Да, мне только он и важен.
Итого состояние я храню такое: . На доске вторым аргументом сначала стояло , и оно сразу же было заменено: давайте я вот здесь напишу другую букву, извините, что так приходится, — букву от слова last. Это просто количество правильных списочных раскрасок вот этого графа, в которых , last color, — и всё. И это очень просто решается: я беру и перебираю цвет следующей вершины и делаю переход вперёд, либо перебираю цвет предыдущей вершины и делаю переход назад. Математически это расписывается просто как тождество: пересчитывается через значения .
И теперь как раз наша суть в том, что вот эту динамику для пути очень легко расширять. Например, если у вас будет вот такая полоса, как я вам и обещал, то как тогда меняется это динамическое программирование? Теперь мой префикс — это на самом деле вот такая широкая «колбаса»: я храню широкий путь. На доске полоса нарисована как ряд квадратных клеток, в каждой из которых проведены обе диагонали, так что каждый блок два на два — это ; у левого края стоит вертикальная двойная стрелка с подписью , два соседних вертикальных столбца обведены овалами, а под левой частью полосы стоит фигурная скобка — это и есть префикс. Чтобы покрасить следующие две вершины, мне важно знать цвета только предыдущих двух вершин; и понятно, что я буду расширять, расширять и расширять эту штуку, а количество будет просто расти по компонентам — компонент будет всё больше и больше. То есть если ширина у меня какая-то , то здесь у меня получится вектор из цветов: .
Соответственно, сколько примерно будет занимать моё динамическое программирование? Если длины списков равны — точнее, не больше, чем , и на доске к строке Input дописано ограничение , — то этих векторов у меня, конечно же, будет , а самих префиксов будет . Именно это зафиксировано на доске двумя фигурными скобками под состоянием: подписано под , а — под . Значит, состояний , переход тоже за , а всего получается примерно с точностью до каких-то ещё множителей от , то есть .
Окей, понятна эта интуиция? Я очень просто расширил динамику, вообще ничего умного не делая. И как раз наша с вами цель — вся цель путевой декомпозиции, которую мы с вами сейчас определим, цель путевой ширины — это как раз взять и все такие динамические программирования обобщить. На самом деле этим графом может быть далеко не путь: я из этого графа могу какие-то рёбра удалить, и всё остальное, и всё равно всё будет работать. Мне будут важны только переходы между вот этим слоем и следующим слоем, и я буду по одному слою потихоньку добавлять. Это наша самая важная интуиция, давайте её пока держать в голове.
Давайте я покажу это на примере — где это у нас было и что я намеренно упустил, чтобы вообще не вспоминать динамическое программирование. Смотрите: в чём, как вы думаете, здесь минус вот этого подхода по сравнению с древесной глубиной? Кто читал уже домашнее задание, мог это заметить; древесная глубина нам такого минуса не давала. По времени тут тоже экспонента — от древесной глубины у нас тоже была экспонента, — а вот что происходит с памятью? Тут памяти, раз у нас такое динамическое программирование, явно нужно . А в древесной глубине у нас была полиномиальная память, потому что рекурсия не требовала того, чтобы мы что-то запоминали в экспоненциальном количестве: мы просто спускались вниз и что-то считали, и запоминания не было. А вот тут уже нужно делать запоминание.
Хорошо, давайте двигаться дальше. Если интуиция с путём понятна, динамическое программирование мы усвоили и вопросов нет, давайте переходить к следующему определению путевой ширины. Мы с вами уже поняли, что это значит — штука с интервальным графом. В частности, кстати, отсюда уже следует вот такой факт, замечание. Здесь правая доска стирается целиком, и на освободившемся месте появляется подчёркнутое «Замечание»: . Вслух это звучало как « хотя бы , ну тут я должен добавить плюс один, видимо» — на доске стоит именно точная форма с единицей. Нет, пока нет, я объясню, откуда там путевая ширина; мы её сейчас построим.
Скажите, понятно, откуда это берётся? Всем понятно? Смотрите: — это был минимум по всем интервальным графам, а — это был минимум только по каким-то интервальным графам. Ну и я ещё вычел единичку, вот эту пресловутую. То определение, с которого мы сравниваем, было помечено на стёртой теперь доске обведённой римской единицей (I): , где минимум берётся по интервальным надграфам.
Хорошо, был хороший вопрос: где вот здесь возникает путевая ширина? Давайте тогда уже определять, собственно, путевую декомпозицию — нет смысла куда-то дальше идти. Смотрите, в чём фишка. Определение путевой ширины через интервальные графы, конечно, консистентно и вообще интуитивно понятно, но, к сожалению, алгоритмически оно не очень подходит, потому что интервальные графы не дают нам вот такой хорошей структуры — её ещё надо выделять. Поэтому учёные, конечно же, стали придумывать, а как же определить хорошую последовательность, по которой можно считать такие динамические программирования. Ну и давайте просто создадим такое понятие — путевая декомпозиция.
Путевая декомпозиция графа — это последовательность множеств; на доске записано «последовательность множеств », то есть подмножеств , и сама последовательность . Обозначают их обычно буквой — сейчас скажу, как они называются и почему я выбрал эту букву. Что про эти множества мы хотим сказать? Сначала я всё напишу, а потом мы поймём, как это относится к интервальным графам.
Первое, что я хочу сказать: любое ребро должно жить внутри какого-то множества. То есть для любого ребра должно у меня найтись такое множество , что . А — потому что это обычно называют сумками, bag, вот так они называются.
А теперь у нас должны откуда-то возникнуть путь, должны откуда-то возникнуть интервалы. Верно следующее: для любой вершинки и для любых — порядок на доске выписан явно, а не просто упомянут — из того, что и , следует . (Произнося эту аксиому, лектор трижды говорит «сумка лежит в », имея в виду вершину, и тут же сам себя поправляет.) По-другому говоря, вершина просто живёт в отрезке сумок: у меня не бывает такого, что вершина появилась, где-то она была, была, была, а потом пропала. Вот такая есть штука — это и есть путевая декомпозиция. Мы сейчас с вами динамическое программирование перенесём вот сюда, сделаем чуть более формально и поймём, почему вот эта штука неудобная.
И давайте напишем второе определение — . Это, опять же, минимаксная история: мы по всем путевым декомпозициям выбираем лучшую. То есть минимум по , где это путевая декомпозиция графа — на доске подстрочник написан сокращённо, (я знаю, что я тут очень мелко написал, извините, пожалуйста; ну вот доску как-то надо экономить). А под минимумом стоит просто максимум по всем от единицы до от размера сумки, ну и, конечно же, наше любимое минус один:
На доске это определение помечено обведённой римской двойкой (II) — в пару к обведённой римской единице (I) у определения через интервальные графы.
Так откуда берутся наши сумки, друзья? Как вы считаете, что это такое — сумка?
— Время жизни вершины.
На самом деле всё правильно, всё правильно, Кость, ты говоришь, что это очень сильно связано со временем жизни. Да, чтобы получить сумку, мы просто берём и сечём наш интервальный граф в одной точке, и всё, что наша точка пересекла, это как раз и есть сумка. И как раз последовательность сумок — это просто последовательность вот таких сечений. Понятно, что вот здесь она будет пустой, и понятно, что у нас будет что-то накапливаться.
Ну давайте я пример приведу. Если вот это у меня было , то у меня будет пустая сумка, потом сумка, состоящая из единички, — здесь я одно сечение пропустил, — потом сумка, состоящая из единички и двойки, потом сумка, состоящая из двойки, единички и четвёрки (именно в таком порядке она и выписана на доске: , то есть как множество это ), потом уже сумка, состоящая из двойки и четвёрки, и так дальше — я не буду всё до конца писать. На доске это четыре горизонтальных интервала с номерами на трёх уровнях, перечёркнутые семью вертикальными линиями-сечениями, а под ними выписана последовательность сумок
Соответствие между интервальными графами и путевой декомпозицией тут достаточно очевидное. Это хорошее определение, потому что оно нам теперь позволяет решать , когда нам задали путевую декомпозицию. Но давайте это формально проделаем — уже без вот этой интуиции просто с путём, а чуть более формально. Принцип будет весь ровно тот же самый.
Я зря, кстати, стёр этот пример: он хорошо пояснял, что такое сумка на самом деле, и он объясняет, почему немножечко там не всё так интуитивно в путевой декомпозиции. Сейчас я его ещё раз нарисую. Давайте я ещё раз нарисую кусочек вот этого графа — давайте я вот это всё сотру и нарисую кусочек графа, вот такого вот. (Левая доска стирается целиком; из написанного на ней остаются только заголовки и в правом верхнем углу.) Вот что является сумкой у такого графа?
— Одной.
Свойства путевой ширины и ДП по сумкам
Итак, у меня есть вот такие пары вершин — вот такие прямоугольнички. Давайте лучше порисуем, прежде чем переходить к динамике. Если на ту динамику мы смотрели по слоям, так что добавлялось по две вершинки, то здесь мы сразу рассматриваем два слоя одновременно: формально это один объект. Чтобы обобщить ту динамику, нам придётся брать сразу целый слой — как в динамическом программировании, где мы считаем сразу две строчки; в этом смысле у нас в сумку сразу входит два слоя.
А если мы, например, добавим в этот граф универсальную вершину, соединённую со всем, то путевая ширина изменится всего на единичку: я просто могу добавить один отрезок максимальной длины, который пересекается со всеми. Это то же самое, что добавить вершинку в клику.
Давайте напишем замечание. Первое замечание: если я беру путевую ширину графа и удаляю из него вершинку, то путевая ширина не может уменьшиться больше, чем на единичку. Не так, извините; правильная запись вот такая: . То есть при удалении вершинки путевая ширина меняется плавно. Замечу, что здесь можно поставить равенство, когда — универсальная вершина; это не критерий, но для универсальной равенство есть, и это можно доказать. Так что равенство выполняется не для всех вершин.
Вторая часть замечания такая. Пусть у меня есть некоторое множество , и — полный граф. Тогда в любой путевой декомпозиции всегда найдётся сумка, содержащая всё целиком; на доске это записано так: , — полный граф . Отсюда, кстати, можно было понять, что сумка обязана целиком содержать два слоя: клика обязана входить в сумку целиком. Но это просто следует из интервальных вещей: если некоторые отрезки попарно пересекаются, значит, у них всех есть общая точка. На прямой это так работает. Наверное, на плоскости тоже. Нет, на плоскости не работает: на плоскости могут быть вот такие штуки — три попарно пересекающихся отрезка без общей точки. Только на прямой это верно, и это важное замечание.
Вот такие интуитивные факты; факты пошли очень скучные, давайте пойдём пободрее. Что мы теперь делаем? Давайте построим, собственно, динамику по путевой ширине и решим , параметризованный путевой шириной — на доске это записано как .
Что мы будем делать? Мы знаем, что у нас есть некоторая последовательность сумок. Теперь, благодаря этой последовательности, нам нужно сделать что-то аналогичное пути: там у нас был прямо чётко выстроенный путь, а здесь есть сумки. Тут понятно что: когда сумки выстроены, это просто некоторый префикс — мы берём первые сумок и их объединяем. Значит, от первого индекса .
А теперь профиль нашей раскраски. Смотрите: если у меня есть сумка и есть все сумки правее, то я знаю, что если есть ребро из вот этого множества вершин в вот это множество вершин, то у него обязательно хотя бы один конец лежит в . Давайте напишем такое — менее очевидное — замечание из тех, что были. Я говорю про любую path decomposition. Заведём первую часть графа как объединение некоторых сумок; индекс я выбираю неудачно, давайте возьму здесь индекс , от слова prefix. То есть , а я беру равным объединению от и дальше — ой, что-то тут не до , тут до : у меня же — число сумок в декомпозиции. Давайте сделаем определение получше, не такое стрёмное: одну сумку захватим, так будет правильнее, то есть . И тогда я могу точно сказать, что множество рёбер между и вкладывается в множество рёбер графа, образованного сумкой : . Вот теперь всё хорошо, до этого определение мне не нравилось.
Скажите, это понятный факт? До этого у нас были очень размыточные [так в записи] факты, а теперь — вот такой жёсткий. Из интервального представления всё делается очень легко: мы в этом месте режем отрезки вертикальной прямой, и отрезки слева с отрезками справа никак не пересекаются. Это наш основной факт.
Теперь мы готовы делать наше динамическое программирование. Мы будем считать раскраски как раз нашего префикса. Что такое ? Это число раскрасок — списочных, понятно — графа, порождённого первыми сумками, то есть графа , таких, что если я возьму , суженную только на множество вершин , то получится функция, эквивалентная : . То есть — это маска только последней сумки, вот этой; только эти цвета я и беру. Понятно такое? Вот это и есть наше динамическое программирование.
Но формальный переход мы ещё не сделали, я пока только определил саму динамику. На чём мы остановились? Мы сформулировали то, что мы считаем, а это, друзья, в динамическом программировании вообще самое важное — сформулировать то, что мы считаем. Это мы сделали. Правда, я не совсем чётко сформулировал, что такое , но это понятно: это раскраска сумки номер . Вот здесь я написал плохо: я же иду до префикса , и — это на самом деле отображение из в некоторые цвета, согласно спискам.
Если мы решаем списочную раскраску, в которой длина каждого списка не больше, чем , то число таких , конечно же, ограничено величиной в степени pathwidth плюс один: . Надо было придумывать так, чтобы из pathwidth вычиталась единичка, и тогда не приходилось бы потом везде читать «плюс единичка». Честно говоря, я не знаю историю, почему, когда придумывали pathwidth, сделали минус единичку; возможно, не думали, что в алгоритмическом анализе это будет не очень приятно. Нам это не важно: я очень часто буду писать здесь просто без плюс единички — позвольте мне такое, пожалуйста. Просто надо помнить, что классически она там есть; это кое-что немножко меняет, но несущественно. То есть наш параметр — это максимальная ширина сумки (строго говоря, по определению — это максимальный размер сумки минус единица).
Тут стоит сделать отдельное замечание: путевую декомпозицию, конечно же, тоже надо вычислять, и это отдельный вопрос — как её вычислять. Там есть много открытых вопросов: до сих пор, как и с древесной глубиной, хочется более хороших алгоритмов, вычисляющих путевую ширину. Когда мы дойдём до древесной ширины, там будет всё лучше: для древесной ширины таких алгоритмов много, а для путевой нет. Это можно себе пометить: путевую ширину и путевые декомпозиции ещё нужно как-то вычислять.
Давайте сделаем формальный переход, то есть как нам перейти от к предыдущему. Сделаем более классические переходы назад: по моему опыту, динамическое программирование легче воспринимается назад, когда рассказываешь что-то общее, математическое; да и доказывать его назад легче. Что у нас происходит? Я знаю, что у меня всё посчитано для префикса , а я хочу посчитать всё для префикса , то есть хочу продлить. Я хочу посчитать профиль — это называется ровно профилем, мы всегда это так и называли. Если вы когда-нибудь писали ДП по профилю, то вот это и есть ДП по профилю. Мы к этому немножко вернёмся потом, потому что окажется, что на графах-решётках здесь всё будет замечательно, и мы увидим почему.
Что мы тогда знаем? Вот здесь был профиль сумки , то есть какая-то раскраска сумки, и я знаю, что должен быть какой-то предыдущий профиль . На самом деле вот эта штука — это просто сумма по всем , согласованным с . Давайте напишу немножко правее, а то смазалось: это сумма по — раскраскам куда-то, я не буду писать куда, — таким, что согласована с , и под суммой стоит от предыдущего профиля: . Понятно такое? Я просто смотрю, какая была предыдущая раскраска, а это ровно то, что мы повторяли.
Только теперь проблема в том, что эти сумки могут пересекаться. Не проблема, а альтернатива: потом мы поймём, почему нам выгодно, что сумки пересекаются — это будет супервыгодно. Сейчас это пока немножко контринтуитивно. Почему? Потому что есть предыдущая сумка и есть следующая сумка, и они в чём-то пересекаются: вот это сумка , а вот это сумка .
Как же проверить согласованность? Давайте раскрою согласованность вот здесь. Во-первых, , суженная на пересечение этих сумок, совпадает с , суженной на пересечение этих же сумок: . Понятно, что значит вот этот знак? Это просто сужение функции. Условие нужно потому, что это же профили одной и той же раскраски — они должны быть согласованы. Это первый пункт. А дальше мы должны где-то понять правильность. Где может быть правильность? Мы знаем, что вся правильность заключается просто внутри сумки: грубо говоря, какие новые рёбра появляются в графе при появлении вот этой новой сумки. Был старый граф, и к нему приписались какие-то новые вершины вот здесь. Естественно, нам нужно проверить — и это уже даже не согласованность и , — что — правильная списочная раскраска.
И заметьте, что здесь так оказалось, что вся согласованность — это только вот это. Никаких рёбер между и мы не смотрим: их просто не может быть, таких рёбер нету. Извините, у меня мел всё время западает. Таких рёбер не бывает — вот так не бывает по определению. Так что все рёбра, которые могут быть у этой части графа и у этой части графа, лежат в пересечении вот этих сумок.
И даже вот это утверждение я мог написать немножко получше — я просто тупанул и плохо написал. На самом деле тут их можно взять и разделить. Давайте разделю согласно прошлому, согласно тому, что там написано: я беру первые сумок, то есть , и вот эту часть, начиная с до , то есть . И тогда у меня разрез вершинный — это как раз пересечение сумок, ; на доске это записано как . Всё это тот же самый факт, друзья. Это то же самое, как если бы я между сумками вписал просто их пересечение: вписать между сумками их пересечение никак не портит путевую декомпозицию. Таких фактов нам анализировать очень много, и это будет просто очень скучно — тут надо просто проверить, посмотреть на отрезочки, и действительно всё будет так. Поэтому этот переход совершенно справедлив; главное — делать раскраски вот такими, хорошими.
А согласованность — это на самом деле просто то, что мы продлеваем раскраску так, чтобы там, где сумки пересекались, было раскрашено одинаково. Это можно сравнить с тем, что у нас было для вот этой штуки: там мы делали динамику немножко сложнее, когда рассматривали вот такой путь. Мы говорили, что есть вот этот слой и вот этот слой, а сумка объединяла два слоя. Разница была в том, что согласованность мы проверяли гораздо сложнее: был какой-то слой и слой , и согласованность между ними заключалась в том, что мы должны проверять рёбра между ними. Здесь же два слоя упакованы сразу в одну сумку, поэтому вот этого нет. Вопросы какие-то на данном этапе?
Давайте посмотрим, сколько работает вот эта штука. Кажется, что это работает за в степени путевая ширина — вот этих параметров , — и вот этих штук у меня . На самом деле можно понять, что количество сумок в путевой декомпозиции не больше, чем , потому что иначе какие…
Замощения доминошками, изломанный профиль и приятные декомпозиции
Иначе какие-то две соседние сумки совпадают. Сумок, наверное, не больше чем — так совсем просто; но можно доказать, что их должно быть не больше чем . Поэтому размер таблицы — это, конечно же, , то есть в степени путевая ширина умножить на число сумок. Переход тут совсем простой: проверить согласованность можно очень легко. Но перебор может занять достаточно большое время — таких вариантов у нас тоже . И получается, что время работы на самом деле . Это не очень круто, это даже очень жирно.
Это можно сделать немножко более умным способом, чтобы было — правда, не очень красивым способом. Но пока что у нас умножить на , потому что, чтобы сделать переход, мы перебираем предыдущий профиль целиком — в такой формулировке, какая у нас пока есть. И проблема здесь только в том, что путевая декомпозиция неудачная: если рассматривать её в совсем простом виде, она просто-напросто неудачная. Давайте с вами поймём, что же такое удачная путевая декомпозиция.
Друзья, понятно ли всё динамическое программирование, понятно ли, почему оно формально сошлось? В целом по всем нашим рисункам всё должно получиться. Справа видно, что переход у нас очень сложный: он занимает перебор профиля целой сумки. И этого мы хотели бы избежать.
Сейчас я приведу вам пример; может быть, вы когда-нибудь такую задачу решали. По крайней мере на курсах алгоритмов — что-то среднее между базовым и продвинутым — изучают такую задачку. Дана шахматная доска с выколотыми клетками. Я, правда, не могу в реальности представить себе шахматную доску с выколотыми клетками; я могу представить, что потеряли шахматы — у меня этого дома полно, шахматных досок с потерянными шахматами.
Итак, дана шахматная доска, и на некоторых клетках стоят пешки — на них ничего класть нельзя. Но шахматная доска, к сожалению, это граф константного размера, поэтому доска у нас будет . Что нужно посчитать? Посчитать число способов замостить незанятые клетки доминошками . Я, опять же, плохо себе представляю, что я взял домино и начал класть их на доску, — но шахматную доску я тоже себе не представляю.
Давайте нарисуем какой-нибудь пример. Если доска без выколотых клеток, это как-то за полином, наверное, считается: тут у меня либо положить две горизонтальные доминошки, либо положить две вертикальные. Когда клетки выкалываем, всё начинает быть интереснее. Я, кстати, не знаю, какая тут комбинаторная формула, но это интересный вопрос: если нет выколотых клеток, какие-нибудь числа чьего-нибудь имени будут, наверное.
Хорошо, а как мы обычно решаем эту задачу, друзья? Кто помнит с курса алгоритмов, если он у них был, такую задачу?
— ДП по изломанному профилю.
Там было две штуки: ДП по профилю и ДП по изломанному профилю. Всё так. И как это всё представляется? Мы замощаем какие-то первые строчек, и за счёт замощения первых строчек у меня какие-то доминошки торчат наружу. Можно пока представлять себе доску без выколотых клеток, друзья: выколотые клетки здесь просто для того, чтобы не считалось легко, — так что, если с ними сложно, думайте про это без них. Когда мы замостили эти строчки полностью, какие-то доминошки торчат наружу: это вертикальные доминошки, которые мы здесь положили. Нам остаётся замостить оставшуюся часть доски, при этом мы знаем вот такой профиль.
И это на самом деле тоже динамика по путевой декомпозиции. Потому что — что это за задача? Как её математически сформулировать, кто может сказать? Я уже называл сегодня эту задачу. Что это за задача и на каком графе, если граф без выколотых клеток? Это, друзья, число совершенных паросочетаний на графе-решётке. Я напишу сразу: на grid graph. Мы, к сожалению, пользуемся английскими терминами: граф-решётка — мы, конечно же, не grid, мы говорим grid graph. Я тоже так буду говорить, но это не значит, что не надо говорить «граф-решётка».
Любая доминошка покрывает ровно две вершины, вершинки накладываться не должны, и при этом мы накрываем все вершины — значит, это совершенное паросочетание. А когда мы выкалываем клетки, мы просто удаляем вершины из этого графа. То есть на подграфе графа-решётки мы должны найти число совершенных паросочетаний.
Давайте нарисуем, собственно, граф-решётку; я нарисую только какую-то его часть — можете посмотреть, как я страдаю, пока его рисую. Обычное ДП по профилю — когда я, например, его реализовывал, я не знал, что можно умнее, — смотрит на две строчки этого поля. И смотрите: этот граф двойственный к доске, точки стали центрами клеток, а рёбра — это как раз доминошки. Не путайте: доминошки мы кладём не сюда, а вот так. И как раз две соседних строчки этой штуки можно запихать в одну и ту же сумку — тогда получится вот такая история: сумки у меня — это две соседние строчки шахматной доски. Это понятно?
И я действительно делаю такую динамику: фиксирую две строчки и смотрю согласованность с предыдущими двумя строчками, но только делаю ограничение, что одна строчка всегда полностью заполнена, потому что меня не интересуют профили, где эта строчка заполнена не полностью. Такую историю, во-первых, очень больно реализовывать: когда у вас выкалываются клетки между строчками, переходы получаются довольно больные, их правда очень тяжело реализовывать. Во-вторых, поскольку вы делаете переходы между двумя строчками, эта динамика будет занимать . Давайте я скажу, что эта ширина у меня , а эта ширина — . Тогда динамика будет занимать : — это количество сумок в путевой декомпозиции, а — это, примерно, профиль внутри одной сумки. Я нигде не вру, всё ли понятно, скажите?
И давайте я скажу, что это — «ДП по профилю», в кавычках. Обычно, если вы просто нагуглите какие-нибудь олимпиадные мануалы… я, правда, никогда не читал в олимпиадных мануалах про ДП по профилю. По крайней мере в университете, когда мы это читаем или слушаем, это называется ДП по профилю.
Но что я тут на самом деле сделал? Я допустил, что сумка должна быть размера , то есть как будто у меня этой решётки — это . А какая на самом деле графа-решётки, как вы считаете? Я ведь взял очень просто: взял две соседних строчки. А гораздо правильнее брать так называемый изломанный профиль. И следующий изломанный профиль у меня будет вот такой — то есть у меня два соседних изломанных профиля.
И вот утверждение. Путевая ширина решётки — как решётку обозначить, я, кстати, не знаю, но давайте обозначим её через букву , — итак, не превосходит плюс один, потому что размер сумки тут : вы взяли две строчки, и они пересекаются по одной вершинке. Но я вычел единичку, опять пресловутую, — так что на доске написано .
Но эта история хороша не тем, что у нас здесь очень маленький размер сумки, — дело не в этом. Как вы думаете, в чём на самом деле крутость этой истории? Что тут можно сказать про две соседние сумки в декомпозиции? Они довольно сильно отличаются, да? А вот тут что можно сказать про две соседние сумки? У них отличие всего в константу вершин — тут конкретно в две. Ну а тут нам ещё и повезло, что путевая ширина стала лучше.
Давайте это запишем, и мы с вами поймём, насколько динамическое программирование перестаёт быть переборным. Та штука очень переборная, потому что нам нужно перебирать предыдущий профиль, сравнивать согласованность и прочее, прочее. А на самом деле всё может быть намного-намного интереснее.
И тут мы приходим к следующему определению. Как вы думаете, как по-английски называются хорошие путевые декомпозиции? Какой такой классный математический термин могли придумать люди? Они просто сказали: хорошие путевые декомпозиции. Правда, не хорошие, а nice — то есть приятные. Приятные путевые декомпозиции.
И оказывается, нам нужно наложить немножечко дополнительных условий, чтобы стало всё замечательно. Итак, Nice Path Decompositions: — это такая путевая декомпозиция, где дополнительно выполняется следующее. Во-первых, начальные и конечные сумки пусты: . Мы потом с вами поймём, почему это хорошо, — это на самом деле интересно, мы немножечко пропустили этот момент.
И следующее ещё верно: у меня вычесть — то есть либо я из что-то удалил, либо я к что-то добавил. (Сейчас, извините, тут не так должно быть.) Поэтому давайте напишем просто симметрическую разность: . Скажите, понятно, что значит треугольничек? Это значит, какой элемент входит в , но не входит в , и наоборот, — то есть какие элементы различаются по отношению принадлежности этим множествам. И это всё, чего нам достаточно, чтобы динамика наша прям преобразилась и стала очень классной.
Почему тогда всё очень классно? Давайте посмотрим, что у нас происходит между сумками. Мы знаем, что крайние сумки у меня пустые. И теперь между двумя соседними сумками происходит ровно одно событие: либо вершинка появилась, либо вершинка пропала. Может быть плюс : например, , потом , потом , потом , потом . И давайте для примера посмотрим, что дальше могло произойти: например, , , и должно быть — и вот мы пришли к пустому множеству. Понятно, что это значит? Чтобы восстановить сумку, нужно просто пройтись по этим событиям, и всё.
Есть, конечно, некоторые утверждения, что любую путевую декомпозицию можно перестроить в приятную путевую декомпозицию с какими-то там расходами. Но давайте я лучше поясню, почему же это круто — иметь такую декомпозицию. Давайте вернёмся в нашу прошлую динамику с list coloring, и сначала я мотивирую первое свойство. Представим, что первого свойства у меня бы не было — например, что . Как мне тогда восстановить число списочных раскрасок графа? Я же посчитал только какие-то динамические программирования, а как мне посчитать само число раскрасок, если ?
Тогда придётся просто суммировать все профили по последней сумке: число списочных раскрасок — это , то есть мне нужно просуммировать нашу динамику от последней сумки по всем профилям. Соответственно, если последняя сумка у нас пустая, то профиль тут может быть только ровно один — и это суммирование происходит автоматически. Ответ у меня будет лежать точно вот здесь, а профиль у пустой сумки один. Но это, скорее, приятная мелочь, друзья.
Самое классное — это переходы. У меня может быть переход, например, забыть какую-то вершину. Это так называемый forget: forget у нас — забыть, по событию . Тогда никакую согласованность сильно проверять не надо, да? Если мы считаем у некоторого профиля , то мы с вами знаем, что должны посчитать что-то от предыдущей сумки, — но в предыдущей сумке ничего нового не происходило, никаких других вершин там не было
Переходы introduce и forget; путевая ширина через игру копов и грабителя
Поэтому мы должны просто взять… нет, наоборот: в этой сумке была лишняя вершинка, вершинка . Значит, всё, что нам нужно сделать, — это перебрать цвет вершинки :
где пробегает цвета вершинки . Смотрите, в чём суть. У меня был некоторый граф, и я хочу посчитать число его списочных раскрасок, если профиль идёт по вот этим вершинам. Но я всегда пользуюсь предыдущей сумкой, а предыдущая сумка содержала ровно на одну вершину больше — вершину . Значит, я могу зафиксировать только одну вершину, и всё. Видите: здесь нет никакого перебора согласованности профилей, никаких сложных вещей — я просто перебрал цвет предыдущей вершины.
Давайте я вот это сотру и напишу более простой переход. Переход от к — это так называемый introduce, то есть когда прибавляется : тогда . Вот тогда это как раз простой переход, и мы считаем : профиль, доставшийся от предыдущей сумки, здесь, наоборот, сократился.
Как это изобразить графически? У меня было вот такое, оно содержало , — это , — а … просто откусывает вот эту вершинку. (Здесь лектор путается в индексах и исправляется на ходу; доска однозначна: при introduce , так что вершину «откусывает» именно .) Поэтому тут вообще просто
то есть профиль , суженный на : нужно просто удалить из множества, из маски, один элементик. (В том виде, в каком этот переход выписан на доске, никакой проверки допустимости профиля в нём нет — она подразумевается самим определением профиля, данным раньше.)
Скажите, товарищи, понятно ли, что произошло, чем мы себе жизнь упростили? Переходы стали линейными. Раньше они были экспоненциальными, а теперь они суперпростые: нужно следить за поведением ровно одной вершины. В общей путевой декомпозиции нам нужно было следить сразу за целыми сумками — за тем, как две сумки согласуются, и всё. А такое замечательное определение позволяет нам писать суперпростые динамики.
Если вы хотите осознать это получше, попробуйте реально решить вот эту задачу — она очень хорошо всё демонстрирует. Попробуйте решить её сначала без такого профиля, а потом с профилем, когда у вас просто хранится строчка, — и вы почувствуете, в чём на самом деле разница. Потому что, когда я читаю лекции студентам, меня всегда бесит рассказывать вот это: формально рассказать это всё — просто жесть. А потом возникает вот это, ты пишешь вот эти два перехода, и всё. Может быть, кто-то мне скажет, что я здесь рассказываю что-то слишком сложное; не знаю, за много лет я пока не научился рассказывать это лучше.
Вопросы, друзья? Хорошо, если вопросов нет, давайте я напоследок поговорю про копов и грабителя. (На записи он говорит «про полицейских и копов» — оговорка: и доска, и весь дальнейший текст говорят именно о копах и грабителе.) Как вы думаете, как нужно поменять определение игр копов и грабителя, чтобы получилась путевая ширина? Давайте вспомним, как было для древесной глубины. Для игры были такие: я ставил копа в вершину, и коп оттуда больше не пропадал. А в путевой ширине копы будут стоять в сумке. Понятно, что сумки постоянно меняются, — и это на самом деле и есть ход копов: поставить копа куда-то в вершину, снять копа из вершины, поставить копа в вершину и так далее.
Ну что, есть какие-нибудь идеи, как нам надо поменять определение? Давайте я быстро его расскажу, а дальше, может быть, на следующей лекции будем анализировать. Просто хочется оставить вам что-то, над чем можно задуматься, — что-то менее алгоритмическое. Потому что тем, у кого с алгоритмами очень хорошо, сегодня, скорее всего, было приятно: это они уже знали; а тем, кому всё было ново, было тяжеловато. Поэтому давайте я чем-то умаслю конец лекции, а я немножко времени у вас за это отниму: масло же чего-то стоит, правильно?
Левая доска стирается начисто, и на ней появляется новый раздел курса: III) pathwidth through cop-robber games. Напомню, что было в treedepth, : копы могут в любой момент удалить вершину из графа и посмотреть, где теперь находится грабитель. Грабитель при этом имел бесконечную скорость, то есть, когда мы смотрим, где находится грабитель, это на самом деле компонента связности текущего графа.
В путевой ширине всё немножко меняется. Во-первых, копы могут уходить из вершины. И тут надо понимать: как только коп ушёл из вершины, преступник моментально, сразу же, может по этой вершине перемещаться. Во-вторых — и это принципиально важно — теперь копы не могут смотреть, где находится грабитель: копы не могут видеть грабителя, пока они его не поймали. (На доске оба пункта выписаны отдельными строками, причём во втором подчёркнуты и «не могут», и «видеть».) Если вот это ограничение убрать, получится древесная ширина, что забавно, — но мы с вами к этому ещё дойдём.
И что, собственно, тогда происходит? Копы всегда будут стоять в какой-то сумке. У меня есть последовательность сумок — но как это выглядит в графе? А вот есть одна часть графа и есть другая часть графа, и они пересекаются ровно вот тут. Вот эта часть графа прочёсана копами полностью, то есть грабителя тут точно нет, а копы находятся сейчас вот в этой сумке. Теперь копы говорят: ага, я хочу переориентироваться с вот этой клики на вот эту вот. Копы уходят отсюда, из этой части; в пересечении они остаются и перемещаются вот сюда.
Что в результате получается? Пересечение блокирует грабителю переход из этой части графа вот в эту. И пока вот эти копы блокируют пересечение, новые копы перемещаются вот сюда: эти копы железно стоят, но в следующий раз они могут уже перейти дальше. То есть вполне себе нормальная задача: надо прочесать весь город — сколько нужно копов, чтобы прочесать город? И тут вопрос: а когда тогда копы ловят грабителя? Ну, когда копы встали в ту же вершину, что и грабитель: как только коп встаёт в ту вершину, где грабитель, грабитель проиграл.
Значит, утверждение такое: равен минимальному числу копов в такой игре. Ну и, конечно же, минус один — вот этот неизбежный мусор. На доске это записано так:
В одну сторону это легко доказать, и эту сторону я уже доказал: по путевой декомпозиции стратегию копов построить легко. Можете проделать формальное доказательство — может, Серёжа захочет дать это вам в домашнее задание, не знаю, захочет он потом это проверять или нет.
Проблема в том, что в обратную сторону я просто не умею доказывать. Чтобы по стратегии копов построить путевую декомпозицию, нужно доказывать, что каждый коп будет стоять в вершине только в течение одного интервала времени, — а вот это я совсем формально объяснить не умею: почему копу невыгодно вернуться в предыдущую вершину, почему такая стратегия невыгодна. Поэтому вот это равенство я прямо формально не доказал. То есть вы можете говорить: «А вот он нехороший, не доказал», — и будете правы. Доказать это сейчас я не смогу, просто не умею. Но на самом деле в оптимальной стратегии копы всегда должны не возвращаться в старые вершины. (Именно поэтому примерно через сорок секунд после самого утверждения под знаком на доске появляется маленькая стрелка — собственная пометка лектора о том, что направление осталось недоказанным.)
Всё, друзья, простите, я уже на пять минут задержал: мы начали в 18:05, а сейчас 19:40. Поэтому всем спасибо. Если есть вопросы, можете задавать их сейчас, прямо под запись, можете подходить, можете писать в Телеграме — с удовольствием будем отвечать. Всё, всем спасибо, до встречи через неделю. Помните, что ДЗ надо делать. (Имеется в виду уже выданное домашнее задание по древесной глубине, объявленное в самом начале этой же лекции; нового задания здесь не появляется.)