Визначення максимальної ваги посилань
Задача на застосування алгоритму Форда-Фалкерсона для визначення максимальної ваги посилань, які можуть бути транспортовані з пункту А в пункт В, побудува маршрут перевезень. Задані графом існуюча транспортна мережа і пропускна спроможність окремих ланок.
| Рубрика | Математика |
| Вид | задача |
| Язык | украинский |
| Дата добавления | 08.08.2009 |
| Размер файла | 104,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Задача
За алгоритмом Форда-Фалкерсона визначити максимальну вагу посилань, що можуть бути транспортовані з пункту А в пункт В, побудувавши маршрут перевезень. Існуюча транспортна мережа і пропускні спроможності окремих ланок задані графом:
f(x,y) - потік вздовж дуги (x,y) (к-ть одиниць, що проходить вздовж дуги)
с(x,y) - максимальна величина пропускної спроможності дуги графа.
Шукаємо всі можливі сполучення з пункту А в пункт В і записуємо їх пропускну здатність.
1.
min{10,20}=10 F(A,C)=10
C(A,C)=10 F(C,B)=10
C(A,B)=20
2.
min{30,20}=10 F(A,E)=20
C(A,E)=30 F(E,B)=20
C(E,B)=20
3.
min{20,30}=10 F(A,D)=10
C(A,D)=20 F(D,B)=10 C(D,B)=30
4.
min{10,10,30}=10 F(A,C)=10
C(A,C)=10 F(C,D)=10
C(C,D)=10 F(D,B)=10
C(D,B)=30
5.
min{20,40,20}=20 F(A,D)=20
C(A,D)=20 F(D,E)=20
C(D,E)=40 F(E,B)=20
C(E,B)=20
Подобные документы
Общая характеристика распространенных проблем поиска величины максимального потока в сети при помощи алгоритма Форда-Фалкерсона. Знакомство с задачами по дискретной математике. Рассмотрение особенностей и этапов постройки дерева кратчайших расстояний.
контрольная работа [740,3 K], добавлен 09.03.2015Необхідні поняття теорії графів. Задача про максимальний потік. Алгоритм Форда знаходження максимального потоку. Модифікація алгоритму Форда розв’язання задачі максимізації кількості призначень у задачах розподілу. Результати числового експерименту.
курсовая работа [499,9 K], добавлен 18.12.2013Оцінювання параметрів розподілів. Незміщені, спроможні оцінки. Методи знаходження оцінок: емпіричні оцінки, метод максимальної правдоподібності. Означення емпіричної функції розподілу, емпіричні значення параметрів. Задача перевірки статистичних гіпотез.
контрольная работа [57,2 K], добавлен 12.08.2010Обчислення середньорічних показників динаміки. Визначення рівних рядів і відсутних в таблиці ланцюгових характеристик динаміки. Визначення абсолютної зміни витрат на виробництво в цілому та за рахунок окремих факторів, грошових витрат на виробництво.
контрольная работа [1,3 M], добавлен 20.11.2009Основные понятия теории графов. Матричные способы задания графов. Выбор алгоритма Форда–Бэллмана для решения задачи поиска минимальных путей (маршрутов) в любую достижимую вершину нагруженного орграфа. Способы выделения пути с наименьшим числом дуг.
курсовая работа [109,1 K], добавлен 22.01.2016Потоки в сетях, структура и принципы формирования алгоритма Форда-Фалкерсона, особенности его реализации программным методом. Минимальные остовные деревья. Алгоритм Борувки: понятие и назначение, сферы и специфика практического использования, реализация.
курсовая работа [311,3 K], добавлен 15.06.2015Основні поняття математичної статистики. Оцінювання параметрів розподілів. Метод максимальної правдоподібності. Парадокси оцінок математичного сподівання та дисперсії, Байєса, методу найменших квадратів, кореляції, перевірки гіпотез та їх пояснення.
дипломная работа [1,1 M], добавлен 12.08.2010Визначення та властивості упорядкованих множин, приклади діаграм. Дистрибутивні ґрати як один з основних алгебраїчних об'єктів. Поняття нижньої і точної грані, їх властивості та приклади, доказ лем. Застосування та суть топологічних стоунових просторів.
курсовая работа [288,0 K], добавлен 24.03.2011Метод найменших квадратів. Задача про пошуки параметрів. Означення метода найменших квадратів. Визначення параметрів функціональних залежностей. Вид нормальної системи Гауса. Побудова математичної моделі, використовуючи метод найменших квадратів.
реферат [111,0 K], добавлен 25.12.2010Эйлеровы цепи и циклы, теоремы. Алгоритм построения эйлерова цикла. Обоснование алгоритма. Нахождение кратчайших путей в графе. Алгоритм Форда отыскания кратчайшего пути. Задача отыскания кратчайших расстояний между всеми парами вершин. Алгоритм Флойда.
реферат [108,4 K], добавлен 01.12.2008
