Determining the equivalence classes of an equivalence relation represented by graph via its adjacent matrix.
up vote
0
down vote
favorite
Good day,
I wanted to write a programme in python which given the inputs n,E , where n is the number of nodes and E a list of edges gives me certain properties about that graph.
I'm mainly interested in 3 things :
-reflexivity
-symmetry
-transitivity
To determine whether the graph represents an equivalence relation and given that it is one I want to get the equivalence classes of that relation.
Now there is a standard way of doing this completely without any adjacent matrices but I found them to be so useful !
For instance : a graph is reflexive if the corresponding adjacent matrix has all 1 on the main diagonal. Or the graph is symmetric if the matrix is symmetric . Absolutely beautiful.
Mathematical notation would be :
Let $A in mathbb R^{n*n}$ be the adjacent matrix of a Graph with entries $a_{ij}$.
Reflexive : $prodlimits_{i=1}^{n}a_{ii} = 1 $
Symmetric: $a_{ij} = a_{ji} , forall i,j = 1,...,n$
Transitivity : if $a_{ij} = a_{jk} = 1$ and $ knot=i $ then $a_{ik}=1$
I already successfully implemented those.
Now I want to get said equivalence classes of that relation from the matrix and it proofed to be harder than thought...
Trying to get a feel I just came up with some graphs and corresponding matrices and had a look at them.
I found that equivalence classes have a property when represented in graphs, they form a circle . I'm not sure if they always form a circle in both directions but I feel like they do .Now finding that circle in the matrix , I recognized that an equivalence class looks like a block in a matrix but I'm not sure if that always checks out either.
As an example to clarify what Im trying to say:
let $G$ be a Graph with Nodes $N={0,1,2,3}$ and Edges $E={(1,2),(2,1),(2,3),(3,2),(1,3),(3,1),(i,i) } $ with $ i=0,1,2,3$
This Graph is definetly describing an equivalence Relation and has 2 equivalence classes: ${[0],[1,2,3]}$
The corresponding adjacent matrix looks like this:
$begin{bmatrix}1 & 0 & 0 &0\0 & 1 & 1&1\ 0&1&1&1 \0&1&1&1end{bmatrix}$
Notice how each equivalence class is a block of 1's in the matrix?
getting the mathemtical notation for identifying the block is not hard, but Im not sure if "block of 1's" accuratly represents equivalence classes in every case.
If someone wants look at my code you can find it here
I´m open to any helpful math tips, and even coding tips although this isn't stackoverflow ^^
linear-algebra graph-theory equivalence-relations
add a comment |
up vote
0
down vote
favorite
Good day,
I wanted to write a programme in python which given the inputs n,E , where n is the number of nodes and E a list of edges gives me certain properties about that graph.
I'm mainly interested in 3 things :
-reflexivity
-symmetry
-transitivity
To determine whether the graph represents an equivalence relation and given that it is one I want to get the equivalence classes of that relation.
Now there is a standard way of doing this completely without any adjacent matrices but I found them to be so useful !
For instance : a graph is reflexive if the corresponding adjacent matrix has all 1 on the main diagonal. Or the graph is symmetric if the matrix is symmetric . Absolutely beautiful.
Mathematical notation would be :
Let $A in mathbb R^{n*n}$ be the adjacent matrix of a Graph with entries $a_{ij}$.
Reflexive : $prodlimits_{i=1}^{n}a_{ii} = 1 $
Symmetric: $a_{ij} = a_{ji} , forall i,j = 1,...,n$
Transitivity : if $a_{ij} = a_{jk} = 1$ and $ knot=i $ then $a_{ik}=1$
I already successfully implemented those.
Now I want to get said equivalence classes of that relation from the matrix and it proofed to be harder than thought...
Trying to get a feel I just came up with some graphs and corresponding matrices and had a look at them.
I found that equivalence classes have a property when represented in graphs, they form a circle . I'm not sure if they always form a circle in both directions but I feel like they do .Now finding that circle in the matrix , I recognized that an equivalence class looks like a block in a matrix but I'm not sure if that always checks out either.
As an example to clarify what Im trying to say:
let $G$ be a Graph with Nodes $N={0,1,2,3}$ and Edges $E={(1,2),(2,1),(2,3),(3,2),(1,3),(3,1),(i,i) } $ with $ i=0,1,2,3$
This Graph is definetly describing an equivalence Relation and has 2 equivalence classes: ${[0],[1,2,3]}$
The corresponding adjacent matrix looks like this:
$begin{bmatrix}1 & 0 & 0 &0\0 & 1 & 1&1\ 0&1&1&1 \0&1&1&1end{bmatrix}$
Notice how each equivalence class is a block of 1's in the matrix?
getting the mathemtical notation for identifying the block is not hard, but Im not sure if "block of 1's" accuratly represents equivalence classes in every case.
If someone wants look at my code you can find it here
I´m open to any helpful math tips, and even coding tips although this isn't stackoverflow ^^
linear-algebra graph-theory equivalence-relations
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Good day,
I wanted to write a programme in python which given the inputs n,E , where n is the number of nodes and E a list of edges gives me certain properties about that graph.
I'm mainly interested in 3 things :
-reflexivity
-symmetry
-transitivity
To determine whether the graph represents an equivalence relation and given that it is one I want to get the equivalence classes of that relation.
Now there is a standard way of doing this completely without any adjacent matrices but I found them to be so useful !
For instance : a graph is reflexive if the corresponding adjacent matrix has all 1 on the main diagonal. Or the graph is symmetric if the matrix is symmetric . Absolutely beautiful.
Mathematical notation would be :
Let $A in mathbb R^{n*n}$ be the adjacent matrix of a Graph with entries $a_{ij}$.
Reflexive : $prodlimits_{i=1}^{n}a_{ii} = 1 $
Symmetric: $a_{ij} = a_{ji} , forall i,j = 1,...,n$
Transitivity : if $a_{ij} = a_{jk} = 1$ and $ knot=i $ then $a_{ik}=1$
I already successfully implemented those.
Now I want to get said equivalence classes of that relation from the matrix and it proofed to be harder than thought...
Trying to get a feel I just came up with some graphs and corresponding matrices and had a look at them.
I found that equivalence classes have a property when represented in graphs, they form a circle . I'm not sure if they always form a circle in both directions but I feel like they do .Now finding that circle in the matrix , I recognized that an equivalence class looks like a block in a matrix but I'm not sure if that always checks out either.
As an example to clarify what Im trying to say:
let $G$ be a Graph with Nodes $N={0,1,2,3}$ and Edges $E={(1,2),(2,1),(2,3),(3,2),(1,3),(3,1),(i,i) } $ with $ i=0,1,2,3$
This Graph is definetly describing an equivalence Relation and has 2 equivalence classes: ${[0],[1,2,3]}$
The corresponding adjacent matrix looks like this:
$begin{bmatrix}1 & 0 & 0 &0\0 & 1 & 1&1\ 0&1&1&1 \0&1&1&1end{bmatrix}$
Notice how each equivalence class is a block of 1's in the matrix?
getting the mathemtical notation for identifying the block is not hard, but Im not sure if "block of 1's" accuratly represents equivalence classes in every case.
If someone wants look at my code you can find it here
I´m open to any helpful math tips, and even coding tips although this isn't stackoverflow ^^
linear-algebra graph-theory equivalence-relations
Good day,
I wanted to write a programme in python which given the inputs n,E , where n is the number of nodes and E a list of edges gives me certain properties about that graph.
I'm mainly interested in 3 things :
-reflexivity
-symmetry
-transitivity
To determine whether the graph represents an equivalence relation and given that it is one I want to get the equivalence classes of that relation.
Now there is a standard way of doing this completely without any adjacent matrices but I found them to be so useful !
For instance : a graph is reflexive if the corresponding adjacent matrix has all 1 on the main diagonal. Or the graph is symmetric if the matrix is symmetric . Absolutely beautiful.
Mathematical notation would be :
Let $A in mathbb R^{n*n}$ be the adjacent matrix of a Graph with entries $a_{ij}$.
Reflexive : $prodlimits_{i=1}^{n}a_{ii} = 1 $
Symmetric: $a_{ij} = a_{ji} , forall i,j = 1,...,n$
Transitivity : if $a_{ij} = a_{jk} = 1$ and $ knot=i $ then $a_{ik}=1$
I already successfully implemented those.
Now I want to get said equivalence classes of that relation from the matrix and it proofed to be harder than thought...
Trying to get a feel I just came up with some graphs and corresponding matrices and had a look at them.
I found that equivalence classes have a property when represented in graphs, they form a circle . I'm not sure if they always form a circle in both directions but I feel like they do .Now finding that circle in the matrix , I recognized that an equivalence class looks like a block in a matrix but I'm not sure if that always checks out either.
As an example to clarify what Im trying to say:
let $G$ be a Graph with Nodes $N={0,1,2,3}$ and Edges $E={(1,2),(2,1),(2,3),(3,2),(1,3),(3,1),(i,i) } $ with $ i=0,1,2,3$
This Graph is definetly describing an equivalence Relation and has 2 equivalence classes: ${[0],[1,2,3]}$
The corresponding adjacent matrix looks like this:
$begin{bmatrix}1 & 0 & 0 &0\0 & 1 & 1&1\ 0&1&1&1 \0&1&1&1end{bmatrix}$
Notice how each equivalence class is a block of 1's in the matrix?
getting the mathemtical notation for identifying the block is not hard, but Im not sure if "block of 1's" accuratly represents equivalence classes in every case.
If someone wants look at my code you can find it here
I´m open to any helpful math tips, and even coding tips although this isn't stackoverflow ^^
linear-algebra graph-theory equivalence-relations
linear-algebra graph-theory equivalence-relations
edited Nov 22 at 9:27
Asaf Karagila♦
301k32422752
301k32422752
asked Nov 22 at 8:53
Astrionn
234
234
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
Equivalence classes in your case are connected components of the graph. Any method finding connected components of the graph will therefore also find equivalence classes.
Additionally, because the relation is an equivalence relation, the equivalence classes will actually be fully connected cliques in the graph. Your network is basically comprised of subsets of nodes, each subset of nodes is fully connected and has no outgoing connections. That means that there exists an ordering of nodes such that the adjacency matrix of the graph will be
$$begin{bmatrix}A_1&0&0&dots&0\ 0 & A_2&0&dots&0\ 0 & 0 & A_3&dots&0\vdots&vdots&vdots & ddots & vdots\0&0&0&dots&A_nend{bmatrix}$$
and $A_1,dots A_n$ are matrices of only ones (and all the zeroes are zero matrices of appropriate dimensions)
Thanks for the quick answer! So my block of 1's almost holds up if the nodes are put into a the right order, a nice insight. But how about finding that order ? I would have to go trough all possible orders of nodes, create the matrices and check for "blockiness". Blockiness would look like a recursive function that checks wether $a_{ij}$ and $a_{i+1 j}$ and $a_{i j+1}$ and $a_{i+1 j+1}$ are all equal to 1 and if not jump back to i-1 which is the size of the block. looks like i ciuld spare i+1 and j+1 since its on the diagonal where i can expect 1's anyways.
– Astrionn
Nov 22 at 11:28
1
@Astrionn To find that order, as said, use any method that finds all connected components of a graph. For example, a simple breadth-first search would do just fine.
– 5xum
Nov 22 at 12:28
Thank you a lot!
– Astrionn
Nov 22 at 13:18
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',
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%2f3008893%2fdetermining-the-equivalence-classes-of-an-equivalence-relation-represented-by-gr%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Equivalence classes in your case are connected components of the graph. Any method finding connected components of the graph will therefore also find equivalence classes.
Additionally, because the relation is an equivalence relation, the equivalence classes will actually be fully connected cliques in the graph. Your network is basically comprised of subsets of nodes, each subset of nodes is fully connected and has no outgoing connections. That means that there exists an ordering of nodes such that the adjacency matrix of the graph will be
$$begin{bmatrix}A_1&0&0&dots&0\ 0 & A_2&0&dots&0\ 0 & 0 & A_3&dots&0\vdots&vdots&vdots & ddots & vdots\0&0&0&dots&A_nend{bmatrix}$$
and $A_1,dots A_n$ are matrices of only ones (and all the zeroes are zero matrices of appropriate dimensions)
Thanks for the quick answer! So my block of 1's almost holds up if the nodes are put into a the right order, a nice insight. But how about finding that order ? I would have to go trough all possible orders of nodes, create the matrices and check for "blockiness". Blockiness would look like a recursive function that checks wether $a_{ij}$ and $a_{i+1 j}$ and $a_{i j+1}$ and $a_{i+1 j+1}$ are all equal to 1 and if not jump back to i-1 which is the size of the block. looks like i ciuld spare i+1 and j+1 since its on the diagonal where i can expect 1's anyways.
– Astrionn
Nov 22 at 11:28
1
@Astrionn To find that order, as said, use any method that finds all connected components of a graph. For example, a simple breadth-first search would do just fine.
– 5xum
Nov 22 at 12:28
Thank you a lot!
– Astrionn
Nov 22 at 13:18
add a comment |
up vote
1
down vote
accepted
Equivalence classes in your case are connected components of the graph. Any method finding connected components of the graph will therefore also find equivalence classes.
Additionally, because the relation is an equivalence relation, the equivalence classes will actually be fully connected cliques in the graph. Your network is basically comprised of subsets of nodes, each subset of nodes is fully connected and has no outgoing connections. That means that there exists an ordering of nodes such that the adjacency matrix of the graph will be
$$begin{bmatrix}A_1&0&0&dots&0\ 0 & A_2&0&dots&0\ 0 & 0 & A_3&dots&0\vdots&vdots&vdots & ddots & vdots\0&0&0&dots&A_nend{bmatrix}$$
and $A_1,dots A_n$ are matrices of only ones (and all the zeroes are zero matrices of appropriate dimensions)
Thanks for the quick answer! So my block of 1's almost holds up if the nodes are put into a the right order, a nice insight. But how about finding that order ? I would have to go trough all possible orders of nodes, create the matrices and check for "blockiness". Blockiness would look like a recursive function that checks wether $a_{ij}$ and $a_{i+1 j}$ and $a_{i j+1}$ and $a_{i+1 j+1}$ are all equal to 1 and if not jump back to i-1 which is the size of the block. looks like i ciuld spare i+1 and j+1 since its on the diagonal where i can expect 1's anyways.
– Astrionn
Nov 22 at 11:28
1
@Astrionn To find that order, as said, use any method that finds all connected components of a graph. For example, a simple breadth-first search would do just fine.
– 5xum
Nov 22 at 12:28
Thank you a lot!
– Astrionn
Nov 22 at 13:18
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Equivalence classes in your case are connected components of the graph. Any method finding connected components of the graph will therefore also find equivalence classes.
Additionally, because the relation is an equivalence relation, the equivalence classes will actually be fully connected cliques in the graph. Your network is basically comprised of subsets of nodes, each subset of nodes is fully connected and has no outgoing connections. That means that there exists an ordering of nodes such that the adjacency matrix of the graph will be
$$begin{bmatrix}A_1&0&0&dots&0\ 0 & A_2&0&dots&0\ 0 & 0 & A_3&dots&0\vdots&vdots&vdots & ddots & vdots\0&0&0&dots&A_nend{bmatrix}$$
and $A_1,dots A_n$ are matrices of only ones (and all the zeroes are zero matrices of appropriate dimensions)
Equivalence classes in your case are connected components of the graph. Any method finding connected components of the graph will therefore also find equivalence classes.
Additionally, because the relation is an equivalence relation, the equivalence classes will actually be fully connected cliques in the graph. Your network is basically comprised of subsets of nodes, each subset of nodes is fully connected and has no outgoing connections. That means that there exists an ordering of nodes such that the adjacency matrix of the graph will be
$$begin{bmatrix}A_1&0&0&dots&0\ 0 & A_2&0&dots&0\ 0 & 0 & A_3&dots&0\vdots&vdots&vdots & ddots & vdots\0&0&0&dots&A_nend{bmatrix}$$
and $A_1,dots A_n$ are matrices of only ones (and all the zeroes are zero matrices of appropriate dimensions)
answered Nov 22 at 8:55
5xum
89.4k393161
89.4k393161
Thanks for the quick answer! So my block of 1's almost holds up if the nodes are put into a the right order, a nice insight. But how about finding that order ? I would have to go trough all possible orders of nodes, create the matrices and check for "blockiness". Blockiness would look like a recursive function that checks wether $a_{ij}$ and $a_{i+1 j}$ and $a_{i j+1}$ and $a_{i+1 j+1}$ are all equal to 1 and if not jump back to i-1 which is the size of the block. looks like i ciuld spare i+1 and j+1 since its on the diagonal where i can expect 1's anyways.
– Astrionn
Nov 22 at 11:28
1
@Astrionn To find that order, as said, use any method that finds all connected components of a graph. For example, a simple breadth-first search would do just fine.
– 5xum
Nov 22 at 12:28
Thank you a lot!
– Astrionn
Nov 22 at 13:18
add a comment |
Thanks for the quick answer! So my block of 1's almost holds up if the nodes are put into a the right order, a nice insight. But how about finding that order ? I would have to go trough all possible orders of nodes, create the matrices and check for "blockiness". Blockiness would look like a recursive function that checks wether $a_{ij}$ and $a_{i+1 j}$ and $a_{i j+1}$ and $a_{i+1 j+1}$ are all equal to 1 and if not jump back to i-1 which is the size of the block. looks like i ciuld spare i+1 and j+1 since its on the diagonal where i can expect 1's anyways.
– Astrionn
Nov 22 at 11:28
1
@Astrionn To find that order, as said, use any method that finds all connected components of a graph. For example, a simple breadth-first search would do just fine.
– 5xum
Nov 22 at 12:28
Thank you a lot!
– Astrionn
Nov 22 at 13:18
Thanks for the quick answer! So my block of 1's almost holds up if the nodes are put into a the right order, a nice insight. But how about finding that order ? I would have to go trough all possible orders of nodes, create the matrices and check for "blockiness". Blockiness would look like a recursive function that checks wether $a_{ij}$ and $a_{i+1 j}$ and $a_{i j+1}$ and $a_{i+1 j+1}$ are all equal to 1 and if not jump back to i-1 which is the size of the block. looks like i ciuld spare i+1 and j+1 since its on the diagonal where i can expect 1's anyways.
– Astrionn
Nov 22 at 11:28
Thanks for the quick answer! So my block of 1's almost holds up if the nodes are put into a the right order, a nice insight. But how about finding that order ? I would have to go trough all possible orders of nodes, create the matrices and check for "blockiness". Blockiness would look like a recursive function that checks wether $a_{ij}$ and $a_{i+1 j}$ and $a_{i j+1}$ and $a_{i+1 j+1}$ are all equal to 1 and if not jump back to i-1 which is the size of the block. looks like i ciuld spare i+1 and j+1 since its on the diagonal where i can expect 1's anyways.
– Astrionn
Nov 22 at 11:28
1
1
@Astrionn To find that order, as said, use any method that finds all connected components of a graph. For example, a simple breadth-first search would do just fine.
– 5xum
Nov 22 at 12:28
@Astrionn To find that order, as said, use any method that finds all connected components of a graph. For example, a simple breadth-first search would do just fine.
– 5xum
Nov 22 at 12:28
Thank you a lot!
– Astrionn
Nov 22 at 13:18
Thank you a lot!
– Astrionn
Nov 22 at 13:18
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.
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%2f3008893%2fdetermining-the-equivalence-classes-of-an-equivalence-relation-represented-by-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