Модульная декомпозиция

Рекурсивное разбиение графа на подмножества узлов

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

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

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

Модули

Поскольку понятие модулей было заново открыто во многих областях, модули также назывались автономными множествами , однородными множествами , стабильными множествами , сгустками , комитетами , внешне связанными множествами , интервалами , неупрощаемыми подсетями и разделяющими множествами (Brandstädt, Le & Spinrad 1999). . Возможно, самая ранняя ссылка на них, а также первое описание модульных коэффициентов и разложения графов, которое они порождают, появились в ( Gallai 1967).

Модуль графа — это обобщение компонента связности . Связный компонент обладает тем свойством, что он представляет собой набор вершин, каждый член которого не является соседом каждой вершины, не принадлежащей . (Это объединение компонентов связности тогда и только тогда, когда оно обладает этим свойством.) В более общем смысле, модуль является модулем, если для каждой вершины либо каждый член не является соседом , либо каждый член является соседом . ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle v\not \in X}$ ${\displaystyle X}$ ${\displaystyle v}$ ${\displaystyle X}$ ${\displaystyle v}$

Эквивалентно, модуль является модулем, если все члены имеют одинаковый набор соседей среди вершин, не входящих в . ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$

В отличие от связных компонентов, модули графа такие же, как и модули его дополнения , и модули могут быть «вложенными»: один модуль может быть собственным подмножеством другого. Обратите внимание, что множество вершин графа является модулем, как и его одноэлементные подмножества и пустое множество; они называются тривиальными модулями . Граф может иметь или не иметь другие модули. Граф называется простым, если все его модули тривиальны. ${\displaystyle V}$

Несмотря на эти различия, модули сохраняют желательное свойство компонентов связности, а именно то, что многие свойства подграфа, индуцированные компонентом связности, не зависят от остальной части графа. Аналогичное явление применимо и к подграфам, индуцированным модулями. ${\displaystyle G[X]}$ ${\displaystyle X}$

Поэтому модули графа представляют большой алгоритмический интерес. Набор вложенных модулей, примером которого является модульная декомпозиция, может использоваться для управления рекурсивным решением многих комбинаторных задач на графах, таких как распознавание и транзитивная ориентация графов сравнимости , распознавание и поиск представлений перестановок графов перестановок , распознавание того, граф - это кограф и нахождение сертификата ответа на вопрос, распознавание интервальных графов и нахождение для них интервальных представлений, определение дистанционно-наследственных графов (Спинрад, 2003) и для рисования графов (Пападопулос, 2006). Они играют важную роль в знаменитом доказательстве теоремы Ловаса о совершенном графе (Golumbic, 1980).

Для распознавания дистанционно-наследственных графов и круговых графов особенно полезно дальнейшее обобщение модульной декомпозиции, называемое расщепленной декомпозицией (Spinrad, 2003).

Чтобы избежать возможности неоднозначности в приведенных выше определениях, дадим следующие формальные определения модулей. . является модулем if : ${\displaystyle G=(V,E)}$ ${\displaystyle M\subseteq V}$ ${\displaystyle G}$

• вершины не могут быть различимы ни одной вершиной в , т. е . либо смежно с обоими , либо не смежно ни с , ни с . ${\displaystyle M}$ ${\displaystyle V\backslash M}$ ${\displaystyle \forall u,v\in M,\forall x\in V\backslash M}$ ${\displaystyle x}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle x}$ ${\displaystyle u}$ ${\displaystyle v}$
• вершины имеют одинаковый набор внешних соседей, т. е. . ${\displaystyle M}$ ${\displaystyle \forall u,v\in M,N(u)\setminus M=N(v)\setminus M}$

${\displaystyle \emptyset }$, и все синглтоны для являются модулями и называются тривиальными модулями . Граф является простым, если все его модули тривиальны. Связные компоненты графа или графа-дополнения также являются модулями графа . ${\displaystyle V}$ ${\displaystyle \{v\}}$ ${\displaystyle v\in V}$ ${\displaystyle G}$ ${\displaystyle G}$

${\displaystyle M}$является сильным модулем графа , если он не перекрывается ни с одним другим модулем : модуль , или или или . ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle \forall M'}$ ${\displaystyle G}$ ${\displaystyle M\cap M'=\emptyset }$ ${\displaystyle M\subseteq M'}$ ${\displaystyle M'\subseteq M}$

Модульные коэффициенты и коэффициенты

Если и являются непересекающимися модулями, то легко увидеть, что либо каждый член является соседом каждого элемента , либо ни один член не является соседним ни с одним членом . Таким образом, связь между двумя непересекающимися модулями является либо смежной , либо несмежной . Никакого промежуточного отношения между этими двумя крайностями не может быть. ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$

По этой причине особый интерес представляют модульные разделы , в которых каждый класс разделов является модулем. Предположим, это модульный раздел. Поскольку классы разбиения не пересекаются, их смежности составляют новый граф, факторграф , вершины которого являются членами . То есть каждая вершина является модулем G, а примыкания этих модулей являются ребрами . ${\displaystyle V}$ ${\displaystyle P}$ ${\displaystyle G/P}$ ${\displaystyle P}$ ${\displaystyle G/P}$ ${\displaystyle G/P}$

На рисунке ниже вершина 1, вершины со 2 по 4, вершина 5, вершины 6 и 7 и вершины с 8 по 11 представляют собой модульный раздел. На верхней правой диаграмме ребра между этими наборами изображают частное, заданное этим разбиением, а ребра внутри наборов изображают соответствующие факторы.

Разделы и являются тривиальными модульными разделами . — это просто граф с одной вершиной, а . Пусть — нетривиальный модуль. Тогда и одноэлементные подмножества являются нетривиальным модульным разбиением . Таким образом, существование любых нетривиальных модулей влечет за собой существование нетривиальных модульных разбиений. В общем, многие или все члены могут быть нетривиальными модулями. ${\displaystyle \{V\}}$ ${\displaystyle \{\{x\}|x\in V\}}$ ${\displaystyle G/\{V\}}$ ${\displaystyle G/\{\{x\}|x\in V\}=G}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle V\backslash X}$ ${\displaystyle V}$ ${\displaystyle P}$

Если — нетривиальное модульное разбиение, то это компактное представление всех ребер, имеющих концы в разных классах разбиения . Для каждого класса разбиения в подграф, индуцированный, называется фактором и дает представление всех ребер с обеими конечными точками в . Следовательно, ребра можно восстановить только по факторграфу и его факторам. Термин «граф простых чисел» возник из-за того, что граф простых чисел имеет только тривиальные факторы и факторы. ${\displaystyle P}$ ${\displaystyle G/P}$ ${\displaystyle P}$ ${\displaystyle X}$ ${\displaystyle P}$ ${\displaystyle G[X]}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle G}$ ${\displaystyle G/P}$

Когда является фактором модульного фактора , возможно, что его можно рекурсивно разложить на факторы и факторы. Каждый уровень рекурсии порождает частное. В базовом случае граф имеет только одну вершину. В совокупности их можно реконструировать индуктивно, реконструируя факторы снизу вверх, инвертируя этапы разложения путем объединения факторов с частным на каждом уровне. ${\displaystyle G[X]}$ ${\displaystyle G/P}$ ${\displaystyle G[X]}$ ${\displaystyle G}$

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

Способ рекурсивного разложения графа на факторы и отношения может не быть уникальным. (Например, все подмножества вершин полного графа являются модулями, а это означает, что существует много разных способов его рекурсивного разложения.) Некоторые способы могут быть более полезными, чем другие.

Модульная декомпозиция

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

Граф, его частное, в котором «мешки» вершин графа соответствуют дочерним элементам корня дерева модульного разложения, и его полное дерево модульного разложения: узлы серии обозначаются буквами «s», параллельные узлы «//» и простые числа. узлы «п».

Ниже приводится ключевое наблюдение для понимания модульной декомпозиции:

Если является модулем и является подмножеством ${\displaystyle X}$ ${\displaystyle G}$ ${\displaystyle Y}$ ${\displaystyle X}$ , то является модулем , если и только если он является модулем . ${\displaystyle Y}$ ${\displaystyle G}$ ${\displaystyle G[X]}$

В (Gallai, 1967) Галлай рекурсивно определил модульное разложение на графе с набором вершин следующим образом: ${\displaystyle V}$

1. В базовом случае, если у дерева только одна вершина, его модульное разложение представляет собой один узел дерева. ${\displaystyle G}$
2. Галлаи показал, что если связно и его дополнение связно, то максимальные модули, являющиеся собственными подмножествами, являются разбиением . Таким образом, они представляют собой модульную перегородку. Частное, которое они определяют, является простым. Корень дерева помечен как простой узел, и эти модули назначаются дочерними элементами . Поскольку они максимальны, каждый не представленный до сих пор модуль содержится в дочернем элементе . Для каждого потомка , замена деревом модульного разложения дает представление всех модулей , согласно ключевому наблюдению выше. ${\displaystyle G}$ ${\displaystyle V}$ ${\displaystyle V}$ ${\displaystyle V}$ ${\displaystyle X}$ ${\displaystyle V}$ ${\displaystyle X}$ ${\displaystyle V}$ ${\displaystyle X}$ ${\displaystyle G[X]}$ ${\displaystyle G}$
3. Если несвязно, то его дополнение связно. Каждое объединение компонент связности является модулем . Все остальные модули являются подмножествами одного связного компонента. Здесь представлены все модули, за исключением подмножеств подключенных компонентов. Для каждого компонента замена деревом модульного разложения дает представление всех модулей , согласно ключевому наблюдению выше. Корень дерева помечается как параллельный узел и присоединяется вместо дочернего узла корня. Фактор, определенный детьми, является дополнением полного графа. ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle G[X]}$ ${\displaystyle G}$ ${\displaystyle X}$
4. Если дополнение отключено, то оно связно. Поддеревья, являющиеся дочерними, определяются симметрично случаю, когда несвязно, поскольку модули графа совпадают с модулями его дополнения. Корень дерева помечен последовательным узлом, а частное, определенное дочерними узлами, представляет собой полный граф. ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle V}$ ${\displaystyle G}$

Итоговое дерево имеет одноэлементные наборы вершин в качестве листьев из-за базового случая. Множество вершин является модулем тогда и только тогда, когда оно является узлом дерева или объединением детей последовательного или параллельного узла. Это неявно дает все модульные разделы . Именно в этом смысле дерево модулярного разложения «включает» все другие способы рекурсивного разложения на частное. ${\displaystyle G}$ ${\displaystyle Y}$ ${\displaystyle G}$ ${\displaystyle V}$ ${\displaystyle G}$

Алгоритмические проблемы

Структура данных для представления дерева модульной декомпозиции должна поддерживать операцию, которая вводит узел и возвращает набор вершин, которые этот узел представляет. Очевидный способ сделать это — назначить каждому узлу список вершин , которые он представляет. Учитывая указатель на узел, эта структура может возвращать набор вершин, которые она представляет во времени. Однако в худшем случае эта структура данных потребует места. ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle {\mathcal {O}}(k)}$ ${\displaystyle \Theta (n^{2})}$

Представление модульного разложения ${\displaystyle {\mathcal {O}}(n)}$

Альтернатива -space, соответствующая этой производительности, получается путем представления дерева модульной декомпозиции с использованием любой стандартной структуры данных корневого дерева и маркировки каждого листа вершиной, которую оно представляет. Набор, представленный внутренним узлом, задается набором меток его листовых потомков. Хорошо известно, что любое корневое дерево с листьями имеет не более внутренних узлов. Можно использовать поиск в глубину, начиная с, чтобы сообщить метки потомков листьев во времени. ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle k}$ ${\displaystyle k-1}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle {\mathcal {O}}(k)}$

Модульное разложение, дополненное коэффициентом дочерних элементов каждого внутреннего узла, дает полное представление . ${\displaystyle G}$

Каждый узел представляет собой набор вершин , и, если это внутренний узел, набор дочерних элементов представляет собой раздел, где каждый класс раздела является модулем. Поэтому они индуцируют частное в . Вершины этого частного являются элементами , поэтому их можно представить, установив ребра среди дочерних элементов . Если и являются двумя членами и и , то и смежны в том и только в том случае, если и смежны в этом частном. Для любой пары вершин это определяется фактором в дочерних элементах наименьшего общего предка и в дереве модульного разложения. Следовательно, модульное разложение, помеченное таким образом факторами, дает полное представление . ${\displaystyle X}$ ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle P}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle G[X]/P}$ ${\displaystyle G[X]}$ ${\displaystyle P}$ ${\displaystyle G[X]/P}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle P}$ ${\displaystyle u\in Y}$ ${\displaystyle v\in Z}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle \{u,v\}}$ ${\displaystyle G}$ ${\displaystyle \{u\}}$ ${\displaystyle \{v\}}$ ${\displaystyle G}$

Многие комбинаторные задачи можно решить , решив задачу отдельно для каждого из этих отношений. Например, является графом сравнимости тогда и только тогда, когда каждое из этих факторов является графом сравнимости (Галлаи, 67; Мёринг, 85). Следовательно, чтобы выяснить, является ли граф графом сравнимости, нужно только выяснить, является ли таковым каждое из частных. Фактически, чтобы найти транзитивную ориентацию графа сравнимости, достаточно транзитивно ориентировать каждый из этих факторов его модульного разложения (Галлаи, 67; Мёринг, 85). Аналогичное явление применимо к графам перестановок (МакКоннелл и Спинрад '94), интервальным графам (Сюй и Ма '99), совершенным графам и другим классам графов. Некоторые важные задачи комбинаторной оптимизации на графах можно решить, используя аналогичную стратегию (Мёринг, 85). ${\displaystyle G}$ ${\displaystyle G}$

Кографы — это графы, в дереве модульного разложения которых есть только параллельные или последовательные узлы.

Первый полиномиальный алгоритм для вычисления дерева модульной декомпозиции графа был опубликован в 1972 году (Джеймс, Стэнтон и Коуэн, 1972), а теперь доступны линейные алгоритмы (МакКоннелл и Спинрад, 1999, Теддер и др., 2007, Курнье и Хабиб, 1994).

Обобщения

Модульная декомпозиция ориентированных графов может быть выполнена за линейное время (МакКоннелл и де Монгольфье, 2005).

За небольшим количеством простых исключений, каждый граф с нетривиальным модульным разложением также имеет косое разбиение (Reed 2008).

Рекомендации

• Брандштедт, Андреас; Ле, Ван Банг; Спинрад, Джереми П. (1999). Классы графов: обзор . Общество промышленной и прикладной математики. дои : 10.1137/1.9780898719796. ISBN 978-0-89871-432-6.
• Галлай, Тибор (1967). «Транзитивный ориентационный графен». Acta Mathematica Academiae Scientiarum Hungaricae . 18 (1–2): 25–66. дои : 10.1007/BF02020961. MR  0221974. S2CID  119485995.
• Джеймс, Ли О.; Стэнтон, Ральф Г.; Коуэн, Дональд Д. (1972). «Декомпозиция графа для неориентированных графов». Учеб. 3-я Юго-восточная международная конференция по комбинаторике, теории графов и информатике (Флоридский Атлантический университет, Бока-Ратон, Флорида, 1972) . Атлантический университет Флориды . стр. 281–290. МР  0351909.
• Голумбик, Мартин К. (1980). Алгоритмическая теория графов и совершенные графы . Академическая пресса. ISBN 0-444-51530-5.
• Сюй, WL; Ма, Т. (1999). «Быстрые и простые алгоритмы распознавания хордальных графов сравнимости и интервальных графов». SIAM Journal по вычислительной технике . 28 (3): 1004–1020. CiteSeerX  10.1.1.104.4647 . дои : 10.1137/S0097539792224814.
• МакКоннелл, Росс М.; де Монгольфье, Фабьен (2005). «Модульная декомпозиция ориентированных графов в линейном времени». Дискретная прикладная математика . 145 (2): 198–209. дои : 10.1016/j.dam.2004.02.017 .
• МакКоннелл, Росс М.; Спинрад, Джереми П. (1999). «Модульная декомпозиция и транзитивная ориентация» (PDF) . Дискретная математика . 201 (1–3): 189–241. дои : 10.1016/S0012-365X(98)00319-7 . МР  1687819.
• Меринг, Рольф Х. (1985). Я. Соперник (ред.). «Алгоритмические аспекты графов сравнимости и интервальных графов». Графики и порядок . Д. Рейдель: 41–101. дои : 10.1007/978-94-009-5315-4_2. ISBN 978-94-010-8848-0.
• Меринг, Рольф Х. (1985). «Алгоритмические аспекты декомпозиции подстановки в оптимизации отношений, систем множеств и булевых функций». Анналы исследования операций . 4 : 195–225. дои : 10.1007/BF02022041. S2CID  119982014.
• Пападопулос, Харис; Фоглис, Константинос (2005). «Построение графиков с использованием модульной декомпозиции» (PDF) . Учеб. 13-й Международный симпозиум по рисованию графов (GD'05) . Конспекты лекций по информатике. Том. 3843. Шпрингер-Верлаг. стр. 343–354. дои : 10.1007/11618058_31. МР  2229205.
• Рид, Брюс (2008). «Наклонные разделы в идеальных графах» (PDF) . Дискретная прикладная математика . 156 (7): 1150–1156. дои : 10.1016/j.dam.2007.05.054 . MR  2404228. Архивировано из оригинала (PDF) 19 сентября 2015 г. Проверено 13 августа 2012 г.
• Спинрад, Джереми П. (2003). Эффективное представление графов . Монографии Филдсовского института. Американское математическое общество. ISBN 0-8218-2815-0.
• Теддер, Марк; Корнейл, Дерек ; Хабиб, Мишель; Пол, Кристоф (2008). «Простое модульное разложение в линейном времени посредством рекурсивной факторизации перестановок». Учеб. 35-й Международный коллоквиум по автоматам, языкам и программированию (ICALP 2008) . Конспекты лекций по информатике. Том. 5125. Шпрингер-Верлаг. стр. 634–645. arXiv : 0710.3901 . дои : 10.1007/978-3-540-70575-8_52.
• Захеди, Эмад; Смит, Джейсон (31 июля 2019 г.). «Модульная декомпозиция графов и свойство сохранения расстояния». Дискретная прикладная математика . 265 (7): 192–198. arXiv : 1805.09853 . Бибкод : 2018arXiv180509853Z. дои : 10.1016/j.dam.2019.03.019.

Внешние ссылки

• Perl - реализация алгоритма модульной декомпозиции.
• Java-реализация алгоритма модульной декомпозиции.
• Реализация Джулии алгоритма модульной декомпозиции