Istituto di Scienza e Tecnologie dell'Informazione     
Sirovich F. Isomorfismo tra grafi: un algoritmo efficiente per trovare tutti gli isomorfismi. Internal note IEI-B71-09, 1971.
A procedure is described for the determination of all isomorphisms, if any, between finite, directed weakly-connected graphs. Attribute lists which are invariant under isomorphism are associated to any node of the given graphs and partitioning of the node sets are derived on the ground of the attribute lists as well as by a partitioning refining algorithm. The concepts of strongly-equivalent cell and weakly-equivalent cell of a partitioning are introduced. It is shown that the identity of the partitionings of the node sets of the graphs is a necessary and sufficient condition for graph isomorphism if the partitionings consist of strongly-equivalent cells only. In such a case the set of all isomorphisms between the given graphs is shown to be straightforwards derivable. Conversely, if the partitionings consist of weakly-equivalent cells also, the procedure derives one strongly-equivalent cells partitioning of the node set of the first graph and a uniquely determined set of strongly-equivalent cell partitioning of the node set of the second graph: no counterexample has been found to the conjecture that all partitioning obtained for the second graph are identical to the one obtained the first graph. However the set of all isomorphisms between the given graphs is easily obtained by disregarding non identical partitionings. The time required to derive the node set partitionings depends, at worst, on the fifth power of the order of the given graphs. The time required to determine all isomorphisms, given the node sets partitioning, depends of course on the number of isomorphisms.

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional