I. Основные вопросы.
II. Задачи для усвоения материала.
I. Необходимые определения и формулировки теорем.
1.В чем состоит задача о раскраске вершин графа?
2.Каков алгоритм решения задачи о раскраске графа?
3.В чем состоит задача о раскраске ребер графа?
4.Что Вы знаете о хроматическом индексе?
1. Для каждого из предложенных графов найдите правильные раскраски рёбер и вершин.
Здесь, к сожалению, придется рисунки переделать вручную: номера их какие-то странные, на некоторых рисунках уже построены правильные раскраски.
]
11. Итоговое повторение темы 2. Контрольная работа № 2.
1. Что такое орграф, граф, вершина, дуга, ребро, путь, цепь, контур, цикл?
2. Каков алгоритм решения задачи о кратчайшем пути в невзвешенном графе?
3. Каков алгоритм решения задачи о кратчайшем пути во взвешенном графе?
4. Что такое эйлерова цепь (цикл), у каких графов они существуют?
5. В чем состоит формула Эйлера и для каких объектов она верна?
6. Как выглядят непланарные графы № 1, № 2, типов 1, 2 и в чем состоит теорема Куратовского-Понтрягина?
7. Что такое хроматическое число графа и что Вы знаете о его величине?
8. Что такое хроматический индекс графа и что Вы знаете и о его величине?