1)Предложите алгоритм, который строит раскраску вершин с числом цветов удовлетворяющим неравенству X(G) <= max deg(G) + 1. Где X(G) - хроматическое число, а max deg(G) - степень максимальной вершины графа G. 2)Предложите алгоритм проверки двудольности графа, использующий число элементарных операций пропорциональное величине |E| + |V|, число ребер плюс число вершин. Подойдет ли под вторую задачу алгоритм поиска в ширину? задан 9 Июн '19 23:53 sedated8 |
Ответ на первую задачу нашел. Подходит жадный алгоритм раскраски графа
Тут вроде бы всё бесхитростно, то есть применяются самые обычные для этих случаев алгоритмы. Правда, при постановке таких вопросов, где оценивается число операций, всегда желательно точное описание того, в каком виде представлен граф. В первой задаче нумеруем вершины и последовательно их раскрашиваем. Цветов всегда хватает, так как очередная вершина соединена не более чем с d предыдущими, и тогда d+1 цвета достаточно. Во второй задаче -- разметка вершин по типу 0 или 1 с последующей проверкой правильности раскраски.