No you do not have to explain 1. It can be done easily by showing that distance d(a,b) >=d(f(a),f(b)) let shortest path be a,x_1,x_2,x_3, ... x_k,b then f(a),f(x_1),f(x_2),f(x_3),...f(x_k),f(b) is also path,
and d(f(a),f(b))>=d(a,b) by using fact that f has inverse function sice it is bijection. Now I think i understand The algorithm from my point of view works this way: let G_i be BFS tree with vertex i as root. (now we can forget edges,but will consider them later) now introduce some notations LABEL(i) is the final labeling of the vertex i. In publication you should laber vertices as v_i but i use simplified notation here. lab(i,j)=(a_ij,b_ij,c_ij,d_ij) a_ij is in which level is i when j is the root, d(v_i,v_j) b_ij,is number of vertices x such that d(v_i,x) =1 and d(v_i,v_j)-1=d(x,v_j) c_ij,is number of vertices x such that d(v_i,x) =1 and d(v_i,v_j)+1=d(x,v_j) b_ij,is number of vertices x such that d(v_i,x) =1 and d(v_i,v_j)=d(x,v_j) LABEL(i)=union of all lab(i,j) for each j. But you have to do some more work on the proof, which can be incorect. 2009/7/19 mimouni <[email protected]> > > dear sir, give me a little time (2 days or 3 days) to give a more > detailed demonstration. > > but I must know two things if you enjoy: > 1) are that I must show that the distance between A and B equals the > distance between f (A) and f (B)? > > 2) are that the algorithm is to explain or not? > > and thank you > > On 18 juil, 16:29, Miroslav Balaz <[email protected]> wrote: > > 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 <[email protected]> > > > > > > > > > > > > > On 16 juil, 18:19, Miroslav Balaz <[email protected]> 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 <[email protected]> > > > > > > > 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 <[email protected]> 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 <[email protected]> > > > > > > > > > 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 [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
