Устройство для исследования графов

 

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

СОЮЗ СОВЕТСНИ1(СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1 (19) (11) (59 4 С 06 С 7/122

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ. (21) 3926078/24-24 (22) 25.06.85 (46) 23.04,87. Бюл. N 15 (71) Научно-производственное объединение космических исследований при

АН АЗССР (72) О.К.Ханмамедов, И.И.Шваченко и О.Б.Анцупова (53) 681.333(088.8) (56) Авторское свидетельство СССР № 486339, кл. (: 06 G 7/48, 1974.

Авторское свидетельство СССР № 1259281, кл. G 06 С 7/122, 1985.

Авторское свидетельство СССР № 717787, кл. G 06 G 7/122, 1977. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ

{57) Изобретение относится к вычислительной технике и может быть ис- . пользовано при построении специализированных вычислительных устройств для решения задач сетевого планирования, а также при построении и исследовании адаптивных и интеллектуальных систем управления сложными динамическими объектами. Целью изобретения является повышение быстродействия и расширение функциональных возможностей устройства sa счет on13 ределения приоритетов моделей узлов.

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

H второго коммутаторов и изменения

Структурных связей между элементами, что позволяет решать качественно новый класс задач сетевого планирования и управления, в которых требует-. ся определить экстремальные пути на сети (последовательность работ), 05720 последовательно преобразующие исходное состояние в виде n"ðàçðÿäíîãî двоичного кода в конечное состояние (n-разрядный двоичный код). При этом преобразование кода моделируется с помощью узлов, а передача кода моделируется с помощью ветвей, Это позволяет .использовать предлагаемое устройство для построения и исследования адаптивных и интеллектуальных систем управления, имеющих сложную сетевую структуру, кроме этого, в данном устройстве автоматически определяются исходная и конечная модели узлов экстремальных путей с указанием приоритета модулей узлов. 1 з.п. ф лыу 1 1 иле

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

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

На фиг. 1 представлена блок-схема предлагаемого устройства, на фиг.2— схема модели ветви, на фиг. 3 — схема блока управления, на фиг. 4 — схе- 20 ма блока индикации на фиг. 5 — схема модели узла ; на фиг. 6 — схема, первого коммутатора на фиг. 7 — схема второго коммутатора, на фиг. 8 — схема сравнения; на фиг. 9 — схема первого узла памяти; на фиг. 10 — схема узла пуска, на фиг. 11 - схема второго узла памяти.

Устройство для исследования графов (фиг. 1) содержит модели 1 ветвей, генератор 2 тактовых импульсов, блок 3 управления, блок 4 индикации, модели 5 узлов, наборное поле 6, первый 7 и второй 8 коммутаторы.

Модель 1 ветви (фиг. 2) содержит счетчик 9 импульсов, дешифратор 10, триггер 11, группу триггеров 12, элемент И 13, группу элементов И 14 первый 15 и второй 16 элементы ИЛИ, элемент 17 задержки, группу информационных входов 18, входы установки в "0" 19<, запуска 19< и тактовых импульсов 19, группу информационных выходов 20, группу приоритетных выходов 21,.группу информационных выходов 22 и установочный выход 23.

Блок 3 управления (фиг. 3) содержит выходы разрешения сброса 19,, разрешения начала работы 19 и тактовых импульсов 19,, группу входов

23 установки нуля, коммутационный элемент 24 (" Сброс" ), узел 25 пуска, триггер 26, схему 27 сравнения, первый 28 и второй 29 элементы И, первый 30 и второй 31 счетчики импульсов, первый 32 и второй 33 дешифраторы, элемент И-HE 34, первый 35 и второй 36 элементы задержки, первый

37 и второй 38 элементы ИЛИ, умножитель 39 частоты, первый 40 и второй 41 узлы памяти, вход 42 тактовых импульсов, группу информационных вхо дов 43, группу выходов 44 разрешения индикации адреса модели узла конца пути, группу выходов 45 разрешения индикации адреса модели узла начала пути, группу выходов 46, выход 47

13О57

3 разрешения индикации и выход 47 окончания работы.

Блок 4 индикации (фиг. 4) содержит первый 48 и второй 49 коммутаторы, первую группу 50 светодиодов, состояп1ую из первой 50 и второй 50 подгрупп светодиодов, содержащих по светодиодов, причем у второй подгруппы 50 светодиодов первой группы аноды соответствуют входам моделей 10 узлов, а катоды — выходам моделей узлов, вторую rpymry 5 1 светодиодов, содержащую k подгрупп светодиодов, третий светодиод 52, источник 53 постоянного тока, транзисторный ключ 15

54, обмотку реле 55, нормально разомкнутые контакты 56 реле 55, источник 57 напряжения и группу из k сопротивлений 58.

Модель 5 узла (фиг. 5) содержит 20 дизъюнктивную программируемую логическую матрицу, состоящую из группы нагрузочных сопротивлений 59 и группы диодов 60, группу элементов ИЛИ 61 первую 62 и вторую 20 группы информационных входов и группу выходов 18.

Первый коммутатор 7 (фиг. 6) представляет собой п-разрядный коммутатор и содержит группу из и параллель но соединенных одноразрядных коммута- 30 торов 63, группу управляющих входов

44, группу информационных входов 22 и группу выходов 43. Каждый коммутатор 63 содержит k входов адресования, выход и k информационных входов. 35

Группа информационных входов состоит из k подгрупп входов, а каждая подгруппа — из и входов.

Второй 8 коммутатор (фиг. 7) представляет собой и-разрядный коммутатор40 и содержит группу из п параллельно соединенных одноразрядных коммутаторов 64 группу управляющих входов

45, группу информационных входов и группу выходов 62. Каждый коммутатор 45

64 содержит k входов адресования, информационный вход и k выходов. Группа выходов 62 состоит из k подгрупп выходов, а каждая погруппа — из и выходов.

Схема 27 сравнения (фиг. 8) содержит группу элементов РАВНОЗНАЧНОСТЬ

65, элемент И 66, первую 43 и вторую

68 группы входов, третий вход 67 и выход 47 . 55

Первый 40 узел ламяти (фиг. 9) содержит группу триггеров 69, группу элементов И 70, элемент 71 задержки, 20 4 первый 72 и второй 19 входы, группу входов 73 записи и группу выходов 46.

Узел 25 пуска (фиг. 10) содержит первый 74 и второй 75 элементы ИЛИ, счетчик 76 импульсов, элемент 77 задержки, первый 78 и второй 79 триггеры, первый 80, второй 81 и третий

82 элементы И, коммутационный элемент 83 (" Пуск" ), вход 42 тактовых импульсов, вход 47 разрешения начальной установки, дополнительный вход 84 установки нуля, вход 85 разрешения промежуточной установки, группу входов 23 установки нуля, выход 67 разрешения сравнения, выход

86 разрешения счета и выход 19 разрешения начала работы.

Второй узел 41 памяти (фиг. 11) ,содержит группу триггеров 87, первый вход 72, группу входов 88 записи и группу выходов 68. При этом 72 первый вход соединен с входами установки нуля триггеров 87, входы установки единицы которых подключены к группе входов 88, а прямые выходы триггеров 87 подключены к группе выходов 68.

Устройство работает следующим образом.

В исходном состоянии, перед решением задачи на устройстве, светодиоды второй подгруппы 50 первой группы блока 4 индикации соединены между собой в соответствии с топологией графа, а модели 1 ветвей и модели 5 узлов также скоммутированы между собой на наборном поле 6 в соответствии с топологией графа. Наборное поле 6 представляет собой совокупность, например пары гнездо-штеккер.

Нажатием коммутационного элемента

24 "Сброс" в блоке 3 управления производится сброс всех триггеров и счетчиков устройства в исходное нулевое состояние, так как при этом нормально разомкнутые контакты коммутационного элемента 24 замыкаются. и единичные импульсы с выхода генератора 2 поступают на входы 72 первого 40 и второго 41 узлов памяти, на соответствующие входы первого 37 и второго 38 элементов ИЛИ, а также на входы установки нуля второго счетчика 31 н триггера 26 блока 3 управления. С входа 72 единичные импульсы поступают на входы установки нулей триггеров 69 и 87 первого 40 и второго 41 узлов памяти, поэтому 13057 триггеры устанавливаются в нулевое состояние. С вйхода первого элемента

ИЛИ 37 единичные импульсы поступают через вход 19 всех моделей 1 ветвей на (п+1)-й вход элемента ИЛИ 16 и входы установки нулей группы триггеров 12 и счетчика 9, а с выхода элемента ИЛИ 16 единичные импульсы поступают на вход установки нуля триггера 11 и выход 23 модели 1 ветви. С выхода 2Э через первый элемент ИЛИ 74 единичные импульсы поступают на входы установки нуля счетчика 76 и первого триггера 78 узла

25 пуска. С выхода элемента ИЛИ 38 единичные импульсы поступают через вход 84 узла 25 пуска на вход установки нуля триггера 79.

Триггер 78 находится в нулевом состоянии, поэтому на выходе 67 узла 20

25 пуска имеется нулевой потенциал, который поступает на (n+i) é вход элемента И 66 схемы 27 сравнения, и на выходе элемента И 66 имеется нулевой потенциал. При этом транзистор25 ный ключ 54 блока 4 индикации закрыт, поэтому обмотка реле 55 обесточена и контакты 56 разомкнуты, а значит, светодиоды второй подгруппы

50 первой группы закрыты и индикация отсутствует. Светодиод 52 и вто- о рая группа,51 светодиодов также закрыты, так как триггер 26 блока 3 управления и счетчики 9 модели 1 ветвей находятся в нулевом состоянии. 35

Затем на входы 73 и 88 записи соответственно первого 40 и второго 41 узлов памяти оператором заносятся двоичные коды исходного и конечного состояний исследуемого графа соответственно, а на вход установки второго счетчика 31 оператором подается последовательный двоичный код адреса исходной модели 5 узла. Номер исходной модели 5 узла индицируется с помощью первой подгруппы 501 светодиодов первой группы блока 4 индикации, и при появлении единичного потенциала на соответствующем выходе

45 группы выходов блока 3 управления соответствующий светодиод подгруппы

50< открывается.

Пусть в момент времени t происходит запуск устройства нажатием комму- 5

5 тационного элемента 83 "Пуск" в узле 25 пуска. При этом нормально-замкнутые контакты коммутационного элемента 83 размыкаются, а нормально

20 6 разомкнутые контакты замыкаются, и единичные импульсы с выхода генератора 2 импульсов поступают на вход установки единицы триггера 79 и первый вход элемента И 82, с выхода которого через элемент ИЛИ 75 единичные импульсы поступают на входы установки единицы триггеров 11 всех моделей 1 ветвей и вход элемента 7 1 задержки, представляющий собой диф ференцирующую резистивно-емкостную, цепочку, первого узла 40 памяти. На прямом выхсде триггера 11 устанавливается единичный потенциал, который, поступая на первый вход элемента

И 13, разрешает поступление единичных а импульсов с выхода умножителя 39 частоты через элемент И 13 на счетный вход счетчика 9 импульсов.

Одновременно через определенный промежуток времени, после поступления единичного импульса на вход элемента

71 задержки на его выходе появляется единичный импульс, поступающий на вторые входы элементов И 70, что при водит к появлению единичных импульсов на выходе тех элементов И 70, на первые входы которых поступает еди-, ничный сигнал с прямых выходов триггеров 69, При этом время задержки передачи единичного импульса элементом 71 задержки должно быть не меньше суммы времени задержки переключения вторых счетчика 31, дешифратора

33 и коммутатора 8, С выхода первого узла 40 памяти двоичный код исходного состояния пос тупает на группу входов второго коммутатора 8, с группы выходов которого двоичный код поступает на группу входов 62 той исходной модели 5 уз- . лов, адрес которой записан во втором счетчике 31 блока Э управления, На выходах соответствующих элементов

ИЛИ 61 появляются единичные импульсы поступающие на аноды соответствующих диодов 60, и на выходых 18 модели 5 узла, связанных с катодами этих дио" дов 60, также появляются единичные импульсы, которые поступают через наборное поле 6 на группу входов 18 соответствующей модели 1 ветви. Поэтому в модели 1 ветви на прямых выходах соответствующих триггеров 12 устанавливаются единичные сигналы, которые поступают на входы элемента

ИЛИ t5, и на его выходе появляется единичный сигнал, который через элемент 17 задержки, представляющий со7 13057 бой. дифференцирующую резистивно-емкостную цепочку, поступает на входы группы элементов И 14.При этом единичные импульсы появляются на выходе тех элементов И 14, на входы которых пос- 5 тупает единичный сигнал с прямых выходов триггеров 12. Единичные импульсы с выходов элементов И 14 поступают на входы элемента ИЛИ 16 и через наборное поле 6 на группу входов 20 10 соответствующей модели 5 узла и т.д.

При этом на выходе элемента ИЛИ 16 появляется единичный импульс, который поступает на вход установки нуля триггера 11, и на его прямом выходе 15 устанавливается нулевой потенциал, который блокирует поступление единичных импульсов с выхода умножителя 39 частоты через элемент И 13 на счетный вход счетчика 9. С выхода элемента ИЛИ 16 единичный импульс поступает также на соответствующий вход элемента ИЛИ 74 узла 25 пуска, и на. выходе элемента ИЛИ 74 появляется единичный импульс, который поступает на входы установки нулей триггера 78 и счетчика 76 и устанавливает их в нулевое состояние, Затем на счетный вход счетчика 76 поступают импульсы с выхода элемента И 81, первый вход которого подключен к выходу-генератора 2, а на второй вход элемента И 81 поступает единичный потенциал с прямого выхода триггера

79. На выходе счетчика 76 формирует- 35 ся единичный импульс переполнения только в том случае, если промежуток времени между двумя последовательными единичными импульсами, поступающими на входы 23 элемента. ИЛИ 74, превышает в 2 раза время ь,, равное сумме времен задержки передачи единичного сигнала триггером 12, элементом И 14, первым 15 и вторым 16 элементами ИЛИ и элементом 17 задержки модели 1 ветви и элементом

ИЛИ 61 модели 5 узла. При этом единичные импульсы на выходах элементов

ИЛИ 16 моделей 1 ветвей последовательно появляются с промежутком времени, равным,, поэтому появление единичного импульса на выходе счетчика 76 означает, что вычислительный процесс, т,е. преобразование двоичного кода в каждой модели 5 узла и передача этого кода каждой моделью 1 ветви сети, завершен, и на выходе элемента 77 задержки, пред20 8 ставляющего собой резистивно-емкостную цепочку, появляется единичный импульс, который поступает на вход установки единицы триггера 78 узла

25 пуска, На прямом выходе триггера

78 в момент времени t устанавлива2 ется единичный потенциал, который поступает на первый вход элемента

И 80 и (n+i)-é вход элемента И 66 схемы 27 сравнения, Единичные импульсы с выхода элемента И 81 поступают также на второй вход элемента И 80, с выхода которого поступают на счетный вход первого счетчика 30, и в зависимости от количества поступивших импульсов на соответствующем выхоце первого дешифратора 32 появляется единичный сигнал, Этот сигнал поступает HB группу входов первого коммутатора 7 и определяеT адрес модели

1 ветви, группа выходов 22 которой подключена через первый коммутатор 7 к группе входов 43 схемы 27 сравнения„

Таким образом, первый коммутатор 7 последовательно подключает группу выходов 22 всех моделей 1 ветвей к группе входов 43 схемы 27 сравнения.

Если в момент времени t появляется единичный сигнал на выходе схемы

27 сравнения, это значит, что двоичный код конечного состояния сети, записанный во втором узле 41 памяти и поступающий на группу входов 68 схемы 27 сравнения, совпадает с двоичным кодом, который поступает на группу входов 43 схемы 27 сравнения, например, с группы выходов 22; i-й модели 1; ветви. Поэтому на выходах всех элементов РАВНОЗНАЧНОСТЬ 65 устанавливаются единичные сигналы и на выходе элемента И 66 также появляется единичный сигнал, который поступает на вход второго элемента 36 задержки, представляющий собой дифференцирующую резистивно-емкостную цепочку. На его выходе появляется единичный импульс, поступающий на соответствующий вход второго элемен та ИЛИ 38, с выхода которого единйч" ный импульс поступает на вход 84 ус-. тановки нуля триггера 79 узла 25 пус" ка, и на прямом выходе триггера 79 устанавливается нулевой сигнал, который блокирует элемент И 81. На .его выходе устанавливается нулевой сигнал, т.е. единичные импульсы на счетный вход первого счетчика 30 не поступают, так как на выходе элемента

1305720

И 80 также устанавливается нулевой сигнал, потому что на его второй вход поступает нулевой сигнал с выхода эл мента И 81. При этом период следования импульсов на выходе гене- . 5 ратора 2. должен быть больше времени равного сумме времен задержки передачи единичного сигнала триггера

79, первого 80 и второго 81 элементов

И узла 25 пуска, первого счетчика 30, 10 первого дешифратора 32, второго элемента 36 задержки, второго элемента

ИПИ 38 блока 3 управЛения, первого коммутатора 7,элемента РАВНОЗНАЧНОСТЬ

65 и элемента И 66 схемы 27 сравнения. Поэтому в момент времени t в первом счетчике 30 записано i импульсов„ а значит, выход второго коммутатора 49 блока 4 индикации подключен к катоду х-ro светодиода 50, второй подгруппы первой группы светодиодов. Так как на вход 47 транзисторного ключа 54 подается высокий положительный потенциал с выхода схемы 27 сравнения, то обмотка реле

55 подключена к источнику 57 напряжения и контакты 56 замкнуты. Допустим, во второй счетчик 31 записано (i+1) импульсов, поэтому íà (i+1)-м выходе 45„ +, второго дешифратора 33 имеется единичный сигнал и группа входов 46 второго коммутатора 8 подключена к группе входов 62, „,, (i+I)-й модели 5 узла, а информационный вход первого коммутатора 48 35 блона 4 индикации подключен к (i+1)-му аноду светодиода 50 „„ второй подгруппы первой группы светодиодов, При этом ток от источника 53 тока протекает по.цепи: выход источI ника 5 тока, информационный вход первого коммутатора 48, анод (i+1)-го светодиода 50« последовательная цепочка из светодиодов 50, соединен-. 4 ных между собой в соответствии с топологией исследуемого графа, катод

i-ro светодиода 50<„, i-й информаI ционный вход второго коммутатора 49, выход второго коммутатора 49, замк- 50 нутые контакты 56 и вход источника

53 тока. Светодиоды подгруппы 50, находящиеся на кратчайшем пути между (i+1)-и и i-м светодиодами подгруппы

50< „ открываются, и излучение с этих диодов попадает на соответствующие фотосопротивления 58, а именно: излучение со светодиода 50,, — на фотосопротивление 58;, и так далее., Таким образом, с помощью светодиодов подгруппы 50 осуществляется индикация моделей S узлов, находящихся на найденном пути графа, на котором осу. ществляется последовательное преобразование исходного состояния в конечное состояние сети.

Если, например, в счетчике 9, i-й модели 1, ветви записано р импульсов (р = i. 2,,„,, m), то на р-м выходе

21„ дешифратора 10; имеется единичный сигнал, который поступает на р-й анод светодиода 51; i-й подгруппы второй группы светодиодов блока 4 индикации, При этом светодиод 51;> открывается, так как сопротивление фотосопротивления 58„ мало из-за того, что на него попадает световой поток излучения светодиода 50, и, таким образом, происходит индикация приоритета модели 5, узлов, а фотосопротивления 58, которые не освещены, имеют большое сопротивление. Поэ. тому величина тока, протекающего в сопротивлении, мала, и светодиоды группы 51, соединенные с этим сопро. тивлением, закрыты.

При этом содержание счетчика 9„ модели 1,„ ветви определяет приоритет модели 5; узла, и чем больше содержимое счетчика 9,, тем выше приоритет модели S; узла. Очевидно, что приоритет модели 5, узла в рассматриваемом случае на найденном пути самый высокий, а приоритет модели

5,,„ узла самый низкий, и тогда модель

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

После регистрации найденного пути оператор вновь осуществляет запуск устройства для поиска других путей, нажимая коммутационный элемент 83

"Пуск" в момент времени t . При этом триггер 79 узла 25 пуска устанавливается в единичное состояние, и импульсы с выхода генератора 2 снова поступают через второй 81 и первый

80 элементы И на счетный вход перво" го счетчика 30, а первый коммутатор

11 13057

7 продолжает подключать группы выходов 22 моцелей 1 ветвей к группе входов 43 схемы 27 сравнения. Если коды на группах входов 43 и 68 схемы 27 сравнения не совпадают, то на ее выходе 47 устанавливается нулевой сигнал, так как на соответствующих выходах элементов РАВНОЗНАЧНОСТЬ 65 присутствуют нулевые сигналы, поступающие на входы элемента И 66, поэ- 10 . тому все светодиоды в блоке 4 индикации обесточены и индикация не про--. изводится.

Если первый счетчик 30 накопил k импульсов, то на k-м выходе первого 15 дешифратора 32 устанавливается единичный сигнал, и с приходом (k+1) — го импульса на счетный вход первого счетчика 30 на Е-м выходе 44 первого дешифратора 32 устанавливается ну- 29 левой сигнал. Поэтому на выходе элемента И-НЕ 34 устанавливается единичйый сигнал, а на выходе первого элемента 35 задержки, представляюще-. го собой дифференцирующую резистивно 25 емкостную цепь, появляется единичный импульс, который поступает на счетный вход второго счетчика 31, и

его содержимое увеличивается на единицу, например становится равным 30

i+2. На (i+2)-м выходе 45„, второ го дешифратора 33 устанавливается единичный сигнал, и двоичный код исходного состояния с группы выходов

4b первого узла 40 памяти поступает 35 через второй коммутатор 8 на группу входов 62 (i+2)-й модели 5„, узла. !

При этом, если на выходе схемы

27 сравнения имеется нулевой сигнал, 40 который подается на инверсный вход элемента И 28, то единичньй импульс с выхода первого элемента 35 задержки последовательно поступает на вход ° элемента И 28, а с его выхода — на 45 вход элемента ИЛИ 37, входы установки нуля первого счетчика 30 и триггеров 12 и (и+1)-й вход элемента

ИЛИ 16 всех моделей 1 ветвей. Поэтому первый счетчик 30 и триггеры 12 устанавливаются в нулевое состояние, а триггер 11 всех моделей 1 ветвей, счетчик 76 и триггер 78 узла 25 пуска также устанавливаются в нулевое состояние, так как единичный импульс 55 с выхода элемента ИЛИ 16 одновременно поступает на вход установки нуля триггера 11 и соответствующий вход ,23 первого элемента ИЛИ 74 узла 25

12

20 пуска, с выхода которого единичньй импульс поступает на входы установки нуля счетчика 76 и триггера 78. Нуле. вой сигнал на прямом выходе триггера

78 блокирует элемент И 80 и элемент

И 66 схемы 27 сравнения, поэтому на их выходах удерживаются нулевые сигналы.

Единичный импульс с выхода первого элемента 35 задержки поступает также на второй вход элемента ИЛИ 75 узла 25 пуска, а с выхода элемента

ИЛИ 75 единичный импульс поступает на входы установки единицы триггеров

11 всех моделей 1 ветвей и вход элемента 71 задержки первого узла 40 памяти. Далее вычислительный процесс протекает как описано с момента времени С„ до момента

Если в момент времени t первый

30 и второй 31 счетчики блока 3 управления накопили по k импульсов, то на выходах 44 k и 45у соответственно первого 32 и второго 33 дешифраторов устанавливаются единичные сигналы. С приходом на счетньй вход первого счетчика 30 (k+1) -го импульса с выхода генератора 2 на выходе 44, первого дешифратора 32 устанавливается нулевой сигнал и на выходе элемента

И-НЕ 34 появляется единичный сигнал, а на выходе первого элемента 35 задержки появляется единичный импульс, который поступает на первые входы элементов И 28 н 29, счетньй вход второго счетчика 31 и второй вход элемента ИЛИ 75 узла 25 пуска. Так. как на второй вход элемента И 29 поступает едипичньй сигнал с выхода

451. второго дешифратора 33, то на вы ходе элемента И 29 появляется единичный импульс, который поступает на вход установки единицы триггера

26 и первый вход элемента ИЛИ 38. На прямом выходе триггера 26 устанавливается единичный сигнал, который поступает на анод светодиода 52 блока

4 индикации и открывает его. Таким образом, осуществляется индикация окончания вычислительного процесса поиска путей на графе, С приходом на счетньй вход второго счетчика 3 1 (k+1)-ro m nyar cz с выхода первого элемента 35 задержки на выходе 451, второго дешифратора 33 устанавливается нулевой сигнал, С выхода первого элемента 35 задержки единичньй импульс поступает

ЗО

13 130 также на второй вход элемента ИЛИ 75 узла 25 пуска, а с выхода элемента

ИЛИ 75 единичный импульс поступает на входы установки единицы триггеров 11 устанавливая их в единичное состояние, и вход элемента 71 задерж ки первого узла 40 памяти, С выхода элемента ИЛИ 38 единичный импульс поступает на вход установки нуля триггера 79, и на его прямом выходе устанавливается нулевой сигнал, который блокирует второй элемент И 81 и с выхода, генератора 2 импульсы на выход элемента И 81 не поступают.

Далее, если на выходе схемы 27 сравнения имеется нулевой сигнал, то элемент И 28 открыт, и единичный импульс с выхода первого элемента 35 задержки через элемент И 28 и элемент ИЛИ 37 подается на входы установки нуля первого счетчика 30 и триггеров 12 и (n+1)-й вход элемента

ИЛИ 1ф всех моделей 1 ветвей. Поэтому первый счетчик 30 и триггеры 12 устанавливаются в нулевое состояние, а триггер 11 всех моделей 1 ветвей, счетчик 76 и триггер 78 узла 25 пуска также устанавливаются в нулевое состояние, так как единичный импульс с выхода элемента ИЛИ 16 одновременно поступает на вход установки нуля триггера 11 и соответствующий вход

23 первого элемента ИЛИ 74 узла 25 пуска, с выхода которого единичный импульс поступает на входы установки нуля счетчика 76 и первого триггера 78. Нулевой сигнал на прямом выходе триггера 78 блокирует первый элемент И 80 и элемент И 66 схемы.

27 сравнения, поэтому на их выходах удерживаются нулевые сигналы, Таким образом, все триггеры и счетчики устройства устанавливаются в нулевое состояние за исключением триггеров первого 40 и второго 41 узлов памяти и триггера 26 блока 3 управления, которые сбрасываются в нулевое состояние нажатием коммутационного элемента 24 "Сброс" блока

3 управления.

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

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

1. Устройство для исследования графов, содержащее генератор такто5720 l4 вых импульсов, блок управления, группу моделей узлов, группу моделей ветвей, блок индикации и наборное поле, блок управления содержит первый и второй элементы задержки, первый и второй элементы И и триггер, каждая из моделей ветвей содержит триггер и элемент И, причем каждый i-й выход (где i = 1, 2, ..., n) j-й подгруппь; (j = 1, 2, ..., 1с) первой группы информационных выходов наборного поля подключен к i-му информационному входу j-й модели ветви группы, каждый i-й выход j-й подгруп" пы второй группы информационных выходов наборного поля подключен к

i-му входу первой группы информацион. ных входов j"é модели узла группы, i-й информационный выход каждой j-u модели ветви группы подключен к -му входу j-й подгруппы первой группы информационных входов наборного поля, о каждый i-й информационный выход группы выходов j"É модели узла группы подключен к i-му входу j"é подгруппы второй .группы информационных входов наборного поля, каждый ij-й вход группы входов индикации приоритета блока индикации подключен к i-му выходу группы приоритетных выходов

j-й модели ветви, вход разрешения индикации и вход индикации конца вычислительного процесса блока индика ции подключены соответственно к выходу разрешения индикации и выходу окончания работы блока управления, вход установки в "0", вход запуска и вход тактовых импульсов каждой модели ветви группы подключены соответственно к выходу разрешения сбро ° са, выходу разрешения начала работы и выходу тактовых импульсов блока управления, о г л и ч а ю щ е е с я тем, что, с целью повышения быстродействия и расширения функциональных возможностей устройства за счет определения приоритета моделей узлов, в него введены первый и второй комму\ таторы, в блок управления введены коммутационный элемент, узел пуска, схема сравнения, первый и второй счетчики импульсов, первый и второй дешифраторы,i элемент И-НЕ, первый и второй элементы ИЛИ, умножитель частаты, первый и второй узлы памяти; в модель ветви: введены счетчик импульсов, дешифратор, группа триггеров, группа элементов И, первый и второй элементы ИЛИ и элемент задержки,при1305720

55

40

55 чем в каждой модели ветви вход установKH в "1" каждого .-го триггера группы является соответствующим входом группы информационных входов модели ветви, прямой выход каждого 1-ro тригге- 5 ра группы подключен к первому входу

i-ro элемента И группы к i-му входу первого элемента ИЛИ, входы установки в "0" всех триггеров группы объедииены с входом установки в "0" счетчи- 50 ка, с (и+1)-м входом второго элемента ИЛИ и являются входами установки в "0" модели ветви, вторые входы элементов И группы модели ветви объединены и подключены к выходу элемента задержки, вход которого подключен к выходу первого элемента ИЛИ модели ветви, выход каждого i-5 о элемента И первой группы модели ветви подключен к х-му входу второго элемента ИЛИ модели ветви и является д-м выходом группы информационных выходов модели ветви, выход второго элемента ИЛИ модели ветви подключен к входу установки в "0" триггера модели ветви, вход установки в "1" которого является входом запуска модели ветви, прямой выход триггера модели ветви подключен к первому входу элемента И ,модели ветви, второй вход которого является тактовым входом модели ветви, выход эдемента И модели ветви подключен к счетному входу счетчика модели ветви, разрядные выходы которого подключены соответственно к входам дешифратора, выходы которого являются группой приоритетных выходов модели ветви и подключены к соответствующим входам группы информационных входов первого. коммутатора, прямой выход каждого i-ro триггера группы модели ветви является i-м выходом группы информационных выходов модели ветви, выход второго элемениа ИЛИ каждо" j-и модели ветви подключен к j-му входу группы входов уста" новки нуля узла пуска блока управления, в блоке управления вход тактовых импульсов узла пуска объединен с входом умножителя частоты и подключен к выходу генератора тактовых импульсов, выход умножителя частоты является выходом тактовых импульсов блока управления, выход разрешения начала работь узла пуска подключен к входу разрешения записи первого узла памяти и является выходом разре-. шения начала работы блока управления. выход разрешения начала сравнения узла пуска подключен к входу разрешения сравнения схемы сравнения блока управления, выход которой подключен к входу разрешения начальной установки узла, пуска, к первому входу перво.ro элемента И блока управления, к входу второго элемента задержки блока управления и является выходом .разрешения индикации блока управления, выход разрешения счета узла пуска подключен к счетному входу первого счетчика блока управления, вход

;сброса которого подключен к выходу первorо элемента ИЛИ блока управления, выход первого элемента ИЛИ блока управления является выходом разрешения сброса блока управления, дополнительный вход установки нуля узла пуска подключен к выходу второго элемента ИЛИ блока управления, вход разрешения промежуточной установки узла пуска пбдключен к выходу первого элемента задержки блока управления, группа разрядных выходов первого счетчика блока управления соответственно подключена к группе входов первого дешифратора блока управления, группа выходов которого соответственно подключена к группе управляющих входов первого коммутатора и к . группе входов индикации адреса моде-, ли узла конца пути блока индикации, кроме этого, в блоке управления k-й выход дешифратора через элемент И-НК подключен к входу первого элемента задержки, выход которого подключен к второму входу первого элемента И блока управления, выход которого подключен к первому входу первого элемента ИЛИ блока управления, второй вход первого элемента KlH блока упи равления объединен с входом установки

I нуля второго счетчика блока управления, с входом установки нуля триггера блока управления, с первым входом второго элемента ИЛИ блока управления, с входом установки в "0" первого узла памяти блока управления, с входом установки в "0" второго узла памяти блока управления и через нормально замкнутые контакты коммутационного элемента блока управления подключены к шине нулевого потенциала, а через нормально разомкнутые контакты коммутационного элемента— к выходу генератора тактовых импульсов, выход первого элемента задерж1305720 ки блока управления подключен к счетному входу второго счетчика блока управления и первому входу второго элемента И блока управления, выход которого подключен к входу установки в "1" триггера бЛока управления и, второму входу второго элемента ИЛИ блока управления, прямой выход триггера блока управления является выходом окончания работы блока управле- 1р ния, выход второго элемента задержки блока управления подключен к третьему входу второго элемента ИЛИ блока управления, группа разрядных выходов второго счетчика блока управления 15 соответственно подключена к группе входов второго дешифратора блока управления, группа выходов которого соответственно подключена к группе управляющих входов второг0 коммутато" 20 ра и группе входов индикации адреса модели узла начала пути блока индикации,,кроме. этого, в блоке управления k-й выход второго дешифратора подключен к второму входу второго 25 элемента И блока управления, группа выходов второго узла памяти блока управления подключена к первой группе информационных входов схемы сравнения.блока управления, группа входов ЗО

I записи второго узла памяти блока управления является группой входов конечного состояния исследуемого гра. фа устройства, группа входов записи первого узла памяти является группой входов начального состояния исследуемого графа. устройства, установочный вход второго счетчика блока управления является установочным входом блока управления, группа выходов пер- 40 вого коммутатора соответственно подключена к второй группе информационных входов схемы сравнения блока управления, группа выходов первого узла памяти блока управления соответ- 45 ственно подключена к группе информационных входов второго .коммутатора, rруппа выходов которого соответственно подключена к группе входов моде" лей узлов.

2. Устройство по п, 1, о т л и— ч а ю щ е е с я тем, что узел пуска содержит первый элемент ИЛИ. счетчик, элемент задержки, первый и второй триггеры, первый, второй и третий элементы И; коммутационный элемент и второй элемент ИЛИ, выход которого является выходом разрешения начала работы узла, первый вход второго элемента ИЛИ является входом разрешения промежуточной установки узла, а второй вход второго элемента ИЛИ подключен к выходу третьего элемента И первый вход которого является входом разрешения начальной установки узла, второй вход третьего элемента И через нормально замкнутые контакты коммутационного элемента подключены к шине нулевого потенциаФ ла вход установки в "1" второго триггера объединен с вторым входом третьего элемента И и через нормально разомкнутые контакты коммутационного элемента объединен с первым входом второго эпемента И и является входом тактовых импульсов узла, вход установки нуля второго триггера является дополнительно входом установки нуля узла, прямой выход триггера подключен z второму входу второго элемента И, выход которого подключен к первому входу первого элемента И, к счетному входу счетчика, вход установки в "0 которого подключен к выходу первого элемента ИЛИ, группа входов которого является группой входов установки нуля узла, выход первого элемента ИЛИ подключен к входу установки нуля первого триггера, выход счетчика через элемент задержки подключен к входу установки в "1" первого триггера, выход которого подключен к второму входу первого элемента И и является выходом разрешения сравнения узла, выход первого элемента И является выходом разреше ния счета узла.

20, zg

) 305720

1305720!

305720

41) 1

Фиа 77

Составитель Т.Сапунова

Техред В. Кадар Корректор M.Ñàìáîpñêàÿ

Редактор О.Юрковецкая

Тираж б73 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, .Раушская наб., д. 4/5

Заказ 1454/48

Производственно-полиграфическое предприятие, г. Ужгород, ул. !!роектная, 4