Algoritmo GYO

El algoritmo GYO ^[1] es un algoritmo que se aplica a los hipergrafos . El algoritmo toma como entrada un hipergrafo y determina si el hipergrafo es α-acíclico . Si es así, calcula una descomposición del hipergrafo.

El algoritmo fue propuesto en 1979 por Graham e independientemente por Yu y Özsoyoğlu , de ahí su nombre.

Definición

Un hipergrafo es una generalización de un grafo . Formalmente, un hipergrafo consiste en un conjunto de vértices V y de un conjunto E de hiperaristas , cada una de las cuales es un subconjunto de los vértices V. Dado un hipergrafo, podemos definir su grafo primario como el grafo no dirigido definido en el mismo conjunto de vértices, en el que ponemos una arista entre dos vértices cualesquiera que se presenten juntos en alguna hiperarista. ${\displaystyle H=(V,E)}$

Un hipergrafo H es α-acíclico si satisface dos condiciones: ser cordal y ser conforme. Más precisamente, decimos que H es cordal si su grafo primal es un grafo cordal . Decimos que H es conforme si, para cada camarilla del grafo primal, hay una hiperarista de H que contiene todos los vértices de la camarilla.

El algoritmo GYO toma como entrada un hipergrafo y determina si es α-acíclico en este sentido.

Principio del algoritmo

El algoritmo elimina iterativamente las llamadas orejas del hipergrafo, hasta que éste se descompone por completo.

Formalmente, decimos que una hiperarista e de un hipergrafo es una oreja si se cumple una de las dos condiciones siguientes: ${\displaystyle H}$

• ${\displaystyle e}$está aislado , es decir, para cualquier otro hiperedge , tenemos ; ${\displaystyle e'}$ ${\displaystyle e\cap e'=\emptyset }$
• ${\displaystyle e}$está casi cubierto por otra hiperarista, es decir, existe otra hiperarista tal que todos los vértices en ocurren solo en . ${\displaystyle f}$ ${\displaystyle e\setminus f}$ ${\displaystyle e}$

En particular, cada borde que es un subconjunto de otro borde es una oreja.

El algoritmo GYO procede entonces de la siguiente manera:

• Encuentra una oreja e en H .
• Elimina e y elimina todos los vértices de H que estén sólo en e .

Si el algoritmo elimina con éxito todos los vértices, entonces el hipergrafo es α-acílico. De lo contrario, si el algoritmo llega a un hipergrafo no vacío que no tiene orejas, entonces el hipergrafo original no era α-acílico:

El algoritmo GYO termina en el hipergrafo vacío si y solo si H es -acíclico ${\displaystyle \alpha }$

Supongamos primero que el algoritmo GYO termina en el hipergrafo vacío, sea la secuencia de orejas que ha encontrado, y sea la secuencia de hipergrafos obtenidos (en particular y es el hipergrafo vacío). Está claro que , el hipergrafo vacío, es -acíclico. Se puede comprobar entonces que, si es -acíclico entonces también es -acíclico. Esto implica que es efectivamente -acíclico. ${\displaystyle e_{1},\ldots ,e_{m}}$ ${\displaystyle H_{0},\ldots ,H_{m}}$ ${\displaystyle H_{0}=H}$ ${\displaystyle H_{m}}$ ${\displaystyle H_{m}}$ ${\displaystyle \alpha }$ ${\displaystyle H_{n}}$ ${\displaystyle \alpha }$ ${\displaystyle H_{n-1}}$ ${\displaystyle \alpha }$ ${\displaystyle H_{0}}$ ${\displaystyle \alpha }$

Para la otra dirección, suponiendo que es -acíclico, se puede demostrar que tiene una oreja . ^[2] Dado que al eliminar esta oreja se obtiene un hipergrafo que sigue siendo acíclico, podemos continuar este proceso hasta que el hipergrafo quede vacío. ${\displaystyle H}$ ${\displaystyle \alpha }$ ${\displaystyle H}$ ${\displaystyle e}$

Referencias

• Abiteboul, Serge; Hull, Richard; Vianu, Victor (2 de diciembre de 1994). Fundamentos de bases de datos: el nivel lógico (PDF) . Reading, Mass.: Pearson. ISBN 978-0-201-53771-0.Véase el algoritmo 6.4.4.

Notas

1. Yu, CT; Ozsoyoglu, MZ (1979). "Un algoritmo para la pertenencia a consultas de árbol de una consulta distribuida". COMPSAC 79. Actas. Software informático y la Tercera Conferencia Internacional de Aplicaciones de la IEEE Computer Society, 1979. págs. 306–312. doi :10.1109/CMPSAC.1979.762509.
2. Brault-Baron, Johann (27 de marzo de 2014). "Revisión de la aciclicidad del hipergrafo". arXiv : 1403.7076 [math.CO].Véase el Teorema 6 para la existencia de una oreja.