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

Reply via email to