Учебное пособие. – Самара: Изд-во Самар. гос. аэрокосм. ун-та, 2013. – 48с. ISBN 978-5-7883-0950-7В пособии содержатся основные сведения о теории графов, приводятся примеры задач, решаемых методами теории графов, описываются алгоритмы их решения. Изложение материала иллюстрируется примерами. Приведен вариант расчетной работы по теории графов.
Рассчитано на студентов экономических специальностей, но будет полезно и студентам других специальностей, изучающим высшую математику.Содержание
Введение
Основные понятия теории графов
Расстояния в графах
Определение расстояний в графах без учета длин ребер. Волновой метод
Определение расстояний в графах с учетом длин ребер. Метод редукции индекса
Построение эйлеровой цепи в графе. Алгоритм Флери
Построение двойного эйлерова цикла в неориентированном графе. Алгоритм Тэрри
Построение остова графа наименьшего веса. Алгоритм Краскала
Сетевое планирование
Построение сетевого графика
Решение задачи сетевого планирования
Алгоритм вычисления ранних сроков наступления событий PiT и критического времени
Построение критического пути
Алгоритм вычисления поздних сроков наступления событий Tj П
Общий план решения
Транспортные сети и потоки. Алгоритм форда Фалкерсона
Основные понятия
Алгоритм построения полного потока
Алгоритм получения потока наибольшей величины (метод индексации)
Заключение
Список литературы
