График частных - Quotient graph

В теория графов, а факторный граф Q графа г - граф, вершинами которого являются блоки раздел вершин г и где блок B примыкает к блоку C если какая-то вершина в B смежна с некоторой вершиной из C относительно набора ребер г.[1] Другими словами, если г имеет край E и набор вершин V и р это отношение эквивалентности индуцированный разбиением, то фактор-граф имеет множество вершин V/р и набор ребер {([ты]р, [v]р) | (ты, v) ∈ E(г)}.

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

Примеры

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

Особые виды частного

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

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

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

Если г это покрывающий граф другого графа ЧАС, тогда ЧАС является фактор-графом г. Блоки соответствующего разбиения являются прообразами вершин ЧАС под покрывающей картой. Однако к покрывающим картам предъявляется дополнительное требование, которое не относится к факторам в целом, - чтобы карта была локальным изоморфизмом.[3]

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

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

использованная литература

  1. ^ Сандерс, Питер; Шульц, Кристиан (2013), «Высококачественное разбиение графа», Разделение графа и кластеризация графа, Contemp. Математика, 588, Амер. Математика. Soc., Providence, RI, стр. 1–17, Дои:10,1090 / conm / 588/11700, Г-Н  3074893.
  2. ^ Блум, Родерик; Габоу, Гарольд Н .; Соменци, Фабио (январь 2006 г.), "Алгоритм для компонентного анализа сильной связности в п журналп символические шаги », Формальные методы в системном дизайне, 28 (1): 37–56, Дои:10.1007 / s10703-006-4341-z.
  3. ^ Гардинер, А. (1974), "Антиподальные накрывающие графы", Журнал комбинаторной теории, Серия B, 16: 255–273, Дои:10.1016/0095-8956(74)90072-0, Г-Н  0340090.
  4. ^ Faria, L .; de Figueiredo, C.MH .; Мендонса, К. Ф. Х. (2001), «Число расщеплений является NP-полным», Дискретная прикладная математика, 108 (1–2): 65–83, Дои:10.1016 / S0166-218X (00) 00220-1, Г-Н  1804713.