Московский институт статистики, экономики, информационных технологий. Бурятский Филиал МЭСИ.
Дисциплина: «Математические методы»
Специальность: «Программное обеспечение ВТ и АС»
Павлов Ю.А, 3 курс Группа БУ ДЛП-902
Курсовая работа.
Тема: «Нахождение максимального потока в графе»
Научный руководитель:
Проверил:
Улан-Удэ. 2012 год.
Оглавление
1.Введение………………………………………………………………………………....3
2. Сводимость задач о максимальном потоке в графе………………………………………………………………………….…………..4
3. Основные определения и теоремы……………………………………………………….…………………………..5
4. Алгоритм Форда-Фалкерсона………………………………………………...……………………………..7
5. Программной реализации решаемой задачи……………………………………………………………………….…………...10
6. Заключение………………… ………………………………………………………….11
7. Список используемойлитературы………………………………………….…………………………………...12
Введение
Актуальность темы исследований.
Стремительные перемены, происходящие в мире, ставят перед наукой много вопросов, связанных с перспективами развития экономики, ее ближайшим и отдаленным будущим. В современных условиях повышение эффективности перемещения товаров от производителя к потребителям, информации между компьютерами через электронные сети по всему миру с меньшими затратами является актуальнойпроблемой. Выбор оптимальных решений таких задач в контексте глобализации современного мира требует научного поиска в этой области. Известно, что графовые модели (т.е. математические модели, имеющие в своей основе графы и процессы на графах) предоставляют необходимую основу для решения задач из самых различных областей: экономики, физики, химии, планово-производственной практики, управленияпроизводством, сетевого и календарного планирования, информационных сетей и многих других. Классическими достижениями этой области математического моделирования являются законы Кирхгофа для электрических цепей, открытие А.Келли природы химических изомеров и созданная Л.Р. Фордом и Д.Р. Фалкерсоном теория потоков в сетях.Если приписать каждой дуге ориентированного графа поток некоторого вещества, графстановится удобной моделью при исследовании целого ряда проблем в транспорте, связи и других областях, связанных с движением товаров, информации и т.п.Задача поиска потока максимальной величины и двойственная ей задача поиска минимального разреза – это классические задачи теории потоков в сетях, имеющие важные научные и практические приложения. Например, определение максимальной интенсивности транспортногопотока между двумя пунктами и определение части сети дорог, которая насыщена и образует «узкое место».4Обычно поток не перемещается по сети мгновенно, а требуется определенное время для прохождения по каждой дуге. В частности, когда принимается решение о маршрутизации пакета в одной части сети, результат может быть заметен в другой части сети спустя некоторое время. Следовательно, не тольковеличина передающегося потока, но и время, требуемое для передачи, играет важную роль.Изменение потока с течением времени – это важная особенность задачи о потоке в сети, возникающая в различных приложениях, таких как управление дорожным и воздушным движением, информационные сети (в том числе Интернет) и финансовые потоки. В таких приложениях величины потока по дугам непостоянны и могут изменяться стечением времени.Указанные выше стороны потока в сети не охватываются классическими моделями стационарного потока. В таких случаях появляется необходимость в рассмотрении потока, изменяющегося с течением времени, т.е. динамического потока, который включает временное измерение и поэтому является более удобным инструментом моделирования многих рактических задач.В классической постановке задач опотоках в сетях граф выступает в качестве носителя задачи о потоке (определяет топологию задачи и пропускную способность дуг), далее рассматривается два класса задач – задачи о стационарном потоке (т.е. в которых поток не меняется во времени) и динамические (в терминологии Л. Форда и Д. Фалкерсона),...
Дисциплина: «Математические методы»
Специальность: «Программное обеспечение ВТ и АС»
Павлов Ю.А, 3 курс Группа БУ ДЛП-902
Курсовая работа.
Тема: «Нахождение максимального потока в графе»
Научный руководитель:
Проверил:
Улан-Удэ. 2012 год.
Оглавление
1.Введение………………………………………………………………………………....3
2. Сводимость задач о максимальном потоке в графе………………………………………………………………………….…………..4
3. Основные определения и теоремы……………………………………………………….…………………………..5
4. Алгоритм Форда-Фалкерсона………………………………………………...……………………………..7
5. Программной реализации решаемой задачи……………………………………………………………………….…………...10
6. Заключение………………… ………………………………………………………….11
7. Список используемойлитературы………………………………………….…………………………………...12
Введение
Актуальность темы исследований.
Стремительные перемены, происходящие в мире, ставят перед наукой много вопросов, связанных с перспективами развития экономики, ее ближайшим и отдаленным будущим. В современных условиях повышение эффективности перемещения товаров от производителя к потребителям, информации между компьютерами через электронные сети по всему миру с меньшими затратами является актуальнойпроблемой. Выбор оптимальных решений таких задач в контексте глобализации современного мира требует научного поиска в этой области. Известно, что графовые модели (т.е. математические модели, имеющие в своей основе графы и процессы на графах) предоставляют необходимую основу для решения задач из самых различных областей: экономики, физики, химии, планово-производственной практики, управленияпроизводством, сетевого и календарного планирования, информационных сетей и многих других. Классическими достижениями этой области математического моделирования являются законы Кирхгофа для электрических цепей, открытие А.Келли природы химических изомеров и созданная Л.Р. Фордом и Д.Р. Фалкерсоном теория потоков в сетях.Если приписать каждой дуге ориентированного графа поток некоторого вещества, графстановится удобной моделью при исследовании целого ряда проблем в транспорте, связи и других областях, связанных с движением товаров, информации и т.п.Задача поиска потока максимальной величины и двойственная ей задача поиска минимального разреза – это классические задачи теории потоков в сетях, имеющие важные научные и практические приложения. Например, определение максимальной интенсивности транспортногопотока между двумя пунктами и определение части сети дорог, которая насыщена и образует «узкое место».4Обычно поток не перемещается по сети мгновенно, а требуется определенное время для прохождения по каждой дуге. В частности, когда принимается решение о маршрутизации пакета в одной части сети, результат может быть заметен в другой части сети спустя некоторое время. Следовательно, не тольковеличина передающегося потока, но и время, требуемое для передачи, играет важную роль.Изменение потока с течением времени – это важная особенность задачи о потоке в сети, возникающая в различных приложениях, таких как управление дорожным и воздушным движением, информационные сети (в том числе Интернет) и финансовые потоки. В таких приложениях величины потока по дугам непостоянны и могут изменяться стечением времени.Указанные выше стороны потока в сети не охватываются классическими моделями стационарного потока. В таких случаях появляется необходимость в рассмотрении потока, изменяющегося с течением времени, т.е. динамического потока, который включает временное измерение и поэтому является более удобным инструментом моделирования многих рактических задач.В классической постановке задач опотоках в сетях граф выступает в качестве носителя задачи о потоке (определяет топологию задачи и пропускную способность дуг), далее рассматривается два класса задач – задачи о стационарном потоке (т.е. в которых поток не меняется во времени) и динамические (в терминологии Л. Форда и Д. Фалкерсона),...
Поделиться рефератом
Расскажи своим однокурсникам об этом материале и вообще о СкачатьРеферат