Происхождение понятия древовидной ширины

Мой вопрос сегодня (как обычно) немного глупый; но я бы попросил вас рассмотреть это.

Я хотел знать о происхождении и / или мотивации концепции ширины дерева. Я уверен, что понимаю, что это используется в алгоритмах FPT, но я не думаю, что это было причиной, почему это понятие было определено.

Я написал заметки писца на эту тему в классе профессора Робина Томаса . Я думаю, что я понимаю некоторые из применений этой концепции (поскольку в ней передаются свойства разделения дерева в разложенный граф), но по какой-то причине я не совсем уверен, что причина, по которой была разработана эта концепция, заключалась в измерении близости графа. к дереву.

Я постараюсь прояснить себя (я не уверен, что смогу, пожалуйста, дайте мне знать, если вопрос не ясен). Я хотел бы знать, существовали ли подобные понятия где-то еще в какой-то другой области математики, откуда это понятие якобы «заимствовано». Мое предположение будет топологией, но из-за недостатка знаний я ничего не могу сказать.

Основная причина, по которой мне это интересно, - когда я в первый раз прочитал его определение, я не был уверен, почему и как кто-то задумывается об этом и с какой целью. Если вопрос все еще не ясен, я, наконец, попытался бы сформулировать это следующим образом: давайте представим, что понятие ширины дерева не существует. Какие естественные вопросы (или расширения некоторых математических теорем / концепций) для дискретных настроек приведут к мысли о том, что определение (позвольте мне использовать это слово) как определение ширины дерева.

Если вы действительно хотите знать, что привело нас с Нилом Робертсоном к ширине дерева, это вовсе не были алгоритмы. Мы пытались решить гипотезу Вагнера о том, что в любом бесконечном наборе графов один из них является второстепенным для другого, и мы были в самом начале. Мы знали, что это было бы правдой, если бы мы ограничивались графами без пути k-вершины; позвольте мне объяснить почему. Мы знали, что все такие графы имеют простую структуру (точнее, каждый граф без пути k-вершины имеет эту структуру, и каждый граф с этой структурой не имеет пути 2 ^ k-вершины); и мы знали, что в каждом бесконечном множестве графов с этой структурой один из них был второстепенным для другого. Таким образом, гипотеза Вагнера была верна для графов с ограничением их максимальной длины пути.

Мы также знали, что это верно для графов без малой k-звезды, опять же, потому что у нас была структурная теорема для таких графов. Мы попытались найти более общие миноры, которые имели соответствующие структурные теоремы, которые мы могли бы использовать для доказательства гипотезы Вагнера, и это привело нас к ширине пути; исключите ЛЮБОЕ дерево как второстепенное, и вы получите ограниченную ширину пути, и если у вас ограниченная ширина пути, то есть деревья, которые вы не можете иметь в качестве второстепенного. (Это была сложная теорема для нас; у нас было чрезвычайно трудное доказательство в первой статье Graph Minors, не читайте ее, это можно сделать намного проще.) Но мы могли бы доказать гипотезу Вагнера для графов с ограниченной шириной пути, и это означало, что это было верно для графов, не содержащих какого-либо фиксированного дерева как младшего; большое обобщение путей и звездных случаев, о которых я упоминал ранее.

Во всяком случае, с этим мы попытались продвинуться дальше. Мы не могли сделать общие графики, поэтому мы подумали о плоских графах. Мы нашли структурную теорему для плоских графов, которая не содержала ни одного фиксированного плоского графа как минор (это было легко); это было ограничено шириной дерева. Мы доказали, что для любого фиксированного плоского графа все плоские графы, которые не содержали его в качестве младшего, имели ограниченную ширину дерева. Как вы можете себе представить, это было действительно захватывающе; по совпадению, теорема о структуре для исключения плоских графов (внутри больших плоских графов) была естественным поворотом в теореме о структуре для исключения деревьев (внутри общих графов). Мы чувствовали, что делаем что-то правильно. И это позволит нам доказать гипотезу Вагнера для всех плоских графов, потому что у нас была эта структурная теорема.

Поскольку ширина дерева работала для исключения плоских графов внутри больших плоских графов, было естественным вопросом, работало ли оно для исключения плоских графов внутри непланарных графов - верно ли, что для каждого фиксированного плоского графа все графы не содержат его как несовершеннолетний имел ограниченную ширину дерева? Это мы не могли доказать долгое время, но именно так мы начали думать о ширине дерева общих графов. И как только у нас появилась концепция ширины дерева, стало ясно, что это хорошо для алгоритмов. (И да, мы не знали, что Халин уже думал о ширине дерева.)

Вот как вы могли бы придумать концепцию ширины дерева самостоятельно.

Предположим, вы хотите посчитать количество независимых наборов в следующем графике.

Независимые наборы могут быть разделены на те, где занят верхний узел, и на те, где он не занят

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

Теперь предположим, что у вас больше нет дерева. Это означает, что разделители больше, но вы можете использовать ту же идею. Рассмотрим подсчет независимых множеств на следующем графике.

Используя ту же идею разбить проблему на подзадачи на разделителе, вы получите следующее

Как и в предыдущем примере, каждый член в сумме разбивается на две меньшие задачи подсчета через разделитель.

Обратите внимание, что в сумме у нас больше терминов, чем в предыдущем примере, потому что мы должны перечислить все конфигурации нашего разделителя, которые потенциально могут расти в геометрической прогрессии в зависимости от размера разделителя (в данном случае - размера 2).

Древовидная декомпозиция - это структура данных для компактного хранения этих рекурсивных шагов разбиения. Рассмотрим следующий граф и его разложение по дереву

Для подсчета с использованием этой декомпозиции вы должны сначала зафиксировать значения в узлах 3,6, которые разбивают его на 2 подзадачи. В первой подзадаче вы дополнительно исправите узел 5, который разбивает его часть на две меньшие части.

Размер наибольшего разделителя в оптимальном рекурсивном разложении - это как раз ширина дерева. Для более крупных задач подсчета размер самого большого разделителя доминирует во время выполнения, поэтому это количество так важно.

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

Затем построите разложение дерева, взяв максимальные клики и соединив их, если их пересечение является максимальным разделителем.

Рекурсивный разделитель и основанный на триангуляции подходы построения разложения дерева эквивалентны. Ширина дерева + 1 - это размер самой большой клики в оптимальной триангуляции графа, или, если график уже триангулирован, просто размер самой большой клики.

Таким образом, в некотором смысле хордовые графы с шириной дерева tw можно рассматривать как деревья, в которых вместо отдельных узлов мы имеем перекрывающиеся клики размером не более tw + 1. Нехордовые графы являются такими "кликовыми деревьями" с отсутствующими краями кликов

Вот некоторые хордальные графы и их ширина дерева.

Я верю, что сама treewidth началась с уже предоставленной статьи Робертсона Сеймура. Но некоторые более ранние предшественники, по-видимому:

• Концепция «размерности» графа, который будет управлять поведением алгоритмов динамического программирования на нем, из Bertelé, Umberto; Бриоски, Франческо (1972), Несерийное динамическое программирование .

• Концепция игр преследования-уклонения на графах, от Parsons, TD (1976). «Погоня за уклонением от графа». Теория и приложения графов . Springer-Verlag. С. 426–441. Позднее было показано, что один из вариантов этого эквивалентен ширине дерева: Seymour, Paul D .; Томас, Робин (1993), «Поиск в графе и теорема минимума для ширины дерева», Журнал комбинаторной теории, Серия B 58 (1): 22–33, doi: 10.1006 / jctb.1993.1027 .

• Разделительные иерархии для плоских графов, начиная с Унгара, Питера (1951), «Теорема о плоских графах», Журнал Лондонского математического общества 1 (4): 256, doi: 10.1112 / jlms / s1-26.4.256 и продолжая с несколькими работами Липтона и Тарьяна в 1979–1980 гг. Размер самого большого разделителя в иерархии этого типа тесно связан с шириной дерева.

Двигаясь вперед ко времени, когда идеи Робертсона-Сеймура могли уже начать распространяться, есть также статья, предшествующая графу Minors II, в которой явно соединены идеи преследования и уклонения от преследования, и которая определяет понятие ширины, эквивалентное ширине пути. : Эллис, JA; Садборо, IH; Turner, JS (1983), "График разделения и поиска числа", Proc. 1983 Allerton Conf. по связи, управлению и вычислениям.

В своей монографии по теории графов Рейнхард Дистел прослеживает концепцию ширины дерева и разложения деревьев назад к статье Халина, написанной в 1976 году (хотя эти имена и не использовались). Он также приписывает этой статье результат, что плоские графы сетки имеют неограниченную ширину дерева. Конечно, он также упоминает более позднюю статью Робертсона и Сеймура, которые «заново открыли концепцию, очевидно, не подозревая о работе Халина» (извините, если мой перевод плохой).

• $S$
• Рейнхард Дистел. Graphentheorie , 3-е немецкое издание, Notizen zu Kapitel 10. (Некоторые английские издания книги доступны для бесплатного скачивания в Интернете).

Понятие ширины дерева [1] (и аналогичное понятие ширины ветви ) было введено Робертсоном и Сеймуром в их основополагающих работах по графу несовершеннолетним .

$G$$H$

См .: Н. Робертсон, П.Д. Сеймур. Граф несовершеннолетних. II. Алгоритмические аспекты ширины дерева . Серия JCT B (1986)