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

Ядро графа — это понятие, описывающее поведение графа в отношении гомоморфизмов графа.

Определение

Граф $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-полной, и ко-NP-полной задачей является проверка, является ли граф своим собственным ядром (то есть что не существует гомоморфизмов в собственные подграфы).