Вопросы для подготовки к экзамену по дисциплине

ВОПРОСЫ ДЛЯ ПОДГОТОВКИ К ЭКЗАМЕНУ ПО ДИСЦИПЛИНЕ

«ТЕОРИЯ ГРАФОВ»

1. Основные понятия.

1. Графы. Изоморфизм графов. Подграфы и дополнения.

2. Маршруты, цепи, пути и циклы.

3. Связность и компоненты графа.

4. Способы задания графов.

5. Оценки числа графов.

6. Геометрическая реализация графов.

7. Реализуемость графов в трехмерном пространстве.

8. Теорема Эйлера о плоских графах.

9. Теорема Эйлера о выпуклых многогранниках.

10. Оценки числа ребер в плоских графах.

11. Непланарность графов K3,3 и K5.

12. Гомеоморфизм графов. Теорема Понтрягина-Куратовского.

13. Графы, матрицы и отношения. – НЕ НАДО

2. Деревья.

1. Деревья, остовы.

2. Элементарные свойства деревьев.

3. Корневые деревья.

4. Способы задания деревьев.

5. Перечисление (оценки числа) деревьев. – НЕ НАДО

3. Эйлеровы и гамильтоновы графы.

1. Эйлеровы графы. Теорема Эйлера.

2. Гамильтоновы графы.

3. Задача коммивояжера.

4. Покрытия и раскраски.

1. Независимые множества и вершинные покрытия.

2. Вершинная раскраска и хроматическое число.

3. Теорема о шести красках (доказательство).

4. Раскрашивание карт. Теорема о четырех красках.

5. Алгоритмы на графах.

1. Обходы графов в глубину и ширину.

2. Поиск в глубину. Отыскание связных компонент.

3. Поиск в глубину. Отыскание двусвязных компонент. – НЕ НАДО

4. Кратчайшие пути. (Алгоритм Дейкстры.)

5. Алгоритм построения эйлерова цикла.

6. Построение минимального остова графа. (Алгоритм Крускала.)

7. Наибольшие паросочетания и задача о назначениях.

8. Алгоритм транзитивного замыкания. – НЕ НАДО

9. Потоки в транспортных сетях. Теорема Форда-Фалкерсона о максимальном потоке в транспортной сети. Помечающий алгоритм нахождения максимального потока в транспортной сети.

РЕКОМЕНДОВАННАЯ ЛИТЕРАТУРА

ПО ДИСЦИПЛИНЕ «ТЕОРИЯ ГРАФОВ»

Основная литература

1. Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 1984.
2. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

Дополнительная литература

1. Берж К. Теория графов и ее применения. – М.: ИЛ, 1962
2. Белов В.В., Воробьёв Е.М., Шаталов В.Е. Теория графов. – М.: Высшая школа, 1976.
3. Зыков А.А. Основы теории графов. – М.: Наука, 1987.
4. Басакер Р., Саати Т. Конечные графы и сети. –М.: Наука, 1974.
5. Харари Ф. Теория графов. – М.: Мир, 1973.
6. Оре О. Теория графов. – М.: Наука, 1968.
7. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1992.
8. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1979, 1986.
9. Дискретная математика и математические вопросы кибернетики. Т.1. – М.: Наука, 1968.
10. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.
11. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: Вильямс, 2000.
12. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. – М.:МЦМНО, 2001.
13. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989.
14. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1975.
15. Кнут Д. Искусство программирования для ЭВМ. Т.1.Основные алгоритмы. – М.: Мир, 1976; Т.2; Получисленные алгоритмы. - М.: Мир, 1977; Т.3. Сортировка и поиск. – М.: Мир, 1978.
16. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика – М.: Мир, 1980.
17. Липский В. Комбинаторика для программистов. – М.: Мир, 1988.
18. Кофман А. Введение в прикладную комбинаторику. – М.: Наука, 1975.
19. Тарьян Р.Э. Сложность комбинаторных алгоритмов. В кн: Кибернетический сборник, новая серия, вып.17. – М.: Мир, 1980, с.60 - 113.
20. Форд Л.Р., Фалкерсон. Д.Л.Потоки в сетях. – М.: Мир, 1966.
21. Ху Т. Целочисленное программирование и потоки в сетях. – М.: Мир, 1974.
22. Кристофидес П. Теория графов. Алгоритмический подход.– М.: Мир, 1978.
23. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982.
24. Евстигнеев В.А. Применение теории графов программировании..– М.: Мир, 1985.
25. Математическая энциклопедия. Т.1. А-Г. – М.: Советская Энциклопедия, 1977. – Стб. 1105-1121.

1) Алгоритм Дейкстры 2) Крускала 3)исток-сток – алгоритм – Орда-Фалкерсона.

Дата добавления: 2015-10-21