Алгоритм GYO

Алгоритм GYO ^[1] — это алгоритм, применимый к гиперграфам . Алгоритм принимает на вход гиперграф и определяет, является ли гиперграф α-ациклическим . Если да, то он вычисляет разложение гиперграфа.

Алгоритм был предложен в 1979 году Грэмом и независимо Ю и Озсойоглу , отсюда и его название.

Определение

Гиперграф — это обобщение графа . Формально гиперграф $H=(V,E)$ состоит из набора вершин V и множества E гиперребер , каждое из которых является подмножеством вершин V . Учитывая гиперграф, мы можем определить его простой граф как неориентированный граф, определенный на одном и том же наборе вершин, в котором мы помещаем ребро между любыми двумя вершинами, которые встречаются вместе в некотором гиперребре.

Гиперграф H называется α-ациклическим, если он удовлетворяет двум условиям: хордальность и конформность. Точнее, мы говорим, что H хордальный, если его простой граф является хордальным графом . Мы говорим, что H конформен, если для каждой клики простого графа существует гиперребро H, содержащее все вершины клики.

Алгоритм GYO принимает на вход гиперграф и определяет, является ли он α-ациклическим в этом смысле.

Принцип алгоритма

Алгоритм итеративно удаляет так называемые уши гиперграфа, пока гиперграф не будет полностью разложен.

Формально мы говорим, что гиперребро e гиперграфа $H$ является ухом, если выполняется одно из следующих двух условий:

$e$ изолирован , т. е . для любого другого гиперребра $e'$ , у нас есть $e\cap e'=\emptyset$ ;
$e$ почти перекрыто другим гиперребром, т. е. существует еще одно гиперребро $f$ такое, что все вершины в $e\setminus f$ происходят только в $e$ .

В частности, каждое ребро, являющееся подмножеством другого ребра, является ухом.

Алгоритм GYO тогда действует следующим образом:

ухо e в H. Найдите
Удалите e и удалите все вершины H, которые находятся только в e .

Если алгоритм успешно исключает все вершины, то гиперграф является α-ацильным. В противном случае, если алгоритм доберется до непустого гиперграфа, не имеющего ушей, то исходный гиперграф не был α-ациклическим:

Алгоритм GYO заканчивается на пустом гиперграфе тогда и только тогда, когда H $\alpha$ -ациклический

Предположим, сначала алгоритм GYO заканчивается на пустом гиперграфе, пусть $e_{1},\ldots ,e_{m}$ будет последовательностью ушей, которые он нашел, и пусть $H_{0},\ldots ,H_{m}$ последовательность полученных гиперграфов (в частности $H_{0}=H$ и $H_{m}$ пустой гиперграф). Ясно, что $H_{m}$ , пустой гиперграф, $\alpha$ -ациклический. Тогда можно это проверить, если $H_{n}$ является $\alpha$ -ациклический тогда $H_{n-1}$ также $\alpha$ -ациклический. Это означает, что $H_{0}$ действительно $\alpha$ -ациклический.

В другом направлении, если предположить, что $H$ является $\alpha$ -ациклический, можно показать, что $H$ имеет ухо $e$ . ^[2] Поскольку удаление этого ушка дает гиперграф, который по-прежнему является ациклическим, мы можем продолжать этот процесс до тех пор, пока гиперграф не станет пустым.

Ссылки

Абитбул, Серж; Халл, Ричард; Виану, Виктор (2 декабря 1994 г.). Основы баз данных: логический уровень (PDF) . Ридинг, Массачусетс: Пирсон. ISBN 978-0-201-53771-0 . См. алгоритм 6.4.4.

Примечания

^ Ю, Коннектикут; Озсойоглу, МЗ (1979). «Алгоритм членства в дереве распределенного запроса» . КОМПСАК 79. Слушания. Компьютерное программное обеспечение и Третья международная конференция по приложениям IEEE Computer Society, 1979 г. стр. 306–312. дои : 10.1109/CMPSAC.1979.762509 .
^ Бро-Барон, Иоганн (27 марта 2014 г.). «Возвращение к ацикличности гиперграфа». arXiv : 1403.7076 [ math.CO ]. См. теорему 6 о существовании уха.

[yu79-1] Ю, Коннектикут; Озсойоглу, МЗ (1979). «Алгоритм членства в дереве распределенного запроса» . КОМПСАК 79. Слушания. Компьютерное программное обеспечение и Третья международная конференция по приложениям IEEE Computer Society, 1979 г. стр. 306–312. дои : 10.1109/CMPSAC.1979.762509 .

[2] Бро-Барон, Иоганн (27 марта 2014 г.). «Возвращение к ацикличности гиперграфа». arXiv : 1403.7076 [ math.CO ]. См. теорему 6 о существовании уха.

[1]

[2]