Cortar (teoría de grafos)
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 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 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 corte .
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 .
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 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 puentes .
El teorema de corte mínimo de flujo máximo demuestra que el flujo de red máximo 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 polinomial para resolver el problema de min-cut, en particular el algoritmo de Edmonds-Karp . [2]
