Модульное разложение

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

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

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

Модули

Понятие модуля было переоткрыто во многих областях. Для этого понятия использовались названия автономные множества, однородные множества, интервалы и дробные множества. Видимо, самым ранним упоминанием и первым описанием модульных частных и разбиения графов, возникающего при этом, было в статье Галаи в 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}$, не зависят от остальной части графа. Похожее явление наблюдается для подграфов, порождённых модулями.

Модули графа представляют поэтому большой алгоритмический интерес. Множество вложенных модулей, для которых модульное разложение является примером, может быть использовано для получения рекурсивного решения многих комбинаторных задач на графах, таких как распознавание и поиск транзитивной ориентации графов сравнимости, распознавание и нахождение перестановочного представления графов перестановок, распознавание, является ли граф кографом, распознавание интервальных графов и нахождение интервального представления для него, определение дистанционно-наследуемых графов[1] и для визуализации графов[2]. Они играют важную роль в доказательстве теоремы о совершенных графах[3].

Для распознавания дистанционно-наследуемых графов и круговых графов особенно полезно дальнейшее обобщение модульного разложения, называемое расщепляемой декомпозицией^[англ.][1].

Во избежание двусмысленности вышеприведённого определения дадим следующее формальное определение модулей. ${\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}$. Таким образом, все элементы двух непересекающихся модулей либо смежны, либо не смежны. Никакое промежуточное состояние между этими двумя крайностями не существует.

Ввиду этого модульные разложения ${\displaystyle V}$, где каждый класс разбиения является модулем, представляет особый интерес. Предположим, что ${\displaystyle P}$ является модульным разложением. Поскольку классы разбиений не пересекаются, их смежность образует новый граф, фактор-граф^[англ.] ${\displaystyle G/P}$, вершинами которого являются члены ${\displaystyle P}$. То есть каждая вершина ${\displaystyle G/P}$ является модулем графа G, а смежность этих модулей задаёт рёбра ${\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», параллельные помечены nodes «//», а простые узлы помечены «p».

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

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

Галлаи[4] определил модульное разложение рекурсивно на графе с множеством вершин ${\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)}$ представление модульного разложения

Альтернатива с памятью ${\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}$.

Многие комбинаторные задачи можно решить на графе ${\displaystyle G}$ путём решения их отдельно для каждого частного. Например, ${\displaystyle G}$ является графом сравнимости тогда и только тогда, когда каждый из этих частных является графом сравнимости[4][5]. Следовательно, чтобы определить, является ли граф графом сравнимости, достаточно проверить это для каждого его частного. Фактически, чтобы найти транзитивную ориентацию графа сравнимости, достаточно найти транзитивную ориентацию каждого из его частных в модульном разложении[4][5]. Аналогичное явление обнаруживается для графов перестановок[6], интервальных графов[7], совершенных графов и других классов графов. Некоторые важные комбинаторные оптимизационные задачи на графах могут быть решены с помощью аналогичных стратегий[8].

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

Первый алгоритм полиномиального времени для вычисления дерева модульного разложения графа был опубликован в 1972[9], а теперь доступны алгоритмы линейного времени[6][10].

Обобщения

Модульное разложение ориентированных графов может быть получено за линейное время[11].

За небольшим количеством простых исключений любой граф с нетривиальным модульным разложением имеет также косое разбиение[12].

Примечания

1. Spinrad, 2003.
2. Papadopoulos, Voglis, 2005.
3. Golumbic, 1980.
4. Gallai, 1967, с. 25–66.
5. Möhring, 1985a, с. 41–101.
6. McConnell, Spinrad, 1999, с. 189–241.
7. Hsu, Ma, 1999, с. 1004–1020.
8. Möhring, 1985b, с. 195–225.
9. James, Stanton, Cowan, 1972, с. 281–290.
10. Tedder, Corneil, Habib, Paul, 2008, с. 634–645.
11. McConnell, de Montgolfier, 2005, с. 198–209.
12. Reed, 2008.

Литература

• Tibor Gallai. Transitiv orientierbare Graphen // Acta Mathematica Academiae Scientiarum Hungaricae. — 1967. — Т. 18. — doi:10.1007/BF02020961.
• Lee O. James, Ralph G. Stanton, Donald D. Cowan. Graph decomposition for undirected graphs // Proc. 3rd Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1972). — Florida Atlantic University, 1972.
• Martin C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — ISBN 0-444-51530-5.
• Hsu W.L., Ma T. Fast and simple algorithms for recognizing chordal comparability graphs and interval graphs // SIAM Journal on Computing. — 1999. — Т. 28, вып. 3. — doi:10.1137/S0097539792224814.
• Ross M. McConnell, Fabien de Montgolfier. Linear-time modular decomposition of directed graphs // Discrete Applied Mathematics. — 2005. — Т. 145, вып. 2. — doi:10.1016/j.dam.2004.02.017.
• Ross M. McConnell, Jeremy P. Spinrad. Modular decomposition and transitive orientation // Discrete Mathematics. — 1999. — Т. 201. — doi:10.1016/S0012-365X(98)00319-7.
• Rolf H. Möhring. Algorithmic aspects of comparability graphs and interval graphs // Graphs and Order. — D. Reidel, 1985a.
• Rolf H. Möhring. Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and Boolean functions // Annals of Operations Research. — 1985b. — Т. 4. — doi:10.1007/BF02022041.
• Charis Papadopoulos, Constantinos Voglis. Drawing graphs using modular decomposition // Proc. 13th International Symposium on Graph Drawing (GD'05). — Springer-Verlag, 2005. — Т. 3843. — (Lecture Notes in Computer Science). — doi:10.1007/11618058_31.
• Bruce Reed. Skew partitions in perfect graphs // Discrete Applied Mathematics. — 2008. — Т. 156, вып. 7. — С. 1150–1156. — doi:10.1016/j.dam.2007.05.054. Архивировано 19 сентября 2015 года.
• Jeremy P. Spinrad. Efficient Graph Representations. — American Mathematical Society, 2003. — (Fields Institute Monographs). — ISBN 0-8218-2815-0.
• Marc Tedder, Derek Corneil, Michel Habib, Christophe Paul. Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations // Proc. 35th International Colloquium on Automata, Languages and Programming (ICALP 2008). — Springer-Verlag, 2008. — Т. 5125. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-70575-8_52.
• Emad Zahedi, Jason Smith. Modular Decomposition of Graphs and the Distance Preserving Property // Discrete Applied Mathematics. — 2018. — Вып. 7.

Ссылки

• Имплементация на языке Perl алгоритма модульного разложения
• Имплементация на языке Java алгоритма модульного разложения
• Имплементация на языке Julia алгоритма модульного разложения