Cortar (teoría de grafos) - Cut (graph theory)

En la teoría de grafos , un corte es una partición de los vértices de un grafo 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értice.

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 corte-set solo consiste en 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 corte .

Definición

Un corte es una partición de de un gráfico en dos subconjuntos S y T . El corte de conjunto de un corte es el conjunto de los bordes que tienen un punto final en S y el otro punto final en T . Si s y t son vértices del gráfico especificado G , a continuación, una s - t corte es un corte en el que s pertenece al conjunto S y t pertenece al conjunto T . ${\ Displaystyle C = (S, T)}$${\ Displaystyle V}$${\ Displaystyle G = (V, E)}$${\ Displaystyle C = (S, T)}$${\ Displaystyle \ {(u, v) \ in E \ mid u \ in S, v \ in T \}}$

En un gráfico no ponderado no dirigido, el tamaño o el peso de un corte es el número de bordes 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 enlace es un conjunto de cortes que no tiene ningún otro conjunto de cortes como subconjunto adecuado.

Corte mínimo

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 corte de tamaño 1 porque el gráfico no tiene puentes .

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 borde de corte de cualquier corte mínimo que separa la fuente y el sumidero son iguales. Existen métodos de tiempo polinómico para resolver el problema de min-cut, en particular el algoritmo de Edmonds-Karp .

Corte máximo

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 corte de tamaño 6, o | E | (el número de aristas), porque la gráfica no es bipartita (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-difícil , lo que significa que no existe un esquema de aproximación de tiempo polinómico 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 se pasa de un problema a otro cambiando de mínimo a máximo en la función objetivo . El problema del flujo máximo es el doble del problema del corte mínimo.

Corte más escaso

El problema del corte más escaso es dividir los vértices en dos partes 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 tanto escasas (pocas aristas cruzan el corte) como equilibradas (próximas a 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 & Vazirani (2009) . ${\ Displaystyle O ({\ sqrt {\ log n}})}$

Cortar espacio

La familia de todos los conjuntos de cortes 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 cíclico . Si se asignan pesos positivos a los bordes del gráfico, la base del peso mínimo del espacio cortado 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 a un enlace en el gráfico original, y el corte mínima entre dos nodos s y t es el vínculo peso mínimo entre los asociados con la trayectoria desde s a t en el árbol.

Ver también

• Conectividad (teoría de grafos)
• Recortes de gráficos en visión artificial
• Split (teoría de grafos)
• Separador de vértices
• Puente (teoría de grafos)

Referencias