ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 4, с. 43-48
КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^^^ МЕТОДЫ
УДК 65.012.122
АЛГОРИТМЫ ВОССТАНОВЛЕНИЯ ГИПЕРГРАФОВ ПО ЗАДАННОМУ ВЕКТОРУ СТЕПЕНЕЙ ВЕРШИН
© 2014 г. Д. С. Костяной, А. В. Мокряков, В. И. Цурков
Москва, "МАТИ-РГТУ им. К.Э. Циолковского", ВЦ РАН Поступила в редакцию 20.03.14 г.
Рассматриваются методы получения некоторых классов гиперграфов из заданного целочисленного вектора степеней вершин. Эти классы таковы: гиперребра с весом 1, инцидентные к вершинам; гиперребра с весом 1, инцидентные к вершинам, при этом вершины могут быть не уникальны; кратные гиперребра, инцидентные к вершинам; произвольный гиперграф, в котором ребра могут содержать любой набор из к вершин. Для каждого из классов представлен алгоритм построения гиперграфа из произвольного вектора. В случае невозможности построения алгоритм устанавливает, насколько нужно уменьшить вектор, чтобы гиперграф можно было реализовать.
Б01: 10.7868/8000233881404009Х
Введение. В статье рассматриваются алгоритмы восстановления гиперграфов [1] некоторых классов из произвольных векторов. Идеи подхода сформулированы при решении задачи о распределении ресурсов, представленных в виде векторов [2]. В процессе построения гиперграфов возникает проблема их сильной вариативности. Построить гиперграф возможно только после того, когда на его структуру будет наложен ряд ограничений.
Введем обозначение Г(к, п) — гиперграф на п вершинах с гиперребрами, которые могут содержать к смежных вершин. Теперь обозначим Г1(к, п) — гиперграф Г(к, п), у которого гиперребра не могут содержать повторяющиеся вершины. В противовес этому в гиперграфе Гш(к, п) каждое гиперребро может содержать до к одинаковых вершин.
Нижний индекс у Г(к, п) обозначает максимальный вес, который может быть у гиперребра: 1 — вес всех гиперребер равен 1; да — вес каждого гиперребра должен быть положительным целочисленным значением. Соответственно рассматриваются четыре класса, получаемых при различных сочетаниях индексов. В дальнейшем мы будем писать сокращенно: Г1 = г1 (к, п).
С.П. Хакими [3] исследовал вопрос реализуемости вектора в граф. Он первым указал на возможность построения графа на основе произвольного вектора. В [4—7] алгоритм Хакими видоизменен таким образом, что появилась возможность получения не одного графа, а всех возможных графов, удовлетворяющих исходному вектору. Однако более сложные модели требуют использования понятия гиперграфа [8, 9]. В ряде работ [10—12] были исследованы вопросы реализации вектора в 2-комплекс (гиперграф). Упомянутые публикации основаны на результатах [13—17]. При этом общего алгоритма для к-комплексов не получено. Здесь делается попытка привести варианты реализации вектора в гиперграф с определенными ограничениями на его структуру. Полученные алгоритмы имеют важное значение для получения общего алгоритма восстановления произвольного гиперграфа.
1. Класс Г1. Первым будет рассмотрен алгоритм, который строит из вектора гиперграф г1 , т.е. гиперграф с единичными ребрами, в которых вершины не повторяются.
Для следующих алгоритмов нам потребуется ввести обозначение: /Л(0) — количество координат целочисленного неотрицательного вектора Л = (а), I = 1, п , равных нулю при I > к.
Алгоритм 1. Пусть дан целочисленный неотрицательный вектор Л = (а1, ..., ап), где п > к. Координаты вектора Л упорядочены по невозрастанию. Для построения гиперграфа будем последовательно отнимать от к выбранных координат вектора Л по 1. Каждое такое вычитание означает построение одного гиперребра. Таким образом постепенно будет построен гиперграф.
Шаг 1. Пусть вектор В = (Ъь ..., Ъп), тогда вектор Л1 = А — В, где
[а = min{öl5 ..., ak_ J, n - k + 1 - /А(0)}, i = 1, k- 1; bt = i -
11, i = k, n - k + 1 + a1. Шаг 2. Вектор А2 = Aj — В, где
I «2 = min{ ab ..., ak_2, ak, n - к - /А(0)}, i = 1, к - 2, i = k;
bt = J -
11, i = к + 1, n - к + a2. Шаг n — к . Вектор An_к = An-к- j — В, где
b = Jan - к = min{ ab ..., ak - 2, an -1, 1 - Ia( 0)}, i = 1, к - 2, i = n - 1; 11, i = n.
Шаг n — к + 1. Если = 0, то сортируем вектор An _ к по невозрастанию и переходим к шагу 1 (при построении гиперребер учитываем, что координаты перенумерованы), иначе находим вектор An - к-1 = An - к - B, где
[a„ - к +1 = min{ ab ..., ak - 2, ab n - к + 1 - Ia(0 )}, i = 1, к - 2, i = к;
bi = J -
11, i = к + 1, n - к + an - к +1.
В общей сложности из at вершины можно вычесть до Ckn. Алгоритм завершает свою работу, когда все варианты вычитаний перебраны или некоторый вектор Ap = 0 .
Пример 1. Построим гиперграф с гиперребрами по три вершины на основе вектора А = = (10, 7, 6, 4, 3).
Построим ряд гиперребер, содержащих по три вершины: {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}. В результате получаем семь наборов по три элемента в каждом и остаток из девяти элементов (четыре первых, три вторых и два первых). Окончательно имеем
A = (10, 7, 6, 4, 3); A1 = (9, 6, 5, 4, 3); A2 = (8, 5, 5, 3, 3); A3 = (7, 4, 5, 3, 2); A4 = (6, 4, 4, 2, 2); A5 = (5, 4, 3, 2, 1); A6 = (4, 4, 3, 1, 0); A7 = (4, 3, 2, 0, 0).
Легко отследить количество исходных наборов элементов, доступных для разложения. 2. Класс Г". Следующий рассматриваемый алгоритм приводит к построению гиперграфа
класса Г" , в котором ребра могут содержать неуникальные вершины.
Алгоритм 2. Пусть дан целочисленный неотрицательный вектор А = (a1, ..., an), где n > к. Координаты вектора А упорядочены по невозрастанию. Для построения гиперграфа будем последовательно отнимать от выбранных координат вектора А в сумме к. Каждое такое вычитание означает построение одного гиперребра с повторяющимися вершинами. Таким образом постепенно будет построен гиперграф.
Шаг 1. Пусть вектор B = (bb ..., bn) и коэффициентp = 0, тогда вектор A1 = А — В, где b1 = min{a1, k -p}; b( = 0, i > 2.
Шаг 2. Если а1 = 0, то сортируем вектор A1 по невозрастанию и переходим к шагу 1. Иначе увеличиваемp на 1 и А2 = A1 — В, где
b1 = min{ab k-p}; b2 = p; bt = 0, i> 3.
Шаг 3. Вектор А3 = А2 — В и p = 1, где
b1 = min{ab k-p}; b3 = p; bt = 0, iФ 1, 3.
Шаг n — 1 . Вектор An -1 = An -2 — В и p = 1, где
b1 = min {a1, k - p}; bn = p; b( = 0, i Ф 1, n.
Ш а г n. Если #1 — 0, то сортируем вектор An _ 1 по невозрастанию и переходим к шагу 1. Иначе увеличиваемp и An = An -1 — В, где
b1 = min{a1, k-p}; b2 = p; bt = 0, i> 3.
И так далее до тех пор, пока a1 > 0 илиp < к. Еслиp = к, а a1 > 0, то вектор невозможно реализовать в гиперграф класса Г" (к, n).
Пример 2. Пусть дан вектор А = (47, 38, 20, 17, 9, 5, 4, 2). Построим гиперграф с гиперребрами по шесть вершин:
A = (47, 38, 20, 17, 9, 5, 4, 2);
A1 = (41, 38, 20, 17 9, 5, 4, 2);
A2 = (36, 37, 20, 17, 9, 5, 4, 2);
A3 = (31, 37, 19, 17 9, 5, 4, 2);
A4 = (26, 37, 19, 16, 9, 5, 4, 2);
A5 = (21, 37, 19, 16, 8, 5, 4, 2);
Аб = (16, 37, 19, 16, 8, 4, 4, 2);
А7 = (11, 37, 19, 16, 8, 4, 3, 2);
А8 = (6, 37, 19, 16, 8, 4, 3, 1); А9 = (2, 35, 19, 16, 8, 4, 3, 1); А10 = (0, 31, 19, 16, 8, 4, 3, 1).
Набор видов элементов отсортирован (первый элемент больше не участвует в разложении) — переходим к сортированному вектору А10:
Аю = (31, 19, 16, 8, 4, 3, 1, 0);
Аи = (25, 19, 16, 8, 4, 3, 1, 0);
А12 = (20, 18, 16, 8, 4, 3, 1, 0);
А13 = (15, 18, 15, 8, 4, 3, 1, 0);
А14 = (10, 18, 15, 7, 4, 3, 1, 0);
А15 = (5, 18, 15, 7, 3, 3, 1, 0);
Л16 = (0, 18, 15, 7, 3, 2, 1, 0).
Набор элементов отсортирован — переходим к вектору A16:
A16 = (18, 15, 7, 3, 2, 1, 0, 0);
Л17 = (12, 15, 7, 3, 2, 1, 0, 0);
Л18 = (7, 14, 7, 3, 2, 1, 0, 0);
Л19 = (2, 14, 6, 3, 2, 1, 0, 0);
Л20 = (0, 10, 6, 3, 2, 1, 0, 0).
Набор элементов отсортирован — переходим к вектору A20:
Л20 = (10, 6, 3, 2, 1, 0, 0, 0);
Л21 = (4, 6, 3, 2, 1, 0, 0, 0);
Л22 = (0, 4, 3, 2, 1, 0, 0, 0).
Набор элементов отсортирован — переходим к вектору A22:
Л22 = (4, 3, 2, 1, 0, 0, 0, 0);
Л23 = (0, 1, 2, 1, 0, 0, 0, 0).
В итоге получаем 23 уникальных ребра и четыре элемента из исходного вектора, которые не могут быть распределены.
3. Класс г! . Третьим рассматривается алгоритм, реализующий исходный вектор в повторяющиеся гиперребра, вершины в которых уникальны.
Алгоритм 3. Пусть дан целочисленный неотрицательный вектор A = (а1, ..., an), где n > к. Координаты вектора A упорядочены по невозрастанию. Для построения гиперграфа будем последовательно отнимать от к выбранных координат вектора A по максимально возможному значению р. Каждое такое вычитание означает построение одного гиперребра с весом р. Таким образом постепенно будет построен гиперграф.
Шаг 1. Пусть вектор В = (й1, ..., bn), тогда вектор A1 = А — В, где
= ja = min{Ö1,..., ak}, i = 1, k;
10, i = k + 1, n.
Ш а г 2. Так как минимум одна из координат равна нулю, то сортируем вектор по невозрастанию и снова переходим к шагу 1.
Алгоритм завершает свою работу, когда вектор становится нулевым или когда n — /A(0) < к. В последнем случае с помощью этого алгоритма реализовать гиперграф невозможно.
Пример 3. Пусть дан вектор A = (47, 38, 20, 17, 9, 5, 4, 2). Требуется разложить исходный вектор на гиперребра, содержащие по три вершины:
Л = (47, 38, 20, 17, 9, 5, 4, 2);
Л1 = (27, 18, 0, 17, 9, 5, 4, 2) ^ (27, 18, 17, 9, 5, 4, 2, 0);
Л2 = (10, 1, 0, 9, 5, 4, 2, 0) ^ (10, 9, 5, 4, 2, 1, 0, 0);
Л3 = (5, 4, 0, 4, 2, 1, 0, 0) ^ (5, 4, 4, 2, 1, 0, 0, 0);
Л4 = (1, 0, 0, 2, 1, 0, 0, 0) ^ (2, 1, 1, 0, 0, 0, 0, 0);
Л5 = (1, 0, 0, 0, 0, 0, 0, 0). В результате получаем 47 повторяющихся гиперребер с уникальными вершинами.
4. Произвольный класс. В случае, когда гиперребра и вершины в них могут повторяться, строится рад разнообразных алгоритмов. Здесь будет представлен только один случай, основанный на предыдущих алгоритмах.
Алгоритм 4. Пусть дан целочисленный неотрицательный вектор A = (ab ..., an), где n > к. Координаты вектора A упорядочены по невозрастанию. Для построения гиперграфа будем последовательно отнимать от к выбранных координат вектора A по максимально возможному значению p. Каждое такое вычитание означает построение одного гиперребра с весом p. В конце объединим оставшиеся вершины
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.