Ядро (теорія графів)

Ядро графу — це поняття, яке описує поведінку графу відносно гомоморфізмів графу.

Визначення

Граф ${\displaystyle C}$ є ядром, якщо будь-який гомоморфізм ${\displaystyle f:C\to C}$ є ізоморфізмом, тобто це бієкція вершин ${\displaystyle C}$.

Ядро графу ${\displaystyle G}$ — це граф ${\displaystyle C}$, такий, що

1. існує гомоморфізм з ${\displaystyle G}$ в ${\displaystyle C}$
2. існує гомоморфізм з ${\displaystyle C}$ в ${\displaystyle G}$
3. з цими властивостями граф ${\displaystyle C}$ мінімальний.

Кажуть, що два графи гомоморфно еквівалентні, якщо вони мають ізоморфні ядра.

Приклади

• Будь-який повний граф є ядром.
• Цикл непарного порядку є власним ядром.
• Будь-які два цикли парного порядку, і, загальніше, будь-які два двочасткових графи гомоморфно еквівалентні. Ядром будь-якого такого графу є повний граф K₂ з двома вершинами.

Властивості

Будь-який граф має єдине (з точністю до ізоморфізму) ядро. Ядро графу ${\displaystyle G}$ завжди є породженим підграфом графу ${\displaystyle G}$. якщо ${\displaystyle G\to H}$ і ${\displaystyle H\to G}$, То графи ${\displaystyle G}$ і ${\displaystyle H}$ обов'язково гомоморфно еквівалентні.

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

Задача перевірки, чи має граф гомоморфізм у власний підграф, є NP-повною, і co-NP-повною задачею є перевірка, чи є граф власним ядром (тобто, що не існує гомоморфізмів у власні підграфи).

Примітки

1. Hell, Nešetřil, 1992.

Література

• Chris Godsil, Gordon Royle. Chapter 6 section 2 // Algebraic Graph Theory. — New York : Springer-Verlag, 2001. — Т. 207. — (Graduate Texts in Mathematics) — .
• Pavol Hell, Jaroslav Nešetřil.  // . — 1992. — Т. 109, вип. 1-3 (18 червня). — С. 117–126. — DOI:10.1016/0012-365X(92)90282-K.
• Jaroslav Nešetřil, Patrice Ossona de Mendez. Proposition 3.5 // Sparsity: Graphs, Structures, and Algorithms. — Heidelberg : Springer, 2012. — Т. 28. — С. 43. — (Algorithms and Combinatorics) — . — DOI:10.1007/978-3-642-27875-4..