Hipergrafía de intervalo D
En la teoría de grafos , un hipergráfico de intervalo d es un tipo de hipergráfico construido utilizando intervalos de líneas reales. El parámetro d es un entero positivo. Los vértices de una hipergrafía de intervalo d son los puntos de d líneas disjuntas (por lo tanto, hay innumerables vértices). Los bordes del gráfico son d -tuplas de intervalos, un intervalo en cada línea real. [1]
El caso más simple es d = 1. El conjunto de vértices de una hipergrafía de 1 intervalo es el conjunto de números reales; cada borde en tal hipergrafía es un intervalo de la línea real. Por ejemplo, el conjunto { [−2, −1], [0, 5], [3, 7] } define una hipergrafía de 1 intervalo. Tenga en cuenta la diferencia con un gráfico de intervalo : en un gráfico de intervalo, los vértices son los intervalos (un conjunto finito); en una hipergrafía de 1 intervalo, los vértices son todos puntos en la línea real (un conjunto incontable).
Como otro ejemplo, en una hipergrafía de 2 intervalos, el conjunto de vértices es la unión disjunta de dos líneas reales, y cada arista es una unión de dos intervalos: uno en la línea #1 y otro en la línea #2.
es cierto para cualquier hipergrafo H .
Tibor Gallai demostró que, en una hipergrafía de 1 intervalo, son iguales: . Esto es análogo al teorema de Kőnig para grafos bipartitos.
Gabor Tardos [1] demostró que, en una hipergrafía de 2 intervalos, , y es estrecha (es decir, cada hipergrafía de 2 intervalos con una coincidencia de tamaño m , puede cubrirse con 2 m puntos).
