StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Assuming there are no isolated vertices in the graph you only need to add max(|sources|,|sinks|) edges to make it strongly connected.</p> <p>Let T={t<sub>1</sub>,…,t<sub>n</sub>} be the sinks and {s<sub>1</sub>,…,s<sub>m</sub>} be the sources of the DAG. Assume that n <= m. (The other case is very similar). Consider a bipartite graph G(T,S) between the two sets defined as follows. G(T,S) has an edge (t<sub>i</sub>,s<sub>j</sub>) if and only if t<sub>i</sub> can be reached from s<sub>j</sub>.</p> <p>Let M be a maximal matching in G(T,S). Without loss of generality assume that M consists of k edges: {(t<sub>1</sub>,s<sub>1</sub>),(t<sub>2</sub>,s<sub>2</sub>),…,(t<sub>k</sub>,s<sub>k</sub>)}. In the original graph DAG G, add directed-edges {(t<sub>1</sub>->s<sub>2</sub>),(t<sub>2</sub>->s<sub>3</sub>),…,(t<sub>k−1</sub>->s<sub>k</sub>),(t<sub>k</sub>->s<sub>1</sub>)}. It's easy to see that by adding these edges, the vertices induced by M are strongly connected in G.</p> <p>Now consider the remaining vertices in G(T,S). Because M maximal, each vertex in S−M (resp. T−M)should be connected to a vertex in T (resp. S−M). So we pair up the remaining vertices arbitrarily, say {(t<sub>k+1</sub>,s<sub>k+1</sub>),…,(t<sub>n</sub>,s<sub>n</sub>)} and add the corresponding directed edges in G. For each remaining source vertex source s<sub>i</sub> (i belongs to {n+1,…,m} we add the edge (t<sub>1</sub>->s<sub>i</sub>) in G. Thus the total number of edges added is max(|sources|,|sinks|).</p> <p><strong>EDIT: Adding a couple of Examples</strong></p> <p>For the example in your input. We fist compute a maximal matching, say:</p> <pre><code>3--1 4--2 7--5 8--6 </code></pre> <p>So we add the edges:</p> <pre><code>3->2 4->5 7->6 8->1 </code></pre> <p>The remaining (sink) vertex not present in the matching is 9 and so we add the arc from 9 to any source vertex in the matching, say <code>9->1</code>.</p> <p>Here's another example that illustrates all the steps of the algorithm:</p> <p>Input Graph:</p> <pre><code>12 3 5 9 10 (sources) \|/ /|\ \/ 4 6 7 8 11 (sinks) </code></pre> <p>Maximal Matching:</p> <pre><code>4--1 6--5 11--9 </code></pre> <p>So we add the edges:</p> <pre><code>4->5 6->9 11->1 </code></pre> <p>Now the remaining sinks are <code>{7, 8}</code> and the remaining sources are <code>{2, 3, 10}</code>. We arbitrary pair 7 with say 2 and 8 with say 3 and add:</p> <pre><code>7->2 8->3 </code></pre> <p>Finally, the remaining (source) vertex is 10 and we add:</p> <pre><code>4->10 </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload