ПОИСК Статьи Рисунки Таблицы Алгоритм выделения путей из "Моделирование сложных химико-технологических схем" Пусть в графе имеются входная (Ь,) и выходная (а,) вершины. Алгоритм выделения путей АВП состоит из двух частей. Первая часть (АВП I) будет выделять в графе совокупность вершин 5 (а , Ь,), входящих во все пути, которые связывают вершину 6 с вершиной а,-. Вторая часть (АВП II) на основе совокупности 5 (а,, Ь,) будет уже непосредственно выделять пути, связывающие вершину Ъ[ с вершиной а,-. Начнем с описания первой части. [c.60] ВХОДЯШ.ИХ в совокупность 5 (а , Ъ . Вершины (IV,18) будут являться элементами множества Q [верхний индекс / указывает, что данное множество построено после шагов число элементов в нем, конечно, может быть меньше, чем ], поскольку не каждая анализируемая вершина могла принадлежать, 5 (а,-, ). По окончании работы АВП I множество будет совпадать с множеством 8 (а,, Ь,). Анализируя в соответствии с некоторым порядком вершины графа, АВП I будет добавлять к множеству вершины, которые заведомо принадлежат одному из путей, связывающих вершины Ь[ и а . [c.61] пусть на у-ом шаге анализируется вершина хК Поскольку в большинстве случаев при переходе к какой-то вершине нельзя сразу сказать, принадлежит или не принадлежит она совокупности 5 (а,, Ь,), то вначале эта вершина добавляется к элементам некоторого вспомогательного множества Q . В нем будет накапливаться некоторая последовательность вершин, являющаяся путем. В дальнейшем элементы множества Qз либо добавятся к множеству (если будет установлено, что они принадлежат множеству 3 (а,-, Ь ), либо просто извлекутся из 3, если выявится, что они заведомо не принадлежит множеству 5 (а , Ъ ). [c.61] В этом случае элементы множества Q f добавляются к элементам множества а множество ( з делается пустым. [c.62] В этом случае следующая анализируемая вершина xi+ выбирается из множества вершин, положительно-инцидентных вершине х х + 6 А (х ). Если вершина х — разъединительная, правило перехода в одну из вершин к к А (х )) будет такое же, как и в АУВР. [c.62] Проиллюстрируем правило 1 на примере рис. 19. Пусть необходимо найти все пути, связывающие вершины 1 ш 4. Пусть также в результате анализа графа в множестве 3 накоплена последовательность вершип 1, 2, 9, 5. Среди вершин данного множества вершины 2 ж 9 — разъединительные и являются элементами множества 2 = 2, 9 - В соответствии со сказанным выше следующей анализируемой вершиной должна быть вершина, положительно-инцидентная вершине 5, т. е. выходная вершина 7. Следовательно, здесь нужно применить правило 1. [c.63] Посмотрим, о каких вершинах можно сказать, что они заведомо не входят в б (1, 4). Такой вершиной является вершина 5, которая в множестве 3 расположена после последней запомненной разъединительной вершины 9. С другой стороны, разъединительная вершина 9 уже входит в путь 1, 2, 9, 8, 4, соединяющий вершины 1 ж 4. Легко видеть, что в данном случае множество Qg включает лишь элемент 5, т. е. Qg = 5 . Конечно, для иного графа последняя, хранящаяся в Qз разъединительная вершина может и не войти в путь, соединяющий заданные вершины и а,-. Важно другое до тех пор, пока у разъединительной вершины не пройдены все выходные дуги, ее нельзя относить ни к множеству 3 (я , ни к множеству вершин, не принадлежащих 3 (а , 6,). Отсюда уже ясно правило 1. [c.63] Пусть анализируемая вершина оказалась выходной. Тогда относительно вершин, хранящихся в 3, можно сказать, что они не принадлежат множеству 5 (а,-, Ь .) только в том случае, если в множестве они расположены после последней запомненной разъединительной вершины. Эти вершины и являются элементами множества Qf. Отсюда становится понятным смысл действий при выполнении условия (IV,22). В данном случае элементы множества Qg заведомо не входят в 3 (а,-, ,), поэтому они извлекаются из 3, а множество делается пустым. Множество непройденных вершин, положительноинцидентных к вершине я, после выполнения -го шага обозначим через А (з). [c.63] Поясним некоторые операции. Операция (IV,26) удаляет из множества (з) пройденную вершину. Как мы уже указывали, разъединительная вершина после внесения в 2 должна там находиться до тех пор, пока не будут пройдены все ее выходные дуги. С помощью операции (IV,27) указанная вершина засылается в а посредством операции (IV,28) удаляется из этого множества, когда все ее выходные дуги будут пройдены. [c.64] Блок-схема АВП I приведена на рис. 27 схематично, без деталей. Так, не показано, как формируется в соответствии с определением (IV,20) множество Qg , не отражено, что блоки 2, 3 и 4 для первой анализируемой вершины не работают. С целью экономии операций блоки 2 и 3 должны были бы работать только для случаев, когда является разъединительным блоком, и т. д. Учет всех этих деталей значительно усложнил бы блок-схему и затруднил бы понимание принципиальной картины. [c.65] Проиллюстрируем работу АВП на примере графа, изображенного на рис. 28. Таблица связей для него приведена в табл. 4. [c.65] Перейдем теперь к описанию второй части алгоритма выделения путей. [c.68] Согласно блок-схеме на рис. 27 вершина (начальная вершина множества Ql) может быть либо вершиной либо вершиной, положительно-инцидентной некоторой разъединительной вершине к[ ( з1 6 (Н)) причем из Ь в к имеется по крайней мере один путь. Действительно, согласно блокам 11 и 17 блок-схемы на рис. 27, множество Q начинает формироваться либо с вершины Ъ- , либо с вершины X = А в), где з = Е (Q ) — последняя разъединительная вершина, храняш,аяся в ( 2- При этом поскольку — разъедипи-тельная вершина, которая хранится в Q , это значит, что существовал путь из Ь,., который содержал указанную вершину. [c.68] что для выполнения неравенства Qf,Ф 0 необходимо, чтобы был выделен хотя бы один путь из вершины 6,- в вершину а- . Отсюда первое множество может быть только некоторым путем, соединяющим 6,- с а,-, т. е. здесь 31 = 6 , д р. 6 В ( ). Действительно, первое множество начинается в вершине Ь,-, а может кончиться только в вершине а- . Совокупность вершин, входящих в этот путь, обозначим через 2 . Вершины в 2 будут расположены в том порядке, в котором они были сформированы в множестве Q. [c.69] что некоторые из совокупностей вершин [(IV,40), ( ,41) могут быть пустыми. [c.70] Очевидно, что совокупность вершин (IV,42) будет являться путем, связывающим й,- с а, при любом 5, / (1 5 г 1 г г). Действительно, 2 Ъ,, к[) — это путь, соединяющий вершины и к , Qit — путь, соединяющий вершины к и к , а 2 к , а,-) — путь, соединяющий вершины к и а,-. Проделав указанную операцию для всех / = 1,. . ., т, мы найдем все пути, связывающие вершины b и а,. [c.70] Вернуться к основной статье