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

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

Визначення

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

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

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

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

Приклади

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

Властивості

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

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

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

Література

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