Adjacency matrices of multigraphs

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
2
down vote

favorite
3












Adj MatrixIncidence Matrix



Should the entry (adjacency matrix) for row = g, column = g be "2" instead of 1?



Also, should the entry (incidence matrix) for row = g, column = e11 be "2" instead of 1?



I have one lecturer saying that both entries should be "1" and another lecturer saying these two entries should have "2". This looks like it should be obvious; but, I've been given conflicting information about these entries and want to check if there is a "right" answer.










share|cite|improve this question























  • For the first question: because the graph is not directed, the entry should indeed be $2$. This is because one could go from $g$ to $g$ in $2$ ways on that line connecting $g$ to itself, as there is no specified direction to travel on that line. See the following link, and look at the undirected graphs section: en.wikipedia.org/wiki/Adjacency_matrix
    – Dave
    Aug 6 '17 at 20:36











  • It shows that a loop on vertex 1 puts a "2" in row = 1, column = 1 (adjacency matrix); so, a loop gets "2" in the adjacency matrix for this type of graph.
    – Doctor Questions
    Aug 6 '17 at 20:40











  • Precisely. And because both ends of edge $e_11$ touch vertex $g$, we have that the $g,e_11$ entry should also be $2$ in the incidence graph.
    – Dave
    Aug 6 '17 at 20:46















up vote
2
down vote

favorite
3












Adj MatrixIncidence Matrix



Should the entry (adjacency matrix) for row = g, column = g be "2" instead of 1?



Also, should the entry (incidence matrix) for row = g, column = e11 be "2" instead of 1?



I have one lecturer saying that both entries should be "1" and another lecturer saying these two entries should have "2". This looks like it should be obvious; but, I've been given conflicting information about these entries and want to check if there is a "right" answer.










share|cite|improve this question























  • For the first question: because the graph is not directed, the entry should indeed be $2$. This is because one could go from $g$ to $g$ in $2$ ways on that line connecting $g$ to itself, as there is no specified direction to travel on that line. See the following link, and look at the undirected graphs section: en.wikipedia.org/wiki/Adjacency_matrix
    – Dave
    Aug 6 '17 at 20:36











  • It shows that a loop on vertex 1 puts a "2" in row = 1, column = 1 (adjacency matrix); so, a loop gets "2" in the adjacency matrix for this type of graph.
    – Doctor Questions
    Aug 6 '17 at 20:40











  • Precisely. And because both ends of edge $e_11$ touch vertex $g$, we have that the $g,e_11$ entry should also be $2$ in the incidence graph.
    – Dave
    Aug 6 '17 at 20:46













up vote
2
down vote

favorite
3









up vote
2
down vote

favorite
3






3





Adj MatrixIncidence Matrix



Should the entry (adjacency matrix) for row = g, column = g be "2" instead of 1?



Also, should the entry (incidence matrix) for row = g, column = e11 be "2" instead of 1?



I have one lecturer saying that both entries should be "1" and another lecturer saying these two entries should have "2". This looks like it should be obvious; but, I've been given conflicting information about these entries and want to check if there is a "right" answer.










share|cite|improve this question















Adj MatrixIncidence Matrix



Should the entry (adjacency matrix) for row = g, column = g be "2" instead of 1?



Also, should the entry (incidence matrix) for row = g, column = e11 be "2" instead of 1?



I have one lecturer saying that both entries should be "1" and another lecturer saying these two entries should have "2". This looks like it should be obvious; but, I've been given conflicting information about these entries and want to check if there is a "right" answer.







matrices discrete-mathematics graph-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Aug 6 '17 at 20:41









Rodrigo de Azevedo

12.7k41752




12.7k41752










asked Aug 6 '17 at 20:31









Doctor Questions

525




525











  • For the first question: because the graph is not directed, the entry should indeed be $2$. This is because one could go from $g$ to $g$ in $2$ ways on that line connecting $g$ to itself, as there is no specified direction to travel on that line. See the following link, and look at the undirected graphs section: en.wikipedia.org/wiki/Adjacency_matrix
    – Dave
    Aug 6 '17 at 20:36











  • It shows that a loop on vertex 1 puts a "2" in row = 1, column = 1 (adjacency matrix); so, a loop gets "2" in the adjacency matrix for this type of graph.
    – Doctor Questions
    Aug 6 '17 at 20:40











  • Precisely. And because both ends of edge $e_11$ touch vertex $g$, we have that the $g,e_11$ entry should also be $2$ in the incidence graph.
    – Dave
    Aug 6 '17 at 20:46

















  • For the first question: because the graph is not directed, the entry should indeed be $2$. This is because one could go from $g$ to $g$ in $2$ ways on that line connecting $g$ to itself, as there is no specified direction to travel on that line. See the following link, and look at the undirected graphs section: en.wikipedia.org/wiki/Adjacency_matrix
    – Dave
    Aug 6 '17 at 20:36











  • It shows that a loop on vertex 1 puts a "2" in row = 1, column = 1 (adjacency matrix); so, a loop gets "2" in the adjacency matrix for this type of graph.
    – Doctor Questions
    Aug 6 '17 at 20:40











  • Precisely. And because both ends of edge $e_11$ touch vertex $g$, we have that the $g,e_11$ entry should also be $2$ in the incidence graph.
    – Dave
    Aug 6 '17 at 20:46
















For the first question: because the graph is not directed, the entry should indeed be $2$. This is because one could go from $g$ to $g$ in $2$ ways on that line connecting $g$ to itself, as there is no specified direction to travel on that line. See the following link, and look at the undirected graphs section: en.wikipedia.org/wiki/Adjacency_matrix
– Dave
Aug 6 '17 at 20:36





For the first question: because the graph is not directed, the entry should indeed be $2$. This is because one could go from $g$ to $g$ in $2$ ways on that line connecting $g$ to itself, as there is no specified direction to travel on that line. See the following link, and look at the undirected graphs section: en.wikipedia.org/wiki/Adjacency_matrix
– Dave
Aug 6 '17 at 20:36













It shows that a loop on vertex 1 puts a "2" in row = 1, column = 1 (adjacency matrix); so, a loop gets "2" in the adjacency matrix for this type of graph.
– Doctor Questions
Aug 6 '17 at 20:40





It shows that a loop on vertex 1 puts a "2" in row = 1, column = 1 (adjacency matrix); so, a loop gets "2" in the adjacency matrix for this type of graph.
– Doctor Questions
Aug 6 '17 at 20:40













Precisely. And because both ends of edge $e_11$ touch vertex $g$, we have that the $g,e_11$ entry should also be $2$ in the incidence graph.
– Dave
Aug 6 '17 at 20:46





Precisely. And because both ends of edge $e_11$ touch vertex $g$, we have that the $g,e_11$ entry should also be $2$ in the incidence graph.
– Dave
Aug 6 '17 at 20:46











2 Answers
2






active

oldest

votes

















up vote
0
down vote













Consider the degree sum formula for a graph $G = (V,E)$,
$$sum_v in V textdegree v = 2|E|.$$
Now take a look at the multi-graph $G = (1,1,1)$. We obviously get a contradiction if we work with this definition of a self-loop ($textdegree v = 1$ for edge $v,v$).






share|cite|improve this answer






















  • Don't really know about multi-graphs. Only seen discrete mathematics for about one week. I'll be able to refer to your post later on.
    – Doctor Questions
    Aug 6 '17 at 20:47










  • @DoctorQuestions It is a graph with 1) potentially multiple edges between two vertices 2) self loops. So the graph in your question is a multi-graph.
    – Adrianos
    Aug 6 '17 at 20:48










  • I did a quick search and it said some authors don't allow loops in a multi-graph. The joys of basic discrete mathematics.
    – Doctor Questions
    Aug 6 '17 at 20:56










  • @DoctorQuestions We are discussing all entries $(a_vv)_v in V$. These are only non-zero in case of self loops...
    – Adrianos
    Aug 6 '17 at 21:09

















up vote
0
down vote













If there is a loop then the entry should be 2 instead of 1. For the incidence matrix, the sum of each column must always be 2.






share|cite|improve this answer




















    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',
    convertImagesToLinks: true,
    noModals: false,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    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%2f2384906%2fadjacency-matrices-of-multigraphs%23new-answer', 'question_page');

    );

    Post as a guest






























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    0
    down vote













    Consider the degree sum formula for a graph $G = (V,E)$,
    $$sum_v in V textdegree v = 2|E|.$$
    Now take a look at the multi-graph $G = (1,1,1)$. We obviously get a contradiction if we work with this definition of a self-loop ($textdegree v = 1$ for edge $v,v$).






    share|cite|improve this answer






















    • Don't really know about multi-graphs. Only seen discrete mathematics for about one week. I'll be able to refer to your post later on.
      – Doctor Questions
      Aug 6 '17 at 20:47










    • @DoctorQuestions It is a graph with 1) potentially multiple edges between two vertices 2) self loops. So the graph in your question is a multi-graph.
      – Adrianos
      Aug 6 '17 at 20:48










    • I did a quick search and it said some authors don't allow loops in a multi-graph. The joys of basic discrete mathematics.
      – Doctor Questions
      Aug 6 '17 at 20:56










    • @DoctorQuestions We are discussing all entries $(a_vv)_v in V$. These are only non-zero in case of self loops...
      – Adrianos
      Aug 6 '17 at 21:09














    up vote
    0
    down vote













    Consider the degree sum formula for a graph $G = (V,E)$,
    $$sum_v in V textdegree v = 2|E|.$$
    Now take a look at the multi-graph $G = (1,1,1)$. We obviously get a contradiction if we work with this definition of a self-loop ($textdegree v = 1$ for edge $v,v$).






    share|cite|improve this answer






















    • Don't really know about multi-graphs. Only seen discrete mathematics for about one week. I'll be able to refer to your post later on.
      – Doctor Questions
      Aug 6 '17 at 20:47










    • @DoctorQuestions It is a graph with 1) potentially multiple edges between two vertices 2) self loops. So the graph in your question is a multi-graph.
      – Adrianos
      Aug 6 '17 at 20:48










    • I did a quick search and it said some authors don't allow loops in a multi-graph. The joys of basic discrete mathematics.
      – Doctor Questions
      Aug 6 '17 at 20:56










    • @DoctorQuestions We are discussing all entries $(a_vv)_v in V$. These are only non-zero in case of self loops...
      – Adrianos
      Aug 6 '17 at 21:09












    up vote
    0
    down vote










    up vote
    0
    down vote









    Consider the degree sum formula for a graph $G = (V,E)$,
    $$sum_v in V textdegree v = 2|E|.$$
    Now take a look at the multi-graph $G = (1,1,1)$. We obviously get a contradiction if we work with this definition of a self-loop ($textdegree v = 1$ for edge $v,v$).






    share|cite|improve this answer














    Consider the degree sum formula for a graph $G = (V,E)$,
    $$sum_v in V textdegree v = 2|E|.$$
    Now take a look at the multi-graph $G = (1,1,1)$. We obviously get a contradiction if we work with this definition of a self-loop ($textdegree v = 1$ for edge $v,v$).







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Aug 6 '17 at 21:01

























    answered Aug 6 '17 at 20:44









    Adrianos

    1,809515




    1,809515











    • Don't really know about multi-graphs. Only seen discrete mathematics for about one week. I'll be able to refer to your post later on.
      – Doctor Questions
      Aug 6 '17 at 20:47










    • @DoctorQuestions It is a graph with 1) potentially multiple edges between two vertices 2) self loops. So the graph in your question is a multi-graph.
      – Adrianos
      Aug 6 '17 at 20:48










    • I did a quick search and it said some authors don't allow loops in a multi-graph. The joys of basic discrete mathematics.
      – Doctor Questions
      Aug 6 '17 at 20:56










    • @DoctorQuestions We are discussing all entries $(a_vv)_v in V$. These are only non-zero in case of self loops...
      – Adrianos
      Aug 6 '17 at 21:09
















    • Don't really know about multi-graphs. Only seen discrete mathematics for about one week. I'll be able to refer to your post later on.
      – Doctor Questions
      Aug 6 '17 at 20:47










    • @DoctorQuestions It is a graph with 1) potentially multiple edges between two vertices 2) self loops. So the graph in your question is a multi-graph.
      – Adrianos
      Aug 6 '17 at 20:48










    • I did a quick search and it said some authors don't allow loops in a multi-graph. The joys of basic discrete mathematics.
      – Doctor Questions
      Aug 6 '17 at 20:56










    • @DoctorQuestions We are discussing all entries $(a_vv)_v in V$. These are only non-zero in case of self loops...
      – Adrianos
      Aug 6 '17 at 21:09















    Don't really know about multi-graphs. Only seen discrete mathematics for about one week. I'll be able to refer to your post later on.
    – Doctor Questions
    Aug 6 '17 at 20:47




    Don't really know about multi-graphs. Only seen discrete mathematics for about one week. I'll be able to refer to your post later on.
    – Doctor Questions
    Aug 6 '17 at 20:47












    @DoctorQuestions It is a graph with 1) potentially multiple edges between two vertices 2) self loops. So the graph in your question is a multi-graph.
    – Adrianos
    Aug 6 '17 at 20:48




    @DoctorQuestions It is a graph with 1) potentially multiple edges between two vertices 2) self loops. So the graph in your question is a multi-graph.
    – Adrianos
    Aug 6 '17 at 20:48












    I did a quick search and it said some authors don't allow loops in a multi-graph. The joys of basic discrete mathematics.
    – Doctor Questions
    Aug 6 '17 at 20:56




    I did a quick search and it said some authors don't allow loops in a multi-graph. The joys of basic discrete mathematics.
    – Doctor Questions
    Aug 6 '17 at 20:56












    @DoctorQuestions We are discussing all entries $(a_vv)_v in V$. These are only non-zero in case of self loops...
    – Adrianos
    Aug 6 '17 at 21:09




    @DoctorQuestions We are discussing all entries $(a_vv)_v in V$. These are only non-zero in case of self loops...
    – Adrianos
    Aug 6 '17 at 21:09










    up vote
    0
    down vote













    If there is a loop then the entry should be 2 instead of 1. For the incidence matrix, the sum of each column must always be 2.






    share|cite|improve this answer
























      up vote
      0
      down vote













      If there is a loop then the entry should be 2 instead of 1. For the incidence matrix, the sum of each column must always be 2.






      share|cite|improve this answer






















        up vote
        0
        down vote










        up vote
        0
        down vote









        If there is a loop then the entry should be 2 instead of 1. For the incidence matrix, the sum of each column must always be 2.






        share|cite|improve this answer












        If there is a loop then the entry should be 2 instead of 1. For the incidence matrix, the sum of each column must always be 2.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Sep 5 at 6:56









        Damian Maxwell

        11




        11



























             

            draft saved


            draft discarded















































             


            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2384906%2fadjacency-matrices-of-multigraphs%23new-answer', 'question_page');

            );

            Post as a guest













































































            這個網誌中的熱門文章

            How to combine Bézier curves to a surface?

            Mutual Information Always Non-negative

            Why am i infinitely getting the same tweet with the Twitter Search API?