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:
1.compare 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.**PYTHON SOURCE CODE**
def relabel(cm, i, j):
cm2 = []
for r in range(0, len(cm)):
row = []
for s in range(0, len(cm[0])):
row.append(cm[r][s])
cm2.append(row)
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:
break
print(cm)
No comments:
Post a Comment