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

Граф ${\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].