21.2.7 Вопросы для контроля к п. 21.2.4…21.2.6
Поясните понятие внутренней устойчивости вершин графа.
Число внутренней устойчивости графа – что это такое и как оно обозначается?
Приведите алгоритм определения внутренне устойчивых множеств вершин графа.
Что такое вершинная раскраска графа? Приведите алгоритм определения минимального числа красок для такой раскраски.
Что такое хроматическое число графа и какие оценки существуют для него?
На чем основан приближенный алгоритм нахождения максимального независимого множества вершин графа?
Примените простейший алгоритм последовательной раскраски вершин графа на примере графа C5. Сколько потребовалось красок? Сколько потребуется красок для раскраски графаC6? Какой вывод можно сделать о раскраске графов–циклов?
Что такое хроматический класс графа и какие оценки существуют для него?
- 21 Лекция №20. Устойчивость графов
- 21.1 Ключевые вопросы
- 21.2 Текст лекции
- 21.2.1 Внешне устойчивые множества вершин графа
- Алгоритм определения внешне устойчивых множеств вершин
- 21.2.2 Вершинная база
- 19.2.3Вопросы для контроля к п. 19.2.1 и 19.2.2
- 21.2.4 Внутренняя устойчивость графа
- 21.2.5 Раскраска вершин графа
- 21.2.6 Реберная раскраска графа
- 21.2.7 Вопросы для контроля к п. 21.2.4…21.2.6