?

Log in

No account? Create an account

Previous Entry | Next Entry


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

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

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

Profile

vestniksveta
Андрей Покатов
Website

Latest Month

August 2019
S M T W T F S
    123
45678910
11121314151617
18192021222324
25262728293031

Tags

Powered by LiveJournal.com
Designed by yoksel