Устройство для определения максимального паросочетания в транспортных сетях
Патент 669360
Авторы
Классы МПК
Устройство для определения максимального паросочетания в транспортных сетях
Иллюстрации
Реферат
Союз Советских
Социалистических
Республик (61) Дополнительное к авт. саид-ву(22) Заявлено 29,1176 (21 j 2425182/18-24 с присоединением заявки М(51)М. Кл.
G 06 G 7/48
Государственный комитет
СССР по делам изобретений н открытий (23) Приоритет— (53) УДК681.335 (088.8) Опубликовано 2506.79. Бюллетень М 23
Дата опубликования описания 2806,79 (72) Авторы изобретений
Ю.О. Чернышев и Н.Н. Садовой (71) ЗайемтЕЛЬ Ростовский-на-Дону институт сельскохоэ яйственного машиностроения (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНОГО
ПАРОСОЧЕТАНИЯ В ТРАНСПОРТНЫХ СЕТЯХ
Изобретение относится к вычислительной технике и может быть использовано для проектирования вычислительных систем и машин.
Известны устройства для моделирования транспортных сетей, содержащие соединенные между собой в соответствии с топологией графа модели узлов и ветвей (1) .
Такие устройства не позволяют решать задачу о нахождении максимального паросочетания графа.
Наиболее близко к предлагаемому изобретению устройство для определения максимального паросочетания в 15 транспортных сетях, содержащее и моделей вершин графа, входы которых подключены к выходу блока управления, модели ребер графа, входы которых подключены к выходам и моделей вершин графа, и блок индикации, группа входов которого подсоединена к выходам соответствующих моделей ребер графа (2} .
Недостатком этого устройства явля-25 ется сравнительно узкий класс решаемых задач.
Цель изобретения — расширение класса решаемых устройством задач. ЗО
Это достигается тем, что устройстВо содержит дополнительно IA моделей вершин графа, и входов каждой из которых через и моделеи ребер подключен к выходам соответствующих основных моделей вершин. В устройстве каждая из дополнительных моделей вершин содержит два триггера, три элемента ИЛИ и три элемента И, выходы которых являются выходами модели, два входа первог0 элемента И соединены соответственно с нулевым выходом первого триггера и с выходом первого элемента ИЛИ, три входа второго элемента И подключены соответственно к единичным выходам первого и второго триггеров и к входу управления модели, а два входа третьего элемента И вЂ” соответственно к единичному выходу первого триггера и к выходу первого элемента
ИЛИ„ установочные входы первого триггера подсоединены к выходам второго и третьего элементов ИЛИ, а установочные входы второго триггера вЂ, к выходу первого элемента ИЛИ и к входу сброса модели в нулевое состояние, входы элементов ИЛИ являются входами модели.
На фиг. 1 дана структурная схема предлагаемого устройства; на фиг. 2
669360 схема дополнительных моделей вершин; на фиг. 3-6 транспортные сети. иллк>стрирующие процесс нахождения максимаЛьного паросочетания.
Устройство (см. фиг. 1) содержит блок 1 управления, и моделей вершин
21 -2> множества (Х) (МВХ), nm моделей ребер 3« 3 (МР) (на фиг. 1 с целью упрощения чертежа показана лишь часть MP), m дополнительных моделей вершин 4 — 4я, множества у (МВУ) и блок 5 индикации. Каждая из I() дополнительных МВУ 41 — 4,я (см. фиг. 2), н свою очередь, содержит триггеры б и 7, три элемента ИЛИ 8-10 и три элемента И 11-13, входы 14, выходы 15 и вход 16 управления, соединенные по схеме (см. фиг. 2).
Работа устройства осуществляется с в соответстнии са следующим алгоритмам, Рассмотрим в качестве примера простой граф G, н котором (Х), (У два не пересекающихся множества вершин.
Паросачетанием пpocтoro графа G называется такое мнажестна ребер, н котором никакие два ребра не смежны.
Обычно требуется решать задачу о нахождении максимального паросочетания, содержащего максимальное число ребер.
Пусть дан простой граф, Дополним ЗО его двумя вершинами: источникам И и стоком С. Каждую нершину Х,6Х соединим ребром с вершиной И, а каждую вершину У 6 У с вершиной С ребром с пропускными способностями равными 1. 35
Получим транспортную сеть, изображенную на фиг. 3.
Задача нахождения максимального. гаросачетания для полученной транспортной сети снадится к нахождению 4О максимального потока н ней, при условии, что ребра, соединяющие вершины (Х и у) имеют пропускную способность, равную се
Алгоритм нахождения максимального потока состоит из нескольких этапов.
Находим первоначальное паросочетание. Для этого пропускаем поток величины 1 ат источника И па какомулибо пути к стоку С, удаляем из графа насыщенные дуги, а дугу, вошедшую н паросочетание, отмечаем знаком (- ), дуги Инцидентные ей -8 fX)(отмечаем меткоВ .(х) (см. фиг. 4).
Далее происходит увеличение паросочетания. 55
Для этого находим вершины множества (Х)), которым не инцидентны ребра, вошедшие в парасочетание. Для рассматриваемого примера - это вершины Х>, У . Отметим нсе ребра, исходящие из этих вершин знакам (И ) (см. фиг. 5). Ребра,инцндентные вершине У;, которой принадлежит ребро, помеченное (11 ), паметнм знаком (0) .
Вершине У;, которой принадлежит ребро,65 помеченное знаком (II ), может принадлежать ребро, помеченное знаком () ° .
Если такое ребра есть, То оно отмечается знаком (— ). После того, как отмечены все ребра, инцидентные вершинам множества (X), не содержащим ребра, вошедшие в паросочетания, этот этап повторяется, только теперь для вершин множества Х, которым принадлежит ребро, помеченное знаком (††).
Для рассматриваемого примера — это вершины Х, Х2. Этот этап будет продолжаться до тех пор, пока не будет помечено знаком (ll ) ребро, инцидентное вершине У;, которой не принадлежит ребро, помеченное знаком (— ), Тогда на ребре, отмеченном знаком (Il ), последний заменяется на знак (†ь ) .
Рассматриваем вершину из Х, инцидейтную этому ребру, стираем метку (— ь ) и т.д., пока не достигнем исходной вершины. После чего все отметки стираются, кроме отметок (— ь ) и, если остались вершины, не вошедшие в паросочетание, то этот этап повторяется. Процесс производится автоматически, а после ега окончания найденные паросачетания индицируются блоком
5 индикации.
Предлагаемое устройство позволяет решать задачу нахождения максимального парасочетания на неариентированных графах, что значительно расширяет класс решаемых задач па сравнению с известными устройствами.
Формула изобретения
1. Устройство для определения максимальнога паросачетания в транспортных сетях, содержащее п моделей вершин графа, входы которых подключены к выходу блока управления, модели ребер графа, входы которых подключены к выходам п.моделей вершин графа, и блок индикации, группа входов которого одсаединена к выходам соответствующих моделей ребер графа, о тл и ч а ю щ е е с я тем, что, с целью расширения класса решаемых устройством задач, ана содержит дополнительно m моделей вершин графа, и входов каждой иэ которых через и моделей ребер подключен к выходам соответствующих основных моделей вершин.
2. Устройство по п. 1,о т л и ч а ющ е е с я тем, что в нем каждая из дополнительных моделей вершин содержит дна триггера, три элемента ИЛИ и три элемента И, выходы которых являются выходами модели, два входа первого элемента И соединены соответ-. ственна с нулевым выходом первого триггера и с выходом первого элемента ИЛИ, три входа второго элемента H подключены соответственно .к единичным ныходам первого и второго триггеров и к входу управления модели,а два входа третьего элемента И - соответственно
S 669360 6 к единичному выходу первого триггера Источники информации, принятые и к выходу первого элемента ИЛИ, ус- во внимание при экспертизе тановочные входы первого триггера подсоединены к выходам второго и тре- 1. Васильев В.B., Дадонов A .Ã. тьего элементов ИЛИ, а установочные Гибридные модели задач оптимнэации, входы второго триггера — к выходу пер- Киев, "Наукова думка, 1974. вого элемента ИЛИ и к входу сброса ма;дели в нулевое состояние, входы эле- 2. Авторское свидетельство СССР ментов ИЛИ являются входами модели. 9 407345. кл. G 06 G 7/48, 1974. юг. г
Фиг.1
Составитель A. Колчин
Редактор Л. Гребенникова Техред О. Андрейко Корректор A. Власенко
Заказ 3658/40 Тираж 779 Подписное
ЦНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Иосква, Ж-35, Раушская наб., д. 4/5
Филиал ППП Патент, г. Ужгород, ул. Проектная, 4