Гомоморфізм графів
відображення між двома графами, що не порушує структури / З Вікіпедії, безкоштовно encyclopedia
Шановний Wikiwand AI, Давайте зробимо це простіше, відповівши на ключові запитання:
Чи можете ви надати найпопулярніші факти та статистику про Гомоморфізм графів?
Підсумуйте цю статтю для 10-річної дитини
Гомоморфізм графів — це відображення між двома графами, що не порушує структури. Конкретніше, це відображення між наборами вершин двох графів, яке відображає суміжні вершини в суміжні.
Гомоморфізми узагальнюють різні поняття розфарбовування графів і дозволяють формулювати важливі класи задач виконання обмежень, таких як деякі задачі складання розкладів[en] або задачі розподілу радіочастот[en][1]. Факт, що гомоморфізми можна використати послідовно, приводить до багатих алгебричних структур — передпорядку на графах, дистрибутивної ґратки і категорій (одна для неорієнтованих графів і одна для орієнтованих графів)[2]. Обчислювальна складність пошуку гомоморфізму між заданими графами в загальному випадку позамежна, але відомо багато окремих випадків, коли задача здійсненна за поліноміальний час. Межі між розв'язними і нездоланними випадками є галуззю активних досліджень[3].