Процесс формирования подмножеств данным методом осуществляется следующим образом. До начала свертки в качестве кандидатов на объединение рассматриваются все элементы множества V. На первом шаге выделяют равноценные по значению заданного критерия подмножества множества V. В общем случае подмножества могут состоять из одного, двух или более элементов (вершин). Сформированные подмножества рассматривают как элементы нового множества, по отношению к которому процедура может быть повторена. Включение в состав формируемого подмножества элементов или частей других подмножеств невозможна. Поясним это замечание. Если V1 и V2 подмножества, сформированные к некоторому шагу свертки, то возможно получение нового подмножества и невозможно - , в котором и или и . Из изложенного ясно, что этим методом формируются только непересекающиеся подмножества.
При объединении подмножеств (элементов) происходит отсечение других вариантов состава подмножеств. Очевидно, что точность получаемого решения определяется тем, является ли оценка выбора кандидатов на объединение отсекающей, то есть точной, или оценкой выбора перспективного решения. В случае, если эта оценка выбора перспективного решения, то метод может обеспечить лишь получение приближенного решения, т.к. он не предусматривает сохранение и рассмотрение других вариантов состава подмножеств.
Возможны два варианта окончания процесса свертки. При первом процесс заканчивается, когда все элементы множества свернуты в один. С практической точки зрения это требуется, если такое событие означает установление того факта, что множество в целом обладает некоторым определяющим свойством, например, что всё множество вершин гиперграфа является минимальным массивом вершин. В тех случаях, когда на подмножества наложены ограничения (например, количество подмножеств, их элементов, суммарный вес элементов), процесс свертки заканчивается при удовлетворении этих условий. По мере получения подмножеств, для которых выполняются заданные ограничения, эти подмножества исключаются из рассмотрения. Процесс свертки можно наглядно представить в виде дерева, в котором вершины j-го уровня сопоставлены подмножествам, являющимся кандидатами на объединение, а ребра указывают на вхождение двух или более подмножеств в новое подмножество. На нижнем уровне вершины соответствуют элементам исходного множества.
Формирование на каждом шаге свертки из n элементов множества X подмножеств, включающих два, три и т.д. элементов, требует перечисление всех соответствующих сочетаний, вычисления для них значения заданного критерия и выбора оптимальных вариантов. Это в пределе ведет к полному перебору.
Избежать полного перебора позволяет попарное объединение элементов на каждом шаге свертки. Такая модификация называется методом двоичной свертки. Различают два варианта двоичной свертки: уравновешенную и неуравновешенную. При уравновешенной двоичной свертке вновь образованный элемент переходит на следующий уровень дерева, т.е. сформированное подмножество становится элементом нового множества. Свертка на текущем уровне продолжается для оставшихся элементов. Очевидно, что на каждом уровне свертки число элементов вдвое меньше, чем на предыдущем. Количество элементов на уровне j определяется по формуле .
При неуравновешенной двоичной свертке элементы или множества, вошедшие в новое подмножество, исключаются из множества, а это новое подмножество включается в него и участвует в процессе свертки. Метод двоичной свертки не гарантирует нахождение точного решения. Действительно, пусть на некотором шаге свертки имеется подмножество , ни одна из пар xi, xj элементов которого не может быть свернута, т.к. значение заданного критерия не удовлетворяет требованию к нему, и ни один из элементов не может быть объединен ни с каким из сформированных подмножеств. Если среди элементов подмножества Xk существуют подмножества, например, из трех элементов, которые удовлетворяют требованиям, предъявляемым к значению соответствующего критерия, то такие подмножества не будут найдены. Примером может служит задача выделения всех минимальных массивов гиперграфа.
Пусть V- непустое конечное множество, E - некоторое множество непустых подмножеств множества V. Пара множеств G= (V,E) [1] называется гиперграфов, с множеством вершин V={v} и множеством ребер E={e}. Число n=|V| называется размерностью гиперграфа. Если вершина v€V принадлежит ребру e€E, они инцидентны. Число deg(v) - число всех инцидентных ребер для вершины v€V , а deg(e) - число вершин в ребре e€E. Мультигиперграф - гиперграф, содержащий хотя одну пару совпадающих ребер e1,e2€E. Два ребра мультигиперграфа называются смежными, если они содержат по крайней мере одну общую вершину. Если для любого ребра e€E число deg(E) =l, мультигиперграф называется l-однородным.
Первый шаг алгоритма состоит в следующем. Для каждого ребра e€E мультигиперграфа G=(V,E) определяется ряд величин: 1) deg(e) ; 2) для смежных с ребром e€E ребер e´€E задано число ; 3) - общее число смежных с ребром e€E ребер.
На втором шаге применяется алгоритм свертки. Выбор метода свертки зависит от вида исходного мультигиперграфа. Можно использовать как уравновешенный метод свертки, так и не уравновешенный метод. Отсекаемыми элементами здесь будут ребра мультигиперграфа G = (V,E). Выбор критериев свертки иметь вид: 1)max (deg(e)} , 2) , 3) . Часто используется именно такая очередность применения этих критериев. Однако очередность будет зависеть от содержательной постановки задачи. Меняя очередность критериев можно получать решения задачи для различных постановок задач. Это зависит от способа выбора максимального значения в 1), 2) и 3). Выбор производится до достижения максимума по более приоритетному критерию. В случае совпадения значений по всем критериям, выбирают ребро с меньшим индексом. В случае l-однородных мультигиперграфов значения deg(e) =l, для каждого ребра всех e€E и нет необходимости использовать первый критерий.
СПИСОК ЛИТЕРАТУРЫ
- Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.: Наука, 1990. - 384 с.
Библиографическая ссылка
Салпагаров С.И. ОБ ОДНОМ АЛГОРИТМЕ ВЫДЕЛЕНИЯ НЕПЕРЕСЕКАЮЩИХСЯ РЕБЕР МУЛЬТИГИПЕРГРАФА // Международный журнал экспериментального образования. – 2010. – № 7. – С. 131-132;URL: https://expeducation.ru/ru/article/view?id=452 (дата обращения: 21.11.2024).