[изифраг] теорема Шеннона о рёберной раскраске для n=2k

evor

как доказывается, подскажите?
кто хочет, может рассказать и для n=2k+1, прочитаю, просвещусь)

antill

хз, но глянь, может тут есть:
версия рабочая, по крайней мере, когда я читал распечатку, то нашел несколько опечаток
так что аккуратнее проверь доказательство, если найдешь его там

evor

спасибо, но мне нужна следующая теорема
colours <= [3*n/2], где n - максимальная степень вершин
очевидно, что можно перейти к регулярным графам со степенью вершин n

evor

чото пичаль какая-то(

antill

ну хз... может, тупо зайти на кафедру дискретной математики на мехмате и там спросить?
Оставить комментарий
Имя или ник:
Комментарий: