А.А. Гурченков, Д.С. Костяной, А.В. Мокряков
4
Шаг
1.
n
Вектор
1
2
=
,
n
n
A A
где
=1;
1
min ,
,
= 1;
=
,
= .
i
a k
i
b
i n
Шаг
n
. Если
1
= 0,
a
то сортируем вектор
1
n
A
по невозрастанию
и переходим к шагу 1. Иначе увеличиваем
и
1
=
,
n
n
A A
где
= 2;
1
min ,
,
= 1;
= ,
= 2;
0,
3.
i
a k
i
b
i
i
И так до тех пор, пока
1
> 0
a
или
< .
k
Если
= ,
k
а
1
> 0,
a
то
вектор невозможно реализовать в гиперграф класса
1
( , ).
k n
Класс
1
( , ).
k n
Третий алгоритм реализует исходный вектор в
повторяющиеся гиперребра, вершины в которых уникальны.
Алгоритм 3
. Пусть дан вектор
1
= ( ,
,
),
n
a a
A
где
.
n k
Коор-
динаты вектора
A
упорядочены по невозрастанию. Для построения
гиперграфа будем последовательно отнимать от
k
выбранных
координат вектора
A
по максимально возможному значению
.
p
Каждое такое вычитание означает построение одного гиперребра с
весом
.
p
Таким образом постепенно будет построен гиперграф.
Шаг 1.
Вектор
1
= ,
A A
где
1
1
= min , ,
, 1
;
=
0,
.
k
i
a a
i k
b
k i n
Шаг 2.
Поскольку как минимум одна из координат равна нулю,
сортируем вектор по невозрастанию и снова переходим к шагу 1.
Алгоритм завершает свою работу, когда вектор становится
нулевым или когда
(0) < .
n l
k
A
В последнем случае с помощью
этого алгоритма реализовать гиперграф невозможно.
Произвольный класс.
В случае, когда гиперребра и вершины в
них могут повторяться, строим ряд разнообразных алгоритмов.
Представим только один случай, основанный на предыдущих алго-
ритмах.
Алгоритм 4
. Пусть дан вектор
1
= ( ,
,
)
n
a a
A
, где
.
n k
Коор-
динаты вектора
A
упорядочены по невозрастанию. Для построения
гиперграфа будем последовательно отнимать от
k
выбранных
