https://wcipeg.com/wiki/index.php?title=Directed_acyclic_graph&feed=atom&action=historyDirected acyclic graph - Revision history2024-03-28T20:29:22ZRevision history for this page on the wikiMediaWiki 1.25.2https://wcipeg.com/wiki/index.php?title=Directed_acyclic_graph&diff=1150&oldid=prevBrian: /* Problems */ - longest path2011-03-18T05:36:28Z<p><span dir="auto"><span class="autocomment">Problems: </span> - longest path</span></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 05:36, 18 March 2011</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L25" >Line 25:</td>
<td colspan="2" class="diff-lineno">Line 25:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>:* '''[[All-pairs shortest paths]]''' can be computed in <math>O(V(E+V))</math> by <math>V</math> invocations of the single-source algorithm. This is, however, no faster than [[breadth-first search]] when the DAG is unweighted, and no faster than the [[Floyd–Warshall algorithm]] when the graph is dense (so that it is an improvement only over sparse weighted DAGs).</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>:* '''[[All-pairs shortest paths]]''' can be computed in <math>O(V(E+V))</math> by <math>V</math> invocations of the single-source algorithm. This is, however, no faster than [[breadth-first search]] when the DAG is unweighted, and no faster than the [[Floyd–Warshall algorithm]] when the graph is dense (so that it is an improvement only over sparse weighted DAGs).</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>::* The same applies to the '''transitive closure problem''' &ndash; it is not easy to improve over the <math>O(V^3)</math> bound given by Warshall's algorithm, but see [[Directed acyclic graph/Transitive closure|this]] for a method that may perform better under certain circumstances. The bounds on the '''transitive reduction problem''' match those on transitive closure.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>::* The same applies to the '''transitive closure problem''' &ndash; it is not easy to improve over the <math>O(V^3)</math> bound given by Warshall's algorithm, but see [[Directed acyclic graph/Transitive closure|this]] for a method that may perform better under certain circumstances. The bounds on the '''transitive reduction problem''' match those on transitive closure.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* '''Longest path problem''': This can also be solved efficiently using dynamic programming. Note that we only need to consider paths that start at a source.</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Identifying all strongly connected components in a digraph and contracting each component to a single vertex produces a DAG, known as the '''kernel DAG'''. Adapting the special transitive closure algorithm on DAGs to the kernel DAG gives an algorithm which may be fast for some classes of digraphs. The kernel DAG is also useful as an intermediate structure in the solutions of various other problems.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Identifying all strongly connected components in a digraph and contracting each component to a single vertex produces a DAG, known as the '''kernel DAG'''. Adapting the special transitive closure algorithm on DAGs to the kernel DAG gives an algorithm which may be fast for some classes of digraphs. The kernel DAG is also useful as an intermediate structure in the solutions of various other problems.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* The '''[[minimum spanning arborescence]] problem''' does not have much to do with DAGs in general, but an arborescence is a specific kind of DAG that looks like a tree.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* The '''[[minimum spanning arborescence]] problem''' does not have much to do with DAGs in general, but an arborescence is a specific kind of DAG that looks like a tree.</div></td></tr>
</table>Brianhttps://wcipeg.com/wiki/index.php?title=Directed_acyclic_graph&diff=1147&oldid=prevBrian at 19:48, 17 March 20112011-03-17T19:48:38Z<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 19:48, 17 March 2011</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L7" >Line 7:</td>
<td colspan="2" class="diff-lineno">Line 7:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>The ordering thus defined is reflexive, since every vertex is reachable from itself. It is antisymmetric, because if <math>u \leq v</math> and <math>v \leq u</math>, and <math>u \neq v</math>, then we have a cycle that contains <math>a</math> and <math>b</math>, a contradiction. And it is transitive because reachability is transitive; if there are paths from <math>u</math> to <math>v</math> and from <math>v</math> to <math>w</math> then we can concatenate them to obtain a path from <math>u</math> to <math>w</math>. So the ordering we have defined is a partial ordering.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>The ordering thus defined is reflexive, since every vertex is reachable from itself. It is antisymmetric, because if <math>u \leq v</math> and <math>v \leq u</math>, and <math>u \neq v</math>, then we have a cycle that contains <math>a</math> and <math>b</math>, a contradiction. And it is transitive because reachability is transitive; if there are paths from <math>u</math> to <math>v</math> and from <math>v</math> to <math>w</math> then we can concatenate them to obtain a path from <math>u</math> to <math>w</math>. So the ordering we have defined is a partial ordering.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Note that whereas a given DAG will correspond to exactly one partial ordering (up to isomorphism) using this convention, there may be more than one DAG that corresponds to a given partial ordering. The DAG with the <del class="diffchange diffchange-inline">greatest number of </del>edges that corresponds to a given partial ordering is known as the [[transitive closure]], whereas the one with the fewest number of edges is <del class="diffchange diffchange-inline">known </del>as the [[transitive reduction]].</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Note that whereas a given DAG will correspond to exactly one partial ordering (up to isomorphism) using this convention, there may be more than one DAG that corresponds to a given partial ordering. The DAG with the <ins class="diffchange diffchange-inline">most </ins>edges that corresponds to a given partial ordering is known as the [[transitive closure]], whereas the one with the fewest <ins class="diffchange diffchange-inline">edges is known as the [[transitive reduction]].</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">==Properties==</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">A '''source''' is a node with zero in-degree; all edges point outward. Likewise, a '''sink''' is a node with zero out-degree. Every finite DAG has at least one source and one sink. To see this, choose any node. If it is a sink we are done; otherwise select any outgoing edge and follow it to another node. Repeating this process, we will never repeat a node, because the graph has no cycles, so after <math>V-1</math> iterations (where <math>V</math> is the </ins>number of <ins class="diffchange diffchange-inline">nodes in the graph), this process must terminate. The proof that there must be at least one source is analogous.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">In fact, a stronger statement holds: a directed graph may be ''[[Topological sort|topologically ordered]]'' if and only if it is acyclic (a DAG).</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Because a DAG has no cycles, each vertex in a DAG forms a separate strongly connected component.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">A DAG with <math>V</math> vertices cannot have more than <math>V(V-1)/2</math> </ins>edges<ins class="diffchange diffchange-inline">, and this bound </ins>is <ins class="diffchange diffchange-inline">attained by taking a complete undirected graph on <math>V</math> vertices, assigning a different number to each vertex, and orienting all edges so that they point from the lower-numbered vertex to the higher-numbered vertex. Such a DAG represents a total order. The proof is not hard and is left </ins>as <ins class="diffchange diffchange-inline">an exercise to </ins>the <ins class="diffchange diffchange-inline">reader.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">==Problems==</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">The following problems either involve DAGs specifically or have simpler/faster solutions for DAGs than for other graphs.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">* The '''</ins>[[<ins class="diffchange diffchange-inline">topological sort]]ing''' problem mentioned in the preceding section.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">* '''[[Shortest paths]]''' and '''transitive closure'''</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">:* '''Single-source shortest paths''' can be computed in <math>O(E+V)</math> time by topologically sorting first and then using [[dynamic programming]].</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">:* '''[[All-pairs shortest paths]]''' can be computed in <math>O(V(E+V))</math> by <math>V</math> invocations of the single-source algorithm. This is, however, no faster than [[breadth-first search]] when the DAG is unweighted, and no faster than the [[Floyd–Warshall algorithm]] when the graph is dense (so that it is an improvement only over sparse weighted DAGs).</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">::* The same applies to the '''transitive closure problem''' &ndash; it is not easy to improve over the <math>O(V^3)</math> bound given by Warshall's algorithm, but see [[Directed acyclic graph/Transitive closure|this]] for a method that may perform better under certain circumstances. The bounds on the '''</ins>transitive reduction <ins class="diffchange diffchange-inline">problem''' match those on transitive closure.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">* Identifying all strongly connected components in a digraph and contracting each component to a single vertex produces a DAG, known as the '''kernel DAG'''. Adapting the special transitive closure algorithm on DAGs to the kernel DAG gives an algorithm which may be fast for some classes of digraphs. The kernel DAG is also useful as an intermediate structure in the solutions of various other problems.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">* The '''[[minimum spanning arborescence</ins>]] <ins class="diffchange diffchange-inline">problem''' does not have much to do with DAGs in general, but an arborescence is a specific kind of DAG that looks like a tree</ins>.</div></td></tr>
</table>Brianhttps://wcipeg.com/wiki/index.php?title=Directed_acyclic_graph&diff=1144&oldid=prevBrian: Created page with "A '''directed acyclic graph (DAG)''' is a directed graph that contains no cycles. DAGs arise in a natural way in modelling situations in which, in some sense, going "forward"..."2011-03-17T06:38:14Z<p>Created page with "A '''directed acyclic graph (DAG)''' is a directed <a href="/wiki/Graph" class="mw-redirect" title="Graph">graph</a> that contains no cycles. DAGs arise in a natural way in modelling situations in which, in some sense, going "forward"..."</p>
<p><b>New page</b></p><div>A '''directed acyclic graph (DAG)''' is a directed [[graph]] that contains no cycles. DAGs arise in a natural way in modelling situations in which, in some sense, going "forward" is sometimes possible but going "backward" is definitely not, so that if <math>v</math> is reachable from <math>u</math>, we know that <math>u</math> is ''not'' reachable from <math>v</math> (unless <math>u = v</math>). An example is given by {{Problem|ccc07s4|Water Park}} from [[CCC]] 2007. In the absence of mechanical intervention, water always flows from high altitudes to low altitudes, so that, when travelling along the waterslides, one can never arrive at the same spot twice. If we create a graph that has a vertex for each marked point in the water park and a directed edge from <math>u</math> to <math>v</math> whenever there is a water slide from <math>u</math> to <math>v</math>, this graph will be acyclic, and hence a DAG. DAGs do not necessarily resemble ''undirected'' acyclic graphs (that is, [[Tree|forests]]) in form or in their properties; there may be multiple paths between a given pair of nodes.<br />
<br />
==As a partial order==<br />
DAGs are often considered representations of partial orderings. We can establish a correspondence as follows:<br />
# Give each vertex of the DAG a unique label (such as the letters '''A''', '''B''', '''C''', ''etc''.). Each label corresponds to an element in our set.<br />
# We define our partial ordering as follows: <math>a \leq b</math> in the ordering if and only if there exists a path from <math>u</math> to <math>v</math>, where <math>u</math> is the vertex in the DAG labelled with <math>a</math> and <math>v</math> is the vertex in the DAG labelled with <math>b</math>.<br />
The ordering thus defined is reflexive, since every vertex is reachable from itself. It is antisymmetric, because if <math>u \leq v</math> and <math>v \leq u</math>, and <math>u \neq v</math>, then we have a cycle that contains <math>a</math> and <math>b</math>, a contradiction. And it is transitive because reachability is transitive; if there are paths from <math>u</math> to <math>v</math> and from <math>v</math> to <math>w</math> then we can concatenate them to obtain a path from <math>u</math> to <math>w</math>. So the ordering we have defined is a partial ordering.<br />
<br />
Note that whereas a given DAG will correspond to exactly one partial ordering (up to isomorphism) using this convention, there may be more than one DAG that corresponds to a given partial ordering. The DAG with the greatest number of edges that corresponds to a given partial ordering is known as the [[transitive closure]], whereas the one with the fewest number of edges is known as the [[transitive reduction]].</div>Brian