Тема 2. Елементи теорії графів

У результаті вивчення теми студенти повинні вміти:

- оперувати основними поняттями і термінологією графів;

- визначати хроматичний клас графа;

- визначати клікове число графа;

- будувати графи та дерева.

Контрольні питання:

1. Задача чотирьох фарб.

2. Хроматичне число, хроматичний клас.

3. Теорема Кенінга.

4. Дерева, теорема про центр дерева.

5. Перегляд графа «пошуком в глибину».

Контрольні завдання:

1. Доведіть, що для правильного розфарбування карти, що одержується при перетині кіл на площині, достатньо двох кольорів.

2. Зобразіть всі кореневі дерева з числом вершин n=4.

3. Зобразіть кліки графа G та додатковий граф:

4. Проілюструйте алгоритм пошуку в глибину на графі: