En teoría de grafos , un corte es una partición de los vértices de un grafo en dos subconjuntos disjuntos . [1] Cualquier corte determina un conjunto de cortes , el conjunto de aristas que tienen un punto final en cada subconjunto de la partición. Se dice que estos bordes cruzan el corte. En un gráfico conectado , cada conjunto de cortes determina un corte único y, en algunos casos, los cortes se identifican con sus conjuntos de cortes en lugar de con sus particiones de vértices.
En una red de flujo , un corte s–t es un corte que requiere que la fuente y el sumidero estén en subconjuntos diferentes, y su conjunto de cortes solo consta de bordes que van desde el lado de la fuente al lado del sumidero. La capacidad de un corte s–t se define como la suma de la capacidad de cada borde en el conjunto de cortes .
Un corte C = ( S , T ) es una partición de V de un gráfico G = ( V , E ) en dos subconjuntos S y T . El conjunto de cortes de un corte C = ( S , T ) es el conjunto {( u , v ) ∈ E | u ∈ S , v ∈ T } de aristas que tienen un punto final en S y el otro punto final en T . Si s y t son vértices especificados del gráfico G , entonces un corte s–t es un corte en el que s pertenece al conjunto S y t pertenece al conjunto T.
En un gráfico no ponderado y no dirigido, el tamaño o peso de un corte es el número de aristas que cruzan el corte. En un gráfico ponderado , el valor o peso se define por la suma de los pesos de los bordes que cruzan el corte.
Un bono es un conjunto de cortes que no tiene ningún otro conjunto de cortes como subconjunto propio.
Un corte es mínimo si el tamaño o peso del corte no es mayor que el tamaño de cualquier otro corte. La ilustración de la derecha muestra un corte mínimo: el tamaño de este corte es 2 y no hay ningún corte de tamaño 1 porque el gráfico no tiene puentes .
El teorema de flujo máximo y corte mínimo demuestra que el flujo máximo de la red y la suma de los pesos de los bordes de corte de cualquier corte mínimo que separe la fuente y el sumidero son iguales. Existen métodos de tiempo polinomial para resolver el problema de corte mínimo, en particular el algoritmo de Edmonds-Karp . [2]
Un corte es máximo si el tamaño del corte no es menor que el tamaño de cualquier otro corte. La ilustración de la derecha muestra un corte máximo: el tamaño del corte es igual a 5 y no hay ningún corte de tamaño 6, o | mi | (el número de aristas), porque el gráfico no es bipartito (hay un ciclo impar ).
En general, encontrar un corte máximo es computacionalmente difícil. [3] El problema de corte máximo es uno de los 21 problemas NP-completos de Karp . [4] El problema de corte máximo también es APX-duro , lo que significa que no existe un esquema de aproximación en tiempo polinomial para él a menos que P = NP. [5] Sin embargo, se puede aproximar dentro de una relación de aproximación constante utilizando programación semidefinida . [6]
Tenga en cuenta que el corte mínimo y el corte máximo no son problemas duales en el sentido de la programación lineal , aunque uno pasa de un problema a otro cambiando min a max en la función objetivo . El problema del flujo máximo es el doble del problema del corte mínimo. [7]
El problema del corte más escaso consiste en biparticionar los vértices para minimizar la relación entre el número de aristas a lo largo del corte dividido por el número de vértices en la mitad más pequeña de la partición. Esta función objetivo favorece soluciones que son dispersas (pocas aristas cruzan el corte) y equilibradas (cerca de una bisección). Se sabe que el problema es NP-difícil y el algoritmo de aproximación más conocido es una aproximación debida a Arora, Rao y Vazirani (2009). [8]
La familia de todos los conjuntos de corte de un gráfico no dirigido se conoce como espacio de corte del gráfico. Forma un espacio vectorial sobre el campo finito de dos elementos de la aritmética módulo dos, con la diferencia simétrica de dos conjuntos de corte como operación de suma vectorial, y es el complemento ortogonal del espacio de ciclo . [9] [10] Si a los bordes del gráfico se les asignan pesos positivos, la base de peso mínimo del espacio de corte puede describirse mediante un árbol en el mismo conjunto de vértices que el gráfico, llamado árbol de Gomory-Hu . [11] Cada borde de este árbol está asociado con un enlace en el gráfico original, y el corte mínimo entre dos nodos s y t es el enlace de peso mínimo entre los asociados con la ruta de s a t en el árbol.
Un corte es una partición de los nodos de un gráfico en dos conjuntos. El tamaño de corte es la suma de los pesos de los bordes "entre" los dos conjuntos de nodos.
