WikiSort.ru - Не сортированное

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

Определение

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

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

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

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

Примеры

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

Свойства

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

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

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

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.