Фактор-граф

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

Приклади

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

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

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

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

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

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

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

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

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

Література

• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття