Spanning tree minimo del grafo multidirezionale

Question

Ho problemi a dedurre un albero radicato da un semplice grafo connesso.

L'inferenza può essere fatta trovando il suo albero di copertura minimo, ma il risultato è limitato da altri due tipi di condizioni:

• C'è una radice nota, che è snel seguente esempio.
• Conosciamo le direzioni di alcuni bordi se vengono scelti . Questi bordi non sono ancora stati scelti o il problema diventa un problema dell'albero di Steiner.

Nota che i numeri sui bordi sono i loro pesi. Quindi otterremo s -> b -> c -> ase viene applicato un normale min spanning tree, ma la direzione del bordo acè sbagliata. D'altra parte, non possiamo usare l'algoritmo di Chu-Liu / Edmonds per coprire l'arborescenza di grafi diretti, perché non conosciamo e non possiamo inferire la direzione del bordo bc.

Possiamo dedurre le direzioni di alcuni bordi in base alla posizione della radice. Ad esempio, nell'esempio, sappiamo s -> be s -> a.

Sembra che il problema possa essere risolto in due passaggi :

1. trasforma il semplice grafico in un multi-grafico. Per i bordi (nel grafico semplice originale) le cui direzioni sono sconosciute, li rappresentiamo in un multigrafo utilizzando due bordi diretti tra due vertici con direzioni inverse.
2. Troviamo lo spanning tree orientato al minimo di questo multigrafo.

---

Spanning Tree orientato

Nella sezione finale dello spanning tree, Wikipedia , viene menzionato lo spanning tree orientato e un articolo [levine2011sandpile]. Il problema si adatta all'impostazione. Dice:

Dato un vertice vsu un multigrafo diretto G, uno spanning tree orientato Tradicato in vè un sottografo aciclico di Gcui ogni vertice diverso da quello vè fuori grado 1.

Si noti che il termine "outdegree" è un po 'confuso, che penso dovrebbe essere "indegree". Ma non importa, perché limita semplicemente il sottografo semplice ad essere un albero diretto con root come sorgente o sink.

Ma non mi è chiaro come un algoritmo possa essere implementato secondo quel documento.

---

• Levine, L. (2011). Gruppi di pile di sabbia e alberi di copertura di grafici a linee dirette. Journal of Combinatorial Theory, serie A, 118 (2), 350-364.
• https://en.wikipedia.org/wiki/Spanning_tree

Answer 1

Come indicato dai commenti, questo è un problema di albero di copertura minimo, che può essere risolto in modo efficiente dall'algoritmo di Edmonds (o dall'algoritmo di Chu – Liu / Edmonds).