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

Изобретение относится к вычислительной технике и может быть использовано для проектирования вьгчислител ных систем и машин. Известны устройств для мо.цвлирования транспортных сетей, содержащие соединенные между собой в соответствии с топологией графа модели узлов и ветвей 1. Такие устройства не позволяют решать задачу о нахождении максимально го паросочетания графа. Наиболее близко к предлагаемому изобретению устройство для определения максимального паросочетания в транспортных сетях, содержащее п моделей вершин графа, входы которых по ключены к выходу блока управления, модели ребер графа, входы которых по ключены к Выходам п моделей вершин графа, и блок индикации, группа входов которого подсоединена к выходам соответствующих моделей ребер графа 121 . Недостатком этого устройства явля ется сравнительно узкий класс решаемых задач. Цель изoбpeteния - расширение кла са решаемых устройством задач. Это достигается тем, что устройство содержит дополнительно m моделей вериин графа, п входов каждой из которых через п моделей ребер подключен к выходам соответствующих основных моделей вершин. В устройстве каждая из дополнительных моделей вершин содержит два триггера, три элемента ИЛИ и три элемента И, выходы которых являются выходами модели, два входа первого элемента И соединены соответственно с нулевым выходом первого триггера и с выходом первого элемента ИЛИ, три входа второго элемента И подключены соответственно к единичным выходам первого и второго ч риггеров и к входу управления модели, а два входа третьего элемента И - соответственно к единичному выходу первого триггера и к выходу первого элемента ИЛИ, установочные входы первого триггера подсоединены к выходам второго итретьего элементов ИЛИ, а установочные входы BTOpoVo триггера - к выходу первого элемента ИЛИ и к входу сброса модели в нулевое состояние, входы Элементов ИЛИ являются входами модели. На фиг. 1 дана структурная схема предлагаемого устройства; на фиг. 2 схема дополнительных моделей вершин; на фиг. З-б транспортные сетИ; иллюстрирующие процесс нахождения максимального паросочетания. Устройство (см, фиг. 1) содержит блок 1 управления, п моделей вершин 2, -2р множества {X} (МВХ), пт моделей ребер 3 - 3 (HP) (на фиг. 1 с целью упрощения чертежа показана лишь часть МР), m дополнительных моделей вершин 4 - 4 множества (у| (МВУ) и блок 5 индикации. Каждая из дополнительных МВУ 4 4 (см. фиг, 2), в свою очередь, содержит триггеры 6 и 7, три элемента ИЛИ 8-1 и три элемента -И 11-13, входы 14, выхода 15 и вход 16 управления, соединенные по схеме (см. фиг. 2). Работа устройства осуществляется в соответствии со следующим алгоритмом. Рассмотрим в качестве примера про той граф G, в котором , yj два не пересекающихся множества вершин . Паросочетанием простого графа G называется такое множество ребер, в котором никакие два ребра не смежны Обычно требуется решат задачу о нахождении максимального паросочетания, содержащего максимальное число ребер. Пусть дан простой граф. Дополним его двумя вepшинa и: источником И и стоком С. Каждую вершину соеди ним ребром с вершиной И, а каждую вершину V в У с вершиной С ребром с пропускными способностями равными 1 Получим транспортную сеть, изображенную йа фиг, 3, .Задача нахождения максимального. паросочетания для полученной транспортной сети сводится к нахождению максимального потока в ней, при условии, что ребра, соединяющие вершины {х| и имеют пропускную способность, равную со , Алгоритм нахождения максимального потока состоит из нескольких этапов Находим первоначальное паросочетание. ;9ля этого пропускаем поток величины 1 от источника И по -какому либо пути к стоку с, удаляем из гра фа насыщенные дуги, а дугу, вошедшую в парос очетание, отмечаем знаком (- дуги инцидентные ей 2 |х отмечаем меткоа .(х) (см. фиг. 4) . Далее происходит увеличение паро сочетания. Для этого находим вершины множес ва , которым не инцидентны реб ра, вошедшие в паросочетание. Для рассматриваемого примг- ра - это вершины Xj, У . Отметим все ребра, исходящие КЗ этих вершин знаком ( И ) (см. фиг, 5). Ребра,инцидентные вер шине У , которой принадлежит ребро, помеченное ( II ) , пометам знаком (О Вершине У; , которой принадлежит реб помеченное знаком (II ), может прин 0 ежать ребро, помеченное знаком (- ). сли такое ребро есть, то оно отмечается знаком (4- ) , После того, как отмечены все ребра, инцидентные вершинам множества Х,не содержащим реба, вошедшие в паросочетания, этот этап повторяется, только теперь для вершин множества |х1 , которым принадлежит ребро, помеченное знаком (4-). Для рассматриваемого примера - это вершины Х, Хз. Этот этап будет продолжаться до тех пор, пока не будет помечено знаком ( II ) ребро, инцидентное вершине У- , которой не принадлежит ребро, помеченное знаком ( ) , Тогда на ребре, отмеченном знаком ( II ), последний заменяется на знак (ь.) . Pacdмaтpивaeм вершину из Х , инцидентную этому ребру, стираем метку ( -ь- ) и т.д,, пока не достигнем исходной вершины. После чего все отметки стираются, кроме отметок (1) и, если остались вершины, не вошедшие в паросочетание, то этот этап повторяется. Процесс производится автоматически, а после его окончания найденные паросочзтания индицируются блоком 5 индикации. Предлагаемое устройство позволяет решать задачу нахождения максимального паросочетания на неориентированных графах, что значительно расширяет класс решаемых задач по сравнению с известными устройствами. Формула изобретения 1.Устройство для определения максимального паросочетания в транспортных сетях, содержащее п моделей вершин графа, входы которых подключены к выходу блока управления, модели ребер графа, входи которых подключены к выходам п. моделей вершин.графа, и блок индикации, группа входов которого подсоединена к выходам соответствующих моделей ребер графа, о тличающееся тем, что, с целью расширения класса решаемых устройством задач, оно содержит дополнительно m моделей вершин графа, п входов каждой из которых через п моделей ребер подключен к выходам соответствующих основных моделей вершин, :, . 2,Устройство поп, 1,отличающ е е с я тем, что в нем каждая из дбполнительных моделей вераин содер жит два триггера, три элемента ИЛИ и три элемента И, выходы которых являются выходами модели, два входа первого элемента И соединены соответственно с нулевым выходом первого триггера и с выходом первого элемента ИЛИ, три входа второго элемента И подключены соответственно -к единичным выходам первого и второго триггеров и к входу управления модели,а два входа третьего элемента И - соответственно