Гомоморфизм графов
Материал из Википедии — свободной encyclopedia
Гомоморфизм графов — это отображение между двумя графами, не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные вершины в смежные.
Гомоморфизмы обобщают различные понятия раскрасок графов и позволяет выражение важных классов задач удовлетворения ограничений, таких как некоторые задачи составления расписаний[англ.] или задачи распределения радиочастот[англ.][1]. Факт, что гомоморфизмы могут быть использованы последовательно, приводит к богатым алгебраическим структурам — предпорядку на графах, дистрибутивной решётке[англ.] и категориям (одна для неориентированных графов и одна для ориентированных графов)[2]. Вычислительная сложность поиска гомоморфизма между заданными графами в общем случае запредельная, но известно много частных случаев, когда задача выполнима за полиномиальное время. Границы между решаемыми и непреодолимыми случаями находятся в области активных исследований[3].