ПОИСК Статьи Рисунки Таблицы Алгоритм упорядочивания вершин разомкнутого графа из "Моделирование сложных химико-технологических схем" Вершины, входящие в последовательность (1У.З) в том порядке, в котором они там стоят, есть элементы множества Q[. Правила построения УП следующие. [c.53] Частным случаем соотношения (IV.4) является соотношении В х) — 0 (это случай, когда х — входная вершина), поскольку пустое множество всегда можно считать подмножеством множества Q[. [c.53] Правило 2. Вообще говоря, в графе может иметься несколько вершин, удовлетворяющих условию (IV.4) любую из них можно присоединить к последовательности (IV.3). Однако для определенности необходимо условиться о каком-либо фиксированном порядке присоединения этих вершин. [c.53] Будем считать, что принят какой-либо порядок нумерации вершин, входящих в О. [c.53] Порядок присоединения следующей вершины к построенной части УП (IV,3) такой вначале просматриваются в соответствии с принятым порядком вершины множества А х1), затем вершины множества О и потом входные вершины, не содержащиеся в ( (. [c.53] Остановимся на порядке просмотра вершин лшожества А (х ). Он отвечает порядку элементов, установленному в множестве А х ) (см. стр. 49). Например, если просматриваются вершины множества А (2) графа (см. рис. 19), то, согласно таблице связей (см. табл. 2), вначале должна быть просмотрена вершина 3, а затем вершина 9. [c.54] Разберем применение правил 1 и 2 на примере графа, показанного на рис. 19. Пусть построена последовательность = 1,2 множество А (2) = 3, 9 , причем для обеих вершин, входящих в А 2), выполняется условие (IV,4). В таблице связи в строчке, отвечающей вершине 2, первой стоит вершина 3 поэтому она и будет присоединена к последовательности 1, 2 . Рассмотрим теперь полученную последовательность = 1, 2, 3 . Множество А (3) = 8 . Вершину 8 нельзя присоединить к этой последовательности, так как В (8) = 3, 9 , а вершина 9 не принадлежит множеству 1, 2, 3. Тогда в соответствии с правилом 2 к последовательности 1, 2, 3 должна быть присоединена вершина 9, поскольку а) она является положительно-инцидентной к разъединительной вершине 2, содержащейся в 1,2, 3 б) для вершины 9 выполняется условие (IV,4) — В (9) = 2 в) вершина 9 еще не содержится в последовательности 1, 2, 3 . [c.54] Получаем новую последовательность 1, 2, 3, 9 . Сделаем одно замечание. Поскольку каждая из вершин х присоединяется к части упорядоченной последовательности (IV,3) только при выполнении условия (IV,4), вся УП будет обладать следующим свойством. Если на г-ом месте стоит вершина а,-, то вершины, выходные дуги которых попадают в вершину а,., будут в УП стоять раньше вершины а,-. Отсюда следует, что полученная УП будет давать ВПРС (см. стр. 44). [c.54] Множество Q состоит из вершин графа, входящих в часть УП, сформированную к /-ому шагу. Множество Q2 = к к Q П и А k) Qi , т. е. это множество включает разъединительные вер-1НИНЫ, входящие в множество Q x и имеющие непройденные выходные дуги (условие А (к) ). Как только у некоторой вершины /с 6 / -будут пройдены все выходные дуги (выполнится условие А (к) 6 6 ( ), она должна исключаться из этого множества. [c.54] Пусть на /-0М шаге вершина к была внесена в множество но при р-ом шаге (р I) она будет внесена в УП (в множество Ql). Тогда ее надо удалить из множества Q . В конце работы АУВР множество должно стать пустым, в противном случае в графе оказались бы непройденными некоторые вершины. В разомкнутом графе этого не происходит. [c.55] Для АУВР множество не нужно, однако оно понадобится для алгоритма разрыва цик-чов графа, который описан в следующее разделе. [c.55] В разомкнутом графе процесс закончится после того, как будут пройдены все вершины, т. е. при ] = N (ТУ —число вершин графа). [c.56] Блок-схема АУВР приведена на рис. 20. При ее описании используем употребляемый в Алголе оператор присваивания =. Например, запись X = х + означает, что переменная слева х принимает значение, записанное справа от оператора, т. е. в данном случае о + 1. [c.56] Пусть сформирована часть УП, оканчивающаяся вершиной 5. В блоке 9 с помощью таблицы связей, согласно правилу 2, находится вершина х, положительно-инцидентная вершине з. Затем происходит переход к блоку 1. Если условие (IV,4) выполняется, вершина х добавляется к (блок 2) и удаляется из А (з) (блок 3). Далее в блоке 4 вершина х удаляется из 3, если она там содержалась. [c.56] Если при переходе в вершину х все вершины множества А (з) пройдены А з) = 0) (блок 5), вершина 5 удаляется из множества 2 если она в него входила (блок 6). Если при переходе в вершину х эта вершина оказалась разъединительной и до этого момента не содержалась в 2, тогда она в него добавляется (блок 7). Если вершина х входная, в блоке 8 она удаляется из У и происходит переход к блоку 10. Если вершина х не выходная, опять происходит переход к блоку 9 -если же она выходная, происходит переход к блоку 13. [c.56] Вернуться к основной статье