WikiDer > Ядро (теория графов) - Википедия

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

Определение

График ${ 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₂.

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

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

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

это НП-полный чтобы проверить, имеет ли граф гомоморфизм к собственному подграфу, и совместно NP-полный, чтобы проверить, является ли граф его собственным ядром (то есть, существует ли такой гомоморфизм) (Ад и Нешетржил 1992).

Рекомендации

• Годсил, Крис, и Ройл, Гордон. Алгебраическая теория графов. Тексты для выпускников по математике, Vol. 207. Springer-Verlag, New York, 2001. Глава 6, раздел 2.
• Ад, Павол; Нешетржил, Ярослав (1992), «Ядро графа», Дискретная математика, 109 (1–3): 117–126, Дои:10.1016 / 0012-365X (92) 90282-К, МИСТЕР 1192374.
• Нешетржил, Ярослав; Оссона де Мендес, Патрис (2012), «Предложение 3.5», Разреженность: графики, структуры и алгоритмы, Алгоритмы и комбинаторика, 28, Гейдельберг: Springer, стр. 43, Дои:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, МИСТЕР 2920058.