What is a DAG (Graph Theory)?

Multi tool use
Multi tool use












1












$begingroup$


I am reading this link on Wikipedia; it states the following definition is given for a DAG.



$bullet$ $textbf{Definition:}$ A $underline{textbf{DAG}}$ is a finite, directed graph with no directed cycles.



Reading this definition believes me to think that the digraph below would be a DAG as there are no directed cycles here (there are cycles of the underlying graph but there are no directed cycles).



enter image description here



$underline{textbf{HOWEVER}}$, all the pictures on Wikipedia show examples of DAGs with arrows pointing the same way. So, I think I am interpreting this definition wrong. In particular, why does the definition mention later on an equivalent definition is that it must have topological ordering such that "every edge is directed from earlier to later in the sequence"? Reading the definition above would lead me to believe that the graph above is a DAG, but then the equivalent definition would make me think otherwise.






graph-theory directed-graphs







share|cite|improve this question









$endgroup$

















    1












    $begingroup$


    I am reading this link on Wikipedia; it states the following definition is given for a DAG.



    $bullet$ $textbf{Definition:}$ A $underline{textbf{DAG}}$ is a finite, directed graph with no directed cycles.



    Reading this definition believes me to think that the digraph below would be a DAG as there are no directed cycles here (there are cycles of the underlying graph but there are no directed cycles).



    enter image description here



    $underline{textbf{HOWEVER}}$, all the pictures on Wikipedia show examples of DAGs with arrows pointing the same way. So, I think I am interpreting this definition wrong. In particular, why does the definition mention later on an equivalent definition is that it must have topological ordering such that "every edge is directed from earlier to later in the sequence"? Reading the definition above would lead me to believe that the graph above is a DAG, but then the equivalent definition would make me think otherwise.






    graph-theory directed-graphs







    share|cite|improve this question









    $endgroup$















      1












      1








      1





      $begingroup$


      I am reading this link on Wikipedia; it states the following definition is given for a DAG.



      $bullet$ $textbf{Definition:}$ A $underline{textbf{DAG}}$ is a finite, directed graph with no directed cycles.



      Reading this definition believes me to think that the digraph below would be a DAG as there are no directed cycles here (there are cycles of the underlying graph but there are no directed cycles).



      enter image description here



      $underline{textbf{HOWEVER}}$, all the pictures on Wikipedia show examples of DAGs with arrows pointing the same way. So, I think I am interpreting this definition wrong. In particular, why does the definition mention later on an equivalent definition is that it must have topological ordering such that "every edge is directed from earlier to later in the sequence"? Reading the definition above would lead me to believe that the graph above is a DAG, but then the equivalent definition would make me think otherwise.






      graph-theory directed-graphs







      share|cite|improve this question









      $endgroup$




      I am reading this link on Wikipedia; it states the following definition is given for a DAG.



      $bullet$ $textbf{Definition:}$ A $underline{textbf{DAG}}$ is a finite, directed graph with no directed cycles.



      Reading this definition believes me to think that the digraph below would be a DAG as there are no directed cycles here (there are cycles of the underlying graph but there are no directed cycles).



      enter image description here



      $underline{textbf{HOWEVER}}$, all the pictures on Wikipedia show examples of DAGs with arrows pointing the same way. So, I think I am interpreting this definition wrong. In particular, why does the definition mention later on an equivalent definition is that it must have topological ordering such that "every edge is directed from earlier to later in the sequence"? Reading the definition above would lead me to believe that the graph above is a DAG, but then the equivalent definition would make me think otherwise.






      graph-theory directed-graphs




      graph-theory directed-graphs






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked 3 hours ago









      W. G.W. G.

      6271716




      6271716






















          2 Answers
          2






          active

          oldest

          votes


















          4












          $begingroup$

          The graph you show is a DAG.



          It is conventional to draw DAGs with all the arrows going in the roughly the same direction, because that usually gives a clearer intuition about what is going on in the graph.



          But remember that locations and directions are not part of the formal definition of a graph -- they're just incidental features of the particular drawing at the graph you're looking at, and it would be the same graph if you drew the vertices in different locations on the paper.



          (Even in your drawing, all the edges go in a broadly southeasterly direction -- or at least more southeast than northwest -- so you're actually following the convention).




          In particular, why does the definition mention later on an equivalent definition is that it must have topological ordering such that "every edge is directed from earlier to later in the sequence"?




          Because that is another way to define the same class of graphs, and sometimes (but not always) a more productive way to think about them. You should be able to prove that the finite directed graphs that have no directed cycles are exactly the same as the finite directed graphs that have a topological ordering.






          share|cite|improve this answer









          $endgroup$





















            2












            $begingroup$

            the given graph is indeed a DAG,



            The equivalent definition says that a graph $(V, E)$ is a dag if and only if you can find a total order that extends the order given by $E$.
            In simpler terms, let $u_1, ldots, u_n$ be the elements of $V$ (the vertices), then $(V, E)$ is a dag if and only if you can find an order $<$ such that if $(u_i, u_k)in E$ then $u_i < u_k$.






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              This was very helpful too. I appreciate your answer!
              $endgroup$
              – W. G.
              2 hours ago











            Your Answer





            StackExchange.ifUsing("editor", function () {
            return StackExchange.using("mathjaxEditing", function () {
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
            });
            });
            }, "mathjax-editing");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "69"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: true,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            noCode: true, onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3127366%2fwhat-is-a-dag-graph-theory%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            2 Answers
            2






            active

            oldest

            votes








            2 Answers
            2






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            4












            $begingroup$

            The graph you show is a DAG.



            It is conventional to draw DAGs with all the arrows going in the roughly the same direction, because that usually gives a clearer intuition about what is going on in the graph.



            But remember that locations and directions are not part of the formal definition of a graph -- they're just incidental features of the particular drawing at the graph you're looking at, and it would be the same graph if you drew the vertices in different locations on the paper.



            (Even in your drawing, all the edges go in a broadly southeasterly direction -- or at least more southeast than northwest -- so you're actually following the convention).




            In particular, why does the definition mention later on an equivalent definition is that it must have topological ordering such that "every edge is directed from earlier to later in the sequence"?




            Because that is another way to define the same class of graphs, and sometimes (but not always) a more productive way to think about them. You should be able to prove that the finite directed graphs that have no directed cycles are exactly the same as the finite directed graphs that have a topological ordering.






            share|cite|improve this answer









            $endgroup$


















              4












              $begingroup$

              The graph you show is a DAG.



              It is conventional to draw DAGs with all the arrows going in the roughly the same direction, because that usually gives a clearer intuition about what is going on in the graph.



              But remember that locations and directions are not part of the formal definition of a graph -- they're just incidental features of the particular drawing at the graph you're looking at, and it would be the same graph if you drew the vertices in different locations on the paper.



              (Even in your drawing, all the edges go in a broadly southeasterly direction -- or at least more southeast than northwest -- so you're actually following the convention).




              In particular, why does the definition mention later on an equivalent definition is that it must have topological ordering such that "every edge is directed from earlier to later in the sequence"?




              Because that is another way to define the same class of graphs, and sometimes (but not always) a more productive way to think about them. You should be able to prove that the finite directed graphs that have no directed cycles are exactly the same as the finite directed graphs that have a topological ordering.






              share|cite|improve this answer









              $endgroup$
















                4












                4








                4





                $begingroup$

                The graph you show is a DAG.



                It is conventional to draw DAGs with all the arrows going in the roughly the same direction, because that usually gives a clearer intuition about what is going on in the graph.



                But remember that locations and directions are not part of the formal definition of a graph -- they're just incidental features of the particular drawing at the graph you're looking at, and it would be the same graph if you drew the vertices in different locations on the paper.



                (Even in your drawing, all the edges go in a broadly southeasterly direction -- or at least more southeast than northwest -- so you're actually following the convention).




                In particular, why does the definition mention later on an equivalent definition is that it must have topological ordering such that "every edge is directed from earlier to later in the sequence"?




                Because that is another way to define the same class of graphs, and sometimes (but not always) a more productive way to think about them. You should be able to prove that the finite directed graphs that have no directed cycles are exactly the same as the finite directed graphs that have a topological ordering.






                share|cite|improve this answer









                $endgroup$



                The graph you show is a DAG.



                It is conventional to draw DAGs with all the arrows going in the roughly the same direction, because that usually gives a clearer intuition about what is going on in the graph.



                But remember that locations and directions are not part of the formal definition of a graph -- they're just incidental features of the particular drawing at the graph you're looking at, and it would be the same graph if you drew the vertices in different locations on the paper.



                (Even in your drawing, all the edges go in a broadly southeasterly direction -- or at least more southeast than northwest -- so you're actually following the convention).




                In particular, why does the definition mention later on an equivalent definition is that it must have topological ordering such that "every edge is directed from earlier to later in the sequence"?




                Because that is another way to define the same class of graphs, and sometimes (but not always) a more productive way to think about them. You should be able to prove that the finite directed graphs that have no directed cycles are exactly the same as the finite directed graphs that have a topological ordering.







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered 3 hours ago









                Henning MakholmHenning Makholm

                241k17307545




                241k17307545























                    2












                    $begingroup$

                    the given graph is indeed a DAG,



                    The equivalent definition says that a graph $(V, E)$ is a dag if and only if you can find a total order that extends the order given by $E$.
                    In simpler terms, let $u_1, ldots, u_n$ be the elements of $V$ (the vertices), then $(V, E)$ is a dag if and only if you can find an order $<$ such that if $(u_i, u_k)in E$ then $u_i < u_k$.






                    share|cite|improve this answer









                    $endgroup$













                    • $begingroup$
                      This was very helpful too. I appreciate your answer!
                      $endgroup$
                      – W. G.
                      2 hours ago
















                    2












                    $begingroup$

                    the given graph is indeed a DAG,



                    The equivalent definition says that a graph $(V, E)$ is a dag if and only if you can find a total order that extends the order given by $E$.
                    In simpler terms, let $u_1, ldots, u_n$ be the elements of $V$ (the vertices), then $(V, E)$ is a dag if and only if you can find an order $<$ such that if $(u_i, u_k)in E$ then $u_i < u_k$.






                    share|cite|improve this answer









                    $endgroup$













                    • $begingroup$
                      This was very helpful too. I appreciate your answer!
                      $endgroup$
                      – W. G.
                      2 hours ago














                    2












                    2








                    2





                    $begingroup$

                    the given graph is indeed a DAG,



                    The equivalent definition says that a graph $(V, E)$ is a dag if and only if you can find a total order that extends the order given by $E$.
                    In simpler terms, let $u_1, ldots, u_n$ be the elements of $V$ (the vertices), then $(V, E)$ is a dag if and only if you can find an order $<$ such that if $(u_i, u_k)in E$ then $u_i < u_k$.






                    share|cite|improve this answer









                    $endgroup$



                    the given graph is indeed a DAG,



                    The equivalent definition says that a graph $(V, E)$ is a dag if and only if you can find a total order that extends the order given by $E$.
                    In simpler terms, let $u_1, ldots, u_n$ be the elements of $V$ (the vertices), then $(V, E)$ is a dag if and only if you can find an order $<$ such that if $(u_i, u_k)in E$ then $u_i < u_k$.







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered 3 hours ago









                    aleph0aleph0

                    3259




                    3259












                    • $begingroup$
                      This was very helpful too. I appreciate your answer!
                      $endgroup$
                      – W. G.
                      2 hours ago


















                    • $begingroup$
                      This was very helpful too. I appreciate your answer!
                      $endgroup$
                      – W. G.
                      2 hours ago
















                    $begingroup$
                    This was very helpful too. I appreciate your answer!
                    $endgroup$
                    – W. G.
                    2 hours ago




                    $begingroup$
                    This was very helpful too. I appreciate your answer!
                    $endgroup$
                    – W. G.
                    2 hours ago


















                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Mathematics Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid …



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3127366%2fwhat-is-a-dag-graph-theory%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    SakI kET dSUpIrpMvDIXd9Lsa,fPt kzku elL 4Q7E,V7QW,JBlNqRaL yvSSjqknRW7Jhhbkaza,ItDP,jXRQa2BVC1KqLqdA2j,r rw
                    -
                    fKIGzjK,UW 7TMphXEMUdQ3W 1jS6K7 8khWF cr Tm,mcdhZ3ZU3WIVHP,pJ7,ajK9Igk zL,DO2,QZBprWwEX8e,h7t4e,R gVE

                    Popular posts from this blog

                    Bundesstraße 106

                    Image
                    Dieser Artikel beschreibt die Bundesstraße 106 in Deutschland. Zur gleichnamigen Straße in Österreich siehe Mölltal Straße. Vorlage:Infobox hochrangige Straße/Wartung/DE-B Bundesstraße 106 in Deutschland Karte Basisdaten Betreiber: Deutschland  Bundesrepublik Deutschland Straßenbeginn: Wismar ( 53° 54′  N , 11° 24′  O 53.900536 11.396875 ) Straßenende: Schwerin ( 53° 36′  N , 11° 24′  O 53.592785 11.404892 ) Gesamtlänge: 40,7 km Bundesland: Mecklenburg-Vorpommern Ausbauzustand: zweistreifig [1] Bundesstraße 106 in Schwerin (Umgehungsstraße) Straßenverlauf Land Mecklenburg-Vorpommern Landkreis Nordwestmecklenburg Ortsumgehung Wismar Wallensteingraben über   Dorf Mecklenburg Wallensteingraben Groß Stieten Bad Kleinen OT Niendorf Bahnstrecke Lübeck–Bad Kleinen Zickhusen Lübstorf Klein Trebbow OT Kirch Stück ...
                    Read more

                    Liste der Kulturdenkmäler in Imsweiler

                    Image
                    In der Liste der Kulturdenkmäler in Imsweiler sind alle Kulturdenkmäler der rheinland-pfälzischen Ortsgemeinde Imsweiler einschließlich des Ortsteils Felsbergerhof aufgeführt. Grundlage ist die Denkmalliste des Landes Rheinland-Pfalz (Stand: 15. August 2017). Inhaltsverzeichnis 1 Denkmalzonen 2 Einzeldenkmäler 3 Literatur 4 Weblinks Denkmalzonen | Bezeichnung Lage Baujahr Beschreibung Bild Denkmalzone Flörsheimer Schlösschen Schloßstraße 4 Lage vor 1236 Reste der Ringmauer der 1236 belegten Wasserburg, vom 1595 erbauten, im Dreißigjährigen Krieg zerstörten Wasserschloss Renaissance-Teile in der Hofanlage des 18. und 19. Jahrhunderts erhalten Einzeldenkmäler | Bezeichnung Lage Baujahr Beschreibung Bild Protestantischer Glockenturm Alsenzstraße, gegenüber Nr. 29 Lage 1877 Sandsteinquaderbau, bezeichnet 1877, Architekt Julius Huth, Kaiserslautern Katholische Pfarrkirche St. Peter in den Ketten ...
                    Read more

                    Santa Maria sopra Minerva (Rom)

                    Image
                    Santa Maria sopra Minerva [1] Konfession: römisch-katholisch Patrozinium: Hl. Maria Weihejahr: 1370 Rang: Basilica minor Orden: Dominikaner (OP) Kardinalpriester: António Marto Anschrift: Piazza della Minerva, 42 00187 Roma 41.898029 12.478194 Koordinaten: 41° 53′ 52,9″  N , 12° 28′ 41,5″  O Santa Maria sopra Minerva ( lateinisch Sanctae Mariae supra Minervam ), vollständig Basilica di Santa Maria sopra Minerva , ist der einzig bedeutende Kirchenbau Roms aus der Zeit der Gotik und eine der Hauptkirchen des Dominikanerordens in Rom. Seit 1566 ist die Basilica minor eine Titelkirche der römisch-katholischen Kirche. Sie befindet sich an der Piazza della Minerva im Rione Pigna im historischen Zentrum Roms, dem Marsfeld südöstlich des Pantheon. Südlich grenzt die Straße Via di S. Caterina da Siena an, benannt nach der Heiligen Katharina von Siena, deren Grab sich unter dem Hauptaltar der Kirche befindet. Die Kirche wurde über den Ruin...
                    Read more