Упражнения

10.1. Найти хроматические числа для графов:

а) К₆

б) К_3,5

в) Е²

г) Е³

10.2. Найти независимые множества вершин, вершинное число независимости и хроматическое число графа G:

а) б) в)

10.3. Найти хроматическое число графа, заданного матрицей смежности:

10.4. Используя точный алгоритм раскрашивания, раскрасить вершины графов из задач 10.2, 10.3.

10.5. Построить граф с хроматическим числом, равным:

а) 4

б) 5

в) 3.

10.6. Найти толщину графа:

Варианты контрольных работ