Elimine el número mínimo de vértices para desconectar el gráfico.

Considere un gráfico no dirigido con una fuente y un vértice de sumidero. Nos gustaría eliminar el número mínimo de vértices en ese gráfico para desconectar cualquier ruta entre la fuente y el sumidero.

¿Podemos hacer esto usando un algoritmo de corte máximo y corte mínimo?

algorithms graph-theory network-flow babysnow
fuente

Debería funcionar (supongo que todos los bordes tienen la misma capacidad).

A.Schulz

Verifique esta pregunta en CSTheory

adrianN

Respuestas:

(Esta respuesta se dio originalmente como parte de la pregunta, con el objetivo de que se verificara).

Mi intuición me dice que podemos usar el algoritmo de flujo mínimo y corte mínimo para resolver este problema:

Reemplace cada uno de los bordes no dirigidos con un par de bordes dirigidos.
$v$ $v_\text{in}$ $v_\text{out}$ $v$ $v_\text{in}$ $v$ $v_\text{out}$
$M$ $M$

FrankW
fuente

v_{in}

$v_\text{in}$

v_{out}

$v_\text{out}$

Para respaldar la respuesta de FrankW, siga los enlaces a continuación, hay un documento de Abdol-Hossein Esfahanian que respalda el reemplazo de un borde no dirigido con dos bordes dirigidos. - networkx.github.io/documentation/latest/reference/generated/… - cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

Pawan Puttaswamy

@pawanp, no te sigo. Por supuesto, puede reemplazar un borde no dirigido con dos bordes dirigidos. La pregunta no es si puede hacerlo, sino si después de aplicar el algoritmo que FrankW enumeró, si se garantiza que la salida sea una solución correcta al problema original. No veo cómo la página de manual de la biblioteca NetworkX es relevante. En cuanto al papel: tiene 14 páginas, con 11 algoritmos diferentes, la mayoría sin pruebas de corrección. ¿Puede ser más específico sobre qué parte ve aquí como relevante?