Редукционные методы восстановления некоторого класса гиперграфов
3
A
10 7 6 4 3
A
1
9 6 5 4 3
A
2
8 5 5 3 3
A
3
7 5 4 2 3
A
4
7 4 3 1 3
A
5
6 3 3 1 2
A
6
5 3 2 1 1
A
7
4 3 2 0 0
В результате имеем 7 наборов по 3 элемента в каждом и остаток
из 9 элементов (4 первых, 3 вторых и 2 первых).
Легко отследить, какое количество исходных наборов элементов
доступно для разложения.
Класс
1
( , ).
k n
Второй алгоритм приводит к построению
гиперграфа класса
1
( , ),
k n
в котором ребра могут содержать не
уникальные вершины.
Алгоритм 2.
Пусть дан вектор
1
= ( ,
,
),
n
a a
A
где
.
n k
Коор-
динаты вектора
A
упорядочены по невозрастанию. Для построения
гиперграфа будем последовательно отнимать от
k
выбранных коор-
динат вектора
A
по 1. Каждое такое вычитание означает построение
одного гиперребра с повторяющимися вершинами.
Шаг 1.
Вектор
1
= ,
A A
где
= 0;
1
min ,
,
= 1;
= ,
= 2;
0,
2.
i
a k
i
b
i
i
Шаг 2.
Если
1
= 0
a
, то сортируем вектор
1
A
по невозрастанию и
переходим к шагу 1. В противном случае увеличиваем
и
2
1
=
,
A A
где
=1;
1
min ,
,
= 1;
= ,
= 2;
0,
3.
i
a k
i
b
i
i
Шаг 3.
Вектор
3
2
=
,
A A
где
=1;
1
min ,
,
= 1;
= ,
= 3;
0,
4.
i
a k
i
b
i
i
