En teoría de grafos , el politopo coincidente de un gráfico dado es un objeto geométrico que representa las posibles coincidencias en el gráfico . Es un politopo convexo cada una de cuyas esquinas corresponde a un emparejamiento. Tiene una gran importancia teórica en la teoría del emparejamiento. [1] : 273–285
Preliminares
Vectores y matrices de incidencia
Sea G = ( V , E ) una gráfica con n = | V | nodos ym = | E | bordes.
Para cada subconjunto U de vértices, su vector de incidencia 1 U es un vector de tamaño n , en el que el elemento v es 1 si el nodo v está en U y 0 en caso contrario. De manera similar, para cada subconjunto F de aristas, su vector de incidencia 1 F es un vector de tamaño m , en el que el elemento e es 1 si la arista e está en F y 0 en caso contrario.
Para cada nodo v en V , el conjunto de aristas en E adyacentes av se denota por E ( v ). Por lo tanto, el vector 1 E (V) es un vector de 1 por m en el que el elemento e es 1 si el borde e es adyacente ay 0 en caso contrario. La matriz de incidencia del gráfico, denotada por A G , es una matriz de n por m en la que cada fila v es el vector de incidencia 1 E (V) . En otras palabras, cada elemento v , e en la matriz es 1 si el nodo v es adyacente al borde e , y 0 en caso contrario.
A continuación se muestran tres ejemplos de matrices de incidencia: el gráfico de triángulo (un ciclo de longitud 3), un gráfico cuadrado (un ciclo de longitud 4) y el gráfico completo en 4 vértices.
Programas lineales
Para cada subconjunto F de aristas, el producto escalar 1 E (v) · 1 F representa el número de aristas en F que son adyacentes a v . Por lo tanto, las siguientes declaraciones son equivalentes:
- Un subconjunto F de aristas representa una coincidencia en G;
- Para cada nodo v en V : 1 E (v) · 1 F ≤ 1.
- A G · 1 F ≤ 1 V .
La cardinalidad de un conjunto F de bordes es el dot producto 1 E · 1 F . Por lo tanto, una coincidencia máxima de cardinalidad en G viene dada por el siguiente programa lineal de enteros :
Maximizar 1 E · x
Sujeto a: x en {0,1} m
__________ A G · x ≤ 1 V .
Politopo coincidente fraccional
El politopo de coincidencia fraccional de un gráfico G , denominado FMP ( G ), es el politopo definido por la relajación del programa lineal anterior, en el que cada x puede ser una fracción y no solo un número entero:
Maximizar 1 E · x
Sujeto a: x ≥ 0 E
__________ A G · x ≤ 1 V .
Este es un programa lineal . Tiene m restricciones de "al menos 0" y n restricciones de "menos de uno". El conjunto de sus soluciones factibles es un politopo convexo . Cada punto de este politopo es una coincidencia fraccional . Por ejemplo, en el gráfico de triángulo hay 3 aristas y el programa lineal correspondiente tiene las siguientes 6 restricciones:
Maximizar x 1 + x 2 + x 3
Sujeto a: x 1 ≥0, x 2 ≥0, x 3 ≥0 .
__________ x 1 + x 2 ≤1 , x 2 + x 3 ≤1, x 3 + x 1 ≤1.
Este conjunto de desigualdades representa un politopo en R 3 , el espacio euclidiano tridimensional.
El politopo tiene cinco esquinas ( puntos extremos ). Estos son los puntos que logran igualdad en 3 de las 6 desigualdades definitorias. Las esquinas son (0,0,0), (1,0,0), (0,1,0), (0,0,1) y (1 / 2,1 / 2,1 / 2). [2] La primera esquina (0,0,0) representa la coincidencia trivial (vacía). Las siguientes tres esquinas (1,0,0), (0,1,0), (0,0,1) representan las tres combinaciones de tamaño 1. La quinta esquina (1 / 2,1 / 2,1 / 2 ) no representa una coincidencia; representa una coincidencia fraccional en la que cada borde está "mitad adentro, mitad afuera". Tenga en cuenta que esta es la coincidencia fraccional más grande en este gráfico: su peso es 3/2, en contraste con las tres coincidencias integrales cuyo tamaño es solo 1.
Como otro ejemplo, en el ciclo de 4 hay 4 aristas. El LP correspondiente tiene 4 + 4 = 8 restricciones. El FMP es un politopo convexo en R 4 . Las esquinas de este politopo son (0,0,0,0), (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0 , 0,1), (1,0,1,0), (0,1,0,1). Cada una de las últimas 2 esquinas representa una coincidencia de tamaño 2, que es una coincidencia máxima. Tenga en cuenta que en este caso todas las esquinas tienen coordenadas enteras.
Politopo a juego integral
El politopo de coincidencia integral (generalmente llamado solo politopo de coincidencia ) de un gráfico G , denotado MP ( G ), es un politopo cuyas esquinas son los vectores de incidencia de las coincidencias integrales en G.
MP ( G ) siempre está contenido en FMP ( G ). En los ejemplos anteriores:
- El MP del gráfico triangular está estrictamente contenido en su FMP, ya que el MP no contiene la esquina no integral (1/2, 1/2, 1/2).
- El MP del gráfico de 4 ciclos es idéntico a su FMP, ya que todas las esquinas del FMP son integrales.
Los politopos coincidentes en un gráfico bipartito
El ejemplo anterior es un caso especial del siguiente teorema general: [1] : 274
G es un gráfico bipartito si-y-solo-si MP ( G ) = FMP ( G ) si-y-solo-si todas las esquinas de FMP ( G ) solo tienen coordenadas enteras.
Este teorema se puede demostrar de varias formas.
Prueba usando matrices
Cuando G es bipartita, su matriz de incidencia A G es totalmente unimodular - cada submatriz cuadrada tiene determinante 0, +1 o 1. La prueba es por inducción en k - el tamaño de la submatriz (que denotamos por K ). La base k = 1 se deriva de la definición de A G : cada elemento en él es 0 o 1. Para k > 1 hay varios casos:
- Si K tiene una columna que consta solo de ceros, entonces det K = 0.
- Si K tiene una columna con un solo 1, entonces det K se puede expandir alrededor de esta columna y es igual a +1 o -1 veces un determinante de una matriz ( k - 1) por ( k - 1), que por la inducción el supuesto es 0 o +1 o −1.
- De lo contrario, cada columna de K tiene dos unos. Dado que el gráfico es bipartito, las filas se pueden dividir en dos subconjuntos, de modo que en cada columna, uno 1 está en el subconjunto superior y el otro 1 está en el subconjunto inferior. Esto significa que la suma del subconjunto superior y la suma del subconjunto inferior son ambas iguales a 1 E menos un vector de | E | unos. Esto significa que las filas de K son linealmente dependientes, por lo que det K = 0.
Como ejemplo, en el ciclo de 4 (que es bipartito), det A G = 1. En contraste, en el ciclo de 3 (que no es bipartito), det A G = 2.
Cada esquina de FMP ( G ) satisface un conjunto de m desigualdades linealmente independientes con igualdad. Por lo tanto, para calcular las coordenadas de la esquina tenemos que resolver un sistema de ecuaciones definidas por una submatriz cuadrada de A G . Según la regla de Cramer , la solución es un número racional en el que el denominador es el determinante de esta submatriz. Este determinante debe ser +1 o −1; por tanto, la solución es un vector entero. Por lo tanto, todas las coordenadas de las esquinas son números enteros.
Por las n restricciones "menos de uno", las coordenadas de las esquinas son 0 o 1; por lo tanto cada esquina es el vector de incidencia de un juego integral en G . Por tanto FMP ( G ) = MP ( G ).
Las facetas del politopo correspondiente.
Una faceta de un politopo es el conjunto de sus puntos que satisfacen una desigualdad definitoria esencial del politopo con igualdad. Si el politopo es d- dimensional, entonces sus facetas son ( d - 1) -dimensionales. Para cualquier gráfico G , las facetas de MP ( G ) vienen dadas por las siguientes desigualdades: [1] : 275-279
- x ≥ 0 E
- 1 E ( v ) · x ≤ 1 (donde v es un vértice no aislado tal que, si v tiene solo un vecino u , entonces { u , v } es un componente conectado de G, y si v tiene exactamente dos vecinos, entonces no son adyacentes).
- 1 E ( S ) · x ≤ (| S | - 1) / 2 (donde S abarca un subgrafo crítico de 2 conectados ).
Politopo a juego perfecto
El politopo de emparejamiento perfecto de un gráfico G , denotado PMP ( G ), es un politopo cuyas esquinas son los vectores de incidencia de los emparejamientos perfectos integrales en G. [1] : 274 Obviamente, PMP ( G ) está contenido en MP ( G ) ; De hecho, PMP (G) es la cara de MP ( G ) determinada por la igualdad:
1 E · x = n / 2.
Ver también
Referencias
- ^ a b c d 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
- ^ "1 Politopo a juego bipartito, Politopo a juego estable x1 x2 x3 Conferencia 10: Descarga de ppt de febrero" . slideplayer.com . Consultado el 17 de julio de 2020 .