Вопросы к экзамену.

1. Геометрическое и алгебраическое определение графа.
Изоморфизм графов. Подграфы.
2. Маршруты, цепи, циклы. Связность, компоненты
связности. Лемма о разрыве цикла.
3. Эйлеровы циклы, теорема Эйлера. 
4. Мосты и точки сочленения, их свойства.
5. Обобщенные точки сочленения и Гамильтоновы циклы.
6. Деревья, теорема о деревьях. Каркас графа.
7. Задача о минимальном соединении. Алгоритм Краскла.
8. Двудольные графы, критерий двудольности. 
9. Плоские и планарные графы. Укладка на сфере.
10. Грани плоского графа. Теорема Эйлера о
многогранниках.
11. Следствия из теоремы Эйлера.
12. Стягивание. Теорема Понтрягина-Куратовского.
13. Раскраска графа. Хроматическое число. Оценки
хроматического числа снизу и сверху.
14. Теорема о пяти красках.
15. Орграфы и сети. Задача о кратчайшем пути. Алгоритм Дейкстры.
16. Задача о сетевом графике.