Файл: Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf

носильно нахождению подобных членов в соответствующих им ло­ гических функциях.

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

Вних можно выделить пять равных подпутей. Это начальный подпуть Я ь представляющий собой следующую совокупность дуг:

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

Процесс определения равных подпутей осуществляется в определенном порядке. Выделение равных подпутей начинается с начальных вершин графов и производится последовательно в на­ правлении их конечной вершины без возвращения к ранее прой­ денным путям.

Установив наличие в алгоритмах одинаковых частей, можно

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

Впроцессе присоединения на базе графов равные подпути сов­ мещаются, а неравные присоединяются введением дополнительных вершин графа, т. е. путем расширения графа. Назначение этих вершин — разветвление алгоритма в соответствии со спецификой решения задач. Поскольку вершинами графа, представляющего алгоритм, являются операции, очевидно, дополнительной вершине графа будет соответствовать операция сравнения.

Впроцессе присоединения могут иметь место следующие три случая:

1)присоединяются равные подпути;

116

Вслучае присоединения равных подпутей конец уже присоеди­ ненного подпути и начало присоединяемого подпути должны сов­ падать. Другими словами, их общая вершина изображается одно­ кратно.

Вслучае присоединения равного подпути к неравным могут быть два варианта.

Первый вариант — когда длина каждого из неравных подпутей больше нуля. В этом случае начальная величина присоединяемого равного подпути совмещается с концами уже изображенных не­ равных подпутей. Таким образом, равный подпуть и два неравных подпути соединяются в одной общей вершине.

равного подпути совмещается с конечной вершиной неравного подпути, длина которого отлична от нуля. Совмещенная вершина соединяется дугой с дополнительной вершиной, введенной в про­ цессе присоединения неравных подпутей. Таким образом, вторая ветвь от дополнительной вершины идет непосредственно в началь­ ную вершину последующего равного подпути.

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

Второй вариант — когда изображенная часть алгоритма закан­ чивается вершиной, представляющей любую из операций, кроме сравнения. После этой вершины вводится дополнительная верши­ на, обеспечивающая разветвление алгоритма. Непосредственно с этой вершиной соединяются конечные вершины начальных дуг присоединяемых неравных подпутей. Общий вид графа, представ­ ляющего составной алгоритм задачи составления сводки о реали­ зации фондов в отделе оборудования и транспортном отделе, изоб­ ражен на рис. 23.

В процессе присоединения, выполняемом на основе логических функций, осуществляется приведение подобных членов, соответст­ вующих равным подпутям. Неравные подпути, оставшиеся после выделения равных подпутей, соединяются между собой дизъюнк­ тивной связью и заключаются в круглые скобки. При этом рассматриваются лишь те подпути, которые заключены между со­ ответствующими равными подпутями. Соединение равных и объ­ единенных неравных подпутей в единый алгоритм осуществляется конъюнктивной связью с добавлением дополнительных членов, со­ ответствующих операциям сравнения.

117

В процессе присоединения с использованием логических функ­ ций могут встречаться те же три случая, что и при использовании графов:

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

Первый вариант — когда равный подпуть заканчивается вер­ шиной, представляющей операцию сравнения. Тогда эта операция принимается за дополнительную вершину. К каждому из нерав­ ных подпутей в конъюнктивной связи прибавляется начальный подпуть единичной длины, отражающий связь этой дополнитель­ ной вершины и конечной вершины равного подпути. Иными сло­ вами, в качестве начальной дуги неравных подпутей вводится дуга

СрСр.

Второй вариант — когда равный подпуть заканчивается опе­ рацией, отличной "от операции сравнения. В этом случае после конечной вершины равного подпути предполагается наличие до­ полнительной вершины, отражающей операцию сравнения.

В логической функции этому будет соответствовать продление с помощью конъюнктивной связи равного подпути на дугу единич­ ной длины, связывающей конечную вершину с дополнительной. Кроме того, в каждом из неравных подпутей начальный подпуть единичной длины видоизменяется. Конечная вершина в них оста­

Первый вариант — когда длина каждого из неравных подпутей больше нуля. В этом случае равный подпуть присоединяется с по­ мощью конъюнктивной связи.

пути предполагается наличие дополнительной вершины, отражаю­ щей операцию сравнения.

В логической функции этому будет соответствовать продление равного подпути на дугу единичной длины, связывающую конеч­ ную вершину с дополнительной. Кроме того, каждый неравный подпуть удлиняется на одну дугу за счет укорочения последующе­ го равного подпути. Подпуть, длина которого не равна нулю, до­ полняется непосредственным добавлением в конъюнктивной связи первой дуги последующего равного подпути. Подпуть, длина ко­ торого равна нулю, дополняется видоизмененной первой дугой последующего равного подпути таким образом, что конечная вер-

119

шина ее остается неизменной, а начальной служит дополнительная вершина.

Построим логическую функцию, соответствующую составному алгоритму решения задачи в транспортном отделе и в отделе обо­ рудования.

Построение логической функции начинаем с записи логической формулы равного начального подпути Пх.

СрСр))ХСрУхУСхССр •

Непосредственно за П\ в алгоритмах следуют неравные под­ пути:

ответствующими начальными подпутями СрСр и имеют вид пер­ вый:

Соединяем полученные пути дизъюнктивной связью и заклю­ чаем в круглые скобки. Объединенные неравные подпути присое­ диняются к равному подпути П\ с помощью конъюнктивной связи. В результате получим следующую формулу:

Далее к неравным подпутям без каких-либо изменений присое­ диняется с помощью конъюнктивной связи равный подпуть:

120