У результаті вивчення теми студенти повинні вміти:
- оперувати основними поняттями і термінологією графів;
- визначати хроматичний клас графа;
- визначати клікове число графа;
- будувати графи та дерева.
Контрольні питання:
1. Задача чотирьох фарб.
2. Хроматичне число, хроматичний клас.
3. Теорема Кенінга.
4. Дерева, теорема про центр дерева.
5. Перегляд графа «пошуком в глибину».
Контрольні завдання:
1. Доведіть, що для правильного розфарбування карти, що одержується при перетині кіл на площині, достатньо двох кольорів.
2. Зобразіть всі кореневі дерева з числом вершин n=4.
3. Зобразіть кліки графа G та додатковий граф:
4. Проілюструйте алгоритм пошуку в глибину на графі: