Mixing
Can I find the connected components of a graph using matrix operations on the graph's adjacency matrix?
$begingroup$
If I have an adjacency matrix for a graph, can I do a series of matrix operations on the adjacency matrix to find the connected components of the graph?
linear-algebra graph-theory connectedness algebraic-graph-theory spectral-graph-theory
edited Jan 18 '15 at 5:17
ml0105
11.4k21538
asked Jan 16 '15 at 16:22
user2073068user2073068
3813
$endgroup$
add a comment |
$begingroup$
If I have an adjacency matrix for a graph, can I do a series of matrix operations on the adjacency matrix to find the connected components of the graph?
linear-algebra graph-theory connectedness algebraic-graph-theory spectral-graph-theory
edited Jan 18 '15 at 5:17
ml0105
11.4k21538
asked Jan 16 '15 at 16:22
user2073068user2073068
3813
$endgroup$
$begingroup$
Hint: square the matrix, cube the matrix etc... to power of matrix to number of nodes
$endgroup$
– sashas
Jan 16 '15 at 16:24
add a comment |
$begingroup$
If I have an adjacency matrix for a graph, can I do a series of matrix operations on the adjacency matrix to find the connected components of the graph?
linear-algebra graph-theory connectedness algebraic-graph-theory spectral-graph-theory
edited Jan 18 '15 at 5:17
ml0105
11.4k21538
asked Jan 16 '15 at 16:22
user2073068user2073068
3813
$endgroup$
If I have an adjacency matrix for a graph, can I do a series of matrix operations on the adjacency matrix to find the connected components of the graph?
linear-algebra graph-theory connectedness algebraic-graph-theory spectral-graph-theory
linear-algebra graph-theory connectedness algebraic-graph-theory spectral-graph-theory
edited Jan 18 '15 at 5:17
ml0105
11.4k21538
asked Jan 16 '15 at 16:22
user2073068user2073068
3813
edited Jan 18 '15 at 5:17
ml0105
11.4k21538
asked Jan 16 '15 at 16:22
user2073068user2073068
3813
edited Jan 18 '15 at 5:17
ml0105
11.4k21538
edited Jan 18 '15 at 5:17
ml0105
11.4k21538
edited Jan 18 '15 at 5:17
ml0105
11.4k21538
11.4k21538
asked Jan 16 '15 at 16:22
user2073068user2073068
3813
asked Jan 16 '15 at 16:22
user2073068user2073068
3813
asked Jan 16 '15 at 16:22
user2073068user2073068
3813
3813
$begingroup$
Hint: square the matrix, cube the matrix etc... to power of matrix to number of nodes
$endgroup$
– sashas
Jan 16 '15 at 16:24
add a comment |
$begingroup$
Hint: square the matrix, cube the matrix etc... to power of matrix to number of nodes
$endgroup$
– sashas
Jan 16 '15 at 16:24
$begingroup$
Hint: square the matrix, cube the matrix etc... to power of matrix to number of nodes
$endgroup$
– sashas
Jan 16 '15 at 16:24
$begingroup$
Hint: square the matrix, cube the matrix etc... to power of matrix to number of nodes
$endgroup$
– sashas
Jan 16 '15 at 16:24
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Yes! Perhaps the easiest way is to obtain the Laplacian matrix and find a basis of its kernel.
In words, call $A$ your adjacency matrix. Obtain the diagonal matrix $D$ of the degrees of each vertex. Set $L=D-A$. Now $dim ker L = $ number of connected components. Moreover, the kernel of $L$ is spanned by vectors constant on each connected component.
For example, a block diagonal matrix $A=diag(A_1,dots,A_n)$, with blocks representing the connected components of your graph, will have an associated Laplacian matrix $L$ with kernel spanned by vectors $v_i=(0,dots,0,1,dots,1,0,dots,0)$ where the string of ones is as long as the number of vertices in $A_i$, and specifically in the entries corresponding to the vertices of that connected component.
EDIT: Edited to more directly answer the original question. Sorry that I misread it earlier!
answered Jan 16 '15 at 16:30
MaxMax
2,207711
$endgroup$
$begingroup$
In what text would someone find a result such as this?
$endgroup$
– Paul Sundheim
Jan 16 '15 at 17:09
$begingroup$
@PaulSundheim By googling "spectral graph theory book" I found this book by Fan Chung math.ucsd.edu/~fan/cbms.pdf
$endgroup$
– Max
Jan 16 '15 at 20:56
1
$begingroup$
Sorry, but this doesn't quite answer my question. I would like to find the actual connected components, not just how many there are. Thank you, though!
$endgroup$
– user2073068
Jan 18 '15 at 23:43
$begingroup$
@user2073068 I think slightly better can be done. My memory is failing me, so I can't remember specifics (which is why I didn't explain above), but I think you can find the connected components easily from the Laplacian. Maybe by checking the eigenbasis corresponding to the eigenvalue 0? If I have time to check I will augment my answer.
$endgroup$
– Max
Jan 18 '15 at 23:56
$begingroup$
@user2073068 I have edited my answer to more directly answer your problem. I apologize for reading your question too quickly earlier!
$endgroup$
– Max
Jan 19 '15 at 3:27
|
show 6 more comments
$begingroup$
If you want use the adjacency matrix and you need the actual components, not just their number, then a brute force approach is as follows. Suppose the graph has adjacency matrix $A$ and $n$ vertices. Compute $M=(A+I)^n$. Now define vertices $u$ and $v$ to be equivalent if $M_{u,v} ne 0$. The equivalence classes of this relation are the connected components of the graph.
This works because $M_{u,v}$ is positive if and only if there is a walk of length at most $n-1$ from from $u$ to $v$, and if two vertices are in the same component they are joined by a walk of length at most $n$.
It is not practical because no-one in their right mind would compute such a large power of $A$. It could be made workable, but there are other methods for finding components, e.g., find a spanning forest.
answered Jan 18 '15 at 17:12
Chris GodsilChris Godsil
11.6k21634
$endgroup$
add a comment |
$begingroup$
If the graph is regular, the multiplicity of the largest eigenvalue of the adjacency matrix will provide the same result. Let $X_{1}, ..., X_{n}$ be the connected components of the graph. Then these are the diagonal submatrices of the adjacency matrix. And so $p_{G}(lambda) = prod_{i=1}^{n} p_{X_{i}}(lambda)$, where $p_{G}(lambda)$ is the characteristic polynomial of $lambda$.
Since $G$ is $k$-regular, $lambda = k$ is the dominant eigenvalue of each component as well as of $G$. And so $k$ appears $n$ times.
If $G$ is not regular, then you should use the Laplacian method as described above.
answered Jan 18 '15 at 5:17
ml0105ml0105
11.4k21538
$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%2f1106870%2fcan-i-find-the-connected-components-of-a-graph-using-matrix-operations-on-the-gr%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Yes! Perhaps the easiest way is to obtain the Laplacian matrix and find a basis of its kernel.
In words, call $A$ your adjacency matrix. Obtain the diagonal matrix $D$ of the degrees of each vertex. Set $L=D-A$. Now $dim ker L = $ number of connected components. Moreover, the kernel of $L$ is spanned by vectors constant on each connected component.
For example, a block diagonal matrix $A=diag(A_1,dots,A_n)$, with blocks representing the connected components of your graph, will have an associated Laplacian matrix $L$ with kernel spanned by vectors $v_i=(0,dots,0,1,dots,1,0,dots,0)$ where the string of ones is as long as the number of vertices in $A_i$, and specifically in the entries corresponding to the vertices of that connected component.
EDIT: Edited to more directly answer the original question. Sorry that I misread it earlier!
answered Jan 16 '15 at 16:30
MaxMax
2,207711
$endgroup$
$begingroup$
In what text would someone find a result such as this?
$endgroup$
– Paul Sundheim
Jan 16 '15 at 17:09
$begingroup$
@PaulSundheim By googling "spectral graph theory book" I found this book by Fan Chung math.ucsd.edu/~fan/cbms.pdf
$endgroup$
– Max
Jan 16 '15 at 20:56
1
$begingroup$
Sorry, but this doesn't quite answer my question. I would like to find the actual connected components, not just how many there are. Thank you, though!
$endgroup$
– user2073068
Jan 18 '15 at 23:43
$begingroup$
@user2073068 I think slightly better can be done. My memory is failing me, so I can't remember specifics (which is why I didn't explain above), but I think you can find the connected components easily from the Laplacian. Maybe by checking the eigenbasis corresponding to the eigenvalue 0? If I have time to check I will augment my answer.
$endgroup$
– Max
Jan 18 '15 at 23:56
$begingroup$
@user2073068 I have edited my answer to more directly answer your problem. I apologize for reading your question too quickly earlier!
$endgroup$
– Max
Jan 19 '15 at 3:27
|
show 6 more comments
$begingroup$
Yes! Perhaps the easiest way is to obtain the Laplacian matrix and find a basis of its kernel.
In words, call $A$ your adjacency matrix. Obtain the diagonal matrix $D$ of the degrees of each vertex. Set $L=D-A$. Now $dim ker L = $ number of connected components. Moreover, the kernel of $L$ is spanned by vectors constant on each connected component.
For example, a block diagonal matrix $A=diag(A_1,dots,A_n)$, with blocks representing the connected components of your graph, will have an associated Laplacian matrix $L$ with kernel spanned by vectors $v_i=(0,dots,0,1,dots,1,0,dots,0)$ where the string of ones is as long as the number of vertices in $A_i$, and specifically in the entries corresponding to the vertices of that connected component.
EDIT: Edited to more directly answer the original question. Sorry that I misread it earlier!
answered Jan 16 '15 at 16:30
MaxMax
2,207711
$endgroup$
$begingroup$
In what text would someone find a result such as this?
$endgroup$
– Paul Sundheim
Jan 16 '15 at 17:09
$begingroup$
@PaulSundheim By googling "spectral graph theory book" I found this book by Fan Chung math.ucsd.edu/~fan/cbms.pdf
$endgroup$
– Max
Jan 16 '15 at 20:56
1
$begingroup$
Sorry, but this doesn't quite answer my question. I would like to find the actual connected components, not just how many there are. Thank you, though!
$endgroup$
– user2073068
Jan 18 '15 at 23:43
$begingroup$
@user2073068 I think slightly better can be done. My memory is failing me, so I can't remember specifics (which is why I didn't explain above), but I think you can find the connected components easily from the Laplacian. Maybe by checking the eigenbasis corresponding to the eigenvalue 0? If I have time to check I will augment my answer.
$endgroup$
– Max
Jan 18 '15 at 23:56
$begingroup$
@user2073068 I have edited my answer to more directly answer your problem. I apologize for reading your question too quickly earlier!
$endgroup$
– Max
Jan 19 '15 at 3:27
|
show 6 more comments
$begingroup$
Yes! Perhaps the easiest way is to obtain the Laplacian matrix and find a basis of its kernel.
In words, call $A$ your adjacency matrix. Obtain the diagonal matrix $D$ of the degrees of each vertex. Set $L=D-A$. Now $dim ker L = $ number of connected components. Moreover, the kernel of $L$ is spanned by vectors constant on each connected component.
For example, a block diagonal matrix $A=diag(A_1,dots,A_n)$, with blocks representing the connected components of your graph, will have an associated Laplacian matrix $L$ with kernel spanned by vectors $v_i=(0,dots,0,1,dots,1,0,dots,0)$ where the string of ones is as long as the number of vertices in $A_i$, and specifically in the entries corresponding to the vertices of that connected component.
EDIT: Edited to more directly answer the original question. Sorry that I misread it earlier!
answered Jan 16 '15 at 16:30
MaxMax
2,207711
$endgroup$
Yes! Perhaps the easiest way is to obtain the Laplacian matrix and find a basis of its kernel.
In words, call $A$ your adjacency matrix. Obtain the diagonal matrix $D$ of the degrees of each vertex. Set $L=D-A$. Now $dim ker L = $ number of connected components. Moreover, the kernel of $L$ is spanned by vectors constant on each connected component.
For example, a block diagonal matrix $A=diag(A_1,dots,A_n)$, with blocks representing the connected components of your graph, will have an associated Laplacian matrix $L$ with kernel spanned by vectors $v_i=(0,dots,0,1,dots,1,0,dots,0)$ where the string of ones is as long as the number of vertices in $A_i$, and specifically in the entries corresponding to the vertices of that connected component.
EDIT: Edited to more directly answer the original question. Sorry that I misread it earlier!
answered Jan 16 '15 at 16:30
MaxMax
2,207711
edited Jan 2 at 22:15
answered Jan 16 '15 at 16:30
MaxMax
2,207711
answered Jan 16 '15 at 16:30
MaxMax
2,207711
answered Jan 16 '15 at 16:30
MaxMax
2,207711
2,207711
$begingroup$
In what text would someone find a result such as this?
$endgroup$
– Paul Sundheim
Jan 16 '15 at 17:09
$begingroup$
@PaulSundheim By googling "spectral graph theory book" I found this book by Fan Chung math.ucsd.edu/~fan/cbms.pdf
$endgroup$
– Max
Jan 16 '15 at 20:56
1
$begingroup$
Sorry, but this doesn't quite answer my question. I would like to find the actual connected components, not just how many there are. Thank you, though!
$endgroup$
– user2073068
Jan 18 '15 at 23:43
$begingroup$
@user2073068 I think slightly better can be done. My memory is failing me, so I can't remember specifics (which is why I didn't explain above), but I think you can find the connected components easily from the Laplacian. Maybe by checking the eigenbasis corresponding to the eigenvalue 0? If I have time to check I will augment my answer.
$endgroup$
– Max
Jan 18 '15 at 23:56
$begingroup$
@user2073068 I have edited my answer to more directly answer your problem. I apologize for reading your question too quickly earlier!
$endgroup$
– Max
Jan 19 '15 at 3:27
|
show 6 more comments
$begingroup$
In what text would someone find a result such as this?
$endgroup$
– Paul Sundheim
Jan 16 '15 at 17:09
$begingroup$
@PaulSundheim By googling "spectral graph theory book" I found this book by Fan Chung math.ucsd.edu/~fan/cbms.pdf
$endgroup$
– Max
Jan 16 '15 at 20:56
1
$begingroup$
Sorry, but this doesn't quite answer my question. I would like to find the actual connected components, not just how many there are. Thank you, though!
$endgroup$
– user2073068
Jan 18 '15 at 23:43
$begingroup$
@user2073068 I think slightly better can be done. My memory is failing me, so I can't remember specifics (which is why I didn't explain above), but I think you can find the connected components easily from the Laplacian. Maybe by checking the eigenbasis corresponding to the eigenvalue 0? If I have time to check I will augment my answer.
$endgroup$
– Max
Jan 18 '15 at 23:56
$begingroup$
@user2073068 I have edited my answer to more directly answer your problem. I apologize for reading your question too quickly earlier!
$endgroup$
– Max
Jan 19 '15 at 3:27
$begingroup$
In what text would someone find a result such as this?
$endgroup$
– Paul Sundheim
Jan 16 '15 at 17:09
$begingroup$
In what text would someone find a result such as this?
$endgroup$
– Paul Sundheim
Jan 16 '15 at 17:09
$begingroup$
@PaulSundheim By googling "spectral graph theory book" I found this book by Fan Chung math.ucsd.edu/~fan/cbms.pdf
$endgroup$
– Max
Jan 16 '15 at 20:56
$begingroup$
@PaulSundheim By googling "spectral graph theory book" I found this book by Fan Chung math.ucsd.edu/~fan/cbms.pdf
$endgroup$
– Max
Jan 16 '15 at 20:56
1
1
$begingroup$
Sorry, but this doesn't quite answer my question. I would like to find the actual connected components, not just how many there are. Thank you, though!
$endgroup$
– user2073068
Jan 18 '15 at 23:43
$begingroup$
Sorry, but this doesn't quite answer my question. I would like to find the actual connected components, not just how many there are. Thank you, though!
$endgroup$
– user2073068
Jan 18 '15 at 23:43
$begingroup$
@user2073068 I think slightly better can be done. My memory is failing me, so I can't remember specifics (which is why I didn't explain above), but I think you can find the connected components easily from the Laplacian. Maybe by checking the eigenbasis corresponding to the eigenvalue 0? If I have time to check I will augment my answer.
$endgroup$
– Max
Jan 18 '15 at 23:56
$begingroup$
@user2073068 I think slightly better can be done. My memory is failing me, so I can't remember specifics (which is why I didn't explain above), but I think you can find the connected components easily from the Laplacian. Maybe by checking the eigenbasis corresponding to the eigenvalue 0? If I have time to check I will augment my answer.
$endgroup$
– Max
Jan 18 '15 at 23:56
$begingroup$
@user2073068 I have edited my answer to more directly answer your problem. I apologize for reading your question too quickly earlier!
$endgroup$
– Max
Jan 19 '15 at 3:27
$begingroup$
@user2073068 I have edited my answer to more directly answer your problem. I apologize for reading your question too quickly earlier!
$endgroup$
– Max
Jan 19 '15 at 3:27
|
show 6 more comments
$begingroup$
If you want use the adjacency matrix and you need the actual components, not just their number, then a brute force approach is as follows. Suppose the graph has adjacency matrix $A$ and $n$ vertices. Compute $M=(A+I)^n$. Now define vertices $u$ and $v$ to be equivalent if $M_{u,v} ne 0$. The equivalence classes of this relation are the connected components of the graph.
This works because $M_{u,v}$ is positive if and only if there is a walk of length at most $n-1$ from from $u$ to $v$, and if two vertices are in the same component they are joined by a walk of length at most $n$.
It is not practical because no-one in their right mind would compute such a large power of $A$. It could be made workable, but there are other methods for finding components, e.g., find a spanning forest.
answered Jan 18 '15 at 17:12
Chris GodsilChris Godsil
11.6k21634
$endgroup$
add a comment |
$begingroup$
If you want use the adjacency matrix and you need the actual components, not just their number, then a brute force approach is as follows. Suppose the graph has adjacency matrix $A$ and $n$ vertices. Compute $M=(A+I)^n$. Now define vertices $u$ and $v$ to be equivalent if $M_{u,v} ne 0$. The equivalence classes of this relation are the connected components of the graph.
This works because $M_{u,v}$ is positive if and only if there is a walk of length at most $n-1$ from from $u$ to $v$, and if two vertices are in the same component they are joined by a walk of length at most $n$.
It is not practical because no-one in their right mind would compute such a large power of $A$. It could be made workable, but there are other methods for finding components, e.g., find a spanning forest.
answered Jan 18 '15 at 17:12
Chris GodsilChris Godsil
11.6k21634
$endgroup$
add a comment |
$begingroup$
If you want use the adjacency matrix and you need the actual components, not just their number, then a brute force approach is as follows. Suppose the graph has adjacency matrix $A$ and $n$ vertices. Compute $M=(A+I)^n$. Now define vertices $u$ and $v$ to be equivalent if $M_{u,v} ne 0$. The equivalence classes of this relation are the connected components of the graph.
This works because $M_{u,v}$ is positive if and only if there is a walk of length at most $n-1$ from from $u$ to $v$, and if two vertices are in the same component they are joined by a walk of length at most $n$.
It is not practical because no-one in their right mind would compute such a large power of $A$. It could be made workable, but there are other methods for finding components, e.g., find a spanning forest.
answered Jan 18 '15 at 17:12
Chris GodsilChris Godsil
11.6k21634
$endgroup$
If you want use the adjacency matrix and you need the actual components, not just their number, then a brute force approach is as follows. Suppose the graph has adjacency matrix $A$ and $n$ vertices. Compute $M=(A+I)^n$. Now define vertices $u$ and $v$ to be equivalent if $M_{u,v} ne 0$. The equivalence classes of this relation are the connected components of the graph.
This works because $M_{u,v}$ is positive if and only if there is a walk of length at most $n-1$ from from $u$ to $v$, and if two vertices are in the same component they are joined by a walk of length at most $n$.
It is not practical because no-one in their right mind would compute such a large power of $A$. It could be made workable, but there are other methods for finding components, e.g., find a spanning forest.
answered Jan 18 '15 at 17:12
Chris GodsilChris Godsil
11.6k21634
edited Jan 19 '15 at 0:43
answered Jan 18 '15 at 17:12
Chris GodsilChris Godsil
11.6k21634
answered Jan 18 '15 at 17:12
Chris GodsilChris Godsil
11.6k21634
answered Jan 18 '15 at 17:12
Chris GodsilChris Godsil
11.6k21634
11.6k21634
add a comment |
add a comment |
$begingroup$
If the graph is regular, the multiplicity of the largest eigenvalue of the adjacency matrix will provide the same result. Let $X_{1}, ..., X_{n}$ be the connected components of the graph. Then these are the diagonal submatrices of the adjacency matrix. And so $p_{G}(lambda) = prod_{i=1}^{n} p_{X_{i}}(lambda)$, where $p_{G}(lambda)$ is the characteristic polynomial of $lambda$.
Since $G$ is $k$-regular, $lambda = k$ is the dominant eigenvalue of each component as well as of $G$. And so $k$ appears $n$ times.
If $G$ is not regular, then you should use the Laplacian method as described above.
answered Jan 18 '15 at 5:17
ml0105ml0105
11.4k21538
$endgroup$
add a comment |
$begingroup$
If the graph is regular, the multiplicity of the largest eigenvalue of the adjacency matrix will provide the same result. Let $X_{1}, ..., X_{n}$ be the connected components of the graph. Then these are the diagonal submatrices of the adjacency matrix. And so $p_{G}(lambda) = prod_{i=1}^{n} p_{X_{i}}(lambda)$, where $p_{G}(lambda)$ is the characteristic polynomial of $lambda$.
Since $G$ is $k$-regular, $lambda = k$ is the dominant eigenvalue of each component as well as of $G$. And so $k$ appears $n$ times.
If $G$ is not regular, then you should use the Laplacian method as described above.
answered Jan 18 '15 at 5:17
ml0105ml0105
11.4k21538
$endgroup$
add a comment |
$begingroup$
If the graph is regular, the multiplicity of the largest eigenvalue of the adjacency matrix will provide the same result. Let $X_{1}, ..., X_{n}$ be the connected components of the graph. Then these are the diagonal submatrices of the adjacency matrix. And so $p_{G}(lambda) = prod_{i=1}^{n} p_{X_{i}}(lambda)$, where $p_{G}(lambda)$ is the characteristic polynomial of $lambda$.
Since $G$ is $k$-regular, $lambda = k$ is the dominant eigenvalue of each component as well as of $G$. And so $k$ appears $n$ times.
If $G$ is not regular, then you should use the Laplacian method as described above.
answered Jan 18 '15 at 5:17
ml0105ml0105
11.4k21538
$endgroup$
If the graph is regular, the multiplicity of the largest eigenvalue of the adjacency matrix will provide the same result. Let $X_{1}, ..., X_{n}$ be the connected components of the graph. Then these are the diagonal submatrices of the adjacency matrix. And so $p_{G}(lambda) = prod_{i=1}^{n} p_{X_{i}}(lambda)$, where $p_{G}(lambda)$ is the characteristic polynomial of $lambda$.
Since $G$ is $k$-regular, $lambda = k$ is the dominant eigenvalue of each component as well as of $G$. And so $k$ appears $n$ times.
If $G$ is not regular, then you should use the Laplacian method as described above.
answered Jan 18 '15 at 5:17
ml0105ml0105
11.4k21538
answered Jan 18 '15 at 5:17
ml0105ml0105
11.4k21538
answered Jan 18 '15 at 5:17
ml0105ml0105
11.4k21538
answered Jan 18 '15 at 5:17
ml0105ml0105
11.4k21538
11.4k21538
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%2f1106870%2fcan-i-find-the-connected-components-of-a-graph-using-matrix-operations-on-the-gr%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$
Hint: square the matrix, cube the matrix etc... to power of matrix to number of nodes
$endgroup$
– sashas
Jan 16 '15 at 16:24