En la disciplina matemática de la teoría de grafos , un conjunto de aristas coincidentes o independientes en un gráfico no dirigido es un conjunto de aristas sin vértices comunes . [1] En otras palabras, un subconjunto de aristas es una coincidencia si cada vértice aparece como máximo en una arista de esa coincidencia. Encontrar una coincidencia en un gráfico bipartito puede tratarse como un problema de flujo de red .
Dado un gráfico G = ( V , E ), una M coincidente en G es un conjunto de aristas no adyacentes por pares, ninguna de las cuales es bucles ; es decir, no hay dos aristas que compartan vértices comunes.
Un vértice coincide (o está saturado ) si es un punto final de una de las aristas en la coincidencia. De lo contrario, el vértice no coincide (o no está saturado ).
Una coincidencia máxima es una coincidencia M de un gráfico G que no es un subconjunto de ninguna otra coincidencia. Una M coincidente de un gráfico G es máxima si cada arista en G tiene una intersección no vacía con al menos una arista en M . La siguiente figura muestra ejemplos de coincidencias máximas (rojo) en tres gráficos.
Una coincidencia máxima (también conocida como coincidencia de cardinalidad máxima [2] ) es una coincidencia que contiene el mayor número posible de aristas. Puede haber muchas coincidencias máximas. El número coincidente de un gráfico G es el tamaño de una coincidencia máxima. Cada coincidencia máxima es máxima, pero no toda coincidencia máxima es una coincidencia máxima. La siguiente figura muestra ejemplos de coincidencias máximas en los mismos tres gráficos.
Una coincidencia perfecta es una coincidencia que coincide con todos los vértices del gráfico. Es decir, una coincidencia es perfecta si cada vértice del gráfico incide en un borde de la coincidencia. Una combinación es perfecta si . Todo emparejamiento perfecto es máximo y, por tanto, máximo. En alguna literatura se utiliza el término emparejamiento completo . En la figura anterior, sólo la parte (b) muestra una coincidencia perfecta. Una combinación perfecta también es una funda de borde de tamaño mínimo . Por lo tanto, el tamaño de una coincidencia máxima no es mayor que el tamaño de una cobertura de borde mínima: . Un gráfico solo puede contener una coincidencia perfecta cuando el gráfico tiene un número par de vértices.
Una coincidencia casi perfecta es aquella en la que exactamente un vértice no coincide. Claramente, un gráfico sólo puede contener una coincidencia casi perfecta cuando el gráfico tiene un número impar de vértices, y las coincidencias casi perfectas son coincidencias máximas. En la figura anterior, la parte (c) muestra una coincidencia casi perfecta. Si cada vértice no tiene una coincidencia casi perfecta, entonces el gráfico se llama factor crítico .
Dada una coincidencia M , un camino alterno es un camino que comienza con un vértice no coincidente [3] y cuyas aristas pertenecen alternativamente a la coincidencia y no a la coincidencia. Una ruta aumentada es una ruta alterna que comienza y termina en vértices libres (inigualables). El lema de Berge establece que una coincidencia M es máxima si y sólo si no hay un camino creciente con respecto a M.
Una coincidencia inducida es una coincidencia que es el conjunto de bordes de un subgrafo inducido . [4]
En cualquier gráfico sin vértices aislados, la suma del número coincidente y el número de cobertura del borde es igual al número de vértices. [5] Si hay una coincidencia perfecta, entonces tanto el número coincidente como el número de cubierta de borde son | V | / 2 .
Si A y B son dos coincidencias máximas, entonces | Un | ≤ 2| B | y | B | ≤ 2| Un | . Para ver esto, observe que cada arista en B \ A puede ser adyacente a como máximo dos aristas en A \ B porque A es una coincidencia; además, cada arista en A \ B es adyacente a una arista en B \ A por maximalidad de B , por lo tanto
Además deducimos que
En particular, esto muestra que cualquier coincidencia máxima es una aproximación 2 de una coincidencia máxima y también una aproximación 2 de una coincidencia máxima mínima. Esta desigualdad es estrecha: por ejemplo, si G es un camino con 3 aristas y 4 vértices, el tamaño de una coincidencia mínima máxima es 1 y el tamaño de una coincidencia máxima es 2.
Hassani Monfared y Mallik dan una caracterización espectral del número coincidente de un gráfico de la siguiente manera: Sea un gráfico en vértices y sean números puramente imaginarios distintos de cero donde . Entonces, el número coincidente de es si y solo si (a) hay una matriz simétrica sesgada real con gráfica y valores propios y ceros, y (b) todas las matrices simétricas sesgadas reales con gráfica tienen como máximo valores propios distintos de cero . [6] Tenga en cuenta que el gráfico (simple) de una matriz de orden simétrica real o simétrica sesgada tiene vértices y aristas dadas por las entradas fuera de la diagonal no nulas de .
Una función generadora del número de k coincidencias de aristas en un gráfico se llama polinomio coincidente. Sea G un gráfico y m k el número de k coincidencias de aristas. Un polinomio coincidente de G es
Otra definición da el polinomio coincidente como
donde n es el número de vértices del gráfico. Cada tipo tiene sus usos; para obtener más información, consulte el artículo sobre cómo hacer coincidir polinomios.
Un problema fundamental en la optimización combinatoria es encontrar una coincidencia máxima . Este problema tiene varios algoritmos para diferentes clases de gráficos.
En un gráfico bipartito no ponderado , el problema de optimización es encontrar una coincidencia de cardinalidad máxima . El problema se resuelve mediante el algoritmo Hopcroft-Karp en el tiempo O ( √ V E ) , y existen algoritmos aleatorios , algoritmos de aproximación y algoritmos más eficientes para clases especiales de gráficos, como gráficos planos bipartitos , como se describe en el artículo principal. .
En un gráfico bipartito ponderado , el problema de optimización es encontrar una coincidencia de peso máximo; Un problema dual es encontrar una coincidencia de peso mínimo. Este problema a menudo se denomina coincidencia bipartita ponderada máxima o problema de asignación . El algoritmo húngaro resuelve el problema de asignación y fue uno de los inicios de los algoritmos de optimización combinatoria. Utiliza una búsqueda de ruta más corta modificada en el algoritmo de ruta aumentada. Si se utiliza el algoritmo Bellman-Ford para este paso, el tiempo de ejecución del algoritmo húngaro se vuelve , o el costo del borde se puede cambiar con el potencial de lograr el tiempo de ejecución con el algoritmo de Dijkstra y el montón de Fibonacci . [7]
En un gráfico ponderado no bipartito , el problema de la coincidencia de peso máximo se puede resolver a tiempo utilizando el algoritmo de flor de Edmonds .
Se puede encontrar una coincidencia máxima con un algoritmo codicioso simple . Una coincidencia máxima también es una coincidencia máxima y, por tanto, es posible encontrar una coincidencia máxima más grande en tiempo polinomial. Sin embargo, no se conoce ningún algoritmo de tiempo polinomial que encuentre una coincidencia máxima mínima , es decir, una coincidencia máxima que contenga el menor número posible de aristas.
Una coincidencia máxima con k aristas es un conjunto de aristas dominantes con k aristas. Por el contrario, si se nos da un conjunto dominante de aristas mínimas con k aristas, podemos construir una coincidencia máxima con k aristas en tiempo polinómico. Por lo tanto, el problema de encontrar una coincidencia máxima mínima es esencialmente igual al problema de encontrar un conjunto dominante de borde mínimo. [8] Se sabe que estos dos problemas de optimización son NP-difíciles ; las versiones de decisión de estos problemas son ejemplos clásicos de problemas NP-completos . [9] Ambos problemas se pueden aproximar dentro del factor 2 en tiempo polinómico: simplemente encuentre una coincidencia máxima arbitraria M. [10]
El número de coincidencias en un gráfico se conoce como índice de Hosoya del gráfico. Es #P-completo calcular esta cantidad, incluso para gráficas bipartitas. [11] También es #P-completo contar coincidencias perfectas , incluso en gráficos bipartitos , porque calcular el permanente de una matriz arbitraria 0–1 (otro problema #P-completo) es lo mismo que calcular el número de coincidencias perfectas en el gráfico bipartito que tiene la matriz dada como matriz de biaadyacencia . Sin embargo, existe un esquema de aproximación aleatoria en tiempo totalmente polinomial para contar el número de coincidencias bipartitas. [12] Un teorema notable de Kasteleyn establece que el número de coincidencias perfectas en un gráfico plano se puede calcular exactamente en tiempo polinómico mediante el algoritmo FKT .
El número de coincidencias perfectas en un gráfico completo K n (con n par) viene dado por el factorial doble ( n − 1)!!. [13] Los números de coincidencias en gráficos completos, sin obligar a que las coincidencias sean perfectas, vienen dados por los números de teléfono . [14]
El número de coincidencias perfectas en un gráfico también se conoce como hafniano de su matriz de adyacencia .
Uno de los problemas básicos en la teoría de coincidencias es encontrar en un gráfico dado todas las aristas que pueden extenderse hasta una coincidencia máxima en el gráfico (dichas aristas se denominan aristas de máxima coincidencia o aristas permitidas ). Los algoritmos para este problema incluyen:
El problema de desarrollar un algoritmo en línea para la comparación fue considerado por primera vez por Richard M. Karp , Umesh Vazirani y Vijay Vazirani en 1990. [18]
En la configuración en línea, los nodos de un lado del gráfico bipartito llegan uno a la vez y deben coincidir inmediatamente con el otro lado del gráfico o descartarse. Esta es una generalización natural del problema de la secretaria y tiene aplicaciones en las subastas de anuncios en línea. El mejor algoritmo en línea, para el caso de maximización no ponderada con un modelo de llegada aleatoria, alcanza una relación competitiva de 0,696 . [19]
El teorema de Kőnig establece que, en gráficos bipartitos, la coincidencia máxima es igual en tamaño a la cobertura mínima de vértices . A través de este resultado, los problemas de cobertura de vértice mínimo, conjunto independiente máximo y biclique de vértice máximo se pueden resolver en tiempo polinomial para gráficos bipartitos.
El teorema del matrimonio de Hall proporciona una caracterización de gráficos bipartitos que tienen una coincidencia perfecta y el teorema de Tutte proporciona una caracterización de gráficos arbitrarios.
Cada nodo incide como máximo en un borde de la coincidencia. Se dice que las aristas son independientes.
{{citation}}
: Mantenimiento CS1: varios nombres: lista de autores ( enlace )