vestniksveta

Без каких либо разьяснений сверх сказанного. Кто понимает научные априори, поймет, а кто не понимает, тому нет смысла вникать.

Являются частым видом гомомоморфизмов, который отражает определение и многие свойства накрытия в топологии. Они определяются как сюръективные гомомоморфизмы, которые локально биективны, то есть является биекцией в окрестности каждой вершины. Функция, отображающая V0 и V1 в V исходного графа является гомоморфизмом и накрывыающим отображением.

Задача о гомоморфизме с фиксированным графом H с правой стороны каждого экземпляра называется задачей H-раскраски. Когда H является полным графом Kk, это задача k-раскраски графа, которая разрешима за полиномиальное время для k=0, 1, 2 и NP-полна в других случаях. В частности, возможность K2-раскраски графа G эквивалентна двудольности графа G, что можно проверить за линейное время.