Элементы теории графов

Description

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