Фактор-граф

Фа́ктор-граф $Q$ графа $G$ — граф, вершини якого є блоками розбиття вершин графа $G$ , а блок $B$ суміжний блоку $C$ , якщо деяка вершина в $B$ суміжна деякій вершині в $C$ . Іншими словами, якщо $G$ має набір ребер $E$ і набір вершин $V$ і $R$ — відношення еквівалентності, породжене розбиттям, то фактор-граф має набір вершин $V/R$ і набір ребер $\{([u]_{R},[v]_{R})\mid (u,v)\in E(G)\}$ .

Формальніше, фактор-граф — це фактор-об'єкт у категорії графів. Категорія графів конкретизовна — відображення графа в його множину вершин робить його конкретною категорією, так що його об'єкти можна розглядати як «множини з додатковою структурою», а фактор-граф відповідає графу, породженому на фактор-множині $V/R$ його множиною вершин $V$ . Далі є гомоморфізм графів (фактор-відображення) з графа у фактор-граф, що переводить кожну вершину або ребро в клас еквівалентності, якому він належить. Інтуїтивно, це відповідає «склеюванню» (формально, «ототожненню») вершин і ребер графа.

Приклади

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

Особливі типи фактор-графів

Ущільнення орієнтованого графа є фактор-графом, коли компоненти сильної зв'язності утворюють блоки розбиття. Цю побудову можна використати для отримання спрямованого ациклічного графа з будь-якого орієнтованого графа^[1].

Результатом одного або більше стягувань ребер у неорієнтованому графі $G$ є фактор-графом графа $G$ , в якому блоки є компонентами зв'язності підграфа графа $G$ , утворені стягуванням ребер. Однак блоки розбиття, що приводять до фактор-графа, не обов'язково утворюють зв'язні підграфи.

Якщо $G$ є накривальним графом іншого графа $H$ , то $H$ є фактор-графом графа $G$ . Блоки відповідного розбиття є оберненими образами вершин $H$ при накривальному відображенні. Однак, накривальні відображення мають додаткові вимоги, які в загальному випадку не виконуються для фактор-графів, а саме, що відображення є локальним ізоморфізмом^[2].

Нерідко, особливо під час роботи з періодичними графами^[en], розглядають фактор-графи, вершини яких відповідають орбітам вершин початкового графа під впливом групи автоморфізмів графа (чи якоїсь її підгрупи).

Обчислювальна складність

Якщо дано $n$ -вершинний кубічний граф $G$ і параметр $k$ , визначення, чи можна граф $G$ отримати як фактор-граф планарного графа з $n + k$ вершинами, є NP-повною задачею^[3].

Примітки

↑ Bloem, Gabow, Somenzi, 2006, с. 37–56.
↑ Gardiner, 1974, с. 255–273.
↑ 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 (January). — С. 37–56. — DOI:10.1007/s10703-006-4341-z.
Gardiner A. Antipodal covering graphs // Journal of Combinatorial Theory. — 1974. — Т. 16. — С. 255–273. — (Series B). — 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.

[FOOTNOTEBloem,_Gabow,_Somenzi200637–56-1] Bloem, Gabow, Somenzi, 2006, с. 37–56.

[FOOTNOTEGardiner1974255–273-2] Gardiner, 1974, с. 255–273.

[FOOTNOTEFaria,_de_Figueiredo,_Mendonça200165–83-3] Faria, de Figueiredo, Mendonça, 2001, с. 65–83.

[1]

[2]

[3]