PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Sirovich F. Isomorfismo fra grafi: un algoritmo efficiente per trovare tutti gli isomorfismi. In: Calcolo, vol. 8 pp. 301 - 337. Springer Verlag Italia, 1972.
 
 
Abstract
(English)
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 partitionings 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 gr:~phs is shown to be straightforwards derivable. Conversely, if the partitioniogs consist of weakly-equivalent cells also, the procedure derives one strongly-equivalent cell partitioning of the node set of the first graph and a uniquely determined set of strongly-equivalent cell partitioning of the node set of second graph: no counterexample has been found to the conjecture that all partitionings obtained for the second graph are identical to the one obtained for 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 partitionings, depends of course on the number of isomorphisms.
Abstract
(Italiano)
E' descritta una procedura perde terminate tutti gli isomorfismi esistenti fra due grafi finiti, non orientati, debolmente connessi. Ad ogni nodo dei grafi dati sono associate liste di attributi che sono invarianti sotto isomorfismo. Gli insiemi dei nodi dei grafi vengono quindi partizionati sulla base delle liste di attributi e per mezzo di un algoritmo di affinamento delle ripartizioni. Vengono introdotti i concetti di cella di equivalenza forte e cella di equivalenza debole di una ripartizione. Viene dimostrato che, se le ripartizioni degli insiemi dei nodi dei grafi sono costituite solamente da celle di equivalenza forte, l' identiche delle ripartizioni condizione necessaria sufficiente per l'esistenza di un isomorfismo fra i grafi dati. In tale caso, si dimostra che l'insieme di tutti gli isomorfismi fra i grafi dati immediatamente ricavabile dalle due ripartizioni. Se invece le ripartizioni dei nodi contengono anche dello di equivalenza debole, la procedura descritta ottiene una ripartizione costituita da sole dello di equivalenza forte per l'insieme dei nodi del primo grafo, ed un insieme,unicamente determinate, di ripartizioni costituite da sole quelle di equivalenza forte per l'insieme di ne di del secondo grafo. Non stato trovato nessun contro-esempio alla congettura che tutte le ripartizioni ottenute in tale mode per il secondo grafo sono identiche a quella ottenuta per il primo grafo. In ogni modo , facile ottenere l'insieme di tutti gli isomorfismi esistenti fra due grafi semplicemente scartando le ripartizioni non identiche. Il tempo richiesto per ottenere le ripartizioni dell'insieme dei nodi di un grafo proporzionale, nel caso peggiore, alla quinta potenza del numero di nodi del grafo. Il tempo necessario per determinare tutti gli isomorfismi, date le ripartizioni degli insiemi dei nodi, dipende ovviamente dal numero di tali isomorfismi .
Subject


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