График частных
В теории графов факторграф , Q графа G — это граф, вершины которого являются блоками разбиения вершин графа G и где блок B смежн с блоком C если некоторая вершина в B смежна с некоторой вершиной в C относительно к ребру G . [1] Другими словами, если G имеет множество ребер E и множество вершин V , а R — отношение эквивалентности , индуцированное разбиением, то факторграф имеет множество вершин V / R и множество ребер {([ u ] R , [ v ] R ) | ( ты , v ) ∈ E ( G )}.
Более формально, факторграф — это факторобъект в категории графов. Категория графов конкретизируема - сопоставление графа с его набором вершин делает его конкретной категорией - поэтому его объекты можно рассматривать как «множества с дополнительной структурой», а факторграф соответствует графу, индуцированному на фактормножестве V / R своего множества вершин V . Кроме того, существует гомоморфизм графа ( факторное отображение ) графа в факторграф, отправляющий каждую вершину или ребро в класс эквивалентности, которому оно принадлежит. Интуитивно это соответствует «склеиванию» (формально «отождествлению») вершин и ребер графа.
Примеры
[ редактировать ]Граф тривиально является факторграфом самого себя (каждый блок разбиения представляет собой одну вершину), а граф, состоящий из одной точки, является факторграфом любого непустого графа (разбиение, состоящее из одного блока всех вершин ). Простейший нетривиальный факторграф получается путем идентификации двух вершин ( идентификация вершин ); если вершины соединены, это называется сжатием ребер .
Специальные виды частного
[ редактировать ]
Конденсация ориентированного графа представляет собой факторграф, в котором сильно связные компоненты образуют блоки разбиения. Эту конструкцию можно использовать для получения ориентированного ациклического графа из любого ориентированного графа. [2]
Результатом одного или нескольких сжатий ребер в неориентированном графе G является фактор G , в котором блоки являются связными компонентами подграфа G, образованного сжатыми ребрами. Однако в более общем плане для частных блоки раздела, порождающие фактор, не обязательно образуют связные подграфы.
Если G — покрывающий граф другого графа H , то H — факторграф G. графа Блоки соответствующего разбиения являются прообразами вершин графа H при отображении покрытия. Однако к покрывающим картам предъявляется дополнительное требование, которое в более общем случае не относится к факторам: отображение должно быть локальным изоморфизмом. [3]
Вычислительная сложность
[ редактировать ]Это NP-полный , учитывая n -вершинный кубический граф G и параметр k , чтобы определить, может ли G быть получен как фактор планарного графа с n + k вершинами. [4]
Ссылки
[ редактировать ]- ^ Сандерс, Питер ; Шульц, Кристиан (2013), «Высококачественное разбиение графов», Разбиение графов и кластеризация графов , Contemp. Матем., вып. 588, амер. Математика. Soc., Провиденс, Род-Айленд, стр. 1–17, номер документа : 10.1090/conm/588/11700 , MR 3074893 .
- ^ Блум, Родерик; Габоу, Гарольд Н .; Соменци, Фабио (январь 2006 г.), «Алгоритм анализа сильно связанных компонентов за n log n символьных шагов», Formal Methods in System Design , 28 (1): 37–56, doi : 10.1007/s10703-006-4341-z , S2CID 11747844 .
- ^ Гардинер, А. (1974), «Антиподальные накрывающие графы», Журнал комбинаторной теории , серия B, 16 (3): 255–273, doi : 10.1016/0095-8956(74)90072-0 , MR 0340090 .
- ^ Фариа, Л.; де Фигейредо, CMH; Мендонса, CFX (2001), «Число расщепления NP-полное», Discrete Applied Mathematics , 108 (1–2): 65–83, doi : 10.1016/S0166-218X(00)00220-1 , MR 1804713 .