Патент ссср 433485

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

И АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Соввтсыиз

Социо алнстнмесюа ееслублетк (11) 433485 (61) Зависимое от авт. свидетельства(22) Заявлено 05, 04, 72(21) I768675/I8-24 (51) М. Кл. а ау и/ео. йсудвратвввввй ввнвтет

Ввввтв Мввеетрев ВСТР вв деваю взебрвтенвв а еткрктвв с присоединением заявки— (32) Приоритет—

Опубликовано 25,05,74 Бюллетень М 23

Дата опубликования описания I5. I2,74 (Я) УДК 68I 333 (-O88.8) Е.А.Ралдугин (72) Автор . изобретения (71) Заявитель Институт электродинамики (54) УСТРОЧСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ХИЯАТИЧЕСКОГО ЧИСЛА ГРАФА

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

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

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

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

15 входом к выходу элемента памяти, соединен со входом накопителя импульсов, выходы которого соединены с первыми входами соответствующих элементов "И" первой группы и, ро кроме первого выхода, с первыми входами соответствующих элементов

"И" второй группы„ второй вход первого элемента Л" первой группы подключен к входу первого цикла решения определителя цвета уз433485

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

"И" первой группы подключены к входу опроса определителя цвета узла, а третьи входы элементов "И" второй группы - к входу второго сброса определителя цвета узла; выходы элементов "Л" первой группы через второй элемент "ЛЛИ" соединены с выхоцным полюсом определителя цвета узла, а выходы элементов " Л" второй группы соединены с соответствующими вхоцами элемента памяти.

На. Фиг. I приведена блок=схеva устройства для определения хроматического числа графа; на фиг.2 — функциональная схема определитзля цвета узла.

Устройство соцержит блок I управления, блок 2 определителей цвета узла, число которых равно числу переменных задачи, наборное поле S, генератор 4 импульсов, блок 5 инцикации. Опрецелитель цвета узла содержит накопитель импульсов 6, элемент 7 памяти, первую группу трехвходовых элементов

8 "Л", число которых равно числу выходов накопителя импульсов 6, вторую группу трехвходовых элементово "И", число которых на единицу våíüøå, чем число выходов накоителя имйульсов 6, элементы ИЛИ

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

Элемент 7 памяти имеет три состояния: исходное (первое), рабочее (второе, исключающее (третье), при4ем переход в рабочее состоянйе возможен только после . установа исхоцного состояния. Если установа в исхоцное состояние нет, то элемент памяти сохраняет исключающее (третье) состояние. Он может быть реализован любым из из10 ние элемента памяти по входу 16 пуска через схему "Й6И" IO в накопители импульсов заносится одиночный имцульс, после чего каждый . накопитель импульсов S выдает разрешение на своем первом выходе I7.

25 В дальнейшем до конца решения по входу I6 пуска никакие импульсы не поступают.

4 вестных способов и служит для выделения импульсов, поступающих в накопитель импульсов.

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

2 и выходные IB, При подаче сигнала "Пуск" блок Т управления устанавливает исходное состояние схемы: на вход

I4 первого цикла решения всех опрецелителей поступает разрешающий потенциал, по входу I5 сброса устанавливается исходное состояБлок I управления последовательно опрашивает импульсами, синхронизированными с первой фазой тактового генератора по входам

I8 опроса элементы "И" 8 первой группы всех определителей цвета узлов. Выходнои сигнал первого элемента "И" 8, пройдя через элемент "ИЛИ" П, появится на выходном полюсе 13 определителя цвета узла, которы,, в соответствии с топологией графа, связан соответствующей клеммси наборного 3 поля с входными полюсами l2 других определителей. Сигнал на входном полюсе переводит в рабочее состояние элемент 7 памяти соответствующего определителя цвета узла.

В рабочем состоянии элемент 7 памяти пропускает на свой выходной полюс l9 импульс второи фазы тактового генератора поступающий на импульсный вход 2О второй фазы управления, которыи, пройдя элемент "ИЛИ" СО, переведет в следующее состояние накопитель импульсов 6. Импульс третьей фазы тактового генератора, поступающий по

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

В дальнейшем ходе решения оп- 10 ределители цвета этих узлов не должны участвовать и поэтому исключаются блоком I управления, а именно: сигнал окончания опроса, сформированный в блоке 1 управле- 15 ния, снимает разрешающий потенциал с входа Х4 первого цикла решения и устанавливает его на входе

I4 второго цикла решения. После этого импульс, поступивший на вход 22 второго сброса, установит в исходное состояние элемент памяти в тех определителях цвета узлов, накопители импульсов которых после первого цикла решения перешли во второе состояние.

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

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

Величину хроматическбго числа графа можно определить после окон- 55 чания решения задачи, проиндициро6 вав номера состояний накопителей всех определителей цвета узлов и выбрав максимальный из них, либо подсчитав с помощью накопительного счетчика количество импульсов сброса, поступивших по входу 22 второго сброса, сформированных за время решенйя блоком управления, ПРЕДАДЕТ ИЭОБРЕТИПИ

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

2. Устройство по п.I, отличаюшееся тем, что определитель цвета узла содержит накопитель импульсов, две группы элементов "И", два элемента ИЛИ" и элемент памяти, к соответствующим входам которого подключены входные полюсы, вход первого сброса и импульснйе входы второй и третьей фазы управления определителем цвета узла, вход пуска определителем цвета узла через первый элемент "ИЛИ", подключенныи вторым входом к выходу элемента памяти, соединен с входом накопителя ймпульсов, выходы которого соединены с первыми входами соответствующих элементов "И" первой группы и, кроме первого выхода, первыми входами соответотвующйх элементов "И" второй группы„ второй вход первого элемента

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

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

-выходным полюсом определителя цвета узла, а выходи элементов "И" второй группы соединены с соответствующими входами элемента па10 ATM

Q !2. ФХ 20 2(Составитель Q QQp)ggg

Ре"à ê" "î Å. )ЪНЧщ) Текред Г,3аоцдъщфорректор Н. ХВН68В6

Заказ g Pg Изд. М 7I5 Тираж 624 Подписно

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

Москва, l}3035 Раушская иаб., 4

Яренщйгитж.- МФвчеит>, Москва, Г-59, Бережковская наб., 24