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

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

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

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

Модули [ править ]

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

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

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

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

• вершины нельзя отличить от любой вершины в , то есть , либо примыкает к обоим и или ни рядом , ни .${\ displaystyle M}$${\ Displaystyle V \ обратная косая черта M}$${\ Displaystyle \ forall u, v \ in M, \ forall x \ in V \ обратная косая черта 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}$является сильным модулем графа, если он не перекрывает ни один другой модуль из : module of , or or or .${\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)}$

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

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

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

Первый полиномиальный алгоритм для вычисления дерева модульной декомпозиции графа был опубликован в 1972 году (James, Stanton & Cowan, 1972), и теперь доступны линейные алгоритмы (McConnell & Spinrad 1999, Tedder et al. 2007, Cournier & Habib 1994).

Обобщения [ править ]

Модульное разложение ориентированных графов может быть выполнено за линейное время ( McConnell & de Montgolfier 2005 ).

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

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