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

Эта статья о гомоморфизмах графов. Информацию о подграфе, в котором все вершины имеют высокую степень, см. в разделе k-core . Информацию об объединении всех максимальных паросочетаний см. в разделе « Разложение Дулмэджа – Мендельсона» .

В математической области теории графов ядро ​​— это понятие, описывающее поведение графа относительно гомоморфизмов графов .

Определение

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

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

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

Два графа называются гомоморфно-эквивалентными или hom-эквивалентными, если они имеют изоморфные ядра.

Примеры

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

Характеристики

Каждый конечный граф имеет ядро, которое определяется однозначно с точностью до изоморфизма . Ядро графа G является индуцированным подграфом G . всегда Если $G\to H$ и $H\to G$ тогда графики $G$ и $H$ обязательно гомоморфно эквивалентны .

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

Он NP-полн , чтобы проверить, имеет ли граф гомоморфизм правильному подграфу, и ко-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, Гейдельберг: Springer, с. 43, номер домена : 10.1007/978-3-642-27875-4 , ISBN  978-3-642-27874-7 , МР   2920058 .