Re: Need Graph Isomorphism Algorithm De-bunked

Ben Livengood wrote:
fgrieu wrote:
Mike Amling wrote:
...
An alternative to step 6 is to output the graph in generic
order based on a sort of the results, making a much shorter
and useful representative of the graph's equivalence class
(this has been suggested by Bill Cox).
I however fail to convince myself that this is equivalent;
or that the "compare graph's hash" variant never falsely
declare graphs isomorphic, or that the "compare sorted
graphs" variant never falsely declare graphs non-isomorphic.

François Grieu

I think it is sufficient to represent the graph over the equivalence
class of its vertices. Let N be the number of equivalence classes over
the vertices in the graph.

Equivalence under what relationship? Is this related to automorphism?

Let A be a modified N*N adjacency matrix
such that A[i,j] is the number of edges from vertices in equivalence
class i to vertices in equivalence class j. To handle vertices with
zero degree the original number of vertices will have to be output as
well.

I don't know much graph theory, so I apologize if this representation
already has a name or a better description, or if it doesn't actually
work.

Ben Livengood

.

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... The first of the two graphs François Grieu provided in his reply to me ... I think that outputting sorted vertices and an equivalence relation ... and as each vertex is mapped all its neighbors can be ... vertexes to the equivalence class I think it is deterministic and in P. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... graphs" variant never falsely declare graphs non-isomorphic. ... I think it is sufficient to represent the graph over the equivalence ... class i to vertices in equivalence class j. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... equivalence class. ... "compare sorted graphs" variant never falsely declare ... They have the same "modified adjacency matrix", ... defined by Ben Livengood, and number of edges. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... each component of the graph should be considered as a second ... equivalence class over the vertices and be intersected with the first. ... vector of size N containing equivalence classes for the corresponding ...
    (sci.crypt)
  • Re: An uncountable countable set
    ... equivalence class and the equivalence class itself. ... This is the principle used in NBG using the von Neumann naturals as ... subjectivity, but the fact that any normal theory only addresses certain ...
    (sci.math)