1)Предложите алгоритм, который строит раскраску вершин с числом цветов удовлетворяющим неравенству X(G) <= max deg(G) + 1. Где X(G) - хроматическое число, а max deg(G) - степень максимальной вершины графа G. 2)Предложите алгоритм проверки двудольности графа, использующий число элементарных операций пропорциональное величине |E| + |V|, число ребер плюс число вершин. Подойдет ли под вторую задачу алгоритм поиска в ширину?

задан 9 Июн 23:53

Ответ на первую задачу нашел. Подходит жадный алгоритм раскраски графа

(10 Июн 0:20) sedated8

Тут вроде бы всё бесхитростно, то есть применяются самые обычные для этих случаев алгоритмы. Правда, при постановке таких вопросов, где оценивается число операций, всегда желательно точное описание того, в каком виде представлен граф. В первой задаче нумеруем вершины и последовательно их раскрашиваем. Цветов всегда хватает, так как очередная вершина соединена не более чем с d предыдущими, и тогда d+1 цвета достаточно. Во второй задаче -- разметка вершин по типу 0 или 1 с последующей проверкой правильности раскраски.

(10 Июн 0:50) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,354
×1,270
×480

задан
9 Июн 23:53

показан
61 раз

обновлен
10 Июн 0:50

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru