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