Monday, March 10, 2014

Maximizing a connectivity matrix

For every simple graph like:
There is a connectivity matrix associated, for the one above with the labeling given it is:

The rows and columns correspond to the letters given in the graph, the first row signifies that A is connected to B, D, F, and G. The second row expresses the connections for B, etc down to row G. 

My idea is to put an ordering on connectivity matrices of the same dimension as follows: the top left cell of both matrices A[0,0] and B[0,0], if A[0,0]  is greater than B[0,0] then connectivity matrix A is greater than B. also if A[0,0] is less than B[0,0] then B is greater than A. if the two are equal, then move to the next cell A[0,1] and B[0,1].
2. Continue going across rows and then wrapping around to the next column until either one matrix is shown to be greater than the other or every cell is exactly the same, in which case A=B.  

Considering a connectivity matrix A, there is an operation I will call a relabeling that consists of swapping both Row I with Row J and Column I and Column J. For example looking at the connectivity matrix above, I could swap row 1 and row 3 and also column 1 and column 3 to get:

I call this relabeling because this is the connectivity graph you would get if you swapped what are called vertex A and vertex C in the original graph and made a connectivity matrix from that graph. A graph is still essentially the same graph under any relabeling. 

It can be seen that under the ordering of connectivity matrices I described CM2 > CM1. This is because comparing across rows and down columns the first 4 values are the same  0101, but the next value of CM2 is 1 and only 0 in CM1. 

So a connectivity graph is maximized if no relabeling or sequence of relabelings can make it greater under the ordering. Then two graphs are isomorphic if and only if their maximized connectivity graphs are the same. 
There might be many algorithms for maximizing a connectivity matrix, from here on I'll be using this conjecture:
Conjecture: A connectivity matrix is maximized if and only if it can not be made greater under any single relabeling operation. 
I can't really even think whether this is likely to be true or not, but first I will describe an algorithm that assumes it is true. 
1. Look through every pairwise combination of possible relabelings and make the relabeling if the new  connectivity matrix is greater. 
2. Repeat 1 until you reach a state where no relabeling makes the graph greater. 
For this connectivity matrix the program I wrote gives:

This one can't be made greater by any single relabeling proven through exhaustion. Remember in this graph there are no vertices connected to themselves so the identity row is all 0's. I think in this case this is the maximum for any type of relabeling of the graph, but I still haven't proven that this algorithm always results in the maximum under any type of relabeling. 
The nice thing about this method is it doesn't assume a binary matrix, all these 1's and 0's could just as easily be any numbers, possibly negative or non-integer, representing weights or directedness or any other feature of a graph.

def relabel(cm, i, j):
    cm2 = []
    for r in range(0, len(cm)):
        row = []
        for s in range(0, len(cm[0])):
    temp = cm2[i]
    cm2[i] = cm2[j]
    cm2[j] = temp
    for r in range(0, len(cm2)):
        temp = cm2[r][i]
        cm2[r][i] = cm2[r][j]
        cm2[r][j] = temp
    return cm2
def greater(cm, cm2):
    for i in range(0, len(cm)):
        for j in range(0, len(cm[0])):
            if cm[i][j] > cm2[i][j]:
                return True
            elif cm[i][j] < cm2[i][j]:
                return False
    return False
def maximize(cm):
    nobetter = False
    for i in range(0, len(cm)-1):
        for j in range(i+1, len(cm)):
            cm2 = relabel(cm, i, j)
            if greater(cm2, cm):
                return cm2, nobetter
    nobetter = True
    return cm, nobetter
cm = [[0,1,0,1,1,1,0],[1,0,1,1,1,0,1],[0,1,0,1,0,1,1],[1,1,1,0,1,0,1],[1,1,0,1,0,1,0],[1,0,1,0,1,0,1],[0,1,1,1,0,1,0]]
nobetter = False
for i in range(0, 10):
    cm, nobetter = maximize(cm)
    if nobetter == True:

No comments:

Post a Comment