Encontrar el corte mínimo de un gráfico no dirigido

Aquí hay una pregunta de un examen anterior que estoy tratando de resolver:

Para un gráfico no dirigido con pesos positivos , estoy tratando de encontrar el corte mínimo. No conozco otras formas de hacerlo además de usar el teorema de corte mínimo de flujo máximo. Pero el gráfico no está dirigido, entonces, ¿cómo debo dirigirlo? Pensé en dirigir los bordes en ambos extremos, pero ¿qué vértice sería la fuente y qué vértice sería el sumidero? ¿O hay otra forma de encontrar el corte mínimo?$G$$w(e) \geq 0$

Hay muchos algoritmos para encontrar el corte mínimo de un gráfico no dirigido. El algoritmo de Karger es un algoritmo aleatorio simple pero efectivo.

En resumen, el algoritmo funciona seleccionando bordes uniformemente al azar y contrayéndolos con los bucles automáticos eliminados. El proceso se detiene cuando quedan dos nodos, y los dos nodos representan un corte. Para aumentar la probabilidad de éxito, el algoritmo aleatorio se ejecuta varias veces. Mientras realiza las carreras, se realiza un seguimiento del corte más pequeño encontrado hasta ahora.

Vea la entrada de Wikipedia para más detalles. Para quizás una mejor introducción, consulte el primer capítulo de Probabilidad e informática: algoritmos aleatorios y análisis probabilístico de Michael Mitzenmacher y Eli Upfal.

$(u,v, weight)$$(u,v, weight)$$(v,u,weight)$

... pero entonces, ¿qué vértice sería la fuente y qué vértice sería el sumidero?

No importa

El algoritmo Ford-Fulkerson debería funcionar para usted. Puede crear dos vértices falsos, a saber. La fuente y el sumidero.

También eche un vistazo al algoritmo Edmonds-Karp . Hay dos variaciones:

1. Una versión elige el camino más corto
2. Otro elige un camino con la capacidad máxima

, a diferencia de Ford-Fulkerson, que elige un camino arbitrario.

Este es un buen recurso.