книги / Теория графов и её приложения.-1
.pdf
Путь μ3 = х0, х2, х4, z: насыщаются дуги х4, х3 и х3, z. Для насыщения этого пути берём ϕ(μ3) = 2. Насыщается дуга х2, х4 = 2.
Больше нет путей из х0 в z, содержащих ненасыщенные дуги. Следовательно, полный поток определяется как ϕ(μ1) + ϕ(μ2) + + ϕ(μ3) = 4.
Нахождение наибольшего потока в транспортной сети
Процесс увеличения потока состоит в разметке графа индексами, указывающими путь, на котором возможно увеличение потока. Помечаем х0 индексом 0.
Если хi – уже помеченная вершина, то помечаем индексом + i все непомеченные вершины, в которые идут ненасыщенные дуги из хi, и индексом –i все непомеченные вершины, из которых идут дуги в вершину хi. Если в результате этого процесса окажется помеченной вершина z, то между вершинами х0 и z найдётся цепь, все вершины которой различны и по-
61
мечены номерами предыдущих вершин. Поток в этой цепи увеличивается на 1.
Если некоторый поток невозможно увеличить указанным образом, т.е. окажется невозможным пометить вершину z, то такой поток – наибольший.
Вершина z оказалась помеченной индексом +4. Последовательность индексов +4, –3, +2, +0 определяет цепь μ = х0, х2, х3, х4, z, поток в которой следует увеличить на 1. Увеличиваем поток в цепи х0, х2, х3, х4, z на 1 – дуга х3, х4 «отключается».
62
Находим цепь μ = х0, х2, х1, х3, х4, z, поток в которой также может быть увеличен на 1.
Увеличиваем поток в цепи х0, х2, х1, х3, х4, z на 1. Дуга х3, х4 «включается» в другом направлении.
63
При новой разметке вершина z осталась непомеченной, т.е. ненасыщенных дуг в z нет. Таким образом, наибольший поток найден. Он равен 6.
Нахождение полного потока в транспортной сети с дополнительной дугой
Ищем путь, все дуги которого не насыщены, и увеличиваем поток на +1 до тех пор, пока он не станет полным. Путь μ1 = х0, х1, х3, z: насыщается дуга х0, х1; ϕ(μ1) = 1:
Путь μ2 = х0, х2, х4, х3, z: насыщаются дуги х4, х3 и х3, z;
ϕ(μ2) = 1:
Путь μ3 = х0, х2, х4, z: насыщаются дуги х4, х3 и х3, z. Для насыщения этого пути берём ϕ(μ3) = 2. Насыщается дуга х2, х4 = 2.
64
Добавляем μ4 = х0, х2, х1, х4, z: Насыщается х1–х4.
Больше нет путей из х0 в z, содержащих ненасыщенные дуги (по другой диагонали не добавишь). Следовательно, полный поток равен ϕ(μ1) + ϕ(μ2) + ϕ(μ3) + ϕ(μ4) = 5.
Нахождение наибольшего потока в транспортной сети
65
Вершина z оказалась помеченной индексом +4. Последовательность индексов +4, –3,+2,+0 определяет цепь μ = х0, х2, х3, х4, z, поток в которой следует увеличить на 1. Увеличиваем поток в цепи х0, х2, х3, х4, z на 1 – дуга х3, х4 «отключается», поэтому поток х4, z увеличивается на 1:
Проводим новую разметку
Находим цепь μ = х0, х2, х1, х3, х4, z, поток в которой также может быть увеличен на 1:
66
При новой разметке вершина z осталась непомеченной, т.е. ненасыщенных дуг в z нет. Таким образом, наибольший поток найден. Он равен 7.
Задание. Найти максимальный поток в заданной транспортной сети (по вариантам) с помощью программы GRIN.
Подготовьте отчёт и будьте готовы к ответу на вопросы по занятию:
1.Особенности разметки транспортной сети по алгоритму Форда–Фалкерсона.
2.Что такое разрез транспортной сети?
3.Что такое полный поток?
4.Что такое максимальный поток?
5.Как решить задачу нахождения максимального потока
впрограмме GRIN?
6.Каковы особенности графа при решении транспортной
задачи?
67
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 8.
АНАЛИЗ ГРАФА МАРКОВСКОЙ ЦЕПИ В СКМ«МАТКАД»
ИВ СИСТЕМЕ WINDCHILL QUALITY SOLUTIONS 10.0
1.Опрос по теоретическому материалу – особенности графа марковской цепи.
2.Коллективное решение задач по теме занятия у доски «вручную».
3.Самостоятельная работа по вариантам – на ПЭВМ в про-
грамме Windchill Quality Solutions 10.0.
Задание: найти коэффициент готовности по заданной марковской цепи.
Граф марковской цепи
Рассмотрим на примере применение для решения «игр с природой» математическогоаппаратамарковскихцепей.
Определить коэффициент готовности КСЗИ по графу марковской цепи (рис. 8.1), где 0 – состояние работоспособности.
Параметр потока отказов блока w = 0,01, параметр потока восстановления блока 
Рис. 8.1. Граф марковской цепи КСЗИ
Получим по этому графу марковской цепи систему дифференциальных уравнений (Колмогорова–Чепмена):
68
Решение будем искать для установившегося режима, тогда получаем алгебраические уравнения:
Pi′ (t) = 0 , а P0 + P1 + P2 = 1:
Из первого уравнения
Из третьего уравнения
Тогда
Подставляя эти значения в четвёртое уравнение, получаем:
69
Решим систему алгебраических уравнений, описывающих граф марковской цепи в СКМ «Маткад».
Берём два первых уравнения и последнее (три уравнения, три неизвестных) (рис. 8.2).
Рис. 8.2. Решение в СКМ Маткад
Ознакомление с модулем Markov
Запустим программу Windchill Quality Solutions 10.0 Tryout (рис. 8.3).
Для выполнения лабораторной работы, необходимо воспользоваться модулем Markov (рис. 8.4).
70