To find the number of spanning trees of a graph given its adjacency matrix
A graph $G$ has the following adjacency matrix:
$$ begin{pmatrix}
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \
0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \
0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \
0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \
1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \
end{pmatrix} $$
I have created a Laplacian matrix from that adjacency matrix, and I know that the determinant of the Laplacian will give you the result, however, I doubt that our prof would make us find the determinant of an 8x8 matrix and I've read around that you can minimize the size of matrix (by deleting corresponding col & rows), though I don't see how I could reduce the size of my 8x8 Laplacian matrix without it losing its unique graph identity?
matrices graph-theory determinant graph-laplacian
edited Dec 10 at 19:58
hardmath
28.7k94994
asked Dec 7 at 16:11
DevAllanPer
1296
add a comment |
A graph $G$ has the following adjacency matrix:
$$ begin{pmatrix}
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \
0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \
0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \
0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \
1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \
end{pmatrix} $$
I have created a Laplacian matrix from that adjacency matrix, and I know that the determinant of the Laplacian will give you the result, however, I doubt that our prof would make us find the determinant of an 8x8 matrix and I've read around that you can minimize the size of matrix (by deleting corresponding col & rows), though I don't see how I could reduce the size of my 8x8 Laplacian matrix without it losing its unique graph identity?
matrices graph-theory determinant graph-laplacian
edited Dec 10 at 19:58
hardmath
28.7k94994
asked Dec 7 at 16:11
DevAllanPer
1296
The missing entry is 1, sorry, forgot to clarify that. Do you have anything to say in regards to the question I asked though?
– DevAllanPer
Dec 7 at 16:31
3
Could you include the Laplacian matrix in question?
– coffeemath
Dec 7 at 19:08
I think there's a typo on that matrix, but anyhow im sure my understanding is correct. The number of spanning trees should be equal to the determinant of the 7x7 Laplacian matrix (7x7 cuz you can remove any row and column)
– DevAllanPer
Dec 9 at 16:32
As the author of the Question, you need to assume responsibility for stating a problem (that you want help with) correctly. Readers depend on you to be the expert on what exactly is being asked, so that they can supply helpful Answers. As promised, I edited the Question to show how math notation can be used on the site (see this brief introduction and its links for more information). At a minimum you should supply the Laplacian matrix that you created and explain what difficulty you encountered proceeding from there.
– hardmath
Dec 10 at 18:14
i already took the exam. thanks anyway
– DevAllanPer
Dec 12 at 2:04
add a comment |
A graph $G$ has the following adjacency matrix:
$$ begin{pmatrix}
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \
0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \
0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \
0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \
1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \
end{pmatrix} $$
I have created a Laplacian matrix from that adjacency matrix, and I know that the determinant of the Laplacian will give you the result, however, I doubt that our prof would make us find the determinant of an 8x8 matrix and I've read around that you can minimize the size of matrix (by deleting corresponding col & rows), though I don't see how I could reduce the size of my 8x8 Laplacian matrix without it losing its unique graph identity?
matrices graph-theory determinant graph-laplacian
edited Dec 10 at 19:58
hardmath
28.7k94994
asked Dec 7 at 16:11
DevAllanPer
1296
A graph $G$ has the following adjacency matrix:
$$ begin{pmatrix}
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \
0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \
0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \
0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \
1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \
end{pmatrix} $$
I have created a Laplacian matrix from that adjacency matrix, and I know that the determinant of the Laplacian will give you the result, however, I doubt that our prof would make us find the determinant of an 8x8 matrix and I've read around that you can minimize the size of matrix (by deleting corresponding col & rows), though I don't see how I could reduce the size of my 8x8 Laplacian matrix without it losing its unique graph identity?
matrices graph-theory determinant graph-laplacian
matrices graph-theory determinant graph-laplacian
edited Dec 10 at 19:58
hardmath
28.7k94994
asked Dec 7 at 16:11
DevAllanPer
1296
edited Dec 10 at 19:58
hardmath
28.7k94994
asked Dec 7 at 16:11
DevAllanPer
1296
edited Dec 10 at 19:58
hardmath
28.7k94994
edited Dec 10 at 19:58
hardmath
28.7k94994
edited Dec 10 at 19:58
hardmath
28.7k94994
28.7k94994
asked Dec 7 at 16:11
DevAllanPer
1296
asked Dec 7 at 16:11
DevAllanPer
1296
asked Dec 7 at 16:11
DevAllanPer
1296
1296
The missing entry is 1, sorry, forgot to clarify that. Do you have anything to say in regards to the question I asked though?
– DevAllanPer
Dec 7 at 16:31
3
Could you include the Laplacian matrix in question?
– coffeemath
Dec 7 at 19:08
I think there's a typo on that matrix, but anyhow im sure my understanding is correct. The number of spanning trees should be equal to the determinant of the 7x7 Laplacian matrix (7x7 cuz you can remove any row and column)
– DevAllanPer
Dec 9 at 16:32
As the author of the Question, you need to assume responsibility for stating a problem (that you want help with) correctly. Readers depend on you to be the expert on what exactly is being asked, so that they can supply helpful Answers. As promised, I edited the Question to show how math notation can be used on the site (see this brief introduction and its links for more information). At a minimum you should supply the Laplacian matrix that you created and explain what difficulty you encountered proceeding from there.
– hardmath
Dec 10 at 18:14
i already took the exam. thanks anyway
– DevAllanPer
Dec 12 at 2:04
add a comment |
The missing entry is 1, sorry, forgot to clarify that. Do you have anything to say in regards to the question I asked though?
– DevAllanPer
Dec 7 at 16:31
3
Could you include the Laplacian matrix in question?
– coffeemath
Dec 7 at 19:08
I think there's a typo on that matrix, but anyhow im sure my understanding is correct. The number of spanning trees should be equal to the determinant of the 7x7 Laplacian matrix (7x7 cuz you can remove any row and column)
– DevAllanPer
Dec 9 at 16:32
As the author of the Question, you need to assume responsibility for stating a problem (that you want help with) correctly. Readers depend on you to be the expert on what exactly is being asked, so that they can supply helpful Answers. As promised, I edited the Question to show how math notation can be used on the site (see this brief introduction and its links for more information). At a minimum you should supply the Laplacian matrix that you created and explain what difficulty you encountered proceeding from there.
– hardmath
Dec 10 at 18:14
i already took the exam. thanks anyway
– DevAllanPer
Dec 12 at 2:04
The missing entry is 1, sorry, forgot to clarify that. Do you have anything to say in regards to the question I asked though?
– DevAllanPer
Dec 7 at 16:31
The missing entry is 1, sorry, forgot to clarify that. Do you have anything to say in regards to the question I asked though?
– DevAllanPer
Dec 7 at 16:31
3
3
Could you include the Laplacian matrix in question?
– coffeemath
Dec 7 at 19:08
Could you include the Laplacian matrix in question?
– coffeemath
Dec 7 at 19:08
I think there's a typo on that matrix, but anyhow im sure my understanding is correct. The number of spanning trees should be equal to the determinant of the 7x7 Laplacian matrix (7x7 cuz you can remove any row and column)
– DevAllanPer
Dec 9 at 16:32
I think there's a typo on that matrix, but anyhow im sure my understanding is correct. The number of spanning trees should be equal to the determinant of the 7x7 Laplacian matrix (7x7 cuz you can remove any row and column)
– DevAllanPer
Dec 9 at 16:32
As the author of the Question, you need to assume responsibility for stating a problem (that you want help with) correctly. Readers depend on you to be the expert on what exactly is being asked, so that they can supply helpful Answers. As promised, I edited the Question to show how math notation can be used on the site (see this brief introduction and its links for more information). At a minimum you should supply the Laplacian matrix that you created and explain what difficulty you encountered proceeding from there.
– hardmath
Dec 10 at 18:14
As the author of the Question, you need to assume responsibility for stating a problem (that you want help with) correctly. Readers depend on you to be the expert on what exactly is being asked, so that they can supply helpful Answers. As promised, I edited the Question to show how math notation can be used on the site (see this brief introduction and its links for more information). At a minimum you should supply the Laplacian matrix that you created and explain what difficulty you encountered proceeding from there.
– hardmath
Dec 10 at 18:14
i already took the exam. thanks anyway
– DevAllanPer
Dec 12 at 2:04
i already took the exam. thanks anyway
– DevAllanPer
Dec 12 at 2:04
add a comment |
active
oldest
votes
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%2f3030070%2fto-find-the-number-of-spanning-trees-of-a-graph-given-its-adjacency-matrix%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3030070%2fto-find-the-number-of-spanning-trees-of-a-graph-given-its-adjacency-matrix%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
The missing entry is 1, sorry, forgot to clarify that. Do you have anything to say in regards to the question I asked though?
– DevAllanPer
Dec 7 at 16:31
3
Could you include the Laplacian matrix in question?
– coffeemath
Dec 7 at 19:08
I think there's a typo on that matrix, but anyhow im sure my understanding is correct. The number of spanning trees should be equal to the determinant of the 7x7 Laplacian matrix (7x7 cuz you can remove any row and column)
– DevAllanPer
Dec 9 at 16:32
As the author of the Question, you need to assume responsibility for stating a problem (that you want help with) correctly. Readers depend on you to be the expert on what exactly is being asked, so that they can supply helpful Answers. As promised, I edited the Question to show how math notation can be used on the site (see this brief introduction and its links for more information). At a minimum you should supply the Laplacian matrix that you created and explain what difficulty you encountered proceeding from there.
– hardmath
Dec 10 at 18:14
i already took the exam. thanks anyway
– DevAllanPer
Dec 12 at 2:04