Adjacency matrices of multigraphs
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
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
add a comment |Â
up vote
2
down vote
favorite
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
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
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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
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
matrices discrete-mathematics graph-theory
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
add a comment |Â
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
add a comment |Â
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$).
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
add a comment |Â
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.
add a comment |Â
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$).
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
add a comment |Â
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$).
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
add a comment |Â
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$).
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$).
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
add a comment |Â
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
add a comment |Â
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.
add a comment |Â
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.
add a comment |Â
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.
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.
answered Sep 5 at 6:56
Damian Maxwell
11
11
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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