Isomorfismo fra grafi: Un algoritmo efficiente per trov are tutti gli isomorfismi View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1971-12

AUTHORS

Franco Sirovich

ABSTRACT

E' descritta una procedura per determinare 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 affiuamento 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'identità delle ripartizioni è condizione necessaria e 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 celle di equivalenza debole, la procedura descritta ottiene una ripartizione costituita da sole celle di equivalenza forte per l'insieme dei nodi del primo grafo, ed un insieme, unicamente determinato, di ripartizioni costituite da sole celle di equivalenza forte per l'insieme di nodi del secondo grafo. Non è stato trovato nessun controesempio alla congettura che tutte le ripartizioni ottenute in tale modo 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. More... »

PAGES

301

Journal

TITLE

Calcolo

ISSUE

4

VOLUME

8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf02575800

DOI

http://dx.doi.org/10.1007/bf02575800

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1028788771


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "author": [
      {
        "affiliation": {
          "name": [
            "Istituto di Elaborazione della Informazione del C.N.R., Via S. Maria 46, 56100, Pisa"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sirovich", 
        "givenName": "Franco", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/321556.321562", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003980246"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0021-9800(67)80003-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009841999"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1464122.1464178", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009859194"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/363872.363899", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015364039"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/800257.808923", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015596528"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1021/c160016a007", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1055225028"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/mspec.1966.5216902", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061424987"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tct.1966.1082573", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061578258"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1971-12", 
    "datePublishedReg": "1971-12-01", 
    "description": "E' descritta una procedura per determinare 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 affiuamento 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'identit\u00e0 delle ripartizioni \u00e8 condizione necessaria e 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 \u00e8 immediatamente ricavabile dalle due ripartizioni. Se invece le ripartizioni dei nodi contengono anche celle di equivalenza debole, la procedura descritta ottiene una ripartizione costituita da sole celle di equivalenza forte per l'insieme dei nodi del primo grafo, ed un insieme, unicamente determinato, di ripartizioni costituite da sole celle di equivalenza forte per l'insieme di nodi del secondo grafo. Non \u00e8 stato trovato nessun controesempio alla congettura che tutte le ripartizioni ottenute in tale modo per il secondo grafo sono identiche a quella ottenuta per il primo grafo. In ogni modo, \u00e8 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 \u00e8 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.", 
    "genre": "non_research_article", 
    "id": "sg:pub.10.1007/bf02575800", 
    "inLanguage": [
      "it"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1135974", 
        "issn": [
          "0008-0624", 
          "1126-5434"
        ], 
        "name": "Calcolo", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "8"
      }
    ], 
    "name": "Isomorfismo fra grafi: Un algoritmo efficiente per trov are tutti gli isomorfismi", 
    "pagination": "301", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "892475021bf13c111e197fec4edb2aa234d5d5dc3897935a757dc3b883354a4a"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02575800"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1028788771"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02575800", 
      "https://app.dimensions.ai/details/publication/pub.1028788771"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13:35", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000370_0000000370/records_46775_00000001.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2FBF02575800"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf02575800'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf02575800'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02575800'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02575800'


 

This table displays all metadata directly associated to this object as RDF triples.

75 TRIPLES      20 PREDICATES      33 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02575800 schema:author Ne5a2d83c324f4cce961ab073f6ef112d
2 schema:citation https://doi.org/10.1016/s0021-9800(67)80003-6
3 https://doi.org/10.1021/c160016a007
4 https://doi.org/10.1109/mspec.1966.5216902
5 https://doi.org/10.1109/tct.1966.1082573
6 https://doi.org/10.1145/1464122.1464178
7 https://doi.org/10.1145/321556.321562
8 https://doi.org/10.1145/363872.363899
9 https://doi.org/10.1145/800257.808923
10 schema:datePublished 1971-12
11 schema:datePublishedReg 1971-12-01
12 schema:description E' descritta una procedura per determinare 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 affiuamento 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'identità delle ripartizioni è condizione necessaria e 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 celle di equivalenza debole, la procedura descritta ottiene una ripartizione costituita da sole celle di equivalenza forte per l'insieme dei nodi del primo grafo, ed un insieme, unicamente determinato, di ripartizioni costituite da sole celle di equivalenza forte per l'insieme di nodi del secondo grafo. Non è stato trovato nessun controesempio alla congettura che tutte le ripartizioni ottenute in tale modo 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.
13 schema:genre non_research_article
14 schema:inLanguage it
15 schema:isAccessibleForFree false
16 schema:isPartOf N44e9435abe0e4babb221d45283e39aea
17 N45f99a5d4e094c2893a329b5c9876152
18 sg:journal.1135974
19 schema:name Isomorfismo fra grafi: Un algoritmo efficiente per trov are tutti gli isomorfismi
20 schema:pagination 301
21 schema:productId N7f9976f01823447ca879d94326192a8c
22 N8f0402c3e83f4dcf8e9e03e1c1caa084
23 Ne7caa80cee344d79af2bbd7ceccd1053
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028788771
25 https://doi.org/10.1007/bf02575800
26 schema:sdDatePublished 2019-04-11T13:35
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher N7a7f4ab483344dbd94100e2f406729cc
29 schema:url http://link.springer.com/10.1007%2FBF02575800
30 sgo:license sg:explorer/license/
31 sgo:sdDataset articles
32 rdf:type schema:ScholarlyArticle
33 N44e9435abe0e4babb221d45283e39aea schema:volumeNumber 8
34 rdf:type schema:PublicationVolume
35 N45f99a5d4e094c2893a329b5c9876152 schema:issueNumber 4
36 rdf:type schema:PublicationIssue
37 N7a7f4ab483344dbd94100e2f406729cc schema:name Springer Nature - SN SciGraph project
38 rdf:type schema:Organization
39 N7f9976f01823447ca879d94326192a8c schema:name doi
40 schema:value 10.1007/bf02575800
41 rdf:type schema:PropertyValue
42 N80a61af4556448ca91c972eef429a5b0 schema:affiliation Nd2d651ec2732415ea28dd3f5808d0fad
43 schema:familyName Sirovich
44 schema:givenName Franco
45 rdf:type schema:Person
46 N8f0402c3e83f4dcf8e9e03e1c1caa084 schema:name dimensions_id
47 schema:value pub.1028788771
48 rdf:type schema:PropertyValue
49 Nd2d651ec2732415ea28dd3f5808d0fad schema:name Istituto di Elaborazione della Informazione del C.N.R., Via S. Maria 46, 56100, Pisa
50 rdf:type schema:Organization
51 Ne5a2d83c324f4cce961ab073f6ef112d rdf:first N80a61af4556448ca91c972eef429a5b0
52 rdf:rest rdf:nil
53 Ne7caa80cee344d79af2bbd7ceccd1053 schema:name readcube_id
54 schema:value 892475021bf13c111e197fec4edb2aa234d5d5dc3897935a757dc3b883354a4a
55 rdf:type schema:PropertyValue
56 sg:journal.1135974 schema:issn 0008-0624
57 1126-5434
58 schema:name Calcolo
59 rdf:type schema:Periodical
60 https://doi.org/10.1016/s0021-9800(67)80003-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009841999
61 rdf:type schema:CreativeWork
62 https://doi.org/10.1021/c160016a007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1055225028
63 rdf:type schema:CreativeWork
64 https://doi.org/10.1109/mspec.1966.5216902 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061424987
65 rdf:type schema:CreativeWork
66 https://doi.org/10.1109/tct.1966.1082573 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061578258
67 rdf:type schema:CreativeWork
68 https://doi.org/10.1145/1464122.1464178 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009859194
69 rdf:type schema:CreativeWork
70 https://doi.org/10.1145/321556.321562 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003980246
71 rdf:type schema:CreativeWork
72 https://doi.org/10.1145/363872.363899 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015364039
73 rdf:type schema:CreativeWork
74 https://doi.org/10.1145/800257.808923 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015596528
75 rdf:type schema:CreativeWork
 




Preview window. Press ESC to close (or click here)


...