¿Cuáles son las aplicaciones de los hipergrafos

Question

Hypergraphs son como simples gráficos, excepto que en lugar de tener bordes que sólo conectan 2 vértices, sus bordes son conjuntos de cualquier número de vértices. Esto significa que todos los gráficos son sólo un subconjunto de hipergráficos.

Me parece que impar, entonces, que nunca he oído hablar de ningún algoritmo basado en hipergráficos, o de ninguna aplicación importante, para modelar fenómenos del mundo real, por ejemplo. Supongo que la explicación superficial es que se trata de una estructura mucho más compleja que un gráfico normal, y dada esta y su generalidad es más difícil hacer algoritmos limpios para, pero yo esperaría que hubiera algo!

¿Alguien ha oído hablar de un algoritmo basado en un hipergrafo, o de una aplicación? Me deja perplejo que los gráficos ordinarios puedan ser tan maravillosamente útiles, pero sus hermanos mayores no tienen nada que ofrecer.

Answer 1

He realizado algunos trabajos que me han hecho apreciar la opinión de que los hipergrafos etiquetados son una de las formas más apropiadas y generales de representar datos en máquinas con estado. En informática, solemos querer dividir el estado en una serie de estructuras de datos posiblemente superpuestas, que contendrán y serán referenciadas por punteros.

Esto se presta a la siguiente representación: las estructuras de datos son hipercubos. Los datos que no son punteros dentro de las estructuras de datos son etiquetas de la hipercaja asociada. Y los punteros están representados por vértices, posiblemente (¡no siempre!) necesitando un atributo para indicar qué hiperborde es la fuente y cuál es el objetivo del puntero. La computación, por tanto, es una reescritura de grafos.

Como dice Qiaochu, las hiperpistas son absurdamente generales. Lo mismo ocurre con la noción de datos. Para que esto sea útil, hay que restringir la forma que adoptan las hiperpistas. Lo bueno es que la necesidad de restringir la forma en que se representa el estado coincide perfectamente con la necesidad en los lenguajes de programación útiles de restringir la representación de los datos, y además, a menudo se pueden mapear limpiamente las restricciones impulsadas por la programación en restricciones razonables en los hipergrafos.

La idea aparece una y otra vez en la literatura sobre transformaciones de gráficos. Un buen punto de partida es Drewes, Habel y Kreowski, 1997, Gramáticas gráficas de sustitución de Hyperedge En Rozenberg, Manual de gramáticas de grafos y computación por transformaciones de grafos .

Answer 2

Los hipergrafos y varias propiedades que podemos demostrar sobre ellos son la base de muchas técnicas que se utilizan en las matemáticas modernas. Mencionaré la demostración de Teorema de la densidad Hales-Jewett por Tim Austin. El teorema de Szmeredi multidimensional también es otra palabra clave que podría querer buscar. El Teorema de Furstenberg-Katznelson puede demostrarse utilizando métodos de hipergrafía. La clasificación de la asignatura de matemáticas es 05C65.

Y lo que es más importante, eche un vistazo a Novedades y busque "hypergraphs" para ver muchos otros resultados que implican métodos de hypergraphs en sus pruebas.

Una cosa más, para las aplicaciones del mundo real, los métodos de hipergrafía aparecen en varios lugares, incluyendo problemas de desclasificación que son muy importantes para aumentar el rendimiento de las bases de datos paralelas.

Answer 3

Un ejemplo: Un hipergrafo 3-uniforme es la forma natural de modelar la estructura de variables/cláusulas de una instancia de 3-Sat. Dado que 3-Sat es uno de los problemas algorítmicos más importantes de la teoría de la complejidad computacional, los hipergrafos desempeñan un papel importante en él.

Para ver uno de los muchos ejemplos posibles, eche un vistazo al siguiente artículo de Feige, Kim y Ofek:

http://research.microsoft.com/en-us/um/redmond/groups/theory/feige/homepagefiles/witness5.9.06.pdf

Answer 4

Matroides y más en general, greedoides son clases especiales de hipergrafos. Para estas clases algoritmos codiciosos dan soluciones óptimas a los problemas de optimización y tienen una complejidad de tiempo polinómica baja. Los casos especiales son

• El algoritmo de Kruskal para encontrar árboles de extensión mínima, y
• El algoritmo de Dijkstra para encontrar los caminos más cortos, ambos en grafos ponderados.

Hay muchos otros algoritmos de matrices. Véase, por ejemplo

• El capítulo de Bixby y Cunningham en el Manual de Combinatoria, volumen 1 o
• El libro de Jungnickel Grafos, redes y algoritmos .

Answer 5

Los hipergráficos pueden surgir como edificios de Bruhat-Tits de grupos, véase por ejemplo aquí .

Algunas aplicaciones del mundo real: En este artículo los autores enumeran algunas aplicaciones a la biología. Su bonito ejemplo inicial es que si uno quiere modelar una reacción química puede escribir A-->B para un proceso que transforma A en B y ver esto como la arista de un gráfico. A veces, dicho proceso sólo funciona en presencia de algún catalizador (A+C-->B+C), lo que lo convierte en una relación entre tres en lugar de dos ingredientes y da una arista 2 de un hipergrafo.