I believe that everything is clear: if I should seek the existence of
the isomorphism between two graphs G and H, I should generate the
label of each vertex of G and each vertex of H. ..

On 16 juil, 18:26, Miroslav Balaz <gpsla...@googlemail.com> wrote:
> And also you should answer the main question , how will you find the
> automorphism function?
> Or how would you use the theorem only to decide if there exists an
> isomorphism?
>
> 2009/7/16 Miroslav Balaz <gpsla...@googlemail.com>
>
>
>
> > I think that there is logical error, in the proof what do you think about
> > it?
> > f(A)=B iff A and B have the same labelig, but what if there are 3 vertices
> > with the same labeling? say A,B,C
> > then F(A)=B and F(A)=C
>
> > you forget to quantify the f. I think everyone stops reading it if you will
> > have such errors there.
>
> > 2009/7/15 mimouni <mimouni.moha...@gmail.com>
>
> >> you can consult in:http://www.wbabin.net/science/mimouni2e.pdf
> >> and I finished on implimentation schedule a php (to find the labels
> >> for a graph exceeds 5000 vertices).
>
> >> On 14 juil, 19:25, Miroslav Balaz <gpsla...@googlemail.com> wrote:
> >> > 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