Устройство для определения числа деревьев графа Советский патент 1979 года по МПК G06G7/48 

(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЧИСЛА ДЕРЕВЬЕВ

ГРАФА торых соединены с выходами всех счетчиков. На чертеже представлена блок-схема устройства для определения числа деревьев графа. Устройство содержит блок 1 перебора сочетаний,запоминающие триггеры 2, управляемые ключевые схемы 3, схему И 4, схему НЕ 5 шину б установки устрой ства в исходное состояние, командную шину 7, шину 8 проверки проводимости, ключи 9, сч&тчики дуг 10, счетчики цепей 11, б«ок сравнения 12, схемы ИЛИ 13, шины 14 отключения триггеров, Входы упрбшляемых ключевых схем соединены между собой в схему, отображающую сеть или орграф, Работа устройстваоснована на том, что проверяется связность всех N узло сети при различных сочетаниях из А дуг сети, по { N -1) дуг, так как после; 1овательность узлов сети X6N , обладающая тем свойством, что (, Х.)при каждом я.1 .., И-1 является цепью: она ведет из .После каждого испы тания количество узлов сети уменьшается до момента, когда из нет ни одного путИ, т, е, до получения разре за сети, содержащего минимальное количество дуг. Устройство работает по тактам t,t2, t,,, fc4 л В такте по шине 6 через схемы ИЛИ Поступает сигнал установки триггеров и счетчикоас в нулевое положение, В каждом такте k на выходе блока перебора сочетания поа.вляется одно из сочетаний С 7 последовательности дуг, ведушнх через узлы N из Х В Кр.которое поступает на входы запоминаюших триггеров 2 и перебрасывает И.Х в единичное срстояние. Триггеры запоминают полученную комбинацию дуг и открывают соответствующие управляемые ключевые схемы. Между входами открытых управляемых ключевых схем 3 образуется электрический контакт. В такте tj по шине 8 поступает сигнал проверки проводимости, который подается на аходы управляемых ключевы . 3. Вход одной из ключевых схем отображает узел сети. Вторые аходы управляемых ключевых схем, отобре жающих цепи из оставшихся ( N-1) узлов, выведены на входы схемы И. Если все узлы сети связаны, то на всех входах схемы И появляются сигналы, и данное сочетание узлов и дуг образует цепь. Схема И срабатывает, и сигнал снее через схему НЕ поступает 55 а счетчик 11, а через ключи, открытые диничным входам запоминающих триггеров, на счетчики 10, соответствующие угам, которые образуют данную цепь, осле выдачи всах возможньк сочетаний локом 1 по шине 7 поступает сигнал кончания испытания. Результаты испыания определяются по показаниям счетика 11, который показывает общее количество цепей сети, и по показаниям четчиков 1О, которые показьшают число цепей сети, образованных с участием соответствующей дуги. В такте 4. блок сравнения 12 проверяет наличие показаний на счетчике 11 и сравнивает показания счетчиков 10, При этом, если показания счетчика 11 не равны нулю, то блок сравнения 12 вььбирает счетчик 10 с наибольшими показаниями и на соответствующем ему выходе 14 формирует единичный сигнал. Этот сигнал через схему ИЛИ 13 и. запоминающий триггер 2 запирает соответствую- щую ключевую схему 3 и ключ 9 счетчика 1О. Получен разрез моделируемой сети. Затем проводятся контрольные испытания полученной сети по тактам .Если в результате очередного испытания показания счетчика 11 оказались равными нулю, то цикл испытаний закончен и полученный разрез сети является минимальным. Результат фиксируется по порядку отключения счетчиков 1О. Таким образом, при добавлении в схему устройства новых элементов (блока сравнения и схем ИЛИ) оно приобретает новые свойства, позволяющие при анализе графа или сети получать разрезы и определить критический (оптимальный) раэрез. Формула изобретения Устройство для определения числа деревьевграфапо аБт,св.№329538, о тичающееся тем, что, с целью расширения функциональных возможностей устройства за счет определения числа дуг минимального разреза сети, в устройство введены блок сравнения и элементы ИЛИ, первые аходы которых подключены к шина установки устройства в нулевое-. состояние, выходы элементов ИЛИ соединены со входами установки в нулевое состояние соответствующих триггеров, вто- 56

рые входы элементов ИЛИ подключены кИсточники информации, принятые во

соответствующим выходам блока сравнения,внимание при экспертизе входы которых соединены с выходами всех1, Авторское свидетельство СССР

счетчиков.№ 329538, G Об G 7/48 197О(прототип).

679998

Н