Corte (teoría de grafos)

En teoría de grafos, un corte es una partición de los vértices de un gráfico en dos subconjuntos disjuntos. Cualquier corte determina un conjunto de cortes, el conjunto de bordes 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 diferentes subconjuntos, y su conjunto de cortes solo consta de bordes que van desde el lado de la fuente hasta el 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.

Definición

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 corte de un corte C = (S, T) es el conjunto {(u, v) ∈ E | u ∈ S, v ∈ T } de aristas que tienen un extremo en S y el otro extremo ent _ Si s y t son vértices específicos 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 dirigido no ponderado, el tamaño o el 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.

Corte mínimo

Un corte es mínimo si el tamaño o el 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 corte de tamaño 1 porque el gráfico no tiene puente.

El teorema de corte mínimo de flujo máximo demuestra que el flujo máximo de la red y la suma de los pesos de corte de cualquier corte mínimo que separa 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.

Corte maximo

Un corte es máximo si el tamaño del corte no es más pequeño 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 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. El problema de corte máximo es uno de los 21 problemas NP-completos de Karp. El problema de corte máximo también es APX-hard, lo que significa que no existe un esquema de aproximación de tiempo polinomial para él a menos que P = NP. Sin embargo, se puede aproximar dentro de una relación de aproximación constante usando programación semidefinida.

Tenga en cuenta que min-cut y max-cut 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 de flujo máximo es el dual del problema de corte mínimo.

Corte más escaso

El problema de corte más escaso es dividir en dos los vértices para minimizar la proporción del 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 a la vez escasas (pocas aristas que cruzan el corte) y equilibradas (cerca de una bisección). Se sabe que el problema es NP-hard, y el algoritmo de aproximación más conocido es una aproximación de Arora, Rao y Vazirani (2009).

Cortar espacio

La familia de todos los conjuntos de cortes de un grafo no dirigido se conoce como el espacio de corte del grafo. 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 cortados como operación de suma vectorial, y es el complemento ortogonal del espacio del ciclo. Si los bordes del gráfico reciben 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. 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 el camino de s a ten el árbol.