433485

) Зависимое от авт. свидетельства(22) Заявлено 05,04 72(21) 176 18-24 (51) М. Ки Оея 5/20 Сзеуднратвнаай неинтет Веаатв Инннетрев ВСЮ не денни нзебретеннй н нтнрытнй(72) Автор . изобретен Заявите ститут злектродииами(56 УСТРОЧСТВО ДЛЯ ОПРЯЕЛЕНИИ ХРОМАТИЧЕСКОГО ЧИСЛА ГРАФАетзобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных машин для решения задач исследования 5 операций и теории графов.Известны устройства для определенИя хроматического числа графа, содержащие блок управления, выход которого соединен с блоком то индикации, а вход подключен к генератору ймпульсове и наборное поле. Однако, эти устройства не позволяют получить данные о величине хроматического числа связного 15 графа"редлагаемое устройство отличается от известных тем, что оно содержит блох определителей цвета узлов, информационные входы и вы- ЯО ходы йоторых соединены на наборноМ . поле согласно топологии графа, управляющие входы и выходы подключены ко вхоцам и выходам блока управления, импульсные входы подклю- иь чены к генератору импульсов, информационные выходы соединейн свходами блока индикации, а сам оп-;ределитель цвета узла содержит накопитель имцульсов, две группыэлементов "И", два элемента иИЛИеи элемент памяти. К соответствующим входам злемейта памяти подключены входные полюсы, вход первогосброса и импульсные входы второйи третьей фаз управления определителя цвета узла, вход пуска определителя цвета узла через первыйэлемент "ИЛИ", подключенный вторымвходом к выходу элемента памяти,соединен со входом накопителя импульсов, выходы которого соединены с первыми входами соответствующих элементов "И" первой группы и,кроме первого выхода, с первымивходами соответствующих элементовиИ" второй группы второй входпервого элемента Ли первой группы подключен к входу первого цикла решения определителя цвета уз3ла, а вторые входы остальных элемейтов "И" первой группы объединены со вторыми вхоцамй соответствующих элементов "И" второй группы иподключены к входам соответствующего цикла решения определителяцвета узла, третьи входы элементов"И" первой группы подключены квходу опроса определителя цветаузла, а третьи входы элементов "Увторой группы - к входу второгосброса определителя цвета узла;выходы элементов "Л" первой группычерез второй элемент "ЛЛИ" соединены с выхоцным полюсом определителя цвета узла, а выходы элементов "Л" второй группы соединены ссоответствующими вхоцами элелентапамяти.На. Фиг. 1 приведена блок:схема устройства для определения хроматического числа графа; на фиг.2- функциональная схема определитзля цвета узла.Устройство соцержит блок 1управления, блок 2 определителейцвета узла, число которых равночислу переменных задачи, наборноеполе Э, генератор 4 импульсов,блок 5 инцикации, Опрецелительцвета узла содержит накопитель импульсов 6, элемент 7 памяти, первую группу трехвходовых элементов8 "Л", число которых равно числувыходов накопителя импульсов 6,вторую группу трехвходовых элементово "И", число которых на единицу меньше, чем число выходов накоителя имйульсов 6, элементы ИЛИОи 11.накопитель импульсов можетбыть прецставлен счетчиком импульсов, цпо 1 остойчивым запоцшиющимэлементом или регистром сцвига иявляется узлом, в котором накапливается и выделяется в конце решения признак цвета узла.Элемент 7 памяти имеет трисостояния: исходное первое), рабочее (второе, исключающее(третье), при 4 ем переход в рабочеесостоянйе возможен только послеустанова исхоцного состояния. Еслиустанова в исхоцное состояние нет,то элемент памяти сохраняет исключающее третье) состояние. Он может быть реализован любым из из 10Ф ние элемента памяти по входу 16 20 пуска через схему "ИлИ" 10 в накопители импульсов заносится одиночный имцульс, послечего каждый накопитель импульсов 6 выдает разрешение на своем первом выходе 17.2 б В дальнейшем до конца решения повходу 16 пуска никакие импульсы не поступают. 60 бб 30 Зб 40 4 б вестных способов и служит для выделения импульсов, поступающих в накопитель импульсов.Перед началом работы устройства вершины исследуемого граФанумеруются в произвольном порядке,а на наборном поле коммутируютсямежду собой в соответствия с произведенной нумерацией полюсы опецелителей цвета узлов-входные2 и выходные 13,При подаче сигнала "Пуск"блок 1 управления устанавливаетисходное состояние схемы: на вход14 первого цикла решения всех опрецелителей поступает разрешающий потенциал, по входу 15 сброса устанавливается исходное состояБлок 1 управления последовательно опрашивает импульсами, синхронизированными с первой фазой тактового генератора по входам 18 опроса элементы "И" 8 первой группы всех определителей цвета узлов. Выходнои сигнал первого элемента "И" 8, пройдя через элемент "ИЛИ" 11, появится на выходном полюсе 13 определителя цвета узла, которы." в соответствии с топологией графа, связан соответствующей клеммси наборного 3 поля с входными полюсами 12 других определителей. Сигнал на входном полюсе переводит в рабочее состояние элемент 7 памяти соответствующего определителя цвета узла.В рабочем состоянии элемент 7 памяти пропускает на свой выходной полюс 19 импульс второи фазы тактового генератора поступающий на импульсный вход 2 О второй фазы управления, которыи, пройдя элемент "ИЛИ" 10, переведет в следующее состояние накопитель импульсов 6. Импульс третьей фазы тактового генератора, поступающий поимпульсному входу 21 третьей фазы управления, переведет в исключающее состояйие элемент памяти. После опроса всех определителей цвета узлов заканчивается первый цикл 5 решения и устройство выдает множество узлов, составляющее максимальный 1 подграф.3 дальнейшем ходе решения оп ределители цвета этих узлов не должны участвовать и поэтому исключаются блоком 1 управления, а именно: сигнал окончания опроса, сформированный в блоке 1 управле ния, снимает разрешающий потенциал с входа 14 первого цикла решения и устанавливает его на входе 14 второго цикла решения, После этого импульс, поступивший на вход 22 второго сброса, установит в исходное состояние элемент памяти в тех определителях цвета узлов, накопители импульсов которых после первого цикла решения перешли во второе состояние.После этого начинается второй цикл решения, по окончании которого устройство выделит множест- ЗО во узлов графа, составляющее максимальный 2 Г подграф и т.д,После второго цикла решения и далее после каждого последующе- З 5 го цикла импульс, поступающии по входу 22 второго сброса, будет возвращать в исходное состояние элементы памяти в тех определителях цвета узлов, накопители импульссов которых после очередного цикла решения перешли в следующее состояние. Если этого не произошло на очередном цикле опроса, то элементы памяти в этих определителях 45 цвета узлов останутся до конца решения в исключающем состоянии, т.е. к конпу решения элементы памятй всех определителей окажутся в исключающем состоянии, а это 50 и является признаком окончания решения.Величину хроматическбго числаграфа можно определить после окон чания решения задачи, проиндициро 6вав номера состояний накопителей всех определителей цвета узлов и выбрав максимальный из них, либо подсчитав с помощью накопительного счетчика количество импульсов сброса, поступивших по входу 22 второго сброса, сформированных за время решенйя блоком управления,ПРЕДЙЕТ ИЭОБРЕТИПИ1. Устройство для определения хроматического числа графа, содержащее блок управления, выход которого соединен с блоком индикации, а вход подключен к генератору ймпульсов, и наборное поле, отличающееся тем, что, с цеЛъю расширения класса решаемых задач, оно содержит блок определителей цвета узлов, информационные входы и выходы которых соединены на наборном поле согласно топологии графа, управлякнцие входы и выходы йодклычены ко входам и выходам блока управления, импульсные входы подключены к генератору импульсов, а информационные выходы соединейы со входами блока индикации.2. Устройство по п.1, отличаюшееся тем, что определитель цвета узла содержит накопитель импульсов, две группы элементов "И", два элемента РИИ" и элемент памяти, к соответствующим входам которого подключены входные полюсы, вход первого сброса и импульснйе входы второй и третьей фазы управления определителем цвета узла, вход пуска определителем цвета узла через первый элемент "ИЛИ", подключенныи вторым входом к выходу элемента памяти, соединен с входом накопителя ймпульсов, выходы которого соединены с первыми входами соответствующих элементов "И" первой группы и, кроме первого выхода, первыми входами соответствующйх элементов "И" второй группы второй вход первого элемента "И" первой группы подключен к .входу первого цикла решения оьределителя цвета узла, а вторые входы остальных элементов "И" первойгруппы объединены со вторыми входами соответствующих элементов"И" второй группы и подключены ивходам соответствующего цикла решения определителя цвета узла,третьи входы элементов "И" первойгруппы подключены к . вхору опросаопределителя цвета узла а третьивхолы элементов "И" второй группы - к; входу второго сброса определителя цвета узла, выходы элементов "Иф первой группы через второй элемент ФИЛИ" соединены с -выходным полюсом определителя цвета узла, а выходы элементов "И" второй группы соединены с соответствующими входами элемента паомяти.(2 Ю УХ 20 2( Фиг.2 Составитель(ОРОКйНВр Гекред ДВСКЛЬ 8 ВЙорректор Н ХВН едакторЯ ИПИ Государственного комнт по делам иэобретеиий Москва, 333035, Раузеитэ, Москва, Г, Бережковская наб 24 каз Ц Изд. М 71 аж 624 Подписно а Совета Министров Си открытийская наб., 4