Politopo coincidente

En teoría de grafos , el politopo coincidente de un grafo dado es un objeto geométrico que representa las posibles coincidencias en el grafo . Es un politopo convexo, cada uno de cuyos vértices corresponde a una coincidencia. Tiene gran importancia teórica en la teoría de coincidencias. ^{[1] : 273–285}

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 1 por 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 A _G , es una matriz 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 a la arista e , y 0 en caso contrario.

A continuación se muestran tres ejemplos de matrices de incidencia: el gráfico triangular (un ciclo de longitud 3), un gráfico cuadrado (un ciclo de longitud 4) y el gráfico completo en 4 vértices.

${\displaystyle {\begin{pmatrix}1&1&0\\1&0&1\\0&1&1\end{pmatrix}}~,~{\begin{pmatrix}1&1&0&0\\0&1&1&0\\0&0&1&1\\1&0&0&1\\\end{pmatrix}}~,~{\begin{pmatrix}1&1&0&0&1&0\\0&1&1&0&0&1\\0&0&1&1&1&1&0\\1&0&0&1&0&1\\\end{pmatrix}}}$

Para cada subconjunto F de aristas, el producto escalar 1 _E(v) · 1 _F representa la cantidad de aristas en F que son adyacentes a v . Por lo tanto, las siguientes afirmaciones son equivalentes:

• Un subconjunto F de aristas representa una correspondencia en G;
• Para cada nodo v en V : 1 _E(v) · 1 _F ≤ 1.
• Una _G · 1 _F ≤ 1 _V .

La cardinalidad de un conjunto F de aristas es el producto escalar 1 _E · 1 _{F .} Por lo tanto, una correspondencia de cardinalidad máxima en G viene dada por el siguiente programa lineal entero :

Maximizar 1 _E · x

Sujeto a: x en {0,1} ^m

__________ Un _G · x ≤ 1 _V .

El politopo coincidente fraccionario 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 entero:

Maximizar 1 _E · x

Sujeto a: x ≥ 0 _E

__________ Un _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 fraccionaria . Por ejemplo, en el gráfico del triángulo hay 3 aristas y el programa lineal correspondiente tiene las siguientes 6 restricciones:

Maximizar x ₁ + x ₂ + x ₃

Sujeto a: x ₁ ≥0, x ₂ ≥0, x ₃ ≥0 _.

__________ x ₁ + x ₂ ≤1 , x ₂ + x ₃ ≤1, x ₃ + x ₁ ≤1.

Este conjunto de desigualdades representa un politopo en R ³ , 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 la coincidencia trivial (vacía). Los siguientes tres vértices (1,0,0), (0,1,0), (0,0,1) representan las tres coincidencias de tamaño 1. El quinto vértice (1/2,1/2,1/2) no representa una coincidencia, sino una coincidencia fraccionaria en la que cada arista está "mitad dentro, mitad fuera". Nótese que este es el mayor emparejamiento fraccionario en este gráfico: su peso es 3/2, en contraste con los tres emparejamientos integrales cuyo tamaño es solo 1.

Como otro ejemplo, en el ciclo de 4 hay 4 aristas. El LP correspondiente tiene restricciones 4+4=8. El FMP es un politopo convexo en R ⁴ . 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. Nótese que en este caso todas las esquinas tienen coordenadas enteras.

El politopo coincidente integral (usualmente llamado simplemente politopo coincidente ) de un grafo G , denotado MP( G ), es un politopo cuyos vértices son los vectores de incidencia de los coincidentes integrales en G.

MP( G ) siempre está contenido en FMP( G ). En los ejemplos anteriores:

• El MP del grafo triangular está estrictamente contenido en su FMP, ya que el MP no contiene el vértice no integral (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 integrales.

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 todos los vértices de FMP( G ) tienen solo coordenadas enteras.

Este teorema se puede demostrar de varias maneras.

Cuando G es bipartita, su matriz de incidencia A _G es totalmente unimodular - cada submatriz cuadrada de ella tiene determinante 0, +1 o -1. La prueba es 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 A _G - cada elemento en ella es 0 o 1. Para k > 1 hay varios casos:

• Si K tiene una columna que consta únicamente 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 multiplicado por un determinante de una matriz ( k  − 1) por ( k  − 1), que por el supuesto de inducción es 0 o +1 o −1.
• De lo contrario, cada columna de K tiene dos 1. Como el gráfico es bipartito, las filas se pueden dividir en dos subconjuntos, de modo que en cada columna, un 1 esté en el subconjunto superior y el otro 1 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.

A modo de ejemplo, en el ciclo 4 (que es bipartito), det  A _G = 1. Por el contrario, en el ciclo 3 (que no es bipartito), det  A _G  = 2.

Cada vértice de FMP( G ) satisface un conjunto de m inecuaciones linealmente independientes con igualdad. Por lo tanto, para calcular las coordenadas de los vértices tenemos que resolver un sistema de ecuaciones definido por una submatriz cuadrada de A _G . Por 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 lo tanto, la solución es un vector entero. Por lo tanto, todas las coordenadas de los vértices son números enteros.

Por las restricciones n "menores que uno", las coordenadas de las esquinas son 0 o 1; por lo tanto, cada esquina es el vector de incidencia de una correspondencia integral en G. Por lo tanto, FMP( G ) = MP( G ).

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 ) están 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 factores 2-conectado ).

El politopo de coincidencia perfecta de un grafo G , denotado PMP( G ), es un politopo cuyos vértices son los vectores de incidencia de las coincidencias perfectas 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:

1E · x = n /2 _.

Edmonds ^[3] demostró que, para cada gráfico G, PMP(G) puede describirse mediante las siguientes restricciones:

1 _E(v) · x = 1 para todo v en V (-- exactamente un borde adyacente a v está en la correspondencia)

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 grafos que tienen 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}

• Politopo coincidente estable

• El politopo correspondiente, de Michael Goemans
• El politopo correspondiente, de Jan Vondrak
• El politopo correspondiente, de Vincent Jost