banavana@clutx.clarkson.edu (Narasimhas Banavara) (04/24/91)
Hi, can someone explain me the "Standard Self-Reducibility" of graphs which enables to search for "an" isomorphism between two graphs G and H given an algorithm which tells us whether the two graphs are "isomorphic". Thanks in advance. Narsim. email : banavana@sun.mcs.clarkson.edu banavana@clutx.clarkson.edu
bdm659@csc.anu.edu.au (04/28/91)
In article <1991Apr24.002002.9063@grape.ecs.clarkson.edu>, banavana@clutx.clarkson.edu (Narasimhas Banavara) writes: > Hi, > can someone explain me the "Standard Self-Reducibility" > of graphs which enables to search for "an" isomorphism between > two graphs G and H given an algorithm which tells us whether > the two graphs are "isomorphic". I don't know what "Standard Self-Reducibility" is, but the task you require is easy. Given two isomorphic graphs G and H, "fix" one vertex v of G by sticking a large clique onto it, making G(v). Then try sticking a clique of the same size onto each vertex of H in turn until one is found, say w, for which the extended graph H(w) is isomorphic to G(v). Then there must be an isomorphism from G to H taking v onto w. Continue in the same way using G(v) and H(w) until an entire isomrphism is found. The whole process takes O(n^2) isomomorphism tests, where G and H have n vertices. > Narsim. Brendan.
jan@cs.umu.se (Jan T}ngring) (05/07/91)
In article <1991Apr28.201043.1@csc.anu.edu.au> bdm659@csc.anu.edu.au writes: > >Given two isomorphic graphs G and H, "fix" one >vertex v of G by sticking a large clique onto it, making G(v). Then try >sticking a clique of the same size onto each vertex of H in turn until one >is found, say w, for which the extended graph H(w) is isomorphic to G(v). >Then there must be an isomorphism from G to H taking v onto w. Continue >in the same way using G(v) and H(w) until an entire isomrphism is found. >The whole process takes O(n^2) isomomorphism tests, where G and H have >n vertices. > >> Narsim. The following beautiful sicstus prolog program implements the above algorithm: -----------------cut here-------------------------------- /* ---------------- support ----------------- */ selected(N, [N|L], L). selected(N, [M|LNL], [M|LL]):- selected(N, LNL, LL). perm([], []). perm(LNL, [N|LL]):- selected(N, LNL, Perm), perm(Perm, LL). equal(L1, L2):- perm(L1, L2). /*-----------------isomorphic------------------------- */ isomorphic([], []). isomorphic([(V,N1)|S1], G2):- selected((V,N2), G2, S2) -> equal(N1, N2), isomorphic(S1, S2). /* The third line of isomorphic is equivalent to: (selected((V,N2), G2, S2), !, equal(N1, N2)), */ -----------------cut here-------------------------------- If G1 and G2 are isomorphic then isomorfic(G1, G2) shows the corresponding corners. G1 & G2 are undirected graphs represented as adjacency sets (lists). An edge between corners a and b should have an entry in the adjacency lists of both a and b. There is no control made that the input data is consistent in this respect. (It should be trivial to write a predicate converting from a briefer notation) The program cunningly uses prolog built-in unification, so the corners of G1 must be constants and the corners of G2 must be variables. Check your prolog-manual for conventions on names, as they may differ. In the example below, variables have a leading capital letter. Example, input: G1 = [(a,[b,e,f]), (b,[a,c,g,e])...], G2 = [(A, [B,C,G]),...], isomorphic(G1, G2). output: A = a, B = d, C = h,... /JanneT jan@cs.umu.se