В теории графов , A фактор - граф Q графа G представляет собой график, вершинами которого являются блоками разбиения вершин G , и где блок В примыкает к блоку C , если некоторая вершина в B находится рядом с некоторой вершиной в C по отношению на множество ребер G . [1] Другими словами, если G имеет множество ребер E и множество вершин V и R - отношение эквивалентности, индуцированное разбиением, то фактор-граф имеет множество вершин V/ R и множество ребер {([ u ] R , [ v ] R ) | ( u , v ) ∈ E ( G )}.
Более формально фактор-граф - это фактор-объект в категории графов. Категория графов конкретизируется - отображение графа на его множество вершин делает его конкретной категорией, поэтому его объекты можно рассматривать как «множества с дополнительной структурой», а фактор-граф соответствует графу, индуцированному на фактормножестве V / R его множество вершин V . Кроме того, существует гомоморфизм графа ( фактор-карта ) от графа к фактор-графу, отправляющий каждую вершину или ребро в класс эквивалентности, которому они принадлежат. Интуитивно это соответствует «склеиванию» (формально «отождествлению») вершин и ребер графа.
Примеры
Граф тривиально является фактор-графом самого себя (каждый блок разбиения представляет собой единственную вершину), а граф, состоящий из одной точки, является фактор-графом любого непустого графа (разбиение, состоящее из единственного блока всех вершин ). Простейший нетривиальный фактор-граф - это граф, полученный путем идентификации двух вершин ( идентификация вершин ); если вершины соединены, это называется стягиванием ребер .
Особые виды частного
Конденсации ориентированного графа является фактор - граф , где сильно связанные компоненты образуют блоки раздела. Эту конструкцию можно использовать для получения ориентированного ациклического графа из любого ориентированного графа. [2]
Результатом одного или нескольких сжатий ребер в неориентированном графе G является фактор G , в котором блоки являются связными компонентами подграфа G, образованного сжатыми ребрами. Однако для частных в более общем смысле блоки разбиения, порождающие частное, не обязательно должны образовывать связанные подграфы.
Если G является покрытием графа другого графа Н , то Н является фактором графом G . Блоки соответствующего разбиения являются прообразами вершин H при отображении покрытия. Однако к покрывающим картам предъявляется дополнительное требование, которое не относится к факторам в целом, - чтобы карта была локальным изоморфизмом. [3]
Вычислительная сложность
Он является NP-полным , учитывая кубический граф G с n- вершинами и параметр k , чтобы определить, может ли G быть получена как фактор планарного графа с n + k вершинами. [4]
Рекомендации
- ^ Сандерс, Питер ; Шульц, Кристиан (2013), «Высококачественное разбиение графа», « Разделение графов и кластеризация графов» , Contemp. Матем., 588 , амер. Математика. Soc., Providence, RI, стр. 1–17, DOI : 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.
- ^ Гардинер, А. (1974), "антиподальное покрытие графов", Журнал комбинаторной теории , серии B, 16 : 255-273, DOI : 10,1016 / 0095-8956 (74) 90072-0 , MR 0340090.
- ^ Faria, L .; де Фигейредо, CMH; Мендоса, CFX (2001), "номер Расщепление является NP-полной", дискретное прикладной математики , 108 (1-2): 65-83, DOI : 10.1016 / S0166-218X (00) 00220-1 , MR 1804713.