Оптимальные каркасы и пути

Задачи

8.1. Найдите хроматическое число графов , , , .

8.2. Найдите хроматическое число графа 1) ; 2) ; 3) .

8.3. Примените алгоритм раскрашивания, основанный на дереве решений, к графу из

задачи 6.9.

8.4. Примените алгоритм последовательной раскраски к графу, изображенному на

рисунке, если вершины упорядочиваются а) по возрастанию номеров; б) по убыванию

номеров.

8.5. Для каких из следующих графов алгоритм последовательной раскраски дает точный

результат при любом упорядочении вершин: , , , ,?

8.6. Найдите хроматический индекс графов , , ,, , .

В задаче об оптимальном каркасе (она известна также как задача о кратчайшем остовном дереве) задан граф , каждому ребру которого приписано число, называемое весом ребра. Вес ребра будем обозначать через . Вес множества определяется как сумма весов составляющих его ребер. Требуется в графе G найти каркас минимального веса. Для решения этой задачи известно несколько алгоритмов. Рассмотрим два из них.