En la teoría de grafos , una coincidencia en un hipergrafo es un conjunto de hipergrafias , en el que cada dos hipergrafias están disjuntos. Es una extensión de la noción de emparejamiento en un gráfico . [1] : 466–470 [2]
Definición
Recuerde que un hipergráfico H es un par ( V , E ), donde V es un conjunto de vértices y E es un conjunto de subconjuntos de V llamados hiperredges . Cada hiperredge puede contener uno o más vértices.
Un emparejamiento en H es un subconjunto M de E , de modo que cada dos hipermercados e 1 y e 2 en M tienen una intersección vacía (no tienen vértice en común).
El número correspondiente de un hypergraph H es el mayor tamaño de un coincidente en H . A menudo se denota por. [1] : 466 [3]
Como ejemplo, sea V el conjunto {1,2,3,4,5,6,7}. considere un hipergrafo uniforme de 3 en V (un hipergrafo en el que cada hipergrafia contiene exactamente 3 vértices). Sea H un hipergrafo uniforme de 3 con 4 hiperexpresiones:
- {{1,2,3}, {1,4,5}, {4,5,6}, {2,3,6}}
Entonces H admite varios emparejamientos de tamaño 2, por ejemplo:
- {{1,2,3}, {4,5,6}}
- {{1,4,5}, {2,3,6}}
Sin embargo, en cualquier subconjunto de 3 hiperredges, al menos dos de ellos se cruzan, por lo que no hay coincidencia de tamaño 3. Por tanto, el número coincidente de H es 2.
Coincidencia en un gráfico como caso especial
Un gráfico sin bucles propios es solo un hipergráfico uniforme de 2: cada borde puede considerarse como un conjunto de los dos vértices que conecta. Por ejemplo, este hipergráfico de 2 uniformes representa un gráfico con 4 vértices {1,2,3,4} y 3 aristas:
- {{1,3}, {1,4}, {2,4}}
Según la definición anterior, una coincidencia en un gráfico es un conjunto M de aristas, de modo que cada dos aristas en M tienen una intersección vacía. Esto equivale a decir que no hay dos aristas en M adyacentes al mismo vértice; esta es exactamente la definición de coincidencia en un gráfico .
Coincidencia fraccional
Una coincidencia fraccionaria en un hipergrafo es una función que asigna una fracción en [0,1] a cada hiperedge, de modo que para cada vértice v en V , la suma de las fracciones de hiperedges que contienen v es como máximo 1. Una coincidencia es un especial caso de un emparejamiento fraccional en el que todas las fracciones son 0 o 1. El tamaño de un emparejamiento fraccionario es la suma de las fracciones de todos los hiperredges.
El número correspondiente fraccional de un hypergraph H es el mayor tamaño de un juego fraccional en H . A menudo se denota por. [3]
Dado que una coincidencia es un caso especial de coincidencia fraccional, para cada hipergrama H :
número-coincidente ( H ) ≤ número-coincidente fraccional ( H );
En símbolos:
En general, el número coincidente fraccionario puede ser mayor que el número coincidente. Un teorema de Zoltán Füredi [4] proporciona límites superiores en la relación número de coincidencia fraccional ( H ) / número de coincidencia ( H ):
- Si cada hiperredge en H contiene como máximo r vértices, entonces. En particular, en un gráfico simple,. [5]
- La desigualdad es aguda: sea H r el plano proyectivo finito uniforme r . Luego ya que cada dos hipermercados se cruzan y por el emparejamiento fraccional que asigna un peso de 1 / r a cada hiperredge (es un emparejamiento ya que cada vértice está contenido en r hyperredges, y su tamaño es r -1 + 1 / r ya que hay r 2 - r +1 hyperredges ). Por lo tanto, la razón es exactamente r -1 + 1 / r .
- Si r es tal que el plano proyectivo finito uniforme r -uniforme no existe (por ejemplo, r = 7), entonces se cumple una desigualdad más fuerte:.
- Si H es r -partita (- los vértices se dividen en r partes y cada hiperredge contiene un vértice de cada parte), entonces En particular, en un gráfico bipartito, . Así lo demostró András Gyárfás . [4]
- La desigualdad es aguda: Sea H r- el plano proyectivo truncado de orden r -1. Luego ya que cada dos hipermercados se cruzan y por el emparejamiento fraccional que asigna un peso de 1 / r a cada hiperredge (hay r 2 - r hyperredges).
Combinación perfecta
Un juego M se llama perfecto si cada vértice v en V está contenido en exactamente uno hyperedge de M . Ésta es la extensión natural de la noción de correspondencia perfecta en un gráfico.
Una coincidencia fraccionaria M se llama perfecta si para cada vértice v en V , la suma de las fracciones de hiperredges en M que contienen v es exactamente 1.
Considere un hipergrafo H en el que cada hipergrabado contiene como máximo n vértices. Si H admite una coincidencia fraccionaria perfecta, entonces su número de coincidencia fraccional es al menos | V | / n . Si cada hiperredge en H contiene exactamente n vértices, entonces su número de coincidencia fraccional está exactamente en | V | / n . [6] : sec.2 Esta es una generalización del hecho de que, en un gráfico, el tamaño de una coincidencia perfecta es | V | / 2.
Dado un conjunto V de vértices, una colección E de subconjuntos de V se llama equilibrada si el hipergrama ( V , E ) admite una coincidencia fraccionaria perfecta.
Por ejemplo, si V = {1,2,3, a, b, c} y E = {{1, a}, {2, a}, {1, b}, {2, b}, {3, c}}, entonces E está equilibrada, con la coincidencia fraccionaria perfecta {1/2, 1/2, 1/2, 1/2, 1}.
Hay varias condiciones suficientes para la existencia de una coincidencia perfecta en un hipergráfico:
- Teoremas de tipo Hall para hipergráficos : presenta condiciones suficientes análogas al teorema del matrimonio de Hall, basado en conjuntos de vecinos.
- Emparejamiento perfecto en hipergráficos de alto grado : presenta condiciones suficientes análogas al teorema de Dirac sobre ciclos hamiltonianos , según el grado de vértices.
- Keevash y Mycroft desarrollaron una teoría geométrica para la coincidencia de hipergráficos. [7]
Hipergrafo de intersección
Un hipergrafo H = ( V , E ) se llama intersección si cada dos hipergrafias en E tienen un vértice en común. En un gráfico de intersección, no hay coincidencia con dos o más hipermercados, por lo tanto. [4]
Familia de conjuntos equilibrada
Una familia de conjuntos E sobre un conjunto básico V se llama equilibrada (con respecto a V ) si el hipergrama H = (V, E) admite una coincidencia fraccionaria perfecta. [6] : sección 2
Por ejemplo, considere el conjunto de vértices V = {1,2,3, a, b, c} y el conjunto de aristas E = {1-a, 2-a, 1-b, 2-b, 3-c}. E está equilibrado, ya que hay una correspondencia fraccionaria perfecta con pesos {1/2, 1/2, 1/2, 1/2, 1}.
Calcular una coincidencia máxima
El problema de encontrar una coincidencia de cardinalidad máxima en un hipergráfico, calculando así , es NP-hard incluso para hipergráficos de 3 uniformes (ver correspondencia tridimensional ). Esto contrasta con el caso de gráficos simples (2 uniformes) en los que se puede calcular una coincidencia de cardinalidad máxima en tiempo polinomial.
Coincidencia y cobertura
Una cobertura de vértice en un hipergrafo H = ( V , E ) es un subconjunto T de V , de modo que cada hiperfilo en E contiene al menos un vértice de T (también se denomina conjunto transversal o de impacto , y es equivalente a una cubierta fija ). Es una generalización de la noción de cobertura de vértice en un gráfico.
El número de vértice de la cubierta de un hypergraph H es el tamaño más pequeño de una cubierta de vértice en H . A menudo se denota por, [1] : 466 para transversal.
Una cobertura de vértice fraccional es una función que asigna un peso a cada vértice en V , de modo que para cada hiperredge e en E , la suma de fracciones de vértices en e es al menos 1. Una cobertura de vértice es un caso especial de vértice fraccionario cubierta en la que todos los pesos son 0 o 1. El tamaño de una cubierta de vértice fraccional es la suma de las fracciones de todos los vértices.
El número de vértice de la cubierta fraccional de un hypergraph H es el tamaño más pequeño de un vértice de la cubierta fraccional en H . A menudo se denota por.
Dado que una cobertura de vértice es un caso especial de una cobertura de vértice fraccional, para cada hipergráfico H :
número-cubierta-vértice-fraccional ( H ) ≤ número-cubierta-vértice ( H ).
La dualidad de programación lineal implica que, para cada hipergráfico H :
número-de-coincidencia-fraccional ( H ) = número-de-cubierta-de-vértice-fraccional ( H ).
Por lo tanto, para cada hipergráfico H : [4]
Si el tamaño de cada hiperredge en H es como máximo r, entonces la unión de todas las hiperredges en una coincidencia máxima es una cobertura de vértice (si hubiera una hiperredge descubierta, podríamos haberla agregado a la coincidencia). Por lo tanto:
.
Esta desigualdad es estrecha: la igualdad se mantiene, por ejemplo, cuando V contienevértices y E contiene todos los subconjuntos de r vértices.
Sin embargo, en general , desde ; ver Coincidencia fraccional arriba.
La conjetura de Ryser dice que, en todos los r -partite r Uniform hypergraph:
.
Se han probado algunos casos especiales de la conjetura; ver la conjetura de Ryser .
Propiedad de Kőnig
Un hipergrafo tiene la propiedad Kőnig si su número máximo coincidente es igual a su número mínimo de cobertura de vértice, es decir, si. El teorema de Kőnig-Egerváry muestra que todo gráfico bipartito tiene la propiedad de Kőnig. Para extender este teorema a los hipergráficos, necesitamos extender la noción de bipartita a los hipergráficos. [1] : 468
Una generalización natural es la siguiente. Un hipergráfico se llama 2-coloreable si sus vértices pueden ser de 2 colores de modo que cada hipergrafia (de tamaño al menos 2) contenga al menos un vértice de cada color. Un término alternativo es propiedad B . Una gráfica simple es bipartita si es 2-coloreable. Sin embargo, hay hipergrafías de 2 colores sin la propiedad de Kőnig. Por ejemplo, considere el hipergráfico con V = {1,2,3,4} con E = todos los tripletes = {{1,2,3}, {1,2,4}, {1,3,4}, { 2,3,4}}. Es 2-colorante, por ejemplo, podemos colorear {1,2} azul y {3,4} blanco. Sin embargo, su número coincidente es 1 y su número de cobertura de vértice es 2.
Una generalización más fuerte es la siguiente. Dado un hipergráfico H = ( V , E ) y un subconjunto V ' de V , la restricción de H a V' es el hipergrama cuyos vértices son V , y por cada hipergrafia en e en E que interseca a V ', tiene una hipergrafia e 'que es la intersección de e y V '. Un hipergráfico se llama equilibrado si todas sus restricciones son 2-coloreables. [8] Un gráfico simple es bipartito si está equilibrado.
Un gráfico simple es bipartito si no tiene ciclos de longitud impar. De manera similar, un hipergrama está equilibrado si no tiene circuitos de longitud impar . Un circuito de longitud k en un hipergrafo es una secuencia alterna ( v 1 , e 1 , v 2 , e 2 , ..., v k , e k , v k +1 = v 1 ), donde los v i son distintos los vértices y el e i son hipereduras distintas, y cada hiperedge contiene el vértice a su izquierda y el vértice a su derecha. El circuito se llama desequilibrado si cada hiperredge no contiene otros vértices en el circuito. Claude Berge demostró que un hipergráfico está equilibrado si no contiene un circuito de longitud impar desequilibrado. Todo hipergrafo equilibrado tiene la propiedad de Kőnig. [9] [1] : 468–470
Los siguientes son equivalentes: [1] : 470–471
- Cada hipergrafo parcial de H (es decir, un hipergrafo derivado de H eliminando algunos hipergrafos) tiene la propiedad Kőnig.
- Todo hipergráfico parcial de H tiene la propiedad de que su grado máximo es igual a su número mínimo de coloración de borde .
- H tiene la propiedad de Helly , y la gráfica de intersección de H (la gráfica simple en la que los vértices son E y dos elementos de E están vinculados si se cruzan) es una gráfica perfecta .
Empaque y emparejamiento
Un empaquetamiento de vértices en una gráfica (simple) es un subconjunto P de sus vértices, de modo que no hay dos vértices en P adyacentes.
El problema de encontrar un empaquetamiento máximo de vértices en un gráfico es equivalente al problema de encontrar un emparejamiento máximo en un hipergráfico: [1] : 467
- Dado un hipergrama H = ( V , E ), defina su gráfico de intersección Int ( H ) como el gráfico simple cuyos vértices son E y cuyas aristas son pares ( e 1 , e 2 ) tal que e 1 , e 2 tienen un vértice en común. Entonces, cada coincidencia en H es un empaquetamiento de vértices en Int ( H ) y viceversa.
- Dado un grafo G = ( V ', E '), defina su hipergrafo de estrella St ( G ) como el hipergrafo cuyos vértices son E 'y cuyos hipergrafos son las estrellas de los vértices de G (es decir, para cada vértice v ' en V ', hay un hiperredge en St ( G ) que contiene todos los bordes en E ' que son adyacentes a v '). Entonces, cada empaquetamiento de vértices en G es una coincidencia en St ( G ) y viceversa.
- Alternativamente, dado un gráfico G = ( V ', E '), defina su hipergráfico clique Cl ( G ) como el hipergráfico cuyos vértices son los cliques de G, y para cada vértice v 'en V ', hay un hipergrafo en Cl ( G ) que contiene todas las camarillas en G que contienen v '. Por otra parte, cada empaquetamiento de vértices en G es una coincidencia en Cl ( G ) y viceversa. Tenga en cuenta que Cl ( G ) no se puede construir a partir de G en tiempo polinomial, por lo que no se puede utilizar como reducción para demostrar la dureza NP. Pero tiene algunos usos teóricos.
Ver también
- Coincidencia tridimensional : un caso especial de coincidencia hipergráfica con hipergráficos uniformes tridimensionales.
- Cubierta de vértice en hipergráficos
- Hipergrafo bipartito
- Coincidencia de arco iris en hipergrafías
- Hipergrama de intervalo D : un hipergrama infinito en el que existe alguna relación entre el número de coincidencia y el de cobertura.
Referencias
- ^ a b c d e f g 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.
- ^ a b Aharoni, Ron; Kessler, Ofra (15 de octubre de 1990). "Sobre una posible extensión del teorema de Hall a hipergrafos bipartitos". Matemáticas discretas . 84 (3): 309–313. doi : 10.1016 / 0012-365X (90) 90136-6 . ISSN 0012-365X .
- ^ a b c d Füredi, Zoltán (1 de junio de 1981). "Grado máximo y emparejamientos fraccionarios en hipergráficos uniformes". Combinatorica . 1 (2): 155-162. doi : 10.1007 / BF02579271 . ISSN 1439-6912 . S2CID 10530732 .
- ^ Lovász, L. (1974). Berge, Claude; Ray-Chaudhuri, Dijen (eds.). "Teoremas de Minimax para hipergráficos". Seminario Hypergraph . Apuntes de clase en matemáticas. Berlín, Heidelberg: Springer. 411 : 111-126. doi : 10.1007 / BFb0066186 . ISBN 978-3-540-37803-7.
- ^ a b Nyman, Kathryn; Su, Francis Edward; Zerbib, Shira (2 de enero de 2020). "División justa con múltiples piezas" . Matemáticas aplicadas discretas . 283 : 115-122. arXiv : 1710.09477 . doi : 10.1016 / j.dam.2019.12.018 . ISSN 0166-218X . S2CID 119602376 .
- ^ Keevash, Peter; Mycroft, Richard (1 de enero de 2015). Una teoría geométrica para la coincidencia de hipergráficos . Memorias de la American Mathematical Society. 233 . Sociedad Matemática Estadounidense. ISBN 978-1-4704-0965-4.
- ^ Berge, CLAUDE (1 de enero de 1973), Srivastava, JAGDISH N. (ed.), "CAPÍTULO 2 - Hipergrafos equilibrados y algunas aplicaciones a la teoría de gráficos" , Una revisión de la teoría combinatoria , Holanda del Norte, págs. 15-23 , ISBN 978-0-7204-2262-7, consultado el 19 de junio de 2020
- ^ Berge, Claude; Vergnas, Michel LAS (1970). "Sur Un Theorems Du Type König Pour Hypergraphes". Anales de la Academia de Ciencias de Nueva York . 175 (1): 32–40. doi : 10.1111 / j.1749-6632.1970.tb56451.x . ISSN 1749-6632 .