Факторграф

Факторграф Q графа G — граф, вершины которого являются блоками разбиения вершин графа G, а блок B смежен блоку C, если некоторая вершина в B смежна некоторой вершине в C[1]. Другими словами, если G имеет набор рёбер E и набор вершин V и R является отношением эквивалентности, порождённым разбиением, то факторграф имеет набор вершин V/R и набор рёбер .

Более формально, факторграф — это факторобъект в категории графов. Категория графов конкретизируема — отображение графа в его множество вершин делает его конкретной категорией, так что его объекты можно рассматривать как «множества с дополнительной структурой», а факторграф соответствует графу, порождённому на фактормножестве V/R его множеством вершин V. Далее имеется гомоморфизм графов (факторотображение) из графа в факторграф, переводящее каждую вершину или ребро в класс эквивалентности, которому он принадлежит. Интуитивно, это соответствует «склеиванию» (формально, «отождествлению») вершин и рёбер графа.

Примеры

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

Специальные типы факторграфов
Ориентированный граф (синий и чёрный цвета) и его конденсация (жёлтый цвет). Компоненты сильной связности (подмножества синих вершин внутри каждой жёлтой вершины) образуют блоки разбиения.

Конденсация ориентированного графа является факторграфом, когда компоненты сильной связности образуют блоки разбиения. Это построение может быть использовано для получения направленного ациклического графа из любого ориентированного графа[2].

Результат одного или более стягивания ребра в неориентированном графе G является факторграфом графа G, в котором блоки являются связными компонентами подграфа графа G образованные стягиванием рёбер. Однако блоки разбиения, приводящие к факторграфу, не обязательно образуют связные подграфы.

Если G является накрывающим графом другого графа H, то H является факторграфом графа G. Блоки соответствующего разбиения являются обратными образами вершин H при накрывающем отображении. Однако накрывающие отображения имеют дополнительные требования, которые в общем случае не выполняются для факторграфов, а именно, что отображение является локальным изоморфизмом[3].

Нередко, особенно при работе с периодическими графами, рассматривают факторграфы, вершины которых соответствуют орбитам вершин исходного графа под действием группы автоморфизмов графа (или какой-то её подгруппе).

Вычислительная сложность

Если дан n-вершинный кубический граф G и параметр k, определение, может ли граф G быть получен как факторграф планарного графа с n + k вершинами, является NP-полной задачей[4].

Примечания
  1. Sanders, Schulz, 2013, с. 1–17.
  2. Bloem, Gabow, Somenzi, 2006, с. 37–56.
  3. Gardiner, 1974, с. 255–273.
  4. Faria, de Figueiredo, Mendonça, 2001, с. 65–83.

Литература
  • Peter Sanders, Christian Schulz. High quality graph partitioning // Graph partitioning and graph clustering. — Amer. Math. Soc., Providence, RI, 2013. — Т. 588. — С. 1–17. — (Contemp. Math.). — doi:10.1090/conm/588/11700.
  • Roderick Bloem, Harold N. Gabow, Fabio Somenzi. An algorithm for strongly connected component analysis in n log n symbolic steps // Formal Methods in System Design. — 2006. — Январь (т. 28, вып. 1). — С. 37–56. — doi:10.1007/s10703-006-4341-z.
  • Gardiner A. Antipodal covering graphs // Journal of Combinatorial Theory. — 1974. — Т. 16. — С. 255–273. — doi:10.1016/0095-8956(74)90072-0.
  • Faria L., de Figueiredo C. M. H., Mendonça C. F. X. Splitting number is NP-complete // Discrete Applied Mathematics. — 2001. — Т. 108, вып. 1—2. — С. 65–83. — doi:10.1016/S0166-218X(00)00220-1.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.