Главная  
  • Программы  
  • Методички  
  • Рефераты  
  • Дипломы  
  • Разное  
  • Фото  
  • Контакты  
  • Карта сайта  

  • Я:
    Найти:
    Возраст:
    -

    Пример 2 выполнения лабораторной работы по Теории систем и системному анализу

    HashFlare


    Лабораторная работа №2

    "Нахождение максимального потока в сети".

    Цель работы: "Выработать у студентов практические навыки работы с пакетом networks для решения задач на нахождение кратчайшего пути".

    Задание: "Найти максимальный поток в сети".

    Вариант № 13




    Теоретическая часть.

          При нахождении максимального потока в сети из источника в сток, необходимо учитывать то, что каждая дуга характеризуется некоторой пропускной способностью.

          Алгоритм нахождения максимального потока.
    1) Пусть источники помечены, но не просмотрены, а все остальные узлы не помечены.
    2) Выбрать любой помеченный, но не просмотренный узел i.
    3) Просмотреть все дуги и их пропускные способности, соединяющие узел i с ещё не помеченными узлами j.Приписать пометки узлам j и отметить дуги, соединяющие с узлом i. Если при этом сток оказался помеченным, то аргументальная цепь найдена.
    4) Если аргументальная цепь не найдена о переходим к шагу 1) и повторяем алгоритм до тех пор, пока не останется помеченных и не просмотренных узлов.



    > restart; with(networks):G:=void(7):

    > E:=[[1,2],[1,3],[2,5],[2,6],[3,4],[3,5],[3,6],[4,5],[5,7],[6,7]];


    > W:=[17,21,38,13,13,10,12,8,26,25];


    > addedge(E,weights=W,G);

    Находим максимальный поток в сети :

    > flow(G,1,7);

    >

    В результате получили, что максимальный поток от узла 1 к узду 7 равен 38.


    © Copyright 2006-2017. Все права защищены. Сайт бесплатно.