Corte (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 ]} Todo corte determina un conjunto de corte , el conjunto de aristas que tienen un extremo en cada subconjunto de la partición. Se dice que estas aristas cruzan el corte. En un grafo conexo , cada conjunto de corte determina un corte único, y en algunos casos los cortes se identifican con sus conjuntos de corte 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 corte solo consta de aristas que van del 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 arista en el conjunto de corte .

Un corte C = ( S , T ) es una partición de V de un grafo 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 en T . Si s y t son vértices específicos del grafo 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 grafo no dirigido sin ponderación, el tamaño o peso de un corte es el número de aristas que lo atraviesan. En un grafo ponderado , el valor o peso se define por la suma de los pesos de las aristas que atraviesan el corte.

Un enlace es un conjunto de corte que no tiene ningún otro conjunto de corte como subconjunto propio.

Un corte es mínimo si su tamaño o peso no es mayor que el de cualquier otro corte. La ilustración de la derecha muestra un corte mínimo: su tamaño es 2, y no existe ningún corte de tamaño 1 porque el gráfico no tiene puente .

El teorema del flujo máximo y el corte mínimo demuestra que el flujo máximo de la red y la suma de los pesos de las aristas de cualquier corte mínimo que separe la fuente y el sumidero son iguales. Existen métodos de tiempo polinomial para resolver el problema del corte mínimo, en particular el algoritmo de Edmonds-Karp . ^{[ 2 ]}

Un corte es máximo si su tamaño no es menor que el de ningún otro corte. La ilustración de la derecha muestra un corte máximo: su tamaño es igual a 5, y no existe ningún corte de tamaño 6, o | E | (el número de aristas), porque el grafo no es bipartito (hay un ciclo impar ).

En general, encontrar un corte máximo es computacionalmente difícil. ^{[ 3 ]} El problema del corte máximo es uno de los 21 problemas NP-completos de Karp . ^{[ 4 ]} El problema del corte máximo también es APX-difícil , 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 razón de aproximación constante utilizando programación semidefinida . ^{[ 6 ]}

Cabe señalar que los problemas de corte mínimo y corte máximo no son duales en el sentido de la programación lineal , aunque se pasa de un problema a otro cambiando "mínimo" por "máximo" en la función objetivo . El problema de flujo máximo es el dual del problema de corte mínimo . ^{[ 7 ]}

El problema del corte más disperso consiste en biparticionar los vértices de manera que se minimice la razón entre el número de aristas que cruzan el corte y el número de vértices en la mitad más pequeña de la partición. Esta función objetivo favorece las soluciones que son a la vez dispersas (pocas aristas que cruzan el corte) y equilibradas (cercanas a una bisección). Se sabe que el problema es NP-difícil, y el mejor algoritmo de aproximación conocido es un${\displaystyle O({\sqrt {\log n}})}$aproximación debida a Arora, Rao y Vazirani (2009) . ^{[ 8 ]}

La familia de todos los conjuntos de corte de un grafo no dirigido se conoce como el espacio de corte del grafo. Forma un espacio vectorial sobre el cuerpo finito de dos elementos de aritmética módulo dos, con la diferencia simétrica de dos conjuntos de corte como la operación de suma vectorial, y es el complemento ortogonal del espacio de ciclos . ^{[ 9 ] [ 10 ]} Si a las aristas del grafo se les dan pesos positivos, la base de peso mínimo del espacio de corte se puede describir mediante un árbol en el mismo conjunto de vértices que el grafo, llamado árbol de Gomory-Hu . ^{[ 11 ]} Cada arista de este árbol está asociada con un enlace en el grafo 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 t en el árbol.

• Conectividad (teoría de grafos)
• Cortes de grafos en visión artificial
• División (teoría de grafos)
• separador de vértices
• Puente (teoría de grafos)
• ancho de corte
• Dicut