|
1)Предложите алгоритм, который строит раскраску вершин с числом цветов удовлетворяющим неравенству X(G) <= max deg(G) + 1. Где X(G) - хроматическое число, а max deg(G) - степень максимальной вершины графа G. 2)Предложите алгоритм проверки двудольности графа, использующий число элементарных операций пропорциональное величине |E| + |V|, число ребер плюс число вершин. Подойдет ли под вторую задачу алгоритм поиска в ширину? задан 9 Июн 23:53 
sedated8 |
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
9 Июн 23:53
показан
71 раз
обновлен
10 Июн 0:50
Связанные исследования
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Ответ на первую задачу нашел. Подходит жадный алгоритм раскраски графа
Тут вроде бы всё бесхитростно, то есть применяются самые обычные для этих случаев алгоритмы. Правда, при постановке таких вопросов, где оценивается число операций, всегда желательно точное описание того, в каком виде представлен граф. В первой задаче нумеруем вершины и последовательно их раскрашиваем. Цветов всегда хватает, так как очередная вершина соединена не более чем с d предыдущими, и тогда d+1 цвета достаточно. Во второй задаче -- разметка вершин по типу 0 или 1 с последующей проверкой правильности раскраски.