В теории графов фактор -граф Q графа G — это граф, вершины которого являются блоками разбиения вершин графа G , и где блок B смежный с блоком 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 является графом покрытия другого графа H , то H является графом факторизации G . Блоки соответствующего разбиения являются обратными образами вершин H при отображении покрытия. Однако, отображения покрытия имеют дополнительное требование, которое не является верным в более общем случае для факторов, а именно, что отображение должно быть локальным изоморфизмом. [3]
Задача NP-полна , если задан кубический граф G с n вершинами и параметр k , и можно ли получить G как частное планарного графа с n + k вершинами. [4]