Фактор-граф

Фа́ктор-граф $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$. Далі є гомоморфізм графів (фактор-відображення) з графа у фактор-граф, що переводить кожну вершину або ребро в клас еквівалентності, якому він належить. Інтуїтивно, це відповідає «склеюванню» (формально, «ототожненню») вершин і ребер графа.

Приклади

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

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

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

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

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

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

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

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

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

Література

• 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.