[В работе] Конспект лекции по раскраскам
Жадная раскраска в теории графов — раскраска вершин неориентированного графа , созданная жадным алгоритмом , который проходит вершины графа в некоторой предопределённой последовательности и назначает каждой вершине первый доступный цвет. Жадные алгоритмы, в общем случае, не дают минимально возможное число цветов, однако они используются в математике в качестве техники доказательств других результатов, относящихся к раскраске, а также в компьютерных программах для получения раскраски с небольшим числом цветов. Корона полный двудольный граф K n , n с удалёнными рёбрами совершенного паросочетания является особенно плохим случаем для жадного алгоритма — если в последовательности вершин поместить подряд две вершины, принадлежащие удалённому ребру из паросочетания, жадный алгоритм использует n цветов, в то время, как оптимальным числом для такого графа является два цвета. Существуют также графы, для которых с большой вероятностью случайно выбранная последовательность вершин приведёт к использованию числа цветов, существенно большему минимально необходимого [ 1 ]. Таким образом, очень важно осторожно выбирать последовательность, в которой вершины проходятся жадным алгоритмом.
Регистрация Выслать повторно письмо для активации Что даёт регистрация на форуме? Форум на Исходниках. RU Программирование Алгоритмы Нравится ресурс? При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями. Приводимые фрагменты исходного кода старайтесь выделять тегами code
![[В работе] Конспект лекции по раскраскам [МОЭВМ Вики [aux-cond.ru]]](https://i.ytimg.com/vi/qoIEi0KA5Xc/sddefault.jpg "Для продолжения работы вам необходимо ввести капчу")
Ваши алгоритмы не работают на графах с одинаковыми степенями вершин. Собственно успешность алгоритма зависит от того с какой вершины начать. Проверял на других графах в которых степени у вершин были разные - выдавал верный результат. Дай 10! Раскраска графа.
