Ядро графу — це поняття, яке описує поведінку графу відносно гомоморфізмів графу.
Визначення Граф є ядром, якщо будь-який гомоморфізм є ізоморфізмом, тобто це бієкція вершин .
Ядро графу — це граф , такий, що
існує гомоморфізм з в існує гомоморфізм з в з цими властивостями граф мінімальний.
Кажуть, що два графи гомоморфно еквівалентні, якщо вони мають ізоморфні ядра.
Приклади Будь-який повний граф є ядром. Цикл непарного порядку є власним ядром. Будь-які два цикли парного порядку, і, загальніше, будь-які два двочасткових графи гомоморфно еквівалентні. Ядром будь-якого такого графу є повний граф K2 з двома вершинами.
Властивості Будь-який граф має єдине (з точністю до ізоморфізму) ядро. Ядро графу завжди є породженим підграфом графу . якщо і , То графи і обов'язково гомоморфно еквівалентні.
Обчислювальна складність Задача перевірки, чи має граф гомоморфізм у власний підграф, є NP-повною, і co-NP-повною задачею є перевірка, чи є граф власним ядром (тобто, що не існує гомоморфізмів у власні підграфи).
Примітки
Література
.