Факторграф
Факторграф Q графа G — граф, вершины которого являются блоками разбиения вершин графа G, а блок B смежен блоку C, если некоторая вершина в B смежна некоторой вершине в CШаблон:Sfn. Другими словами, если G имеет набор рёбер E и набор вершин V и R является отношением эквивалентности, порождённым разбиением, то факторграф имеет набор вершин V/R и набор рёбер .
Более формально, факторграф — это факторобъект в категории графов. Категория графов конкретизируема — отображение графа в его множество вершин делает его конкретной категорией, так что его объекты можно рассматривать как «множества с дополнительной структурой», а факторграф соответствует графу, порождённому на фактормножестве V/R его множеством вершин V. Далее имеется гомоморфизм графов (факторотображение) из графа в факторграф, переводящее каждую вершину или ребро в класс эквивалентности, которому он принадлежит. Интуитивно, это соответствует «склеиванию» (формально, «отождествлению») вершин и рёбер графа.
Примеры
Граф тривиально является факторграфом самого себя (каждый блок разбиения является отдельной вершиной), а граф, состоящий из отдельной точки, является факторграфом любого непустого графа (разбиение состоит из блока, содержащего все вершины). Простейший нетривиальный факторграф получается склеиванием двух вершин (отождествление вершин), если же две вершины смежны, это называется стягиванием ребра.
Специальные типы факторграфов
Конденсация ориентированного графа является факторграфом, когда компоненты сильной связности образуют блоки разбиения. Это построение может быть использовано для получения направленного ациклического графа из любого ориентированного графаШаблон:Sfn.
Результат одного или более стягивания ребра в неориентированном графе G является факторграфом графа G, в котором блоки являются связными компонентами подграфа графа G образованные стягиванием рёбер. Однако блоки разбиения, приводящие к факторграфу, не обязательно образуют связные подграфы.
Если G является накрывающим графом другого графа H, то H является факторграфом графа G. Блоки соответствующего разбиения являются обратными образами вершин H при накрывающем отображении. Однако накрывающие отображения имеют дополнительные требования, которые в общем случае не выполняются для факторграфов, а именно, что отображение является локальным изоморфизмомШаблон:Sfn.
Нередко, особенно при работе с Шаблон:Iw, рассматривают факторграфы, вершины которых соответствуют орбитам вершин исходного графа под действием группы автоморфизмов графа (или какой-то её подгруппе).
Вычислительная сложность
Если дан Шаблон:Mvar-вершинный кубический граф G и параметр Шаблон:Mvar, определение, может ли граф G быть получен как факторграф планарного графа с Шаблон:Math вершинами, является NP-полной задачейШаблон:Sfn.