Файл: 9. Гамильтоновы графы. Достаточные условия гамильтоновости графа. 17.docx

СОДЕРЖАНИЕ

1. Основные понятия теории графов. Задачи, послужившие основой теории графов.

2. Ориентированные и неориентированные графы. Изоморфизм графов.

3. Способы задания графов. Метрические характеристики графа.

4. Деревья и леса.

5. Плоские графы. Формула Эйлера для плоских графов.

6. Основные примеры неплоских графов. Существование у плоского графа вершин малых степеней.

7. Теорема Фари.

8. Эйлеровы графы. Построение эйлеровых циклов. Обход ребер графа по одному разу в обоих направлениях.

9. Гамильтоновы графы. Достаточные условия гамильтоновости графа.

10. Взвешенные графы. Минимальное остовное дерево и алгоритмы его построения.

11. Кратчайшие пути на графах. Алгоритмы Декстры и Белламана- Мура.

12. Кратчайшие пути между всеми парами вершин графа. Алгоритм Флойда.

14. Алгоритм нахождения максимального пути в графе.

15. Потоки в сетях. Построение максимального потока транспортной сети.

16. Сетевой график. Правила построения сетевых графиков.

17. Двудольные графы. Теорема Кенига.

18. Максимальные паросочетания. Количество ребер в максимальном паросочетании.

19. Алгоритм построения максимального паросочетания.

20. Построение оптимального паросочетания во взвешенном двудольном графе. Задача о назначениях.

21. Система различных представителей. Теорема Холла.

22. Раскраски графов. Хроматическое число графа. Графы с малым хроматическим числом.

23. Алгоритмы построения оптимальных раскрасок.

24. Хроматическое число планарного графа. Теорема Хивуда о пяти красках.