Java - Collegamenti critici grafici

Question

Ho un grafico in cui ho due nodi (0 e 6) e devo tagliare il minor numero possibile di margini in modo che non siano collegati. Ad esempio in questo grafico

Essendo i nodi 0 e 6 i bordi meno che devo tagliare sono 2-7 e 3-7. La mia idea era trovare il percorso più breve tra entrambi usando bfs, trovo uno (0-2-7-6) ma poi non so come trovare l'altro (0-3-7-6). Anche allora non ho idea di come scegliere i bordi da tagliare.

Sarebbe bello se qualcuno potesse darmi alcuni suggerimenti su questo argomento.

Answer 1

Questo problema sembra molto simile a quello di trovare nodi di articolazione all'interno di un grafico. La definizione tecnica di un punto di articolazione, o di un componente biconettato, è un nodo la cui rimozione provocherebbe la divisione di un grafico in due parti.

La scoperta di nodi articolati da un grafico è un problema in gran parte risolto e si possono trovare maggiori dettagli su di esso qui: http://en.wikipedia.org/wiki/Biconnected_component

Mi sembra che il modo in cui si vorrebbe affrontare un problema come questo, in generale, sarebbe qualcosa lungo queste linee:

1. Find all articulation points 
2. Do a bfs from each node and determine articulation points along the path 
3. Split graph at the articulation point, choosing the side with minimal edges 
4. Continue until the two nodes are not connected 

nell'esempio precedente, 7 è l'unico punto di articolazione e così si tagliava i bordi tra 7, 2 e 3 poiché vi sono solo due bordi tra 7 e 0-4 grafico e 3 spigoli tra 7 e il grafico 5,6,8.

C'è un algoritmo più definito per fare questo (leggi: uno che non mi è venuto in mente) chiamato algoritmo di Karger che può risolvere il tuo problema, anche se in n^2 volta.

Questo algoritmo funziona collegando efficacemente nodi adiacenti l'un l'altro fino a quando ci sono solo due nodi e quindi contando il numero di spigoli rimasti tra i due nodi. Il numero di bordi è quindi il numero minimo di tagli necessari per dividere il grafico.

Il modo in cui implementeresti l'algoritmo di Karger nel tuo problema avrebbe solo bisogno di avvertire che dovresti sempre unire i nodi ai due nodi che vuoi dividere. Inoltre, per poter tornare indietro ai bordi originali che è necessario tagliare, è necessario mantenere un riferimento a cui i bordi originariamente appartenevano.

C'è una grande visualizzazione dell'algoritmo di Karger qui: http://en.wikipedia.org/wiki/Karger%27s_algorithm

Answer 2

quello che vuoi è un taglio min s-t. Il modo usuale per trovarne uno in un grafico generale è eseguire un algoritmo come push relabel con source 0 e sink 6, che calcola un taglio min s-t come sottoprodotto di calcolo di un flusso massimo.

L'algoritmo di Karger trova un taglio minimo, cioè riduce al minimo s e t oltre ai tagli. Poiché s e t sono corretti per te, Karger's non è appropriato. Un vertice di articolazione è un vertice la cui rimozione disconnette il grafico. Ti interessa rimuovere i bordi, non i vertici.