Htykuut

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 ^^

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)