Now it is more clear to me. So labeling of vertex is set of n fourtuples. Still i do not understand the proof( first implication trivialy holds, because such labeling is in variant to permutation)
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. try to explain it in more details. this is not proof. Try to be more formal at high level. If you cant prove it, than it is not worth anything. If you say that something is trivial and i don't understand, it means, that it is not trivial and you can't prove it. If it were trivial then i would understand it. you were may thinking about graph isomorphism more than me, so from your point of view it can be trivial because you are on higher level. 2009/7/17 mimouni <mimouni.moha...@gmail.com> > > > > On 16 juil, 18:19, Miroslav Balaz <gpsla...@googlemail.com> wrote: > > 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 -~----------~----~----~----~------~----~------~--~---
