Фактор-граф

Фа́ктор-граф ${\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].

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

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