ПОИСК Статьи Рисунки Таблицы Алгоритм разрыва циклов графа из "Моделирование сложных химико-технологических схем" Задачей АРЦ является получение одной из совокупностей дуг (неоптимальной), разрыв которых превращает замкнутый граф-в разомкнутый. [c.57] Множество этих дуг обозначим через Р (р ). Таких множеств будет т. Далее разорвем все дуги одного из этих множеств, скажем, у множества Р р )- Теперь для анализа полученного графа вновь применим АУВР. Поскольку в новом графе вершина р входная, здесь она уже будет пройдена. Если после разрыва дуг множества Р (рг) граф стал разомкнутым, то после окончания работы АУВР в Q3 не останется ни одной вершины. Если же он все же остался замкнутым, то опять в Q3 останется ряд вершин. Снова мы разрываем дуги одного из множеств Р (р ) и т. д. Легко видеть, что любой замкнутый граф через конечное число шагов станет разомкнутым в результате выполнения этой процедуры. [c.58] При работе данного алгоритма для каждой непройденной вершины Pi требуется знать все вершины kj 6 В (pi), удовлетворяющие условию (IV,16). Эти вершины можно получить следующим образом. Будем в 5-таблице связей отмечать как-нибудь вершины, если они оказались пройденными при работе АУВР. Тогда оставшиеся неотмеченными в указанной таблице вершины и будут удовлетворять условию (IV,16). [c.58] Теперь можно перейти к описанию блок-схемы АРЦ (рис. 21). Блок 1 представляет собой АУВР. По окончании его работы проводится проверка имеются ли вершины в Q . Если такие вершины есть, происходит переход к блоку 3. Здесь осуществляется разрыв дуг одного из множеств Р [р ) в соответствии с критерием (IV,17). [c.58] Разорванные дуги запоминаются. Затем происходит переход к блоку 1. Если после его работы множество 3 окажется пустым, происходит переход к блоку 4. Здесь проводится проверка имеются. ни запомненные разорванные дуги. Если таких дуг нет, значит, исходный граф был разомкнутый, если же такие дуги есть, — замкнутый, и разрыв этих дуг превращает замкнутый граф в разомкнутый. [c.59] И Р (И) будут Р (4) = (14, 4), (13, 4) Р (И) = (10, И) . Будем считать, что размерности всех дуг в графе одинаковы. Тогда сумма размерностей дуг множества Р (11) меньше суммы размерностей дуг множества Р (4). Отсюда в соответствии с блоком 3 дуга (10, И) будет разорвана и запомнена. [c.59] Согласно критерию (IV,17), в блоке 3 разрывается и запоминается дуга (15, 9), откуда получаем граф, изображенный на рис. 23. Теперь опять работает блок 1. В множество будут добавлены вершины 9, 10, и оно примет вид = 1, 3, 2, 12, 16, И, 9, 10 . В ( з останется только вершина. Отсюда в блоке 3 дуги (14, 4) и (13, 4) будут разорваны и запомнены. После этого в блоке 1 будут пройдены все оставшиеся вершины, и алгоритм закончит свою работу. Разомкнутый граф будет иметь вид, показанный на рис. 24. [c.60] Вернуться к основной статье