corte mínimo a través de vértices/nodos - no bordes

Question

todos conocemos y amamos algoritmos s-t de corte mínimo, pero todos cortan los bordes en el gráfico. ¿Hay alguna variante que corte a través de los nodos?

Answer 1

Por lo tanto, para utilizar el algoritmo de corte mínimo s-t, debe transformar su gráfico en una red de flujo. Esto proporciona un gráfico dirigido implícito (la dirección del flujo hacia adelante de un borde). Puede usar esta representación dirigida para transformar el gráfico en algo que debería resolver esto. Básicamente transforma cada vértice, V (excluyendo la fuente y el sumidero) en dos vértices, llámelos A y B. A obtiene todos los bordes de V, B obtiene todos los bordes de V. Luego crea el borde A -> B con una capacidad máxima de infinito.

Creo que si ejecuta el algoritmo de corte mínimo s-t habitual en esto, solo seleccionará los bordes que cree. La única modificación que puedo pensar que es necesaria es en los casos en que el grado de A es uno, puede seleccionar ese borde para cortar, pero simplemente elija A como el vértice. (Esto depende de la implementación del algoritmo s-t)

Espero que tenga sentido. No estoy seguro si eso funciona (es decir, no tengo ganas de pensar en una prueba adecuada), pero tiene sentido intuitivo que lo haga. La idea intuitiva que tengo es que si cortas un borde "sin vértice", también podrías cortar un borde de "vértice" ya que tiene el mismo efecto que desconectar el gráfico.