Hispanopedia WikiEn teoría de grafos , el politopo de emparejamiento de un grafo dado es un objeto geométrico que representa los posibles emparejamientos en el grafo . Es un politopo convexo cuyos vértices corresponden a cada uno de los emparejamientos. Tiene gran importancia teórica en la teoría de emparejamientos. [ 1 ] : 273–285
Preliminares
Vectores y matrices de incidencia
Sea G = ( V , E ) un grafo con n = | V | nodos y m = | E | aristas.
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 a v se denota por E ( v ). Por lo tanto, cada vector 1 E(v) es un vector de 1 × m en el que el elemento e es 1 si la arista e es adyacente a v, y 0 en caso contrario. La matriz de incidencia del grafo, denotada por AG , es una matriz de n × 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 a la arista e , y 0 en caso contrario.
A continuación se muestran tres ejemplos de matrices de incidencia: el grafo triangular (un ciclo de longitud 3), un grafo cuadrado (un ciclo de longitud 4) y el grafo completo de 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 afirmaciones son equivalentes:
- Un subconjunto F de aristas representa un emparejamiento 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 aristas es el producto escalar 1 E · 1 F . Por lo tanto, un emparejamiento de cardinalidad máxima en G viene dado por el siguiente programa lineal entero :
Maximizar 1 E · x
Sujeto a: x en {0,1} m
__________ A G · x ≤ 1 V .
Politopo de coincidencia fraccionaria
El politopo de emparejamiento fraccional de un grafo G , denotado 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 "menor que uno". El conjunto de sus soluciones factibles es un politopo convexo . Cada punto de este politopo es un emparejamiento fraccional . Por ejemplo, en el grafo triangular 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 vértices ( puntos extremos ). Estos son los puntos que alcanzan la igualdad en 3 de las 6 desigualdades definitorias. Los vértices son (0,0,0), (1,0,0), (0,1,0), (0,0,1) y (1/2,1/2,1/2). [ 2 ] El primer vértice (0,0,0) representa el emparejamiento trivial (vacío). Los siguientes tres vértices (1,0,0), (0,1,0), (0,0,1) representan los tres emparejamientos de tamaño 1. El quinto vértice (1/2,1/2,1/2) no representa un emparejamiento, sino un emparejamiento fraccional en el que cada arista es "mitad dentro, mitad fuera". Nótese que este es el emparejamiento fraccional más grande en este grafo: su peso es 3/2, en contraste con los tres emparejamientos enteros cuyo tamaño es solo 1.
Como otro ejemplo, en el ciclo 4 hay 4 aristas. El LP correspondiente tiene 4+4=8 restricciones. El FMP es un politopo convexo en R 4 . Los vértices 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 uno de los últimos 2 vértices representa un emparejamiento de tamaño 2, que es un emparejamiento máximo. Nótese que en este caso todos los vértices tienen coordenadas enteras.
politopo de coincidencia integral
El politopo de emparejamiento integral (generalmente llamado simplemente politopo de emparejamiento ) de un grafo G , denotado MP( G ), es un politopo cuyos vértices son los vectores de incidencia de los emparejamientos 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 entera (1/2, 1/2, 1/2).
- El MP del gráfico de 4 ciclos es idéntico a su FMP, ya que todos los vértices del FMP son enteros.
Los politopos coincidentes en un grafo bipartito
El ejemplo anterior es un caso especial del siguiente teorema general: [ 1 ] : 274
G es un grafo bipartito si y solo si MP( G ) = FMP( G ) si y solo si todos los vértices de FMP( G ) tienen solo coordenadas enteras.
Este teorema se puede demostrar de varias maneras.
Demostración mediante matrices
Cuando G es bipartita, su matriz de incidencia AG es totalmente unimodular : cada submatriz cuadrada de ella tiene determinante 0, +1 o −1. La demostración se realiza por inducción sobre k , el tamaño de la submatriz (que denotamos por K ). La base k = 1 se deduce de la definición de AG : cada elemento de ella es 0 o 1. Para k > 1 existen 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 de ( k − 1) por ( k − 1), que por la suposición de inducción es 0 o +1 o −1.
- De lo contrario, cada columna de K tiene dos 1. Dado que el grafo es bipartito, las filas se pueden dividir en dos subconjuntos, de modo que en cada columna, un 1 se encuentra en el subconjunto superior y el otro en el inferior. Esto significa que la suma del subconjunto superior y la suma del subconjunto inferior son iguales a 1 E menos un vector de | E | unos. Esto implica que las filas de K son linealmente dependientes, por lo que det K = 0.
Como ejemplo, en el ciclo 4 (que es bipartito), det A G = 1. En cambio, en el ciclo 3 (que no es bipartito), det A G = 2.
Cada vértice de FMP( G ) satisface un conjunto de m desigualdades linealmente independientes con igualdad. Por lo tanto, para calcular las coordenadas de los vértices, debemos resolver un sistema de ecuaciones definido por una submatriz cuadrada de AG . Según la regla de Cramer , la solución es un número racional cuyo denominador es el determinante de esta submatriz. Este determinante debe ser +1 o −1; por lo tanto, la solución es un vector entero. En consecuencia, todas las coordenadas de los vértices son números enteros.
Por las n restricciones "menores que uno", las coordenadas de las esquinas son 0 o 1; por lo tanto, cada esquina es el vector de incidencia de un emparejamiento integral en G. Por lo 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 esencial definitoria del politopo con igualdad. Si el politopo es d- dimensional, entonces sus facetas son ( d - 1)-dimensionales. Para cualquier grafo 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 conexo 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 factor 2-conexo ).
politopo de coincidencia perfecta
El politopo de emparejamiento perfecto de un grafo G , denotado PMP( G ), es un politopo cuyos vértices 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.
Edmonds [ 3 ] demostró que, para cada grafo G, PMP(G) puede describirse mediante las siguientes restricciones:
1 E(v) · x = 1 para todo v en V (-- exactamente una arista adyacente a v está en el emparejamiento)
1 E(W) · x ≥ 1 para cada subconjunto W de V con |W| impar (-- al menos una arista debe conectar W con V\W). Estas restricciones se denominan restricciones de corte impares .
x ≥ 0 E
Utilizando esta caracterización y el lema de Farkas , es posible obtener una buena caracterización de los grafos que poseen un emparejamiento perfecto. [ 4 ] : 206 Al resolver problemas algorítmicos en conjuntos convexos , se puede encontrar un emparejamiento perfecto de peso mínimo. [ 4 ] : 206-208
Véase también
Referencias
- 1 2 3 4 Lovász, László ; Plummer, MD (1986), Teoría de correspondencias , Annals of Discrete Mathematics, vol. 29, Holanda Septentrional, ISBN 0-444-87916-1, MR 0859549
- ↑ "1 Politopo de emparejamiento bipartito, politopo de emparejamiento estable x1 x2 x3 Lección 10: descarga de ppt de febrero" . slideplayer.com . Consultado el 17 de julio de 2020 .
- ↑ Edmonds, Jack (enero de 1965). "Ajuste máximo y un poliedro con vértices 0,1" (PDF) . Journal of Research of the National Bureau of Standards, Section B. 69B ( 1 y 2): 125. doi : 10.6028/jres.069B.013 . ISSN 0022-4340 .
- 1 2 Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria , Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi : 10.1007/978-3-642-78240-4 , ISBN 978-3-642-78242-8, MR 1261419
Enlaces externos
- El politopo correspondiente, por Michael Goemans
- El politopo correspondiente, por Jan Vondrak
- El politopo correspondiente, por Vincent Jost
- Emparejamiento (teoría de grafos)
- politopos