stringtranslate.com

Coincidencia en hipergrafos

En teoría de grafos , un emparejamiento en un hipergrafo es un conjunto de hiperaristas , en el que cada dos hiperaristas son disjuntas . Es una extensión de la noción de emparejamiento en un grafo . [1] : 466–470  [2]

Definición

Recordemos que un hipergrafo H es un par ( V , E ) , donde V es un conjunto de vértices y E es un conjunto de subconjuntos de V llamados hiperaristas . Cada hiperarista puede contener uno o más vértices.

Una coincidencia en H es un subconjunto M de E , tal que cada dos hiperaristas e 1 y e 2 en M tienen una intersección vacía (no tienen ningún vértice en común).

El número de coincidencia de un hipergrafo H es el tamaño más grande de una coincidencia en H . A menudo se denota por ν( H ) . [1] : 466  [3]

Como ejemplo, sea V el conjunto {1,2,3,4,5,6,7}. Consideremos un hipergrafo 3-uniforme en V (un hipergrafo en el que cada hiperarista contiene exactamente 3 vértices). Sea H un hipergrafo 3-uniforme con 4 hiperaristas:

{ {1,2,3}, {1,4,5}, {4,5,6}, {2,3,6} }

Entonces H admite varias coincidencias 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 hiperaristas, al menos dos de ellas se intersecan, por lo que no hay coincidencia de tamaño 3. Por lo tanto, el número de coincidencia de H es 2.

Hipergrafo intersecante

Un hipergrafo H = ( V , E ) se denomina intersecante si cada dos hiperaristas en E tienen un vértice en común. Un hipergrafo H es intersecante si y solo si no tiene correspondencia con dos o más hiperaristas, si y solo si ν( H ) = 1 . [4]

La correspondencia en un gráfico como caso especial

Un grafo sin bucles propios es simplemente un hipergrafo 2-uniforme: cada arista puede considerarse como un conjunto de los dos vértices que conecta. Por ejemplo, este hipergrafo 2-uniforme representa un grafo 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 grafo es un conjunto M de aristas, de modo que cada dos aristas en M tienen una intersección vacía. Esto es equivalente a decir que no hay dos aristas en M adyacentes al mismo vértice; esta es exactamente la definición de una coincidencia en un grafo .

Coincidencia fraccionaria

Una coincidencia fraccionaria en un hipergrafo es una función que asigna una fracción en [0,1] a cada hiperarista, de modo que para cada vértice v en V , la suma de las fracciones de las hiperaristas que contienen a v es como máximo 1. Una coincidencia es un caso especial de una coincidencia fraccionaria en el que todas las fracciones son 0 o 1. El tamaño de una coincidencia fraccionaria es la suma de las fracciones de todas las hiperaristas.

El número de coincidencia fraccionaria de un hipergrafo H es el tamaño más grande de una coincidencia fraccionaria en H . A menudo se denota por ν *( H ) . [3]

Dado que una coincidencia es un caso especial de una coincidencia fraccionaria, para cada hipergrafo H :

Número coincidente ( H ) ≤ número coincidente fraccionario ( H )

Simbólicamente este principio está escrito:

En general, el número de coincidencia fraccionaria puede ser mayor que el número de coincidencia. Un teorema de Zoltán Füredi [4] proporciona límites superiores para la relación entre el número de coincidencia fraccionaria ( H ) y el número de coincidencia ( H ):


En particular, en un gráfico simple: [5]





En particular, en un grafo bipartito, ν *( H ) = ν ( H ) . Esto fue demostrado por András Gyárfás . [4]


Combinación perfecta

Una coincidencia M se denomina perfecta si cada vértice v en V está contenido en exactamente una hiperarista de M. Esta es la extensión natural de la noción de coincidencia perfecta en un grafo.

Una coincidencia fraccionaria M se llama perfecta si para cada vértice v en V , la suma de las fracciones de hiperaristas en M que contienen a v es exactamente 1.

Considérese un hipergrafo H en el que cada hiperarista contiene como máximo n vértices. Si H admite una correspondencia fraccionaria perfecta, entonces su número de correspondencia fraccionaria es al menos | V |n . Si cada hiperarista en H contiene exactamente n vértices, entonces su número de correspondencia fraccionaria es exactamente | V |n . [6] : sec.2  Esta es una generalización del hecho de que, en un grafo, el tamaño de una correspondencia perfecta es | V |2 .

Dado un conjunto V de vértices, una colección E de subconjuntos de V se llama equilibrada si el hipergrafo ( V , E ) admite una correspondencia 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á equilibrado, con la correspondencia fraccionaria perfecta {1/2, 1/2, 1/2, 1/2, 1}.

Existen varias condiciones suficientes para la existencia de un emparejamiento perfecto en un hipergrafo:

Familia de conjuntos equilibrados

Una familia de conjuntos E sobre un conjunto base V se denomina equilibrada (con respecto a V ) si el hipergrafo H = ( V , E ) admite una correspondencia fraccionaria perfecta. [6] : sec.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 existe 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 correspondencia de máxima cardinalidad en un hipergrafo, y por lo tanto calcular , es NP-difícil incluso para hipergrafos 3-uniformes (ver correspondencia tridimensional ). Esto contrasta con el caso de los grafos simples (2-uniformes) en los que el cálculo de una correspondencia de máxima cardinalidad se puede realizar en tiempo polinomial.

Combinación y cobertura

Una cobertura de vértices en un hipergrafo H = ( V , E ) es un subconjunto T de V , tal que cada hiperarista en E contiene al menos un vértice de T (también se denomina transversal o conjunto de impacto , y es equivalente a una cobertura de conjuntos ). Es una generalización de la noción de cobertura de vértices en un grafo.

El número de cobertura de vértice de un hipergrafo H es el tamaño más pequeño de una cobertura de vértice en H . A menudo se denota por τ ( H ) , [1] : 466  para transversal.

Una cobertura de vértices fraccionaria es una función que asigna un peso a cada vértice en V , de modo que para cada hiperarista e en E , la suma de las fracciones de vértices en e es al menos 1. Una cobertura de vértices es un caso especial de una cobertura de vértices fraccionaria en el que todos los pesos son 0 o 1. El tamaño de una cobertura de vértices fraccionaria es la suma de las fracciones de todos los vértices.

El número de cobertura de vértices fraccionarios de un hipergrafo H es el tamaño más pequeño de una cobertura de vértices fraccionarios en H . A menudo se denota por τ *( H ) .

Dado que una cobertura de vértices es un caso especial de una cobertura de vértices fraccionaria, para cada hipergrafo H :

número de cobertura de vértice fraccional ( H ) ≤ número de cobertura de vértice ( H ).

La dualidad de programación lineal implica que, para cada hipergrafo H :

número-coincidente-fraccional ( H ) = número-de-cobertura-de-vértice-fraccional ( H ).

Por lo tanto, para cada hipergrafo H : [4]

Si el tamaño de cada hiperarista en H es como máximo r , entonces la unión de todas las hiperaristas en una correspondencia máxima es una cobertura de vértices (si hubiera una hiperarista descubierta, podríamos haberla agregado a la correspondencia). Por lo tanto:

Esta desigualdad es estricta: la igualdad se cumple, por ejemplo, cuando V contiene rν ( H ) + r – 1 vértices y E contiene todos los subconjuntos de r vértices.

Sin embargo, en general τ *( H ) < rν ( H ) , ya que ν *( H ) < rν ( H ) ; ver correspondencia fraccional más arriba.

La conjetura de Ryser dice que, en cada hipergrafo r -partito y r -uniforme:

Se han demostrado algunos casos especiales de la conjetura; véase la conjetura de Ryser .

La propiedad del rey

Un hipergrafo tiene la propiedad de Kőnig si su número máximo de coincidencias es igual a su número mínimo de cobertura de vértices, es decir, si ν ( H ) = τ ( H ) . El teorema de Kőnig-Egerváry muestra que todo grafo bipartito tiene la propiedad de Kőnig. Para extender este teorema a los hipergrafos, necesitamos extender la noción de bipartididad a los hipergrafos. [1] : 468 

Una generalización natural es la siguiente. Un hipergrafo se llama 2-coloreable si sus vértices pueden ser 2-coloreados de modo que cada hiperarista (de tamaño al menos 2) contenga al menos un vértice de cada color. Un término alternativo es la Propiedad B . Un grafo simple es bipartito si es 2-coloreable. Sin embargo, hay hipergrafos 2-coloreables sin la propiedad de König. Por ejemplo, considere el hipergrafo con V = {1,2,3,4} con todos los tripletes E = { {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} }. Es 2-coloreable, por ejemplo, podemos colorear {1,2} de azul y {3,4} de blanco. Sin embargo, su número coincidente es 1 y su número de cobertura de vértices es 2.

Una generalización más fuerte es la siguiente. Dado un hipergrafo H = ( V , E ) y un subconjunto V' de V , la restricción de H a V' es el hipergrafo cuyos vértices son V , y para cada hiperarista e en E que interseca a V' , tiene una hiperarista e' que es la intersección de e y V' . Un hipergrafo se llama equilibrado si todas sus restricciones son esencialmente 2-coloreables , lo que significa que ignoramos las hiperaristas singleton en la restricción. [8] Un grafo simple es bipartito si y solo si está equilibrado.

Un grafo simple es bipartito si y solo si no tiene ciclos de longitud impar. De manera similar, un hipergrafo está balanceado si y solo si no tiene circuitos de longitud impar . Un circuito de longitud k en un hipergrafo es una secuencia alternada ( v 1 , e 1 , v 2 , e 2 , …, v k , e k , v k +1 = v 1 ) , donde las v i son vértices distintos y las e i son hiperaristas distintas, y cada hiperarista contiene el vértice a su izquierda y el vértice a su derecha. El circuito se llama desbalanceado si cada hiperarista no contiene otros vértices en el circuito. Claude Berge demostró que un hipergrafo está balanceado si y solo si no contiene un circuito desbalanceado de longitud impar. Todo hipergrafo balanceado tiene la propiedad de König. [9] [1] : 468–470 

Los siguientes son equivalentes: [1] : 470–471 

Combinación y embalaje

El problema del empaquetamiento de conjuntos es equivalente al de la correspondencia de hipergrafos.

Un empaquetamiento de vértices en un gráfico (simple) es un subconjunto P de sus vértices, tal 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 una correspondencia máxima en un hipergráfico: [1] : 467 

Véase también

Referencias

  1. ^ abcdefg Lovász, László ; Plummer, MD (1986), Teoría de correspondencias , Annals of Discrete Mathematics, vol. 29, Holanda Septentrional, ISBN 0-444-87916-1, Sr.  0859549
  2. ^ Berge, Claude (1973). Gráficos e hipergráficos . Ámsterdam: Holanda Septentrional.
  3. ^ ab 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.
  4. ^ abcd Füredi, Zoltán (1981-06-01). "Correspondencias de grado máximo y fraccionarias en hipergrafos uniformes". Combinatorica . 1 (2): 155–162. doi :10.1007/BF02579271. ISSN  1439-6912. S2CID  10530732.
  5. ^ Lovász, L. (1974). "Teoremas de minimax para hipergrafos". En Berge, Claude; Ray-Chaudhuri, Dijen (eds.). Hypergraph Seminar . Lecture Notes in Mathematics. Vol. 411. Berlín, Heidelberg: Springer. págs. 111–126. doi :10.1007/BFb0066186. ISBN 978-3-540-37803-7.
  6. ^ ab Nyman, Kathryn; Su, Francis Edward; Zerbib, Shira (2020-01-02). "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.
  7. ^ Keevash, Peter; Mycroft, Richard (1 de enero de 2015). Una teoría geométrica para la correspondencia de hipergrafos. Memorias de la American Mathematical Society. Vol. 233. American Mathematical Society. ISBN 978-1-4704-0965-4.
  8. ^ Berge, CLAUDE (1 de enero de 1973), Srivastava, JAGDISH N. (ed.), "CAPÍTULO 2 – Hipergrafos equilibrados y algunas aplicaciones a la teoría de grafos", A Survey of Combinatorial Theory , North-Holland, págs. 15-23, ISBN 978-0-7204-2262-7, consultado el 19 de junio de 2020
  9. ^ Berge, Claude; Vergnas, Michel LAS (1970). "Sobre un teorema del tipo rey para hipergrafías". Anales de la Academia de Ciencias de Nueva York . 175 (1): 32–40. Bibcode :1970NYASA.175...32B. doi :10.1111/j.1749-6632.1970.tb56451.x. ISSN  1749-6632. S2CID  84670737.