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

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

ОпределениеПравить

Граф $C$$C$  является ядром, если любой гомоморфизм $f:C\to <!--\; \to \; -->C$$f:C\to C$  является изоморфизмом, то есть это биекция вершин $C$$C$ .

Ядро графа $G$$G$  — это граф $C$$C$ , такой, что

1. существует гомоморфизм из $G$$G$  в $C$$C$ 
2. существует гомоморфизм из $C$$C$  в $G$$G$ 
3. с этими свойствами граф $C$$C$  минимален.

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

ПримерыПравить

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

СвойстваПравить

Любой граф имеет единственное (с точностью до изоморфизма) ядро. Ядро графа G всегда является порождённым подграфом графа G. Если $G\to <!--\; \to \; -->H$$G\to H$  и $H\to <!--\; \to \; -->G$$H\to G$ , то графы $G$$G$  и $H$$H$  обязательно гомоморфно эквивалентны.

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

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