Фактор-граф

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

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

Приклади

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

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

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

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

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

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

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

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

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

Примітки

1. Bloem, Gabow, Somenzi, 2006, с. 37–56.
2. Gardiner, 1974, с. 255–273.
3. 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.