¿Cuáles son las aplicaciones de los hipergrafos?

Question

Hipergráficos son como los grafos simples, salvo que en lugar de tener aristas que sólo conectan 2 vértices, sus aristas son conjuntos de cualquier número de vértices. Esto significa que todos los grafos son un subconjunto de los hipergrafos.

Me llama la atención, pues, que nunca haya oído hablar de ningún algoritmo basado en hipergrafos, ni 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 la de un grafo regular, y dado esto y su generalidad es más difícil hacer algoritmos ordenados para ella, pero ¡esperaría que hubiera algo!

¿Alguien ha oído hablar de un algoritmo basado en el hipergrafo, o de su aplicación? Me deja perplejo que los grafos ordinarios puedan ser tan maravillosamente útiles, pero sus hermanos mayores no tengan 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 hiperedges. Los datos que no son punteros dentro de las estructuras de datos son etiquetas de la hipercobertura asociada. Y los punteros son 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. Igualmente, la noción de datos. Para que esto sea útil, hay que restringir la forma que adoptan las hipérboles. 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 grafos. 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é Deducción del teorema de la densidad de Hales-Jewett a partir de un lema de eliminación infinita por Tim Austin. El teorema multidimensional de Szmerédi es también otra palabra clave que puede querer buscar. El teorema de Furstenberg-Katznelson (véase Un teorema ergódico de Szemerédi para transformaciones conmutativas puede demostrarse utilizando los métodos del hipergrafo. La clasificación de la asignatura de matemáticas es 05C65.

Y lo que es más importante, echa un vistazo al blog de Terry Tao 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 los problemas de desclasificación (ver Liu y Wu - Un enfoque basado en el hipergrafo para los problemas de desglose ) 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 artículo de Feige, Kim y Ofek: Testigos de la no satisfabilidad de las fórmulas densas aleatorias de 3CNF .

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

Hipergrafos dirigidos se utilizan para modelar redes de reacciones químicas. Esto está estrechamente relacionado con la aplicación biológica que Peter Arndt menciona en su respuesta.

La red de reacción y el hipergrafo subyacente se relacionan a través del matriz estequiométrica que es una matriz formada por unos, ceros y menos unos que generaliza la matriz de adyacencia de un gráfico.

Una pregunta obvia que se puede hacer sobre una red de este tipo es "¿hay bucles de retroalimentación? Esto se traduce en el problema matemático de encontrar hipercircuitos dirigidos en un hipergrafo dirigido. Esto resulta ser un problema NP-completo (como se muestra en este documento de Can Özturan) y, por tanto, ofrece otro ejemplo del tipo que menciona Gowers en su comentario.