Книга: Таланов А. В., Алексеев В. Е. «Графы и алгоритмы»

Курс посвящен алгоритмам на графах. Приводятся базовые понятия и факты из теории графов и излагаются некоторые алгоритмы для решения задач на графах.
Основной принцип отбора и организации материала состоял в том, что каждый рассматриваемый пример должен нести определенную идейную нагрузку, знакомить слушателя с одним из важных изобретений или открытий в алгоритмической области. При этом предпочтение отдавалось не самым последним или рекордным алгоритмам, а более простым для понимания и убедительно демонстрирующим ту или иную идею. Для большинства рассматриваемых алгоритмов даются доказательства их правильности (т. е. того, что алгоритм действительно решает поставленную задачу) и оценок трудоемкости. Умение достаточно строго обосновывать алгоритмы и оценивать их трудоемкость является существенной частью квалификации алгоритмиста. Материал первой части может быть использован и в общем курсе дискретной математики.

Содержание:

Выходные данные...... 3 Лекция 1. Начальные понятия теории графов...... 4 Лекция 2. Маршруты, связность, расстояния...... 23 Лекция 3. Важнейшие классы графов...... 32 Лекция 4. Поиск в ширину...... 47 Лекция 5. Поиск в глубину...... 55 Лекция 6. Блоки...... 64 Лекция 7. Пространство циклов графа...... 73 Лекция 8. Эйлеровы и гамильтоновы циклы...... 82 Лекция 9. Независимые множества, клики, вершинные покрытия...... 90 Лекция 10. Раскраски...... 101 Лекция 11. Рационализация переборных алгоритмов...... 108 Лекция 12. Паросочетания...... 115 Лекция 13. Оптимальные каркасы...... 126 Лекция 14. Жадные алгоритмы и матроиды...... 132 Лекция 15. Кратчайшие пути...... 140 Лекция 16. Потоки...... 144 Список литературы...... 152

Издательство: "Национальный Открытый Университет «ИНТУИТ»" (2016)

ISBN: 5955600663