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

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

Определение

Граф [math]\displaystyle{ C }[/math] является ядром, если любой гомоморфизм [math]\displaystyle{ f:C \to C }[/math] является изоморфизмом, то есть это биекция вершин [math]\displaystyle{ C }[/math].

Ядро графа [math]\displaystyle{ G }[/math] — это граф [math]\displaystyle{ C }[/math], такой, что

1. существует гомоморфизм из [math]\displaystyle{ G }[/math] в [math]\displaystyle{ C }[/math]
2. существует гомоморфизм из [math]\displaystyle{ C }[/math] в [math]\displaystyle{ G }[/math]
3. с этими свойствами граф [math]\displaystyle{ C }[/math] минимален.

Говорят, что два графа гомоморфно эквивалентны, если они обладают изоморфными ядрами.

Примеры

• Любой полный граф является ядром.
• Цикл нечётного порядка является своим же ядром.
• Любые два цикла чётного порядка, и более обще, любые два двудольных графа гомоморфно эквивалентны. Ядром любого такого графа является полный граф K₂ с двумя вершинами.

Свойства

Любой граф имеет единственное (с точностью до изоморфизма) ядро. Ядро графа G всегда является порождённым подграфом графа G. Если [math]\displaystyle{ G \to H }[/math] и [math]\displaystyle{ H \to G }[/math], то графы [math]\displaystyle{ G }[/math] и [math]\displaystyle{ H }[/math] обязательно гомоморфно эквивалентны.

Вычислительная сложность

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