Graph isomorphism is not very good problem, because for human generated graphs the algorithhm for tree-isomprphism wlll work. But that is only my personal opinion.
But it is hard to understand your algorithm. Mainly because i do not understand the words you are using peak-? summit-? pseudo tree-? stoppage-? nhbm-? Also you have there a lot of errors( i do not mean englis erros) You should rework that, i was rewriting my master's thesis proofs at least 3 times each. 2009/7/14 mimouni <mimouni.moha...@gmail.com> > > Hello, I found a new labeling vertex, which can make the deference > between the peaks of a graph, and thus resolve the automorphism and > isomorphism. Its complexity is estimated to O (n^3). > And here is the procedure: > To build a pseudo tree this way: > 1. Put a single vertices (example: A) in the Level 1. > 2. Putting all the peaks surrounding the vertices An in Level 2. And > not forgetting the edges. > 3. Putting all the peaks adjacent to each vertex exists in the > nouveau2, and without duplication and without forgetting the edges. > In > the level 3. > 4. Repeat Step 3 until more vertices. > Labeling the vertices; is therefore in this way: > 1. in built all the pseudo trees. > 2. In seeking pseudo tree that’s a vertices lies in the level x. > 3. Labeling the vertices in the A-level x is composed of four parts: > the number of times or A lies in the level x, the total number of > stoppages A up, the total number of stoppages in the same A level, > and > finally the total number of stoppages A down. > 4. And labeling a vertex is the labeling on all levels. > Making the deference between A and B. > the two vertices A and B are isomorphism between waters if they both > have the same labeling. > If the labeling of A in a level x is deferential to the labeling of B > at the same level, then A and B are deferens. > ======================== > Validity of the algorithm > The demonstration validation of this algorithm is trivial! > Theorem Let A and B, two peaks in a graph G. function of the > automorphism of G to G is noted f. > f (A) = B if and only if, A and B have the same labeling. > Proof 1) f (A) = B. > Here we will show that A and B on the same labeling. Let x and two > other top graph G, such that f (x) = y. Labeling is based on pseudo- > tree, so if the tree with pseudo-header as x, A is in the p, and B is > in the level q. then the automorphism keeps the distance, then: > For the pseudo-tree with it as header, B is in the p, and A is in the > level q. > With the same idea was for the pseudo-tree x, adjacent to A summits > are divided into three parts (top, at the same level as A, and > bottom), then the pseudo-tree there, the adjacent peaks B are also > divided into three parts (top, at the same level as B, and bottom). > So the two summits: A and B have the same labeling > 2) A and B have the same labeling. > If the labeling of A in the pseudo-tree x is nhmb, labeling B in the > pseudo-tree is also: n hmb because it af (x) = y. with the same idea > (the automorphism keeps distance), we find that f (A) = B. > So: f (A) = B if and only if, A and B have the same labeling. > Complexity of the algorithm > the complexity of a pseudo-tree is O(n²). > the complexity of all pseudo is so O(n³). > the complexity of labeling a summit from a pseudo-tree is O(n). > the complexity of the labeling is a summit O(n²). > So the algorithm is polynomial > ======= > implementation > an application in beta (for small graphs) in php is available on: > http://mohamed.mimouni1.free.fr/ > and for big graphs is avaibles on: > http://sites.google.com/site/isomorphismproject/ > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
