How-many-different-adjacency-matrix-with-N-vertices-and-E-edges-have?
$begingroup$
i'm studing graphs in algorithm and complexity and was perplexed in front of the following questions. I hope I get clear explanation for it...
How-many-different-adjacency-matrix-with-N-vertices-and-E-edges-have?
I found out that the answer is n! on this website:
source
The link simply says that the number of possible matrix is equal to number of permutations of n elements.
But I don't know how to get this answer.
combinatorics graph-theory
asked Jul 11 '15 at 19:32
user3624963user3624963
12
$endgroup$
add a comment |
$begingroup$
i'm studing graphs in algorithm and complexity and was perplexed in front of the following questions. I hope I get clear explanation for it...
How-many-different-adjacency-matrix-with-N-vertices-and-E-edges-have?
I found out that the answer is n! on this website:
source
The link simply says that the number of possible matrix is equal to number of permutations of n elements.
But I don't know how to get this answer.
combinatorics graph-theory
asked Jul 11 '15 at 19:32
user3624963user3624963
12
$endgroup$
$begingroup$
I don't see where the note you linked above says any thing like that. A count of adjacency matrices for graphs with $N$ vertices and $E$ edges will depend on both $N$ and $E$.
$endgroup$
– hardmath
Dec 13 '18 at 17:38
add a comment |
$begingroup$
i'm studing graphs in algorithm and complexity and was perplexed in front of the following questions. I hope I get clear explanation for it...
How-many-different-adjacency-matrix-with-N-vertices-and-E-edges-have?
I found out that the answer is n! on this website:
source
The link simply says that the number of possible matrix is equal to number of permutations of n elements.
But I don't know how to get this answer.
combinatorics graph-theory
asked Jul 11 '15 at 19:32
user3624963user3624963
12
$endgroup$
i'm studing graphs in algorithm and complexity and was perplexed in front of the following questions. I hope I get clear explanation for it...
How-many-different-adjacency-matrix-with-N-vertices-and-E-edges-have?
I found out that the answer is n! on this website:
source
The link simply says that the number of possible matrix is equal to number of permutations of n elements.
But I don't know how to get this answer.
combinatorics graph-theory
combinatorics graph-theory
asked Jul 11 '15 at 19:32
user3624963user3624963
12
asked Jul 11 '15 at 19:32
user3624963user3624963
12
asked Jul 11 '15 at 19:32
user3624963user3624963
12
asked Jul 11 '15 at 19:32
user3624963user3624963
12
asked Jul 11 '15 at 19:32
user3624963user3624963
12
12
$begingroup$
I don't see where the note you linked above says any thing like that. A count of adjacency matrices for graphs with $N$ vertices and $E$ edges will depend on both $N$ and $E$.
$endgroup$
– hardmath
Dec 13 '18 at 17:38
add a comment |
$begingroup$
I don't see where the note you linked above says any thing like that. A count of adjacency matrices for graphs with $N$ vertices and $E$ edges will depend on both $N$ and $E$.
$endgroup$
– hardmath
Dec 13 '18 at 17:38
$begingroup$
I don't see where the note you linked above says any thing like that. A count of adjacency matrices for graphs with $N$ vertices and $E$ edges will depend on both $N$ and $E$.
$endgroup$
– hardmath
Dec 13 '18 at 17:38
$begingroup$
I don't see where the note you linked above says any thing like that. A count of adjacency matrices for graphs with $N$ vertices and $E$ edges will depend on both $N$ and $E$.
$endgroup$
– hardmath
Dec 13 '18 at 17:38
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
You shouldn't believe everything you read online, or at least, you should take it with a grain of salt. Basically the author is saying that any permutation of vertices will give an isomorphic graph, if you consider the vertices to be ordered. The total number of permutations of $n$ vertices is $n!$. However this is not to say that the number of DISTINCT isomorphic graphs is always $n!$ if you have $n$ vertices. Consider for example the graph with no edges, or the graph with all edges. These have no other distinct isomorphic graphs, other than themselves, so the number of isomorphic graphs for these is simply 1, regardless of the number of vertices $n$.
answered Jul 11 '15 at 19:43
user2566092user2566092
21.5k1947
$endgroup$
$begingroup$
Shouldnt maximum possible number of adjacency matrices for $n$ node graph be $(n!)^2$ for both undirected and directed graphs? We can permute rows of adjacency matrix in n! ways. Similarly we can permute columns of adjacency matrix in n!. For both directed and undirected graphs, permuting any one or both of rows and columns will give new adjacency matrix. So shouldnt it be $(n!)^2$?
$endgroup$
– anir
Apr 7 '18 at 9:13
1
$begingroup$
@anir if you permute just the rows without applying the same permutation to the columns, you might not have an adjacency matrix anymore. (Consider that the adjacency matrix of an undirected graph must be symmetric, but permuting rows without permuting columns can break symmetry.)
$endgroup$
– Gregory J. Puleo
Dec 13 '18 at 14:28
add a comment |
$begingroup$
The Accepted Answer above explains what interpretation might be placed on the expression $n!$, i.e. counting the number of labellings of vertices in a graph $G$ that has $n$ vertices. While such a labelling is required to get an adjacency matrix that represents a (simple) graph, it cannot account for the number of edges that we want such a graph to have. Moreover two different labellings may or may not lead to the same adjacency matrix for $G$.
If a graph $G$ has $n$ vertices and $e$ edges, the possible adjacency matrices, without restriction as to which labelling is chosen, are given by choosing $e$ of the possible $binom{n}{2}$ entries below the diagonal of the $ntimes n$ matrix (setting these to $1$ and the rest of the entries, including the diagonal, to zero).
The same count, $binom{binom{n}{2}}{e}$, is given by choosing an $e$-subset of the $binom{n}{2}$ edges in the complete graph $K_n$ on $n$ vertices.
answered Dec 13 '18 at 17:56
hardmathhardmath
29k953100
$endgroup$
add a comment |
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
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1357782%2fhow-many-different-adjacency-matrix-with-n-vertices-and-e-edges-have%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
$begingroup$
You shouldn't believe everything you read online, or at least, you should take it with a grain of salt. Basically the author is saying that any permutation of vertices will give an isomorphic graph, if you consider the vertices to be ordered. The total number of permutations of $n$ vertices is $n!$. However this is not to say that the number of DISTINCT isomorphic graphs is always $n!$ if you have $n$ vertices. Consider for example the graph with no edges, or the graph with all edges. These have no other distinct isomorphic graphs, other than themselves, so the number of isomorphic graphs for these is simply 1, regardless of the number of vertices $n$.
answered Jul 11 '15 at 19:43
user2566092user2566092
21.5k1947
$endgroup$
$begingroup$
Shouldnt maximum possible number of adjacency matrices for $n$ node graph be $(n!)^2$ for both undirected and directed graphs? We can permute rows of adjacency matrix in n! ways. Similarly we can permute columns of adjacency matrix in n!. For both directed and undirected graphs, permuting any one or both of rows and columns will give new adjacency matrix. So shouldnt it be $(n!)^2$?
$endgroup$
– anir
Apr 7 '18 at 9:13
1
$begingroup$
@anir if you permute just the rows without applying the same permutation to the columns, you might not have an adjacency matrix anymore. (Consider that the adjacency matrix of an undirected graph must be symmetric, but permuting rows without permuting columns can break symmetry.)
$endgroup$
– Gregory J. Puleo
Dec 13 '18 at 14:28
add a comment |
$begingroup$
You shouldn't believe everything you read online, or at least, you should take it with a grain of salt. Basically the author is saying that any permutation of vertices will give an isomorphic graph, if you consider the vertices to be ordered. The total number of permutations of $n$ vertices is $n!$. However this is not to say that the number of DISTINCT isomorphic graphs is always $n!$ if you have $n$ vertices. Consider for example the graph with no edges, or the graph with all edges. These have no other distinct isomorphic graphs, other than themselves, so the number of isomorphic graphs for these is simply 1, regardless of the number of vertices $n$.
answered Jul 11 '15 at 19:43
user2566092user2566092
21.5k1947
$endgroup$
$begingroup$
Shouldnt maximum possible number of adjacency matrices for $n$ node graph be $(n!)^2$ for both undirected and directed graphs? We can permute rows of adjacency matrix in n! ways. Similarly we can permute columns of adjacency matrix in n!. For both directed and undirected graphs, permuting any one or both of rows and columns will give new adjacency matrix. So shouldnt it be $(n!)^2$?
$endgroup$
– anir
Apr 7 '18 at 9:13
1
$begingroup$
@anir if you permute just the rows without applying the same permutation to the columns, you might not have an adjacency matrix anymore. (Consider that the adjacency matrix of an undirected graph must be symmetric, but permuting rows without permuting columns can break symmetry.)
$endgroup$
– Gregory J. Puleo
Dec 13 '18 at 14:28
add a comment |
$begingroup$
You shouldn't believe everything you read online, or at least, you should take it with a grain of salt. Basically the author is saying that any permutation of vertices will give an isomorphic graph, if you consider the vertices to be ordered. The total number of permutations of $n$ vertices is $n!$. However this is not to say that the number of DISTINCT isomorphic graphs is always $n!$ if you have $n$ vertices. Consider for example the graph with no edges, or the graph with all edges. These have no other distinct isomorphic graphs, other than themselves, so the number of isomorphic graphs for these is simply 1, regardless of the number of vertices $n$.
answered Jul 11 '15 at 19:43
user2566092user2566092
21.5k1947
$endgroup$
You shouldn't believe everything you read online, or at least, you should take it with a grain of salt. Basically the author is saying that any permutation of vertices will give an isomorphic graph, if you consider the vertices to be ordered. The total number of permutations of $n$ vertices is $n!$. However this is not to say that the number of DISTINCT isomorphic graphs is always $n!$ if you have $n$ vertices. Consider for example the graph with no edges, or the graph with all edges. These have no other distinct isomorphic graphs, other than themselves, so the number of isomorphic graphs for these is simply 1, regardless of the number of vertices $n$.
answered Jul 11 '15 at 19:43
user2566092user2566092
21.5k1947
answered Jul 11 '15 at 19:43
user2566092user2566092
21.5k1947
answered Jul 11 '15 at 19:43
user2566092user2566092
21.5k1947
answered Jul 11 '15 at 19:43
user2566092user2566092
21.5k1947
21.5k1947
$begingroup$
Shouldnt maximum possible number of adjacency matrices for $n$ node graph be $(n!)^2$ for both undirected and directed graphs? We can permute rows of adjacency matrix in n! ways. Similarly we can permute columns of adjacency matrix in n!. For both directed and undirected graphs, permuting any one or both of rows and columns will give new adjacency matrix. So shouldnt it be $(n!)^2$?
$endgroup$
– anir
Apr 7 '18 at 9:13
1
$begingroup$
@anir if you permute just the rows without applying the same permutation to the columns, you might not have an adjacency matrix anymore. (Consider that the adjacency matrix of an undirected graph must be symmetric, but permuting rows without permuting columns can break symmetry.)
$endgroup$
– Gregory J. Puleo
Dec 13 '18 at 14:28
add a comment |
$begingroup$
Shouldnt maximum possible number of adjacency matrices for $n$ node graph be $(n!)^2$ for both undirected and directed graphs? We can permute rows of adjacency matrix in n! ways. Similarly we can permute columns of adjacency matrix in n!. For both directed and undirected graphs, permuting any one or both of rows and columns will give new adjacency matrix. So shouldnt it be $(n!)^2$?
$endgroup$
– anir
Apr 7 '18 at 9:13
1
$begingroup$
@anir if you permute just the rows without applying the same permutation to the columns, you might not have an adjacency matrix anymore. (Consider that the adjacency matrix of an undirected graph must be symmetric, but permuting rows without permuting columns can break symmetry.)
$endgroup$
– Gregory J. Puleo
Dec 13 '18 at 14:28
$begingroup$
Shouldnt maximum possible number of adjacency matrices for $n$ node graph be $(n!)^2$ for both undirected and directed graphs? We can permute rows of adjacency matrix in n! ways. Similarly we can permute columns of adjacency matrix in n!. For both directed and undirected graphs, permuting any one or both of rows and columns will give new adjacency matrix. So shouldnt it be $(n!)^2$?
$endgroup$
– anir
Apr 7 '18 at 9:13
$begingroup$
Shouldnt maximum possible number of adjacency matrices for $n$ node graph be $(n!)^2$ for both undirected and directed graphs? We can permute rows of adjacency matrix in n! ways. Similarly we can permute columns of adjacency matrix in n!. For both directed and undirected graphs, permuting any one or both of rows and columns will give new adjacency matrix. So shouldnt it be $(n!)^2$?
$endgroup$
– anir
Apr 7 '18 at 9:13
1
1
$begingroup$
@anir if you permute just the rows without applying the same permutation to the columns, you might not have an adjacency matrix anymore. (Consider that the adjacency matrix of an undirected graph must be symmetric, but permuting rows without permuting columns can break symmetry.)
$endgroup$
– Gregory J. Puleo
Dec 13 '18 at 14:28
$begingroup$
@anir if you permute just the rows without applying the same permutation to the columns, you might not have an adjacency matrix anymore. (Consider that the adjacency matrix of an undirected graph must be symmetric, but permuting rows without permuting columns can break symmetry.)
$endgroup$
– Gregory J. Puleo
Dec 13 '18 at 14:28
add a comment |
$begingroup$
The Accepted Answer above explains what interpretation might be placed on the expression $n!$, i.e. counting the number of labellings of vertices in a graph $G$ that has $n$ vertices. While such a labelling is required to get an adjacency matrix that represents a (simple) graph, it cannot account for the number of edges that we want such a graph to have. Moreover two different labellings may or may not lead to the same adjacency matrix for $G$.
If a graph $G$ has $n$ vertices and $e$ edges, the possible adjacency matrices, without restriction as to which labelling is chosen, are given by choosing $e$ of the possible $binom{n}{2}$ entries below the diagonal of the $ntimes n$ matrix (setting these to $1$ and the rest of the entries, including the diagonal, to zero).
The same count, $binom{binom{n}{2}}{e}$, is given by choosing an $e$-subset of the $binom{n}{2}$ edges in the complete graph $K_n$ on $n$ vertices.
answered Dec 13 '18 at 17:56
hardmathhardmath
29k953100
$endgroup$
add a comment |
$begingroup$
The Accepted Answer above explains what interpretation might be placed on the expression $n!$, i.e. counting the number of labellings of vertices in a graph $G$ that has $n$ vertices. While such a labelling is required to get an adjacency matrix that represents a (simple) graph, it cannot account for the number of edges that we want such a graph to have. Moreover two different labellings may or may not lead to the same adjacency matrix for $G$.
If a graph $G$ has $n$ vertices and $e$ edges, the possible adjacency matrices, without restriction as to which labelling is chosen, are given by choosing $e$ of the possible $binom{n}{2}$ entries below the diagonal of the $ntimes n$ matrix (setting these to $1$ and the rest of the entries, including the diagonal, to zero).
The same count, $binom{binom{n}{2}}{e}$, is given by choosing an $e$-subset of the $binom{n}{2}$ edges in the complete graph $K_n$ on $n$ vertices.
answered Dec 13 '18 at 17:56
hardmathhardmath
29k953100
$endgroup$
add a comment |
$begingroup$
The Accepted Answer above explains what interpretation might be placed on the expression $n!$, i.e. counting the number of labellings of vertices in a graph $G$ that has $n$ vertices. While such a labelling is required to get an adjacency matrix that represents a (simple) graph, it cannot account for the number of edges that we want such a graph to have. Moreover two different labellings may or may not lead to the same adjacency matrix for $G$.
If a graph $G$ has $n$ vertices and $e$ edges, the possible adjacency matrices, without restriction as to which labelling is chosen, are given by choosing $e$ of the possible $binom{n}{2}$ entries below the diagonal of the $ntimes n$ matrix (setting these to $1$ and the rest of the entries, including the diagonal, to zero).
The same count, $binom{binom{n}{2}}{e}$, is given by choosing an $e$-subset of the $binom{n}{2}$ edges in the complete graph $K_n$ on $n$ vertices.
answered Dec 13 '18 at 17:56
hardmathhardmath
29k953100
$endgroup$
The Accepted Answer above explains what interpretation might be placed on the expression $n!$, i.e. counting the number of labellings of vertices in a graph $G$ that has $n$ vertices. While such a labelling is required to get an adjacency matrix that represents a (simple) graph, it cannot account for the number of edges that we want such a graph to have. Moreover two different labellings may or may not lead to the same adjacency matrix for $G$.
If a graph $G$ has $n$ vertices and $e$ edges, the possible adjacency matrices, without restriction as to which labelling is chosen, are given by choosing $e$ of the possible $binom{n}{2}$ entries below the diagonal of the $ntimes n$ matrix (setting these to $1$ and the rest of the entries, including the diagonal, to zero).
The same count, $binom{binom{n}{2}}{e}$, is given by choosing an $e$-subset of the $binom{n}{2}$ edges in the complete graph $K_n$ on $n$ vertices.
answered Dec 13 '18 at 17:56
hardmathhardmath
29k953100
answered Dec 13 '18 at 17:56
hardmathhardmath
29k953100
answered Dec 13 '18 at 17:56
hardmathhardmath
29k953100
answered Dec 13 '18 at 17:56
hardmathhardmath
29k953100
29k953100
add a comment |
add a comment |
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.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1357782%2fhow-many-different-adjacency-matrix-with-n-vertices-and-e-edges-have%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
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
$begingroup$
I don't see where the note you linked above says any thing like that. A count of adjacency matrices for graphs with $N$ vertices and $E$ edges will depend on both $N$ and $E$.
$endgroup$
– hardmath
Dec 13 '18 at 17:38