H необходимо построить минимальное остовное
Рис. 2. Гиперграф ?(gX)
Тогда на множестве гиперграфов H необходимо построить минимальное остовное дерево, такой связной части графа, содержащей все его вершины, чтобы ее полная мера была минимальной. Эта задача близка к задаче коммивояжера, однако в рассматриваемом нами случае нет требований к поиску именно маршрута - решение может быть найдено в более широком подклассе графов - деревьях. Для решения поставленной задачи воспользуемся алгоритмом построения минимального остовного дерева для обыкновенных графов Р.С. Прим. Тогда получаем следующий алгоритм для пространства гиперграфов инвариантов подобия.
А л г о р и т м 1.
Шаг 1. Выбрать среди множества ребер графа ребро с минимальной мерой.
Шаг 2. До тех пор, пока часть содержит не все вершины, повторять пункт 3.
Шаг 3. Из множества ребер, инцидентных хотя бы одной вершине, входящей в уже построенную часть, и при этом инцидентных хотя бы одной вершине, не входящей в уже построенную часть, выбрать ребро с наименьшей мерой и добавить его к части.
Здесь для выбора оптимальной последовательности проверки взаимосвязанных циклов системы на первом шаге проверяется цикл наименьшей длины. Далее последовательно проверяются циклы, имеющие с уже проверенными хотя бы одно общее ребро, согласно возрастания их длин, до тех пор, пока не окажутся охваченными все ребра графа ?'(w(s)). Данный прием определяет план проверки потенциально несовместных подсистем, оптимальный относительно количества требуемых вычислительных операций.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий