En matemáticas , un hipergráfico es una generalización de un gráfico en el que una arista puede unir cualquier número de vértices . Por el contrario, en un gráfico ordinario, una arista conecta exactamente dos vértices.
Formalmente, un hipergrafo no dirigido es un par dónde es un conjunto de elementos llamados nodos o vértices , y es (en un hipergrafo no dirigido) un conjunto de subconjuntos no vacíos de llamados hipermercados o bordes . Por lo tanto, es un subconjunto de , dónde es el conjunto de poder de. El tamaño del conjunto de vértices se denomina orden del hipergráfico y el tamaño de los bordes establecidos es el tamaño del hipergráfico .
Un hipergrafo dirigido difiere en que sus hipergrafos no son conjuntos, sino un par ordenado de subconjuntos de , constituyendo la cola y la cabeza del hiperredge.
Mientras que los bordes del gráfico conectan solo 2 nodos, los hipermercados conectan un número arbitrario de nodos. Sin embargo, a menudo es deseable estudiar hipergráficos donde todos los hipergráficos tienen la misma cardinalidad; un hipergrafo uniforme k es un hipergrafo tal que todos sus hipergrafos tienen un tamao k . (En otras palabras, uno de esos hipergrafos es una colección de conjuntos, cada uno de estos conjuntos es un hipergrafo que conecta k nodos). De modo que un hipergrafo de 2 uniformes es un grafo, un hipergrafo de 3 uniformes es una colección de triples desordenados, etc. Un hipergrama no dirigido también se denomina sistema de conjuntos o familia de conjuntos extraídos del conjunto universal .
Los hipergráficos pueden verse como estructuras de incidencia . En particular, hay un "gráfico de incidencia" bipartito o " gráfico de Levi " correspondiente a cada hipergráfico y, a la inversa, la mayoría, pero no todos, los gráficos bipartitos pueden considerarse como gráficos de incidencia de hipergráficos.
Los hipergrafos tienen muchos otros nombres. En geometría computacional , un hipergrafo no dirigido a veces se puede llamar un espacio de rango y luego los hipergrafos se llaman rangos . [2] En la teoría de juegos cooperativos , los hipergráficos se denominan juegos simples (juegos de votación); esta noción se aplica para resolver problemas en la teoría de la elección social . En algunas publicaciones, los bordes se denominan hipervínculos o conectores . [3]
La colección de hipergráficos es una categoría con homomorfismos hipergráficos como morfismos .
Aplicaciones
Los hipergráficos no dirigidos son útiles para modelar cosas como problemas de satisfacción, [4] bases de datos, [5] aprendizaje automático, [6] y problemas de árbol de Steiner . [7] Se han utilizado ampliamente en tareas de aprendizaje automático como el modelo de datos y la regularización del clasificador (matemáticas) . [8] Las aplicaciones incluyen el sistema de recomendación (comunidades como hiperedges), [9] recuperación de imágenes (correlaciones como hiperedges), [10] y bioinformática (interacciones bioquímicas como hiperedges). [11] Las técnicas representativas de aprendizaje hipergráfico incluyen agrupamiento espectral hipergráfico que extiende la teoría del gráfico espectral con hipergráfico Laplaciano, [12] y aprendizaje hipergráfico semi-supervisado que introduce un costo estructural hipergráfico adicional para restringir los resultados del aprendizaje. [13] Para hipergráficos a gran escala, también está disponible un marco distribuido [6] construido con Apache Spark .
Los hipergráficos dirigidos se pueden utilizar para modelar cosas que incluyen aplicaciones de telefonía, [14] detección de lavado de dinero , [15] investigación de operaciones [16] y planificación del transporte. También se pueden usar para modelar la satisfacción de Horn . [17]
Generalizaciones de conceptos a partir de gráficos.
Muchos teoremas y conceptos que involucran gráficos también son válidos para los hipergráficos, en particular:
- Coincidencia en hipergráficos ;
- Cobertura de vértices en hipergráficos (también conocido como: transversal );
- Gráfico de líneas de un hipergráfico ;
- Gramática de hipergráficos : creada al aumentar una clase de hipergráficos con un conjunto de reglas de reemplazo;
- Teorema de Ramsey ;
- Teorema de Erdős-Ko-Rado ;
- Teorema de Kruskal-Katona sobre hipergráficos uniformes;
- Teoremas de tipo Hall para hipergráficos .
En hipergráficos dirigidos: cierre transitivo y problemas de camino más corto. [dieciséis]
Dibujo de hipergrafo
Aunque los hipergráficos son más difíciles de dibujar en papel que los gráficos, varios investigadores han estudiado métodos para la visualización de hipergráficos.
En una posible representación visual de los hipergráficos, similar al estilo de dibujo de gráficos estándar en el que se utilizan curvas en el plano para representar los bordes del gráfico, los vértices de un hipergráfico se representan como puntos, discos o cajas, y sus hipergrafias se representan como árboles que tienen los vértices como sus hojas. [18] [19] Si los vértices se representan como puntos, los hiperredges también pueden mostrarse como curvas suaves que conectan conjuntos de puntos, o como simples curvas cerradas que encierran conjuntos de puntos. [20] [21] [22]
En otro estilo de visualización hipergráfica, el modelo de subdivisión del dibujo hipergráfico, [23] el plano se subdivide en regiones, cada una de las cuales representa un único vértice del hipergráfico. Los hiperrápidos del hipergráfico están representados por subconjuntos contiguos de estas regiones, que pueden indicarse coloreando, dibujando contornos alrededor de ellas, o ambos. Un diagrama de orden n Venn , por ejemplo, puede verse como un dibujo de subdivisión de un hipergráfico con n hipergrafias (las curvas que definen el diagrama) y 2 n - 1 vértices (representados por las regiones en las que estas curvas subdividen el plano). En contraste con el reconocimiento de tiempo polinomial de gráficas planas , es NP-completo determinar si un hipergrafo tiene un dibujo de subdivisión planar, [24] pero la existencia de un dibujo de este tipo puede probarse de manera eficiente cuando el patrón de adyacencia del regiones está restringido a ser un camino, ciclo o árbol. [25]
En la figura de la parte superior de este artículo se muestra una representación alternativa del hipergráfico llamado PAOH [1] . Los bordes son líneas verticales que conectan vértices. Los vértices están alineados a la izquierda. La leyenda de la derecha muestra los nombres de los bordes. Ha sido diseñado para hipergráficos dinámicos, pero también se puede utilizar para hipergráficos simples.
Coloración de hipergrafo
La coloración hipergráfica clásica está asignando uno de los colores del conjunto a cada vértice de un hipergrafo de tal manera que cada hipergrabado contenga al menos dos vértices de colores distintos. En otras palabras, no debe haber hiperredge monocromático con cardinalidad al menos 2. En este sentido, es una generalización directa de la coloración del gráfico. El número mínimo de colores distintos utilizados sobre todos los colorantes se denomina número cromático de un hipergráfico.
Los hipergráficos para los que existe una coloración que utiliza hasta k colores se denominan k-coloreables . Los hipergráficos de 2 colores son exactamente los bipartitos.
Hay muchas generalizaciones de la coloración hipergráfica clásica. Una de ellas es la denominada coloración hipergráfica mixta, cuando se permiten bordes monocromáticos. Algunos hipergráficos mixtos no se pueden colorear para cualquier número de colores. Se desconoce un criterio general de decoloración. Cuando un hipergráfico mixto se puede colorear, el número mínimo y máximo de colores utilizados se denominan números cromáticos inferior y superior, respectivamente. Consulte http://spectrum.troy.edu/voloshin/mh.html para obtener más detalles.
Propiedades de los hipergrafos
Un hipergráfico puede tener varias propiedades, como:
- Vacío : no tiene bordes.
- No simple (o múltiple ) : tiene bucles (hipermercados con un solo vértice) o bordes repetidos, lo que significa que puede haber dos o más bordes que contengan el mismo conjunto de vértices.
- Simple : no tiene bucles ni bordes repetidos.
- -regular - cada vértice tiene grado, es decir, contenido exactamente hiperextensiones.
- 2-coloreable : sus vértices se pueden dividir en dos clases U y V de tal manera que cada hiperred con cardinalidad de al menos 2 contenga al menos un vértice de ambas clases. Un término alternativo es propiedad B .
- Dos propiedades más fuertes son bipartitas y equilibradas .
- -uniforme - cada hiperredge contiene precisamente vértices.
- -partita : los vértices se dividen en partes, y cada hiperredge contiene precisamente un vértice de cada tipo.
- Cada -hipergrafo partita (para) es ambos -uniforme y bipartita (y 2-coloreable).
- Cerrado hacia abajo : cada subconjunto de los bordes de un hipergráfico no dirigido también es un hiperrápido. Un hipergráfico cerrado hacia abajo generalmente se denomina complejo simplicial abstracto .
- Un complejo simplicial abstracto con una propiedad adicional llamada propiedad de aumento se llama matroide .
Hipergrafos relacionados
Debido a que los enlaces hipergráficos pueden tener cualquier cardinalidad, existen varias nociones del concepto de subgrafo, llamadas subhipergrafos , hipergrafos parciales e hipergrafos de seccion .
Dejar ser el hipergrafo que consta de vértices
y tener el borde establecido
dónde y son los conjuntos de índices de los vértices y aristas respectivamente.
Un subhipergrafo es un hipergrafo con algunos vrtices eliminados. Formalmente, el subhipergrafo Inducido por Se define como
Un término alternativo es la restricción de la H a A . [26] : 468
Una extensión de un subhipergrafo es un hipergrafo donde cada hipergrafia de que está parcialmente contenido en el subhipergrafo está completamente contenido en la extensión . Formalmente
- con y .
El hipergrafo parcial es un hipergrafo con algunos bordes eliminados. [26] : 468 Dado un subconjunto del conjunto de índices de borde, el hipergrama parcial generado por es el hipergrafo
Dado un subconjunto , el hipergrafo de la seccion es el hipergrafo parcial
El dual de es un hipergrafo cuyos vértices y aristas se intercambian, de modo que los vértices están dados por y cuyas aristas están dadas por dónde
Cuando una noción de igualdad se define adecuadamente, como se hace a continuación, la operación de tomar el dual de un hipergráfico es una involución , es decir,
Un grafo conexo G con el mismo conjunto de vértices como hypergraph conectado H es un gráfico de acogida para H si cada hyperedge de H induce un subgrafo conectado en G . Para un hipergráfico desconectado H , G es un gráfico anfitrión si hay una biyección entre los componentes conectados de G y de H , de modo que cada componente conectado G ' de G es un anfitrión del H' correspondiente .
El 2-sección (o gráfico camarilla , gráfico que representa , gráfico primal , gráfico Gaifman ) de un hypergraph es la gráfica con los mismos vértices de la hypergraph, y bordes entre todos los pares de vértices contenidos en la misma hyperedge.
Matriz de incidencia
Dejar y . Cada hipergrafo tiene un matriz de incidencia .
Para un hipergrafo no dirigido, dónde
La transposición de la matriz de incidencia define un hipergrafollamado el dual de, dónde es un conjunto de elementos m yes un conjunto de n elementos de subconjuntos de. Para y si y solo si .
Para un hipergrafo dirigido, las cabezas y colas de cada hipergrafia se denotan por y respectivamente. [17] dónde
Gráfico de incidencia
Un hipergráfico H puede representarse mediante un gráfico bipartito BG de la siguiente manera: los conjuntos X y E son las particiones de BG , y ( x 1 , e 1 ) están conectados con una arista si y solo si el vértice x 1 está contenido en la arista e 1 en H .
Por el contrario, cualquier gráfico bipartito con partes fijas y sin nodos desconectados en la segunda parte representa algún hipergráfico de la manera descrita anteriormente. Este gráfico bipartito también se denomina gráfico de incidencia .
Ciclos
En contraste con los gráficos ordinarios no dirigidos para los que existe una única noción natural de ciclos y gráficos acíclicos , existen múltiples definiciones naturales no equivalentes de aciclicidad para hipergráficos que colapsan a aciclicidad de gráfico ordinario para el caso especial de gráficos ordinarios.
Claude Berge dio una primera definición de aciclicidad para hipergráficos : [27] un hipergráfico es Berge-acíclico si su gráfico de incidencia (el gráfico bipartito definido anteriormente) es acíclico. Esta definición es muy restrictiva: por ejemplo, si un hipergráfico tiene algún par de vértices y algún par de hiperextensiones tales que y , entonces es Berge-cíclico. La ciclicidad de Berge obviamente se puede probar en tiempo lineal mediante una exploración del gráfico de incidencia.
Podemos definir una noción más débil de aciclicidad hipergráfica, [5] posteriormente denominada aciclicidad α. Esta noción de aciclicidad es equivalente a que el hipergráfico sea conforme (cada pandilla del gráfico primario está cubierto por algún hiperrápido) y su gráfico primario es cordal ; también es equivalente a la reducibilidad al gráfico vacío a través del algoritmo GYO [28] [29] (también conocido como algoritmo de Graham), un proceso iterativo confluente que elimina los hiperfregos utilizando una definición generalizada de oídos . En el dominio de la teoría de bases de datos , se sabe que un esquema de base de datos disfruta de ciertas propiedades deseables si su hipergráfico subyacente es α-acíclico. [30] Además, la α-aciclicidad también está relacionada con la expresividad del fragmento protegido de la lógica de primer orden .
Podemos probar en tiempo lineal si un hipergráfico es α-acíclico. [31]
Tenga en cuenta que la α-aciclicidad tiene la propiedad contraintuitiva de que agregar hipergrafias a un hipergrafo α-cíclico puede hacer que sea α-acíclico (por ejemplo, agregar una hiperedge que contenga todos los vértices del hipergrafo siempre lo hará α-acíclico). Motivado en parte por esta deficiencia percibida, Ronald Fagin [32] definió las nociones más fuertes de β-aciclicidad y γ-aciclicidad. Podemos afirmar la β-aciclicidad como el requisito de que todos los subhipergramas del hipergráfico sean α-acíclicos, lo que equivale [32] a una definición anterior de Graham. [29] La noción de γ-aciclicidad es una condición más restrictiva que es equivalente a varias propiedades deseables de los esquemas de bases de datos y está relacionada con los diagramas de Bachman . Tanto la β-aciclicidad como la γ-aciclicidad se pueden probar en tiempo polinómico .
Esas cuatro nociones de aciclicidad son comparables: aciclicidad de Berge implica γ-aciclicidad que implica β-aciclicidad que implica α-aciclicidad. Sin embargo, ninguna de las implicaciones inversas se cumple, por lo que esas cuatro nociones son diferentes. [32]
Isomorfismo, simetría e igualdad
Un homomorfismo de hipergráfico es un mapa del conjunto de vértices de un hipergráfico a otro, de modo que cada borde se asigna a otro borde.
Un hipergrafo es isomorfo a un hipergrafo, Escrito como si existe una biyeccion
y una permutación de tal que
La biyeccion Entonces se llama isomorfismo de las gráficas. Tenga en cuenta que
- si y solo si .
Cuando los bordes de un hipergráfico se etiquetan explícitamente, se tiene la noción adicional de isomorfismo fuerte . Uno dice quees fuertemente isomorfo asi la permutación es la identidad. Uno luego escribe. Tenga en cuenta que todos los gráficos fuertemente isomórficos son isomórficos, pero no al revés.
Cuando los vértices de un hipergráfico se etiquetan explícitamente, se tienen las nociones de equivalencia y también de igualdad . Uno dice quees equivalente ay escribe si el isomorfismo posee
y
Tenga en cuenta que
- si y solo si
Si, además, la permutación es la identidad, se dice que es igual a y escribe . Tenga en cuenta que, con esta definición de igualdad, los gráficos son auto-duales:
Un automorfismo hipergráfico es un isomorfismo de un conjunto de vértices en sí mismo, es decir, un reetiquetado de vértices. El conjunto de automorfismos de un hipergráfico H (= ( X , E )) es un grupo en composición, llamado grupo de automorfismos del hipergráfico y escrito Aut ( H ).
Ejemplos de
Considere el hipergrafo con bordes
y
Entonces claramente y son isomorfos (con , etc. ), pero no son fuertemente isomórficos. Entonces, por ejemplo, en, vértice se encuentra con los bordes 1, 4 y 6, de modo que,
En grafico , no existe ningún vértice que se encuentre con las aristas 1, 4 y 6:
En este ejemplo, y son equivalentes, , y los duales son fuertemente isomorfos: .
Simetría
La rango de un hipergrafo es la cardinalidad máxima de cualquiera de los bordes del hipergráfico. Si todas las aristas tienen la misma cardinalidad k , se dice que el hipergrafo es uniforme o k-uniforme , o se llama k-hipergrafo . Un gráfico es solo un hipergrama de 2 uniformes.
El grado d (v) de un vértice v es el número de aristas que lo contienen. H es k-regular si cada vértice tiene grado k .
El dual de un hipergráfico uniforme es regular y viceversa.
Dos vértices x y y de H se llaman simétrica si existe un automorfismo tal que. Dos aristas y se dice que son simétricos si existe un automorfismo tal que.
Se dice que un hipergrafo es transitivo al vértice (o simétrico al vértice ) si todos sus vértices son simétricos. De manera similar, un hipergráfico es transitivo por los bordes si todos los bordes son simétricos. Si un hipergráfico es simétrico tanto en el borde como en el vértice, entonces el hipergráfico es simplemente transitivo .
Debido a la dualidad hipergráfica, el estudio de la transitividad de los bordes es idéntico al estudio de la transitividad de los vértices.
Particiones
Un teorema de partición debido a E. Dauber [33] establece que, para un hipergráfico de borde transitivo, existe una partición
del conjunto de vértices tal que el subhipergrafo generado por es transitivo para cada , y tal que
dónde es el rango de H .
Como corolario, un hipergráfico de borde transitivo que no es transitivo de vértice es bicolor.
La partición de gráficos (y en particular, la partición de hipergráficos) tiene muchas aplicaciones para el diseño de circuitos integrados [34] y la computación paralela. [35] [36] [37] Los algoritmos de partición hipergráficos eficientes y escalables también son importantes para procesar hipergráficos a gran escala en tareas de aprendizaje automático. [6]
Más generalizaciones
Una posible generalización de un hipergráfico es permitir que los bordes apunten a otros bordes. Hay dos variaciones de esta generalización. En uno, los bordes consisten no solo en un conjunto de vértices, sino que también pueden contener subconjuntos de vértices, subconjuntos de subconjuntos de vértices, etc. ad infinitum . En esencia, cada borde es solo un nodo interno de un árbol o un gráfico acíclico dirigido , y los vértices son los nodos de las hojas. Entonces, un hipergráfico es solo una colección de árboles con nodos comunes y compartidos (es decir, un nodo interno u hoja determinada puede aparecer en varios árboles diferentes). A la inversa, cada colección de árboles puede entenderse como este hipergráfico generalizado. Dado que los árboles se utilizan ampliamente en la informática y en muchas otras ramas de las matemáticas, se podría decir que los hipergráficos también aparecen de forma natural. Entonces, por ejemplo, esta generalización surge naturalmente como un modelo de álgebra de términos ; las aristas corresponden a términos y los vértices corresponden a constantes o variables.
Para tal hipergráfico, la pertenencia al conjunto proporciona un orden, pero el orden no es ni un orden parcial ni un preorden , ya que no es transitivo. El gráfico correspondiente al gráfico de Levi de esta generalización es un gráfico acíclico dirigido . Considere, por ejemplo, el hipergráfico generalizado cuyo conjunto de vértices es y cuyos bordes son y . Entonces, aunque y , no es cierto que . Sin embargo, el cierre transitivo de la pertenencia al conjunto para tales hipergráficos induce un orden parcial y "aplana" el hipergráfico en un conjunto parcialmente ordenado .
Alternativamente, se puede permitir que los bordes apunten a otros bordes, independientemente del requisito de que los bordes se ordenen como gráficos acíclicos dirigidos. Esto permite gráficos con bucles de borde, que no necesitan contener vértices en absoluto. Por ejemplo, considere el hipergráfico generalizado que consta de dos bordes y y cero vértices, de modo que y . Como este bucle es infinitamente recursivo, los conjuntos que son los bordes violan el axioma de fundación . En particular, no existe un cierre transitivo de la pertenencia al conjunto para tales hipergráficos. Aunque estas estructuras pueden parecer extrañas al principio, pueden entenderse fácilmente si se observa que la generalización equivalente de su gráfico de Levi ya no es bipartita , sino más bien una gráfica dirigida general .
La matriz de incidencia generalizada para tales hipergráficos es, por definición, una matriz cuadrada, de un rango igual al número total de vértices más aristas. Por lo tanto, para el ejemplo anterior, la matriz de incidencia es simplemente
Ver también
- Diseño combinatorio
- Gráfico de factores
- Greedoid
- Estructura de incidencia
- Multigraph
- Sistema P
- Multiplicación dispersa matriz-vector
Notas
- ↑ a b Valdivia, Paola; Buono, Paolo; Plaisant, Catherine; Dufournaud, Nicole; Fekete, Jean-Daniel (2020). "Análisis de hipergráficos dinámicos con visualización de hipergráficos ordenados agregados en paralelo" (PDF) . Transacciones IEEE sobre visualización y gráficos por computadora . IEEE. 26 : 12. doi : 10.1109 / TVCG.2019.2933196 . eISSN 1941-0506 . ISSN 1077-2626 . PMID 31398121 .
- ^ Haussler, David ; Welzl, Emo (1987), "ε-nets and simplex range queries", Discrete and Computational Geometry , 2 (2): 127-151, doi : 10.1007 / BF02187876 , MR 0884223.
- ^ Judea Pearl, en Estrategias de búsqueda inteligente HEURISTICS para la resolución de problemas informáticos , Addison Wesley (1984), p. 25.
- ^ Feige, Uriel; Kim, Jeong Han; Ofek, Eran (2006). Testigos de la no satisfacción de fórmulas densas de 3CNF aleatorias . IEEE.
- ^ a b Beeri, C .; Fagin, R .; Maier, D .; Yannakakis, M. (1983). "Sobre la conveniencia de los esquemas de base de datos acíclicos" (PDF) . Revista de la ACM . 30 (3): 479–513. doi : 10.1145 / 2402.322389 .
- ^ a b c Huang, Jin; Zhang, Rui; Yu, Jeffrey Xu (2015), "Aprendizaje y procesamiento de hipergráficos escalables" (PDF) , Actas de la Conferencia internacional IEEE sobre minería de datos
- ^ Brasil, M; Zachariasen, M (2015). "Árboles Steiner en gráficos e hipergráficos" . Algoritmos y Combinatoria . Saltador. 29 . doi : 10.1007 / 978-3-319-13915-9_5 . ISBN 978-3-319-13915-9.
- ^ Zhou, Dengyong; Huang, Jiayuan; Scholkopf, Bernhard (2006), "Aprendizaje con hipergráficos: agrupamiento, clasificación e incrustación", Avances en los sistemas de procesamiento de información neuronal (2): 1601–1608
- ^ Tan, Shulong; Bu, Jiajun; Chen, Chun; Xu, Bin; Wang, Can; Él, Xiaofei (2013), "Uso de información enriquecida de las redes sociales para la recomendación de música a través del modelo hipergráfico" , ACM Transactions on Multimedia Computing, Communications, and Applications (1), Bibcode : 2011smma.book..213T
- ^ Liu, Qingshan; Huang, Yuchi; Metaxas, Dimitris N. (2013), "Hypergraph con muestreo para recuperación de imágenes", Reconocimiento de patrones , 44 (10-11): 2255-2262, doi : 10.1016 / j.patcog.2010.07.014
- ^ Patro, Rob; Kingsoford, Carl (2013), "Predicción de interacciones de proteínas a través de la inferencia de la historia de la red parsimoniosa", Bioinformatics , 29 (10-11): 237-246, doi : 10.1093 / bioinformatics / btt224 , PMC 3694678 , PMID 23812989
- ^ Gao, Tue; Wang, Meng; Zha, Zheng-Jun; Shen, Jialie; Li, Xuelong; Wu, Xindong (2013), "Aprendizaje de relevancia conjunta visual-textual para la búsqueda de imágenes sociales basada en etiquetas" , IEEE Transactions on Image Processing , 22 (1): 363–376, Bibcode : 2013ITIP ... 22..363Y , doi : 10.1109 / tip.2012.2202676 , PMID 22692911 , S2CID 7432373
- ^ Tian, Ze; Hwang, TaeHyun; Kuang, Rui (2009), "Un algoritmo de aprendizaje basado en hipergráficos para clasificar la expresión génica y los datos de arrayCGH con conocimientos previos", Bioinformatics , 25 (21): 2831-2838, doi : 10.1093 / bioinformatics / btp467 , PMID 19648139
- ^ Goldstein, A (1982). "Una base de datos de hipergrafo dirigido: un modelo para la planta de telefonía de bucle local" (PDF) . El diario técnico de Bell System . 61 .
- ^ Ranshous, Stephen; Joslyn, Cliff; Kreyling, Sean; Nowak, Kathleen; Samatova, Nagiza; West, Curtis; Winters, Samuel (2017). Minería de patrones de intercambio en el hipergráfico dirigido por transacciones de Bitcoin (PDF) . Criptografía financiera y seguridad de datos. Saltador. doi : 10.1007 / 978-3-319-70278-0_16 .
- ^ a b Ausiello, Giorgio; Laura, Luigi (2017). "Hipergrafos dirigidos: Introducción y algoritmos fundamentales - Una encuesta" . Informática Teórica . 658 : 293-306. doi : 10.1016 / j.tcs.2016.03.016 .
- ^ a b Gallo, G .; Longo, G .; Pallottino, S .; Nguyen, S. (1993). "Hipergrafos dirigidos y aplicaciones" . Matemáticas aplicadas discretas . 42 (2-3): 177-201. doi : 10.1016 / 0166-218X (93) 90045-P .
- ^ Sander, G. (2003), "Disposición de hipergráficos dirigidos con hipergrafias ortogonales" , Proc. XI Simposio Internacional sobre Dibujo de Gráficos (GD 2003) , Lecture Notes in Computer Science , 2912 , Springer-Verlag, págs. 381–386.
- ^ Eschbach, Thomas; Günther, Wolfgang; Becker, Bernd (2006), "Dibujo hipergráfico ortogonal para mejorar la visibilidad" (PDF) , Journal of Graph Algorithms and Applications , 10 (2): 141-157, doi : 10.7155 / jgaa.00122.
- ^ Mäkinen, Erkki (1990), "Cómo dibujar un hipergráfico", International Journal of Computer Mathematics , 34 (3): 177-185, doi : 10.1080 / 00207169008803875.
- ^ Bertault, François; Eades, Peter (2001), "Dibujar hipergráficos en el subconjunto estándar", Proc. Octavo Simposio Internacional sobre Dibujo de Gráficos (GD 2000) , Lecture Notes in Computer Science, 1984 , Springer-Verlag, págs. 45–76, doi : 10.1007 / 3-540-44541-2_15 , ISBN 978-3-540-41554-1.
- ^ Naheed Anjum, Arafat; Bressan, Stéphane (2017), "Hypergraph Drawing by Force-Directed Placement", 28th International Conference on Database and Expert Systems Applications (DEXA 2017) , Lecture Notes in Computer Science, 10439 , Springer International Publishing, págs. 387–394, doi : 10.1007 / 978-3-319-64471-4_31 , ISBN 978-3-319-64470-7.
- ^ Kaufmann, Michael; van Kreveld, Marc; Speckmann, Bettina (2009), "Dibujos de subdivisión de hipergráficos", Proc. 16º Simposio Internacional sobre Dibujo de Gráficos (GD 2008) , Lecture Notes in Computer Science, 5417 , Springer-Verlag, págs. 396–407, doi : 10.1007 / 978-3-642-00219-9_39 , ISBN 978-3-642-00218-2.
- ^ Johnson, David S .; Pollak, HO (2006), "Planaridad hipergráfica y la complejidad de dibujar diagramas de Venn", Journal of Graph Theory , 11 (3): 309–325, doi : 10.1002 / jgt.3190110306.
- ^ Buchin, Kevin; van Kreveld, Marc; Meijer, Henk; Speckmann, Bettina; Verbeek, Kevin (2010), "Sobre soportes planos para hipergráficos", Proc. 17th International Symposium on Graph Drawing (GD 2009) , Lecture Notes in Computer Science, 5849 , Springer-Verlag, págs. 345–356, doi : 10.1007 / 978-3-642-11805-0_33 , ISBN 978-3-642-11804-3.
- ^ a b Lovász, László ; Plummer, MD (1986), Teoría de emparejamiento , Annals of Discrete Mathematics, 29 , Holanda Septentrional, ISBN 0-444-87916-1, MR 0859549
- ^ Berge, Claude (1973). Gráficos e hipergráficos . Amsterdam: Holanda Septentrional. ISBN 0-7204-2450-X.
- ^ Yu, CT; Özsoyoğlu, MZ (1979). "Un algoritmo para la membresía de consulta de árbol de una consulta distribuida" (PDF) . Proc. IEEE COMPSAC : 306–312.
- ^ a b Graham, MH (1979). "Sobre la relación universal". Informe técnico . Toronto, Ontario, Canadá: Universidad de Toronto.
- ^ Abiteboul, S .; Hull, RB ; Vianu, V. (1995). Fundamentos de bases de datos . Addison-Wesley. ISBN 0-201-53771-0.
- ^ Tarjan, RE ; Yannakakis, M. (1984). "Algoritmos simples de tiempo lineal para probar la cordalidad de los gráficos, probar la aciclicidad de los hipergráficos y reducir selectivamente los hipergráficos acíclicos". Revista SIAM de Computación . 13 (3): 566–579. doi : 10.1137 / 0213035 .
- ^ a b c Fagin, Ronald (1983). "Grados de aciclicidad para hipergrafos y esquemas de bases de datos relacionales". Revista de la ACM . 30 (3): 514–550. doi : 10.1145 / 2402.322390 .
- ^ E. Dauber, en teoría de grafos , ed. F. Harary, Addison Wesley, (1969) pág. 172.
- ^ Karypis, G., Aggarwal, R., Kumar, V. y Shekhar, S. (marzo de 1999), "Multilevel hypergraph particioning: applications in VLSI domain", IEEE Transactions on Very Large Scale Integration (VLSI) Systems , 7 ( 1): 69–79, CiteSeerX 10.1.1.553.2367 , doi : 10.1109 / 92.748202 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Hendrickson, B., Kolda, TG (2000), "Modelos de partición de gráficos para computación en paralelo" , Computación en paralelo (manuscrito enviado), 26 (12): 1519-1545, doi : 10.1016 / S0167-8191 (00) 00048-X .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Catalizador, UV; Aykanat, C. (1995). Un modelo hipergráfico para mapear cálculos repetidos de productos de matriz dispersa-vector en multicomputadoras . Proc. Congreso Internacional de Computación de Alto Rendimiento (HiPC'95).
- ^ Catalizador, UV; Aykanat, C. (1999), "Descomposición basada en particiones hipergráficas para la multiplicación de vectores de matriz dispersa en paralelo", Transacciones IEEE en sistemas paralelos y distribuidos , 10 (7): 673–693, CiteSeerX 10.1.1.67.2498 , doi : 10.1109 /71.780863 .
Referencias
- Claude Berge, "Hipergrafos: Combinatoria de conjuntos finitos". Holanda Septentrional, 1989.
- Claude Berge, Dijen Ray-Chaudhuri, "Seminario Hypergraph, Universidad Estatal de Ohio 1972", Notas de la conferencia en Matemáticas 411 Springer-Verlag
- "Hypergraph" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
- Alain Bretto, "Teoría del hipergráfico: una introducción", Springer, 2013.
- Vitaly I. Voloshin. "Colorear Hipergrafos Mixtos: Teoría, Algoritmos y Aplicaciones". Monografías del Fields Institute, American Mathematical Society, 2002.
- Vitaly I. Voloshin. "Introducción a la Teoría de Gráficos e Hipergrafos". Nova Science Publishers, Inc. , 2009.
- Este artículo incorpora material de Hypergraph en PlanetMath , que tiene la licencia Creative Commons Attribution / Share-Alike License .
enlaces externos
- PAOHVis : sistema PAOHVis de código abierto para visualizar hipergráficos dinámicos.