Гомоморфная эквивалентность

В математике теории графов два графа, G и H , называются гомоморфно эквивалентными, если существует гомоморфизм графов. $f\colon G\to H$ и гомоморфизм графов $g\colon H\to G$ . Пример использования этого понятия: любые два ядра графа гомоморфно эквивалентны.

Гомоморфная эквивалентность также возникает в теории баз данных . Учитывая схему базы данных , два экземпляра I и J в ней называются гомоморфно эквивалентными, если существует гомоморфизм экземпляров. $f\colon I\to J$ и экземплярный гомоморфизм $g\colon J\to I$ .

Решение о том, гомоморфно эквивалентны ли два графа, является NP-полным . ^[1]

Фактически для любой категории C можно определить гомоморфную эквивалентность. Он используется в теории доступных категорий , где «слабая универсальность» — лучшее, на что можно надеяться с точки зрения классов инъективности; видеть ^[2]

Ссылки

^ Флум, Дж.; Гроэ, М. (1 мая 2006 г.). Параметризованная теория сложности . Springer Science & Business Media. п. 330. ИСБН 978-3-540-29953-0 .
^ Адамек и Росицки, «Локально презентабельные и доступные категории».

Эта теории графов статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .

[Flum_Grohe_2006_p.-1] Флум, Дж.; Гроэ, М. (1 мая 2006 г.). Параметризованная теория сложности . Springer Science & Business Media. п. 330. ИСБН 978-3-540-29953-0 .

[2] Адамек и Росицки, «Локально презентабельные и доступные категории».

[1]

[2]