I. Основные вопросы

II. Задачи для усвоения материала.

I. Необходимые определения и формулировки теорем.

1. В чем состоит задача о раскраске вершин графа?

2. Каков алгоритм решения задачи о раскраске графа?

3. В чем состоит задача о раскраске ребер графа?

4. Что Вы знаете о хроматическом индексе?

1. Для каждого из предложенных графов найдите правильные раскраски рёбер и вершин.

Здесь, к сожалению, придется рисунки переделать вручную: номера их какие-то странные, на некоторых рисунках уже построены правильные раскраски.

]

11. Итоговое повторение темы 2. Контрольная работа № 2.

1. Что такое орграф, граф, вершина, дуга, ребро, путь, цепь, контур, цикл?

2. Каков алгоритм решения задачи о кратчайшем пути в невзвешенном графе?

3. Каков алгоритм решения задачи о кратчайшем пути во взвешенном графе?

4. Что такое эйлерова цепь (цикл), у каких графов они существуют?

5. В чем состоит формула Эйлера и для каких объектов она верна?

6. Как выглядят непланарные графы № 1, № 2, типов 1, 2 и в чем состоит теорема Куратовского-Понтрягина?

7. Что такое хроматическое число графа и что Вы знаете о его величине?

8. Что такое хроматический индекс графа и что Вы знаете и о его величине?

Дата добавления: 2014-11-25