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