1
Изобретение относится к области вычислительной техники и может быть использовано при решении комбинаторно-логических задач на графах, связанных с выделением из графа частей с экстремальными свойствами.
Известны устройства, содержащие блоки ввода и вывода информации, управляющие входы которых подключены к выходам блока управления, соединенного с решающем полем.
Известные устройства не позволяют эффективно решать задачи выделения экстремальных частей в графе, которыми могут быть семейства максимальных внутреннеустойчивых независимых, несвязанных множеств и максимальных полных, связанных множеств графа. Отличительной особенностью при решении таких задач является выбор максимальных (к примеру, независимых) подмножеств из всего множества (независимых подмножеств).
Известные алгоритмы работы устройств при решении таких задач имеют два этапа: выделение всех (независимых) подмножеств; выделение из всех (независимых) подмножеств максимальных (независимых).
Таким образом, известные алгоритмы не допускают распараллелизования решения таких задач и делают применение известных устройств не эффективным, так как требуются значительные затраты времени.
Цель изобретения - повышение быстродействия устройства при выделении экстремальных частей в графе.
Это достигается тем, что в устройство введены блок моделирования матрицы смежности графа и блок анализа матрицы, выходы которого соединены соответственно с входами блока вывода информации, блока унравления и первым входом блока моделирования матрицы смежности графа. Второй вход последнего подключен к выходу блока ввода информации, третий вход - к выходу блока управления, а выход - к первому входу блока анализа матрицы, второй вход которого соединен с соответствующим выходом блока управления.
Введение указанных блоков позволяет реализовать оператор «выделения экстремальных частей в графе.
На чертеже представлена структурная схема устройства.
В состав схемы входят: блок 1 управления, блок 2 ввода информации, блок 3 моделирования матрицы смежности грифа, блок 4 анализа матрицы, блок 5 вывода информации.
Блок 1 управления позволяет записать матрицу смежности графа в блок 3, выполненный на основе однородной сети. Кроме того, о« служит для управления работой устройства и выработки управляющих сигналов выбора следующей строки в блок анализа матрицы. Однородная сеть блока 3 предназначена для хра
| название | год | авторы | номер документа |
|---|---|---|---|
| Способ моделирования виртуальных сетей в условиях деструктивных программных воздействий | 2018 |
|
RU2701994C1 |
| УСТРОЙСТВО ДЛЯ ПОДСЧЕТА ЗНАЧЕНИЯ ИНТЕНСИВНОСТИ РАЗМЕЩЕНИЯ В ПОЛНОСВЯЗНЫХ МАТРИЧНЫХ СИСТЕМАХ | 2007 |
|
RU2356084C1 |
| Способ контроля состояния логической структуры сети связи | 2018 |
|
RU2672137C1 |
| УСТРОЙСТВО ПОИСКА НИЖНЕЙ ОЦЕНКИ РАЗМЕЩЕНИЯ В СИСТЕМАХ С МАТРИЧНОЙ ОРГАНИЗАЦИЕЙ ПРИ НАПРАВЛЕННОЙ ПЕРЕДАЧЕ ИНФОРМАЦИИ | 2009 |
|
RU2406135C2 |
| АНАЛИЗАТОР СЕТЕЙ СВЯЗИ | 2006 |
|
RU2311675C1 |
| УСТРОЙСТВО ПОДСЧЕТА ЗНАЧЕНИЯ ИНТЕНСИВНОСТИ РАЗМЕЩЕНИЯ В ПОЛНОСВЯЗНЫХ МАТРИЧНЫХ СИСТЕМАХ ПРИ НАПРАВЛЕННОЙ ПЕРЕДАЧЕ ИНФОРМАЦИИ | 2007 |
|
RU2356085C1 |
| УСТРОЙСТВО ДЛЯ ПОДСЧЕТА МИНИМАЛЬНОГО ЗНАЧЕНИЯ ИНТЕНСИВНОСТИ РАЗМЕЩЕНИЯ В СИСТЕМАХ С ДРЕВОВИДНОЙ ОРГАНИЗАЦИЕЙ | 2008 |
|
RU2379749C1 |
| Устройство для решения комбинаторнологических задач на графах | 1990 |
|
SU1709349A1 |
| Устройство для решения комбинаторно-логических задач при проектировании печатных плат | 1982 |
|
SU1059579A1 |
| Способ построения диалогового режима на естественно-подобном языке при решении автоматизированных задач управления в комплексах средств автоматизации | 2020 |
|
RU2751435C1 |
