Re: New algorithm for the isomorphism of graphs

On Jul 10, 8:48 am, mimouni <mimouni.moha...@xxxxxxxxx> wrote:
On 9 juil, 22:49, Proginoskes <CCHeck...@xxxxxxxxx> wrote:



On Jul 9, 2:29 pm, mimouni <mimouni.moha...@xxxxxxxxx> wrote:

Hello has all,

Here a method to find the function of isomorphism between two
isomorphous

"isomorphic"

graphs: For each vertex S of the graph G, one drawing a
pseudo-tree in this manner.
1. in the first level there is the vertex S.
2. in bottom there are all the adjacent vertices at the vertex S.
3. idem for this level (all adjacent vertices at the vertices of the
high level).
4. and one vertices when there N is more of the vertices.

This is known as a Breadth-First-Search (BFS) tree of the graph G; I
will use this abbreviation below.

In the second graph there is a vertex which has the same pseudo-tree.

You need to find this vertex and BFS tree. So what you might have to
do is to find all BFS trees for all vertices of G'; you may have to
permute the order of the vertices in the representation of G' to do
this, and this is a problem. (See below.)

Since the construction of these pseudo-tree this fact in a time
polynomial, then the problem of the isomorphism of graphs is
polynomial.

How do you know you will be constructing polynomially many BFS trees?
Sure, you may get lucky when you construct the second, but in the
worst case, you may have to find them all, and there are graphs with
exponentially many BFS trees. This would ruin your polynomial result.

Prove:
G and G' are isomorphous, then for a vertex S of G, there exists in G'
a vertex which has the same one dismantles and adjacent with a group
of the vertices (bottom grade) which has the same number is
isomorphous with the group of the bottom grade for G.

??? I think what you're trying to say is: "Suppose G and G' are
isomorphic. We want to explicitly construct an isomorphism F from G to
G'. To do so, let S be a vertex of G."

Thus to find F (S), F is related to isomorphism between the two graphs
G and G', one seeks in G' all the vertices which one dismantles equal
to dismantles S, then which is the level second isomorph on the same
level of S, and one finished when the correspondence is found.

What this seems to say is "Match up the neighbors of S with the
neighbors of some candidate for F(S). Then match up the neighbors of
the neighbors of S with the neighbors of the neighbors of F(S). And so
on."

The problem is that you have a non-polynomial number of possibilities
of matching up the neighbors of S with the neighbors of S' (a
candidate for F(S)). If G [and G'] is a regular triangle-free graph
with degree n/2, then the number of ways to match up the neighbors of
S with the neighbors of S' is (n/2)!, which is exponential in n.
Unless you have some way to eliminate a lot of these (and you don't,
since you're only looking at the first neighborhood of S and S'), you
have to look at them all.

Any isomorphism-checking algorithm should also be able to deal with
the case where G and G' are not isomorphic.

Or if
one arrives towards the low level with several vertices then S is
isomorphous with one of its vertices.

And to afflict for the syntax, spelling mistakes and grammar. (A
machine translation)

An example of how your algorithm works would help. Let G be the graph
with vertex-set {1,2,3,4,5} and edges {12, 13, 15, 23, 34, 45}, and G'
the graph with vertex-set {a,b,c,d,e} and edges {ab, ac, ae, bd, be,
cd}.

f(2)=e.
f(1)=a or f(1)=b.
f(3)=b or f(3)=a.
f(5)=c or f(5)=d.
f(4)=d or f(4)=c.

f(1,2,3,4,5)=(a,e,b,d,c).
f(1,2,3,4,5)=(b,e,a,c,d).

Okay. So what I said above really applies: In short, you have to
consider the cases f(1)=a and f(1)=b and ahead of time, and then
consider sub-cases from there.

Since you have to choose between two options, and there's no immediate
reason for choosing one over the other, you (probably) won't have a
polynomial-time algorithm. (Incidentally, "more than one choice" is
why a lot of problems become NP-complete when some parameter becomes 2
or 3. If you are 2-coloring a graph, once you color one vertex, you're
basically done, since the color of every other vertex is forced.
However, if you are 3-coloring a graph, you have a choice between 2
colors to color each of the neighbors of the first vertex. Since, as
in your isomorphism algorith, you have to make a choice here, you have
to consider both options. My gut feeling, BTW, is that the graph
isomorphism problem is NP-complete.)

[ONE LAST THOUGHT:]

A good test for your algorithm would be to pick two k-regular graphs
with girth at least (say) k/3. You can find a lot of regular graphs
with a given number of vertices, and a given girth, at
http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html .

--- Christopher Heckman

.

Relevant Pages

  • Re: New algorithm for the isomorphism of graphs
    ... This is known as a Breadth-First-Search tree of the graph G; ... How do you know you will be constructing polynomially many BFS trees? ... We want to explicitly construct an isomorphism F from G to ... What this seems to say is "Match up the neighbors of S with the ...
    (sci.math)
  • Re: New algorithm for the isomorphism of graphs
    ... Here a method to find the function of isomorphism between two ... This is known as a Breadth-First-Search tree of the graph G; ... How do you know you will be constructing polynomially many BFS trees? ... What this seems to say is "Match up the neighbors of S with the ...
    (sci.math)
  • Re: New algorithm for the isomorphism of graphs
    ... of the planar ones. ... of two trees, or the case of two planar graphs, then you can solve the ... since the Graph Isomorphism problem would be known to be in P. ...
    (sci.math)
  • Re: (Probably flawed) Polynomial time Graph Isomorphism
    ... On random input graphs graph isomorphism ... Note that testing degree sequences is a deterministic algorithm. ... The problem here is the algorithm relies on a hash function, ...
    (comp.theory)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... Bill Cox algorithm that you verified up to 8 nodes, ... not in your implementation) is in my rendering of Bill Cox's ... proved the graphs are not isomorphic. ... graphs are equal iff you have established an isomorphism between the two graphs, and to do that you have to cope with Bill Cox's automorphism issue. ...
    (sci.crypt)