Векторная задача о сочетаниях на гиперграфах

К настоящему времени известен весьма ограниченный перечень задач на гиперграфах и не получила достаточного освещения технология решения таких задач. Под технологией решения задачи понимается четко описанная система действий, выполняемых при ее решении. При этом основной частью этой технологии является алгоритмическая. В данной работе сформулирована математическая постановка векторной задачи о сочетаниях на l -однородных l -дольных гиперграфах. Получена верхняя оценка мощности множества допустимых решений как для задач с равномощными долями, так и для задач с долями разной мощности. Для решения этой задачи построен алгоритм. Первая часть представленного алгоритма нахождения сочетаний l -дольных l -однородных гиперграфах, основана на классическом алгоритме нахождения паросочетаний в двудольном графе. Нахождение допустимых решений задачи выполняется без учета значений весов ребер заданного гиперграфа. Во второй части алгоритма из допустимых решений производится построение множества паретооптимальных решений векторной задачи.

Vectorial Problem on Combinations on Hypergraphs

To date, a very limited list of problems on hypergraphs is known and the technology for solving such problems has not been adequately covered. The technology of solving a problem is understood as a clearly described system of actions performed in its solution. The main part of this technology is algorithmic. In this paper, a mathematical formulation of the vectorial problem of combinations on l -homogeneous l -partite hypergraphs is formulated. An upper bound is obtained for the cardinality of the set of admissible solutions both for problems with equipotential parts and for problems with parts of different cardinality. An algorithm is constructed to solve this problem. The first part of the presented algorithm for finding combinations on l -partite l -homogeneous hypergraphs is based on the classical algorithm for finding matchings in a bipartite graph. The determination of admissible solutions of the problem is performed without taking into account the values of the weights of the edges of a given hypergraph. In the second part of the algorithm, from the admissible solutions, a set of paretooptimal solutions of the vectorial problem is constructed.