Algoritmo del tempo lineare per creare un grafico fortemente connesso

Question

Abbiamo un digrafo debolmente aciclico.

Inoltre, viene fornito un set A che mantiene i vertici di G che hanno lo zero in-degree e un set B che trattiene i vertici che hanno zero di grado zero. (la dimensione di A è minore della dimensione di B).

Inoltre, sappiamo anche che se gli elementi in A e B hanno un ordine particolare DFS ha iniziato alle visite ai bi (1≤ i ≤ m).

È possibile progettare un algoritmo di tempo lineare che rende G fortemente connesso aggiungendo ad esso il minor numero possibile di spigoli?

Answer 1

Aggiungi archi b _j -> un _{j + 1} per j = 1, ..., m-1 e archi b _j -> un per j = m, ... , n.

Il grafico risultante è fortemente connesso perché la A e B sono fortemente collegati da archi aggiunti e percorsi da un _i a B _i e, per ogni nodo x, esistono i, j tale che vi esiste un percorso nel grafico originale da un _i a xe un percorso nel grafico originale da xa b _j.

Non possiamo usare meno archi, perché un arco in uscita deve essere aggiunto a ciascuna delle b , ..., b _n.

Answer 2

Edited - Dopo non produce una soluzione con meno link:

È possibile eseguire http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm in tempo lineare. Vi propongo di farlo e di notare che "nessun componente fortemente connesso verrà identificato prima di nessuno dei suoi successori". Pertanto, la prima componente fortemente fuori dal grafico non deve essere un successore di nessuno degli altri componenti. Suggerisco che ogni volta che si emette un componente fortemente connesso che non ha alcun successore, si aggiunge un collegamento che lo collega a questo primo componente. Suggerisco di aggiungere anche un collegamento ogni volta che si riavvia sostanzialmente l'algoritmo di Tarjan con una chiamata non ricorsiva a strongconnect(), collegando il primo componente al vertice al quale si sta riavviando.

Con questi collegamenti è possibile ottenere dal primo componente forte a ogni altro componente e da ogni altro componente al primo componente forte. - sfortunatamente questa non è necessariamente la soluzione con i collegamenti minimi - vedi il secondo commento di Per sotto.