Миноры графов и характеризация семейств запрещёнными минорами

Друзья, всем добрый вечер. Мы продолжаем наш курс; сегодня у нас, кажется, шестая лекция. Давайте поговорим про очень широкую тему, которая сама по себе заслуживает отдельного курса по структурной теории графов. Конечно, мы с вами не планировали читать именно курс по структурной теории графов, а скорее смотреть на разные параметры и на то, как они между собой взаимосвязаны: в структурной теории графов можно рассказывать про совершенно разное. Так что сегодня мы поговорим про миноры — это я и пишу заголовком на доске.

Где вы могли слышать про миноры графов, в какой из теорем? Да, обычная характеризация планарности. А как эта теорема называется? Вроде бы она называется теоремой Понтрягина — Куратовского. Но в Википедии она вообще-то называется теоремой Вагнера, и я не знаю почему; надо, кстати, с этим как-то разобраться. Я только пока шёл сюда на лекцию, понял, что она всегда называлась по-другому. Ладно, это не суть — результат мы с вами напишем и вспомним, что там про планарный граф.

Давайте дадим определение минора. Определение: граф HH — обычный совершенно неориентированный граф — является минором GG, если HH можно получить из GG с помощью двух операций: удаления вершин и рёбер и стягивания рёбер. Удаление — это просто отношение «быть подграфом», здесь никакого секрета нет. А вот стягивание рёбер — это операция, когда у меня были вершинки uu и vv, у них могли быть общие соседи, а могли быть и не общие, и стягивание ребра uvuv превращает это ребро в одну вершину. Множество соседей новой вершины становится объединением множеств соседей исходных вершин; никаких мультирёбер при этом не появляется, потому что графы у нас простые. Рядом с определением я рисую картинку: слева треугольник на a,u,va, u, v, где у uu есть ещё одно висячее ребро, а у vv — два, а справа одна вершина, из которой выходят все пять этих рёбер.

Итак, то, что мы все с вами могли встречать: граф GG планарный тогда и только тогда, когда K5K_5 не минор GG и K3,3K_{3,3} не минор GG. Чьего она имени, я писать не буду, потому что сам запутался: я всегда слышал «Понтрягина — Куратовского», а пока готовился, в английской Википедии это была почему-то теорема Вагнера — хотя Куратовский тоже западный учёный. В общем, непонятно, чья она точно. К этой же строке я дописываю на доске короткую форму того же утверждения:   ⟺  {K5,K3,3}-free\iff \{K_5, K_{3,3}\}\text{-free}.

Можно убедиться, что K5K_5 — не планарный граф. А про K3,3K_{3,3} я недавно видел фильм, и там, оказывается, такую задачку дают школьникам: вам дали три домика здесь и три домика тут, и надо их соединить. Я удивился: ничего себе, почему мне в школе такого не давали! И гениальным решением там считалось взять одно ребро и провести его сверху листочка. Не знаю, почему это считалось гениальным — ну да, вложить граф в поверхность большего рода, хорошо.

— Мне казалось, что одна теорема — что это не минор, а другая — что нет K5K_5 как подразбиения.

— А, вот так. Спасибо, Лёша поправил. Соответственно, вот в этой формулировке это теорема Вагнера. Нет подразбиения K5K_5 как подграфа — да, я понимаю.

Когда мы говорим о подразбиениях, мы, по сути, говорим о минорах. Если мы возьмём, например, треугольник и просто добавим вершины на рёбра — подразбиение ребра, то есть мы добавляем на ребро вершинку, — то это порождает граф, для которого исходный граф является минором получившегося. Справа от картинки со стягиванием я рисую на доске именно это: треугольник и тот же треугольник с вершиной, посаженной на каждое ребро. Подробно обсуждать, почему так, мы не будем. Мы с вами не стремимся изучать сейчас планарные графы и вложения графов в плоскость или в поверхности большего рода; мы просто цепляемся за то, что уже знаем, — за то, что вы, наверное, уже видели и слышали.

Хорошо, давайте приведём ещё определения. Видите, в этом утверждении — K5K_5 не минор, K3,3K_{3,3} не минор — мы явно описываем целое семейство графов каким-то конечным набором графов. Определение: для конечного множества графов H\mathcal{H} — давайте я нарисую H\mathcal{H} красивое — граф GG является H\mathcal{H}-minor-free, если GG не содержит в качестве минора ни одного из элементов H\mathcal{H}. На доске это записано точнее: для любого H∈HH \in \mathcal{H} граф GG не содержит HH как минор. Кстати, на русский это довольно сложно переводить, короткого слова нет, — попробуйте перевести это на русский так, чтобы было так же классно; непонятно, получится ли.

В частности, планарные графы — это {K5,K3,3}\{K_5, K_{3,3}\}-free графы. Супер: оказывается, целое огромное семейство графов можно записать всего лишь двумя маленькими графами.

Давайте с вами попробуем попридумывать описания каких-нибудь семейств. Записанную панель доски я поднимаю наверх и опускаю чистую — ничего не стираю, определение и теорема остаются на виду. Пишу заголовок «Примеры». Давайте, например, опишем ациклический граф: какого минора у него не должно быть?

— (ответ из аудитории неразборчив)

— Да, всё так. Ациклический — это то же самое, что не иметь C3C_3 в качестве минора: что такое граф, не являющийся ациклическим? Он обязательно содержит цикл, а любой цикл можно стянуть до треугольника. Так и запишем: ациклический   ⟺  C3\iff C_3-free. Отлично — на самом деле мы с вами описали леса, то есть все графы-леса, они ациклические. К ориентированным графам это не относится ни в коем случае: миноры у нас неориентированный концепт.

Какие ещё у нас есть семейства? Давайте попробуем описать просто цикл, граф CnC_n: можем ли мы в виде минора описать то, что граф является циклом? Свойство простое, но непонятно, как это сделать, потому что связность мы гарантировать не можем. Наверное, нет — и мы с вами объясним, почему нет; постараемся объяснить, либо поймём, что я здесь вам что-то недоговариваю. На доске я ставлю рядом знак вопроса и приписываю «наверное, нет, из-за связности», а правее рисую восьмиугольник, на который указывает стрелка.

Давайте придумаем что-нибудь поестественнее — а у меня что-то нет ничего поестественнее. Тогда возьмём не набор циклов, а немножко усложним предыдущий граф и скажем, что у нас linear forest, так называемый: граф, у которого любая компонента связности — это путь. Понятно, что связность мы тут уже никак не отслеживаем, потому что в минорах мы не можем ничего потребовать от связности. Что нужно запретить? Понятно, что C3C_3 — чтобы граф был ациклическим; кажется, это нам нужно. И если мы запретим ещё вот такое — давайте я нарисую рисунки, — то есть {C3,K1,3}\{C_3, K_{1,3}\}-free, то это нам и нужно. На доске в фигурных скобках нарисованы сами пиктограммы: треугольник и клешня K1,3K_{1,3}; рядом — набросок линейного леса из путей на 3, 4 и 2 вершинах и одной изолированной вершины.

Кстати, тут можно подумать, почему набор циклов сделать не получится. Я объясню почему: на самом деле, если мы возьмём подграф такого графа, он не будет таким же. То есть если бы я взял, например, cycle forest, то есть независимые циклы, то это просто вообще дурацкое семейство: если я буду брать его подграфы, у меня это семейство не замкнуто, правильно? Но мы к этому сейчас немножко придём.

Давайте поймём, почему linear forest описывается именно так, — интересно же доказать. На самом деле мы с вами хотим просто доказать…

— Там написано, что нет вершины степени 3 и больше, правда?

— Не совсем так. С точки зрения K1,3K_{1,3} так будет, но это не всегда верно: для вершин степени 3 это так. Смотрите, например, если мы возьмём просто K1,dK_{1,d}-free — вот тут dd вершин, на доске под листьями звезды стоит фигурная скобка с подписью dd, — то степень в графе всё равно может быть очень маленькой. Какой граф не является K1,dK_{1,d}-free? Например, вот такой — ой, извините, это получился просто путь, давайте нарисуем вот так: это гребёнка, горизонтальный путь-хребет, из каждой вершины которого вниз свисает по одному висячему ребру.

Угу, да-да-да. Да, для K1,3K_{1,3}-free действительно эквивалентно тому же, что иметь вершину степени 3 (оговорка лектора: имеется в виду отсутствие вершины степени ≥3\ge 3; дальше он сам себя поправляет), потому что если вершины степени 3 нету, то любая компонента связности — это либо путь, либо цикл. А циклы у нас запрещены. Вот, да, всё-всё правильно, спасибо. То есть это просто конкретный случай, именно с K1,3K_{1,3}.

А с K1,dK_{1,d}-free, конечно, у меня могут быть графы степени 3, в которых есть минор K1,dK_{1,d}, — просто потому, что я стягиваю весь этот путь, весь хребет гребёнки. Ну, можно попридумывать и разные другие примеры.

Давайте мы немножечко вернёмся к прошлой лекции: мы на самом деле не успели обработать один интересный момент, который нам будет важен потом. Мы с вами определяли путевую ширину, но не обсудили, а как выглядят графы с путевой шириной 1. Мы говорили, что, наверное, хотим, чтобы это был путь, но это не совсем так. У кого есть предположение, как это выглядит? Я напомню, что это графы, в которых любая сумка в путевом разложении может иметь размер не больше чем 2: я могу иметь сумку, добавить ребро между вершинами и забыть какую-то вершину из сумки. Есть предположение, как выглядят графы pathwidth 1? Слева на доске я пишу Pathwidth=1\mathrm{Pathwidth} = 1.

Понятно, что у пути pathwidth 1, потому что в сумках должны быть последовательные рёбра. Но это всего лишь подмножество таких графов. Тут важно следующее: у меня каждая вершина входит ровно в две сумки, кроме крайних. И фишка в том, что я могу бесплатно создавать вершины, которые входят ровно в одну сумку, — могу создавать вот такую штуку. Писать это целиком бессмысленно, потому что картинка дальше продлевается на листе, но это не важно. Это называется дерево-гусеница, caterpillar tree: горизонтальный хребет, из каждой вершины которого свисают висячие ножки, а поверх хребта нарисованы перекрывающиеся эллипсы-сумки, ii-я из которых накрывает {vi,vi+1}\{v_i, v_{i+1}\}, то есть ∣Xi∣≤2|X_i| \le 2.

Вы можете проверить, что у таких графов pathwidth 1, потому что это делается так: вы привели вершину, сначала все эти вершины-ножки поназакидывали в сумки, потом взяли следующую вершину хребта и забыли вот эту вершину, опять поназакидывали все ножки, торчащие из этой вершины, и взяли опять следующую.

И забавно, что у pathwidth 1 очень похожее семейство запрещённых подграфов (оговорка лектора: речь о запрещённых минорах — класс замкнут относительно взятия миноров, и как условие на подграфы эта пара не работает). Конечно же, это цикл, потому что у меня не может быть цикла в графе путевой ширины 1; возможно, дадим вам это доказать в домашнем задании. И вот такого графа — я показываю на рисунок рядом: это центральная вершина с тремя лучами длины 2, то есть подразбитая клешня на семи вершинах, T2T_2. На доске это записано так: Pathwidth=1  ⟺  {C3,T2}-free\mathrm{Pathwidth} = 1 \iff \{C_3, T_2\}\text{-free}, причём в фигурных скобках стоят сами пиктограммы — треугольник и T2T_2.

Да, смотрите: оказывается, что придумывать эти семейства даже прикольно. Я надеюсь, не только мне это было прикольно делать. И спрашивается, а что это нам вообще даёт глобально? Очень сложно сказать, что это даёт алгоритмически. Некоторый результат мы, конечно, с вами выведем, но всё-таки какое-то понимание того, как могут выглядеть графы и как они между собой связаны, мы с вами увидим. А потом мы с вами плавненько перейдём к древесной ширине, потому что она отсюда очень хорошо получается; скажем так, это одна из сторон, с которой можно прийти к древесной ширине.

Но смотрите, почему у нас не получилось сделать циклы CnC_n? Понятно, следующее здесь было. Давайте такое замечание: на самом деле у меня H\mathcal{H}-minor-free семейства замкнуты относительно взятия миноров.

Теорема Робертсона — Сеймура и запрещённые миноры для путевой ширины

Понятно, что если у меня был какой-то граф и в нём не было какого-то минора, то, взяв минор этого графа, такого минора я тоже не получу, — он не может появиться. Поэтому, в частности, цикл CnC_n нам и не подходил: мы не можем брать подграф цикла и всегда получать цикл.

Одно из главнейших достижений структурной теории графов — это теорема Робертсона — Сеймура, касающаяся H-minor-free\mathcal{H}\text{-minor-free} графов. Пусть у меня есть некоторое семейство графов G\mathcal{G} — бесконечное семейство графов, замкнутое относительно взятия миноров. Тогда оказывается… Сейчас, секундочку, что я хочу сказать? Я хочу сказать, что G\mathcal{G} характеризуется… Давайте так: утверждаю, что найдётся некоторое конечное семейство H\mathcal{H}, что G\mathcal{G} — это в точности H-minor-free\mathcal{H}\text{-minor-free}. На доске это отношение записано тройной чертой: G≡H-minor-free\mathcal{G} \equiv \mathcal{H}\text{-minor-free}. Но это, конечно, не совсем справедливое утверждение, это не то, что я вам хочу рассказать.

То есть смотрите, что я бы хотел сказать: любое бесконечное семейство графов, замкнутое относительно взятия миноров, можно охарактеризовать H-minor-free\mathcal{H}\text{-minor-free} графами. Но что-то я сейчас в этом утверждении не уверен, где-то я его неправильно написал. Это моё желание того, что я хочу сказать. Почему это моё желание? Потому что я вам здесь показал несколько примеров семейств, замкнутых относительно взятия миноров, и нам получилось построить, что они некоторые H-minor-free\mathcal{H}\text{-minor-free}. Но это не то, что мы хотим: на самом деле это не теорема Робертсона — Сеймура, это то, как я хотел бы, чтобы она выглядела, но не всё так просто.

Давайте поймём, что у нас здесь происходит на самом деле. Посылка-то нормальная, а результат следующий: тогда в G\mathcal{G} конечное… Скажите, а видно вот этот мел вообще? Почти не видно, я понял. Ну да, надо вытирать заранее, короче. Написанный вывод здесь стирается, и на его месте появляется другой: тогда в G\mathcal{G} конечное количество минимальных элементов. Ну а что такое минимальных элементов? По взятию миноров — так на доске и приписано в скобках: «(по взятию миноров)».

Вот это уже точная формулировка теоремы, но она и то присутствует там как бы не в одном виде: вводятся разные формулировки. Например, такая: в любой бесконечной последовательности графов найдутся два графа, один из которых является минором другого. Она ещё и так формулируется. Но мы не хотим с вами в это сильно-сильно углубляться, мы хотим скорее просто понять, про что это вообще. Доски здесь сдвигаются, и ниже открывается записанное раньше определение: для конечного множества графов H\mathcal{H} граф GG является H-minor-free\mathcal{H}\text{-minor-free}, если для любого H∈HH \in \mathcal{H} он не содержит HH как минор, — именно на это определение всё дальнейшее и опирается.

Давайте поймём, почему это то, что надо. Мне всегда это давалось с трудом, но сейчас мы с вами эту работу проведём. Попробуйте сейчас понять сами, почему это то, что надо, а я пока сотру. Нижняя доска опускается и вытирается целиком, от прежней записи остаётся только заголовок «Миноры».

— (реплика из аудитории неразборчива)

То есть, Костя, ты утверждаешь, что это прямо эквивалентно тому, что я написал сначала? В одну сторону — да, согласен. Доказательство теоремы Робертсона — Сеймура мы, конечно же, разбирать не будем: его можно прочитать в серии из двадцати трёх работ Робертсона и Сеймура, а где именно там она доказывается, я не знаю. Мы благодарны людям за то, что они нам сказали про эту теорему и прочитали эти работы.

Давайте посмотрим, чего это нам даёт. Я бы хотел охарактеризовать любое семейство как H-minor-free\mathcal{H}\text{-minor-free}, и сейчас немножко подумаю, как бы нам это сделать. Я говорю, что у меня есть такое бесконечное семейство, в нём есть какие-то минимумы, и я знаю, что всё моё семейство выглядит вот так: вот это мои миноры, которые могут быть. На доске это три перекрывающихся конуса, раскрытых вниз, с меловой точкой в каждой вершине и штриховкой внутри; вершины подписаны M1,M2,M3M_1, M_2, M_3, а объединение конусов — это и есть G\mathcal{G}. Словами этот рисунок не описывается, лектор только показывает на него рукой, и к концу сюжета он будет стёрт.

Давайте напишем, что эта теорема гласит, и просто распишем по шагам, потому что без шагов как-то тяжело: как нам перейти от того, что кто-то является чьим-то минором. Что мы с вами нашли? Давайте я введу какую-нибудь другую букву, например просто букву MM. Теорема гласит, что найдутся M1,M2,…,Mt∈GM_1, M_2, \dots, M_t \in \mathcal{G} для некоторого конечного tt. И я теперь знаю, что для любого графа… Утверждаю даже более сложный факт — как раз доска высыхает, — что GG принадлежит нашему семейству тогда и только тогда, когда найдётся ii, что MiM_i является минором GG. На доске это вторая строка: ∀G: G∈G  ⟺  ∃i: Mi⪯G\forall G:\ G \in \mathcal{G} \iff \exists i:\ M_i \preceq G. Скажите, в это верится или нет? Мне кажется, должно быть правдой. Утверждаю, что мы это на самом деле получаем из нашего результата.

Что ещё раз? Для большого GG?

— В этом смысле таким графом всегда будет просто граф, состоящий из одной вершины, потому что из любого графа можно получить…

Да, вот будет, да. Нет, но не обязательно мы его включали в G\mathcal{G}, правильно? То есть мы не обязательно включаем этот граф из одной вершины вот туда. Получается, что всё как-то не очень чистенько. Например, если мы возьмём G\mathcal{G} множеством всех планарных графов, тогда получится ерунда, потому что граф из одной вершины действительно является планарным. При этом он является минором всех графов вот там — относительно взятия миноров он лежит ниже всех.

— Может быть… То есть, насколько я понял, если минор меньше, чем исходный граф, то это означает, что всё что угодно меньше.

Согласен, теорема в том виде, в котором мы её написали… Здесь как бы либо надо говорить максимальных элементов, либо порядок. Сейчас, давайте посмотрим, что-то я где-то косякнул. Извините, пожалуйста. Странно, у меня всё сходилось при подготовке, потому что это ровно то, что я выписывал. Кто меня обманул-то по ходу дела?

Ну да, всё правильно, minor closed — это то, что… of minimal elements in S. А, ну понятно: я теорему переврал, короче, полностью. Она так и должна была выглядеть, как нам нужно. Но сейчас нет, это мне уже forbidden minor characterization говорит. Да, мне, конечно, не этого хотелось очень сильно: мне как бы сразу предлагают — напиши-ка forbidden minor characterization. То есть исходная формулировка моя, получается, была правильной в результате. Я думаю, что фишка скорее в том, что порядок…

— А можно наоборот, сказать, что…

Да, да, я просто не понял, я при чём. Я ведь списал в точности формулировку откуда-то — извините, я списал просто её как-то криво. Речь-то о том, что как раз вне G\mathcal{G} конечное множество минимальных элементов, и как раз тогда это и есть то самое запрещённое семейство. Если мы возьмём дополнение всех графов… Ну давайте просто запишем исходную формулировку, которая была; простите, пожалуйста. Строка про конечное количество минимальных элементов в G\mathcal{G} стирается, и на её место возвращается то, что было написано вначале.

Видите, что мы с вами на самом деле пропустили? Это minor closed family — вот здесь мы не разобрались, что это такое, поэтому, конечно, и по ходу дела разбирались. Итак: тогда найдётся некоторое H\mathcal{H} — конечное семейство, — что G\mathcal{G} в точности совпадает с H-minor-free\mathcal{H}\text{-minor-free}, то есть G≡H-minor-free\mathcal{G} \equiv \mathcal{H}\text{-minor-free}. (В посылке на доске стоит «бесконечное семейство графов, замкнутое относительно взятия миноров»; бесконечность здесь, строго говоря, лишняя — теореме достаточно замкнутости относительно взятия миноров.) Хорошо, давайте тогда забудем вот эти все истории: я хотел как-то из этого интересно всё вывести — не вывел, извините. Мы с вами сначала построили такие семейства и во всём убедились.

Теперь что хочется сказать? Можно заметить следующее — ну как заметить, не заметить, а узнать: проверить, является ли HH минором заданного графа, можно за время примерно такое — за какое-то большое время от HH, умноженное на число вершин графа; на доске записано f(H)⋅n2f(H)\cdot n^2. Асимптотика будет такая, она будет зависеть от HH, но если бы HH было неограниченного размера, если бы здесь не было функции от HH, то за полином мы ничего бы определять не смогли, потому что мы решили бы тогда P=NP\mathrm{P} = \mathrm{NP}. Например, если мы поставим HH просто циклом CnC_n, который совпадает с GG по количеству вершин, то мы смогли бы просто проверять граф на гамильтоновость: тут CnC_n, а тут nn-вершинный граф.

И отсюда для многих наших структурных параметров оказывается, что вычислять их можно за какое-то адекватное время. Правда, мы сейчас только поймём, что значит «вычислять за какое-то адекватное время». Рассмотрим, например, проверку того, что путевая ширина некоторого графа меньше, чем kk; на доске это подчёркнутый заголовок «Проверка pw(G)<kpw(G) < k». Как это можно сделать? Пусть Gk\mathcal{G}_k — это семейство всех графов, у которых pw(G)<kpw(G) < k. Мел сегодня ещё и неудобный, ужас просто. Вам остаётся убедиться только, что это семейство действительно замкнуто по взятию миноров.

Проще всего рассмотреть, например, путевую декомпозицию и что-нибудь там стянуть. Кажется, что проблем никаких не должно возникнуть, потому что я знаю: раз у меня есть ребро между двумя вершинами, они встречаются где-то в одной сумке. Давайте вспомним, что такое путевая декомпозиция на самом деле: это набор каких-то отрезков. Если у меня было ребро между двумя вершинами, значит, их два отрезка пересекались, поэтому я могу взять и заменить ребро uvuv просто на вот этот большой отрезок. На доске это нарисовано квадратными скобками, внутри которых стоит сумка-овал со стрелкой вниз. Понятно, что это будет всё ещё путевой декомпозицией исходного графа.

При этом понятно, что ширина у этой путевой декомпозиции только уменьшилась, потому что я однозначно уменьшил количество вложенности: если вот здесь вот была вложенность 22, то она теперь стала 11. То есть я получаю граф с меньшей путевой шириной. И отсюда что следует? Что найдётся некоторое семейство Hk\mathcal{H}_k, что наше Gk\mathcal{G}_k — это в точности Hk-minor-free\mathcal{H}_k\text{-minor-free}, то есть Gk≡Hk-minor-free\mathcal{G}_k \equiv \mathcal{H}_k\text{-minor-free}. Ну и всё.

Что мы знаем про это семейство из этой теоремы? Что оно задано только параметром kk, правильно? То есть мы знаем, что размер Hk\mathcal{H}_k ограничен некоторой функцией g(k)g(k) — на доске это записано через мощность: ∣Hk∣⩽g(k)|\mathcal{H}_k| \leqslant g(k). Причём что это за функция, мы можем только гадать. То есть количество всех графов внутри ограничено некоторой функцией, потому что семейство Hk\mathcal{H}_k в принципе конечного размера и зависит только от выбора kk.

Свойства графов без запрещённого минора: вырожденность, число Хадвигера, путевая ширина планарных графов

Отсюда проверить, что граф имеет путевую ширину не больше, чем kk, можно просто проверяя, что каждый граф из этого семейства не является минором нашего графа. Вся выкладка целиком выглядит так. Есть теорема о том, что проверить, является ли HH минором GG, можно за f(H)⋅n2f(H)\cdot n^2. Пусть Gk={ G:pw(G)<k }\mathcal{G}_k = \{\,G : \mathrm{pw}(G) < k\,\} — семейство всех графов путевой ширины меньше kk; оно замкнуто относительно взятия миноров, поэтому существует конечное семейство Hk\mathcal{H}_k, для которого Gk\mathcal{G}_k — это в точности Hk\mathcal{H}_k-minor-free графы, причём ∣Hk∣⩽g(k)|\mathcal{H}_k| \leqslant g(k). Следовательно, существует алгоритм, который за h(k)⋅n2h(k)\cdot n^2 проверяет pw(G)<k\mathrm{pw}(G) < k. Таким образом, мы доказали, что путевую ширину можно вычислять за fpt-время — как-то.

Фишка в том, что совершенно непонятно, как это реализовать: что это за семейство такое Hk\mathcal{H}_k? Всё, что мы доказали, — это что существует некоторый алгоритм, работающий за h(k)⋅n2h(k)\cdot n^2, потому что я для каждого запрещённого минора вызываю проверку минорности. А что такое h(k)h(k)? Это какая-то функция, склеенная из ff и gg — из f(H)f(H) в теореме о проверке минорности и из оценки g(k)g(k) на размер семейства. К сожалению, для нас как для имплементаторов алгоритмов это не очень имеет много смысла: для каждого kk это своё семейство, и явной конструкции у него нет вообще никакой. Более того, путевую декомпозицию это нам тоже не даёт. Но тем не менее: вычисление путевой ширины можно делать за fpt-время, хотя и с очень страшной, страшной константой.

Вопросы какие-то, может, появились, друзья? Да, я зафейлился с теоремой Робертсона — Сеймура: я думал, что получится вывести что-то умное, но мы сразу записали её в самой удобной форме. Ну и пусть так и будет, ничего страшного: раз зафейлился, так зафейлился. Отсюда можно понять, что многие семейства графов оказываются HH-minor-free, то есть образуют minor closed family. Например, граф из одной вершины обязан принадлежать вашему семейству обязательно — как заметил Саша.

А давайте мы вот это обзовём правильно. Вот это называется non-uniform FPT. Почему это так называется? Потому что для каждого значения параметра kk алгоритм свой. Но при этом, если мы зафиксируем kk, с ростом размера графа время работы всё ещё растёт полиномиально. Это интересный вывод, который отсюда есть; напрямую к нашим параметрам графа он не относится, но какое-то отношение всё-таки имеет.

Давайте поговорим о каких-то общих свойствах HH-минор-фри графов. Что стоит от них ожидать? Во-первых, у них маленькая степень — точнее, маленькая вырожденность, и записана на доске именно вырожденность. Теорема: KhK_h-минор-фри граф является O ⁣(hlog⁡h)O\!\left(h\sqrt{\log h}\right)-вырожденным, то есть если в графе нельзя выделить клику на hh вершинах — точнее, если KhK_h не является минором этого графа, — то он hlog⁡hh\sqrt{\log h}-вырожденный. На доске символ O(⋅)O(\cdot) опущен, но константа в этой оценке, разумеется, есть.

Какая здесь интуиция? Если граф очень плотный, он не может быть KhK_h-минор-фри. Например, если минимальная степень в графе является чем-то вроде n1/10n^{1/10}, то, конечно же, вы не найдёте какое-то константное hh, при котором всё так работает. Понятно, что если наши графы HH-минор-фри для какого-то фиксированного конечного семейства, то они будут разреженными. Давайте тут напишем: следовательно, разрежены.

Вот скажите, а понятно, почему мне достаточно писать всё только для KhK_h-минор-фри графов? Смотрите, на самом деле история такая. Если я взял некоторое семейство графов H\mathcal{H}, но оно конечное и в нём есть сколько-то графов — пусть H={H1,H2,…,Ht}\mathcal{H} = \{H_1, H_2, \dots, H_t\}, — то возьму hh просто как максимум числа вершин по всем HiH_i, то есть h=max⁡i∣V(Hi)∣h = \max_i |V(H_i)|. А отсюда что будет следовать? Что на самом деле H\mathcal{H}-минор-фри графы будут вкладываться полностью в KhK_h-минор-фри графы: H-minor-free⊆Kh-minor-free\mathcal{H}\text{-minor-free} \subseteq K_h\text{-minor-free}. Правильно, нигде я ничего не перепутал? Смотрите, я говорю: если граф не содержит HiH_i в качестве минора, то уж он точно не содержит его надграф в качестве минора. Я беру самый большой граф и превращаю его в клику — то есть это расширяет семи…

— (реплика из аудитории неразборчива)

— Что? Сейчас, да, наверное, тут надо выбрать самый маленький. Наверное, мне нужно выбрать… Нет, такого вроде быть не должно, у нас же наоборот. Сейчас, сейчас. Да, вот: когда мы запрещаем какие-то подграфы, мы запретили подграф побольше и получили семейство пошире в результате. То есть у меня HiH_i — это минор KhK_h для любого ii: ∀i: Hi⪯Kh\forall i:\ H_i \preceq K_h. И отсюда я знаю, что если граф HiH_i-minor-free, то он автоматически KhK_h-minor-free. Если у графа из этого семейства нет в качестве минора HiH_i-того, то автоматически нет в качестве минора и KhK_h-того.

С минорами такая история, что про них надо помнить, что они есть, но они, к сожалению, мозгодробительные. Мы должны помнить, что миноры стоят где-то у истоков теории графов, и хорошо бы про них сделать какую-то серию лекций, но в данном курсе мы в них погружаться никак не будем. То есть нам нужны вот такие базовые знания: если мы имеем такое семейство графов, то вот так получаем.

Например, с путевой шириной эта штука выводится гораздо более очевидно. Можно заметить такое утверждение: в графе путевой ширины не больше kk есть вершина степени не больше, чем kk. Понятно, как это доказать? Если у меня путевая ширина не больше, чем kk, почему есть вершина степени не больше, чем kk? Давайте возьмём путевую декомпозицию — её удобно представлять отрезочками — и посмотрим на первую вершинку, которая пропадает. Я взял nice path decomposition и знаю, что есть какой-то момент: вершинка vv была вот в этой сумке, а вот в этой сумке её уже нет.

Получается, что вот эта сумка содержит всех соседей вершины vv: справа они находиться больше не могут, а слева соседи только появляются. То есть вот эта сумка — надмножество вот этой, вершины могли только появляться. Отсюда эта клика будет содержать всех соседей вершины vv. Нам нужно было брать не отрезок с самым левым левым концом, а отрезок с самым левым правым концом — и тогда всё получится. Если мы возьмём отрезок Iv=[ℓv,rv)I_v = [\ell_v, r_v) с самым левым правым концом, то есть с rv=min⁡urur_v = \min_u r_u, то в этом месте обязаны быть все его соседи. Как раз мы знаем, что не больше, чем kk отрезков будет пересечено, и всё получится: N(v)⊆XrvN(v) \subseteq X_{r_v}, а ∣Xrv∣⩽k+1|X_{r_v}| \leqslant k+1, откуда deg⁡v⩽k\deg v \leqslant k.

Что вообще мы из миноров можем вынести ещё кроме этого? Есть всякие замечательные свойства — например, как хроматическое число графа связано с минорами. Всё-таки у нас сегодня речь о параметрах, давайте введём какие-нибудь параметры. Давайте введём число Хадвигера. Это наибольшее hh такое, что KhK_h является минором графа GG: h(G)=max⁡{ h:Kh⪯G }h(G) = \max\{\,h : K_h \preceq G\,\}. Не надо там нигде плюс один, всё нормально.

Давайте уж и актуальные темы озвучивать. Была одна гипотеза, которая связана с числом Хадвигера, — она называется, собственно, гипотезой Хадвигера. Она гласит — по крайней мере гласила — следующее: миноры являются одним из препятствий для раскраски графов. То есть если у меня нет очень большого минора, я могу раскрасить свой граф в маленькое количество цветов; на доске это записано как χ(G)⩽h(G)\chi(G) \leqslant h(G). Например, на планарных графах можно увидеть, что это доказывает теорему о четырёх красках: для планарных графов наибольшее hh — это 4, и гипотеза работает, то есть из гипотезы следует теорема о четырёх красках.

Её проверили вроде бы для всех значений числа Хадвигера от единички до шести, и недавно OpenAI её развалил — то есть это неправда, так не работает. [Последнее утверждение приводится по лекции; на момент подготовки конспекта гипотеза Хадвигера считается открытой для h⩾7h \geqslant 7 — для h⩽6h \leqslant 6 она доказана, — так что ссылку на опровержение стоит проверить отдельно.] Но для маленьких значений гипотеза работает: если вы знаете, что у вас наибольший кликовый минор — это 6, то значит, ваш граф раскрашивается в 6 цветов.

Конечно, в обратную сторону это никак не связано, потому что я из любого графа со сколь угодно большим минором могу сделать двураскрашиваемый граф. Если вы возьмёте треугольник и просто налепите по вершинке на каждое ребро, то понятно, что при подразбиении ребра все миноры у графа сохраняются, только новые появляются. Поэтому число Хадвигера не может уменьшиться, только увеличиться в этом случае. А этот граф, конечно, раскрашивается в два цвета, потому что в нём нет нечётных циклов. Нарисованный пример — это подразбиение K3K_3, то есть C6C_6, с h⩾3h \geqslant 3 и χ=2\chi = 2; чтобы минор был действительно сколь угодно большим, надо подразбивать KnK_n — подразбиение KnK_n двудольно и имеет h⩾nh \geqslant n.

Но можно заметить, что из вырожденности какие-то оценки сверху на число цветов, в которые граф раскрашивается, у нас всё-таки есть. Вырожденность — это очень простой аргумент: я просто беру вершинку минимальной степени и крашу её; точнее, делается это наоборот — я вершинки добавляю по очереди и крашу вершинку в свободный цвет. Каждый раз, когда я добавляю вершинку, у неё не больше, чем сколько-то соседей.

К чему я хотел переходить сегодня дальше? Вспомнил: одна из самых интересных, наверное, теорем про планарные графы гласит следующее — давайте запишем эту теорему. Путевая ширина планарного графа есть O(n)O(\sqrt{n}). На этом строится довольно много всяких эффективных алгоритмов на планарных графах: у нас действительно есть маленький параметр, и у нас есть очень приятные динамики по путевой декомпозиции. Но давайте я расскажу, на чём это строится. Поскольку у нас сегодня лекция такая, что мы скорее собираем какие-то определения, которые нам важно знать, но которые при этом алгоритмически сильно помогают, давайте мы введём ещё какие-то определения. А вот это определение конкретно помогает для вычисления путевой ширины — это сбалансированные сепараторы.

Сбалансированные разделители: от планарного сепаратора к древесной глубине

Попробуем сразу что-нибудь из этого вывести — посмотрим, насколько это трудно. Честно говоря, я не успел проделать этот вывод сам, поэтому давайте попробуем вместе: получится или нет. А что такое определение? Множество S⊆VS \subseteq V называется сбалансированным разделителем, если в G−SG - S любая компонента связности имеет размер не больше, чем 23n\tfrac{2}{3}n. Здесь nn — число вершин в исходном графе. (Раздел на доске озаглавлен по-английски — Balanced Separators, — а сам предикат сокращён до bal. sep.; доска даёт определение в виде «S⊆VS \subseteq V наз-ся bal. sep., если в G−SG-S любая к.с. имеет размер ⩽23n\leqslant \tfrac{2}{3}n». Оговорка «не знаю, как это записать» — живое отступление ровно про эту строчку.)

О чём здесь речь: весь граф как бы делится пополам. Есть небольшое множество SS, и есть оставшиеся множества — в лучшем случае их будет два, но их может быть и больше, — и каждое из них меньше, чем 23n\tfrac{2}{3}n. То есть я знаю, что среди них не будет одного большого и одного маленького: в худшем случае одно будет в два раза больше другого. Размер самого SS здесь никак не учитывается, но обычно ∣S∣|S| сильно меньше nn. Конкретно в планарных графах он равен корню из nn. (На доске рядом с определением нарисована картинка: два эллипса, AA слева и BB справа, а между ними узкая вертикальная «линза» с пунктиром внутри, подписанная SS.)

Теорема о планарном сепараторе — звучит она так. В некоторой формулировке, то есть с деталями про константы: в планарном графе есть сбалансированный разделитель размера O(n)O(\sqrt{n}). Это было доказано когда-то ещё раньше путевой ширины, и на самом деле всё очень сильно взаимосвязано: путевая ширина, конечно же, даёт мне небольшие сбалансированные сепараторы. (Этот блок доска выделяет английским подчёркнутым заголовком Planar Separator Theorem — вслух он никогда не произносится; первое слово лектор пишет мелом как Planer, это его описка, а не ошибка расшифровки.)

Например, для деревьев такой сбалансированный сепаратор у нас тоже есть — это центроид, то есть вершина, удаление которой бьёт граф на части, размер каждой из которых не больше n/2n/2. И в частности, из той теоремы про путевую ширину планарного графа следует вот это: можно просто взять где-нибудь посередине сумку и её обрезать, тогда слева и справа будет примерно по половине — надо только правильно подобрать сумку.

Что я хотел попробовать — это вывести из этой теоремы вот ту. То есть если у меня есть сбалансированный сепаратор, то хочется отсюда сразу получить небольшую путевую ширину. Но, кажется, это совершенно нетривиально, потому что непонятно, чем мне помогает то, что здесь просто маленькие половинки. Я не вижу, как это сделать тривиально, хотя при подготовке было написано, что да, вот это мы имеем, и отсюда легко понять, что путевая ширина тоже ограничена. Честно говоря, я не понимаю, как это понять быстро. Давай, как?

— Смотри, мы взяли, допустим, левую половину… по индукции… Ну, её ширина — O(n)O(\sqrt{n}) умножить на две трети. Дальше мы просто взяли и во все сумки добавили вот этот наш сепаратор глобальный…

— (реплика из аудитории неразборчива)

— Да. Да. Угу. Ну давайте проделаем, потому что я пока не понимаю, где сойдётся. Спасибо, да, я понял, кажется, где можно выиграть за счёт двух третьих: там, видимо, сумма арифметической прогрессии должна получиться. [Так в записи: прогрессия здесь геометрическая, со знаменателем 2/3\sqrt{2/3}.] Хорошо, давайте, если верится, то проделаем. Я просто что-то сегодня, видите, с полуоборота не заводится — но давайте это проделаем, потому что это интересно.

Сейчас мы докажем более интересный факт. А как доказывается сам планарный сепаратор, я, честно сказать, не знаю. И есть даже вопросы, а как вообще искать такие сбалансированные сепараторы, — но это отдельная, непростая история.

— (реплика из аудитории неразборчива — речь о том, что в планарном графе сепаратор ищется за линейное время)

— Ну да, в планарных графах много чего хорошо делается. Но вообще их можно искать и в общих графах тоже, с какой-то точностью приближения.

Хорошо, давайте попробуем вывести из теоремы о планарном сепараторе оценку на путевую ширину. Что предлагает нам Серёжа? Серёжа предлагает следующее. Давайте возьмём наш сепаратор; мы знаем, что он размера O(n)O(\sqrt{n}), но лучше напишем константу явно, потому что у нас константы будут меняться: ∣S∣⩽Cn|S| \leqslant C\sqrt{n}. И давайте рекурсивно построим путевую декомпозицию вот здесь и путевую декомпозицию вот здесь. При этом мы предполагаем по индукции, что путевая ширина графа не больше, чем DnD\sqrt{n}: CC — это константа из теоремы о сбалансированном сепараторе, а по индукции мы доказываем, что pw⩽Dnpw \leqslant D\sqrt{n}.

Тогда вот здесь у меня не больше, чем 23n\tfrac{2}{3}n, и вот здесь не больше, чем 23n\tfrac{2}{3}n. Ещё есть плюс некоторая прибавочка CnC\sqrt{n}, потому что… или я SS включаю в эти графы, или нет? Вроде должен включать, сам сепаратор. Итак, в результате я делю свой граф на две части, G1G_1 и G2G_2, — и что я получаю? Что pw(G1)pw(G_1) у меня не больше… Нет, теперь я SS туда не добавляю, мне вообще всё равно, и сюда не добавляю, мне тоже всё равно. Значит, pw(G1)pw(G_1) не превосходит чего? D23nD\sqrt{\tfrac{2}{3}n}. И pw(G2)pw(G_2) не превосходит того же. (Над обеими половинками картинки на доске выписано 23n\tfrac{2}{3}n — симметрия, которая в речи только подразумевается, — а от линзы вниз идёт стрелка с подписью ⩽Cn\leqslant C\sqrt{n}. Как именно компоненты G−SG - S, которых может быть много, группируются ровно в две части размера не больше 23n\tfrac{2}{3}n, на записи не говорится: на доске нарисованы сразу две доли.)

А что я теперь делаю? У меня есть путевая декомпозиция G1G_1 — я её вот так прямо записал, с сумочками, — и путевая декомпозиция G2G_2, тоже с сумочками. А теперь я, чтобы вообще не переживать, множество SS прямо приписываю: плюс SS сюда, плюс SS сюда — в каждую сумку я его добавляю. (Этому соответствует отдельный рисунок: цепочка сумок-кружков, идущая слева направо двумя группами, по одной на каждый GiG_i, и под каждым кружком прямоугольник, присоединённый к нему стрелкой вверх; самый левый прямоугольник подписан +S+S.)

Какая у меня получается путевая ширина? В результате не больше, чем D23n+CnD\sqrt{\tfrac{2}{3}n} + C\sqrt{n}. А моя цель какая? Я хочу доказать, что вся индукция прошла, то есть что это не больше, чем DnD\sqrt{n}. Отсюда видно следующее: здесь DD на самом деле взято с константой меньше единички, то есть достаточно, чтобы D23+C⩽DD\sqrt{\tfrac{2}{3}} + C \leqslant D. А CC у нас фиксировано вот этой теоремой, значит, мне просто надо подобрать DD достаточно большим, чтобы это выполнялось. Подберём. (На доске это собрано в одну цепочку: ⩽D23n+Cn⩽Dn\leqslant D\sqrt{\tfrac{2}{3}n} + C\sqrt{n} \leqslant D\sqrt{n}, а строкой ниже — сокращённое условие на константы D23+C⩽DD\sqrt{\tfrac{2}{3}} + C \leqslant D, именно с радикалом. Ещё одно место, которое вслух не оговаривается: индукция требует, чтобы G1G_1 и G2G_2 сами оставались HH-minor-free — а это верно, потому что класс замкнут относительно взятия миноров, что было доказано чуть раньше.)

Спасибо, действительно, оказалось очень просто. Причём путевая декомпозиция получилась даже не очень умная: я просто иерархически добавляю сюда SS. Такое ощущение, что мы вообще древесную глубину получили, — потому что я же приписывал SS прямо целиком вверх. Это вообще древесная глубина, а не путевая ширина получилась. Круто: значит, мы доказали ещё более сильную теорему.

Понятно, да, что древесная глубина вышла? Потому что я что сделал? Я записал прямо SS вот так вот, а здесь отдельно сделал древесные декомпозиции для G1G_1 и для G2G_2. Ну и всё — это просто высота моего дерева получилась. То есть путевая ширина здесь оказалась ни при чём. (Словами этот аргумент больше ничем не раскрывается, но на доске он нарисован, и этот рисунок и есть доказательство: высокий вертикальный овал — столбик вершин из SS, то есть путь длины ⩽Cn\leqslant C\sqrt{n}, с короткой засечкой-корнем сверху, — от нижнего конца которого двумя рёбрами спускаются два кружка: деревья элиминации для G1G_1 и G2G_2. Высота такого дерева элиминации удовлетворяет td(G)⩽Cn+td(23n)=O(n)td(G) \leqslant C\sqrt{n} + td\bigl(\tfrac{2}{3}n\bigr) = O(\sqrt{n}), и поскольку td⩾pw+1td \geqslant pw + 1, оценка на древесную глубину действительно строго сильнее оценки на путевую ширину.)

Из забавных фактов. Кажется, что всё это касается только планарных графов, но на самом деле это касается любых HH-minor-free графов: у HH-minor-free графа есть сбалансированный сепаратор размера O(n)O(\sqrt{n}). Тут OO-шка, конечно же, скрывает под собой что-то зависящее от hh, то есть, по-моему, здесь не универсальная константа. Я могу ошибаться, но было бы странно, если бы здесь была константа, никак не зависящая от hh. (Это и есть последняя строчка, появляющаяся на доске за всю лекцию: «Thm У HH-minor-free графа есть bal. sep размера O(n)O(\sqrt{n})».)

И всё — что мы с вами в результате доказали? Это вообще что-то очень крутое: что древесная глубина любого HH-minor-free графа не превосходит корня из nn. (Строго говоря, доказана оценка td(G)=O(n)td(G) = O(\sqrt{n}) с константой, зависящей от hh, — он сам говорит об этом строкой выше; произнесённая формулировка — разговорное сокращение. Это последнее утверждение лекции на доске так и не появляется: мелом записана только предыдущая строчка про сбалансированный сепаратор.)

Если нам всё нравится и если у вас нет каких-то вопросов, то на этом можно заканчивать сегодняшнюю лекцию про не очень легкий концепт. Да, сегодня много чего было совершенно без доказательств, и это было целенаправленно: непонятно, зачем нам перегружаться доказательствами про миноры. Но теперь мы хоть знаем, что такое эти самые миноры. Попробуем подвести их к древесной ширине на следующей лекции — но обещаю, что миноров так много не будет и так тупить у доски я тоже сильно не буду. Вот.