В математической области теории графов , ядро представляет собой понятие , которое описывает поведение графа относительно гомоморфизмов графов .
Определение
График является ядром, если каждый гомоморфизмявляется изоморфизмом , то есть это биекция вершин.
Ядро графа это график такой, что
- Существует гомоморфизм из к ,
- существует гомоморфизм из к , а также
- минимальна с этим свойством.
Два графа называются гомоморфизм эквивалентными или гом-эквивалентными, если они имеют изоморфные ядра.
Примеры
- Любой полный граф - это ядро.
- Цикл нечетной длины является его собственное ядро.
- Каждые два цикла четной длины и, в более общем смысле, каждые два двудольных графа гом-эквивалентны. Ядром каждого из этих графов является полный граф с двумя вершинами K 2 .
Характеристики
У каждого графа есть ядро, которое определяется однозначно с точностью до изоморфизма . Ядро графа G всегда является индуцированный подграф из G . Если а также тогда графики а также обязательно гомоморфно эквивалентны .
Вычислительная сложность
Это NP-полный, чтобы проверить, имеет ли граф гомоморфизм к собственному подграфу, и co-NP-полный, чтобы проверить, является ли граф его собственным ядром (то есть, не существует ли такого гомоморфизма) ( Hell & Nešetřil 1992 ).
Рекомендации
- Годсил, Крис , и Ройл, Гордон . Алгебраическая теория графов. Тексты для выпускников по математике, Vol. 207. Springer-Verlag, Нью-Йорк, 2001. Глава 6, раздел 2.
- Ад, Павол ; Нешетржил, Ярослав (1992), «Ядро графа», Дискретная математика , 109 (1–3): 117–126, DOI : 10.1016 / 0012-365X (92) 90282-K , MR 1192374.
- Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «Предложение 3.5», Разреженность: графы, структуры и алгоритмы , алгоритмы и комбинаторика, 28 , Гейдельберг: Спрингер, стр. 43, DOI : 10.1007 / 978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR 2920058.