Ядро графа — это понятие, описывающее поведение графа в отношении гомоморфизмов графа.
Определение Граф является ядром, если любой гомоморфизм является изоморфизмом, то есть это биекция вершин .
Ядро графа — это граф , такой, что существует гомоморфизм из в существует гомоморфизм из в с этими свойствами граф минимален.
Говорят, что два графа гомоморфно эквивалентны, если они обладают изоморфными ядрами.
Ядро графа, если оно существует, является одновременно минимальным внешне и максимальным внутренне устойчивым множеством ее вершин.
Примеры Любой полный граф является ядром. Цикл нечётного порядка является своим же ядром. Любые два цикла чётного порядка, и более обще, любые два двудольных графа гомоморфно эквивалентны. Ядром любого такого графа является граф K2. Ядро графа, представляющего задачу потребительского выбора, является решением задачи выбора по Нейману-Моргенштерну. Если граф не содержит циклов, а множество предпочтений транзитивно, то ядро такого графа дает множество недоминируемых альтернатив.
Свойства Любой граф имеет единственное (с точностью до изоморфизма) ядро. Ядро графа G всегда является порождённым подграфом графа G. Если и , то графы и обязательно гомоморфно эквивалентны.
Вычислительная сложность Задача проверки, имеет ли граф гомоморфизм в собственный подграф, является NP-полной, и ко-NP-полной задачей является проверка, является ли граф своим собственным ядром (то есть что не существует гомоморфизмов в собственные подграфы).
Примечания
Литература
.
Категория:Объекты теории графов