Устройство для моделирования ориентированных графов Советский патент 1986 года по МПК G06G7/48 

10

15

20

25

«о1203548

(57) Изобретение относится к анаоговой вычислительной технике и Ожет быть использовано при решении задач определения характеристик систем, отображаемых графами.

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

,На фиг. 1 изображена функциональная схема предлагаемого устройства; на фиг. 2-5 - графы, применительно к которым иллюстрируются возможности устройства.

Устройство содержит модели дуг 1 и вершин 2, источник 3 регулируемого напряжения, блок А индикации, выполненный в виде вольтметра, переключатель 5.

Модель 1 содержит операционный усилитель б, выпрямительный элемент 7, замыкающий контакт 8, первьш масштабный резистор 9, вторые масштабные резисторы 10 и переменные резисторы 11, размЕжающий контакт 12 Модель 2 содержит операционный усилитель 13, многополюсный двухпози- ционный переключатель 14, масштабные резисторы 15.

В работе устройства можно выделить три этапа.

Первый этап - моделирование критического пути. Напряжение от источника 3 подается через контакты 12 на резисторы 11 всех моделей дуг. Резисторы 11 включены по схеме потенциометра и позволяют установить напряжения, пропорциональные длительностям работ. Установка производится по шкале потенциометра и может контролироваться и уточняться с помощью блока 4, подключаемого к моделям 1 посредством переключателя 5. Операционные усилители 6 моделей 1 работают в режиме суммирования входных напряжений, напряжения на выходе их пропорциональны ранним срокам окончания работ. Выходы моделей 1,. входящих в вершину, соединены каждая со своим входом модели 2 этой вершины и через замкнутые контакты переключателя 14 и масштабные резисторы 15 подключены к входу операционного усилителя 13. Выпрямительные элементы 7 осзга;ествляют выбор максимума напряжение на выходах моделей 1, входящих в вершину, операционный усилитель 13 модели 2 восстанавлиро ле Пр ти бл де ин ко из св эл за да на ус ще

ве ва ну ма ве вы пе в ро На 30 ве эл

35

40

45

50

во

м ля

пу в щи и р у т с н и в г

j,j м

и

ЗJ

5

0

5

ливает полярность напряжения в устройстве и подает его на входы моделей 1, выходящих Из этой вершины. Протяженность частных и общего критических путей определяются с помощью блока 4, подключаемого к выходам моделей 2 через переключатель 5. Для индикации дуг, лежащих на критическом пути, можно использовать любое из известнь х устройств, например светодиод в качестве выпрямительного элемента 7. Источник 3 позволяет задавать уровень напряжения на входах моделей 1 так, чтобы последний на критическом пути операционный усилитель 6 не вошел в режим насыщения.

Второй этап - определение рангов вершин. Если всем дугам рассматриваемого графа приписать длину, равную 1, то ранг вершины равен максимальному пути от начала графа до этой вершины. Напряжение U, источника 3, выставляемое с помощью блока 4, в первом положении переключателя 5 и в нулевых пололсениях всех резисторов 11 подано на входы всех моделей 1 и соответствует единичной длине их. Напряжение на выходе модели 2 j-й, 0 вершины графа, при том же состоянии элементов устройства, что и на пер-

вом этапе, равно

KjU,,

где К; - ранг

J-и вершины, и определяется вольтметром 4, подключаемым к модели 2 j-й вершины при помощи переключателя 5 .

Третий этап - определение числа путей в ориентированном графе. Во всех моделях 1 и 2 замыкают контакты 8 и переключают переключатель 14. В моделях 1 всех дуг, кроме выходящих из начальной вершины графа, производят размыкание контакта 12. В результате все модели дуг, кроме указанных, переводятся в режим инвертора, а все модели вершин - в режим суммирования входных напряжений. Напряжение U источника 3 подано на входы моделей 1 дуг, выходящих из. начальной вершины графа. Количество путей Nj, ведущих в j-ю вершину графа, равно отношению напряжений

и,

и.

на выходе модели 2 j-й вершины и , т.е. Nj Uj/Uf|, замеряемых при помощи блока 4 и переключателя -5.

Устройство позволяет определять и число R, ; путей, проходящих через

В этом случае

,j путей, ЗJaлaннyю дугу dj;

R(; N- M , где Nj - число путей, ведущих из начальной вершины в вершину i графа. Числа N- и М, (где Mj - число путей, ведущих в конечную вершину из вершины J) определяются указанным выше способом, причем при определении Mj источник 3 подключается лишь к одному из свободных входов модели 2 j-й вершины графа.

Устройство позволяет определять ошибки, допущенные при построении производственной сети, а именно контуры и тупики 1 первого рода. Пусть, например, имеем ориентированный граф изображенный на фиг. 2. Если О - начальная вершина графа, то на выходах моделей других его вершин, при работе устройства в режиме определения рангов вершин, будут напряжения; 1, 2, 3 вершины, образующие контур - напряжения насьпцения операционных усилителей; 4-я вершина - тупик первого рода - нулевое.

Обеспечивается также возможность определения критического пути в графе при помощи устройств : ДЛЯ опреде- ления кратчайшего пути и наоборот. Пусть, например, имеем граф, изображенный на фиг. 3, с указанными длинами дуг и рангами вершин (ранги указаны в квадратах) и устройство для определения кратчайшего пути в графе. Требуется определить критический путь в графе. Посредством преобразования

t;j-(rj-r;) ,. (1) перейдем от графа на фиг. 3 с длинами дуг t;j к графу на фиг. 4 с дли- 1нами дуг t- . В выражении (1) г .

ранги вершин j и i, а

(2)

t .

При помощи имеющегося устройства определяют кратчайший путь в графе на фиг. 4. Им будет путь О-Г-2-3-4 с Т 8. Нетрудно заметить, что этот же путь 0-1-2-3-4 является критическим для графа на фиг. 3. Величину Ткр определяем на основе обратного (1) преобразования

Tkp(r+-r)-.t -T««H -5-8 12,

что соответствует прямому расчету . Пусть теперь требуется при помощи устройства для определения критического пути определить кратчайший путь в графе на фиг. 3. Посредством преобразования (1) перейдем от графа на фиг. 3 с длинами дуг t;; к графу на фиг. 5 с длинами дуг t . . В отличие от первого слу4J

чая здесь

5.

При помощи имеющегося устройства определяем критический путь 0-2-4 с Т 17. Этот же путь 0-2-4 является кратчайшим для графа на фиг. 3, а его

Т (г -г V мич -О - кр - I -5

что соответствует результату прямого расчета.

Формула изобретения

,

30

35

40

45

50

Устройство для моделирования ориентированных графов, содержащее ис25 точник регулируемого напряжения и модели вершин и дуг, соединенные согласно топологии графа, причем модель каждой вершины содержит операционный усилитель, а модель каждой дуги - три масштабных и переменный резисторы и операционньй усилитель, выход которого через последовательно соединенные выпрямительный элемент и первый масштабньй резистор соединен со своим входом, подвижный контакт переменного резистора через второй масштабный резистор соединен с входом операционного усилителя, первьй вывод третьего масштабного резистора подключен к входу операционного усилителя, а второй вывод третьего масштабного резистора соединен с выходом операционного усилителя модели вершины, из которой исходит дуга, отличающееся тем, что, с целью расширения функциональных возможностей путем определения рангов вершин и числа путей в графе, в него, введены блок индика- ции и переключатель, в каждую модель вершины - многополюсный двухпозици- онный переключатель и масштабные резисторы, а в каждую модель дуги - размыкающий контакт и замыкакнций контакт, включенный параллельно вы55 прямительному элементу, в модели вершины размыкающие контакты много- полюсного двухпозиционного переключателя соединены - с первым выводом

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

035486

.переключателя, подвижный контакт которого соедииен с входом блока индикации, первый вывод источника регулируемого напряжения соединен с 5 шиной нулевого потенциала,, второй вывод через размыкающий контакт подключён к первому выводу переменного резистора каждьм модели дуги, второй вывод которого соединен с шиной ну- 10 левого потен1р1ала, а выход операционного уси.пителя каждой модели вершины подключен к соответствующему неподвижному контакту переключателя.

Изобретение относится к аналоговой технике и может быть использовано при решении задач определения характеристик систем, отображаемых графами. Цель изобретения состоит в расширении функциональных возможностей за счет определения рангов вершин и числа путей в графе. Устройство содержит модели дуг 1 и вершин 2, источник 3 регулируемого напряжения, блок 4 индикации и переключатель 5. Модель 1 содержит операционный усилитель 6, вьтрямитель- ный элемент 7, замыкающий контакт 8, масштабные 9, 10 и переменньА 11 резисторы, размыкающий контакт 12. Модель 2 содержит операционный усилитель 13, многрполюсный двухпози- ционный переключатель 14, масштабные резисторы 15. Задавая с помощью резисторов 11 напряжения, пропорциональные длительностям работ, с помощью блока 4 определяют протяженность частных ч общего критических путей. Приписывгш дугам длину, равную 1, определяют ранг вершин, а осуществляя необходимые коммутации с помощью переключателей определяют число путей в графе. 2 ил,. § (Л с: .JJ

Фиг.2

Фиг.5

Составитель А. Шеренков Редактор Г. Волкова Техред О.Ващишина Корректор И. Эрдейи

Заказ 8419/53 Тираж 709Подписное

ВНШПИ Государственного комитета СССР

по делам изобретений и открытий . 113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП Патент, г. Ужгород, ул. Проектная, 4