Graph canonization (original) (raw)
In graph theory, a branch of mathematics, graph canonization is the problem of finding a canonical form of a given graph G. A canonical form is a labeled graph Canon(G) that is isomorphic to G, such that every graph that is isomorphic to G has the same canonical form as G. Thus, from a solution to the graph canonization problem, one could also solve the problem of graph isomorphism: to test whether two graphs G and H are isomorphic, compute their canonical forms Canon(G) and Canon(H), and test whether these two canonical forms are identical.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, a branch of mathematics, graph canonization is the problem of finding a canonical form of a given graph G. A canonical form is a labeled graph Canon(G) that is isomorphic to G, such that every graph that is isomorphic to G has the same canonical form as G. Thus, from a solution to the graph canonization problem, one could also solve the problem of graph isomorphism: to test whether two graphs G and H are isomorphic, compute their canonical forms Canon(G) and Canon(H), and test whether these two canonical forms are identical. The canonical form of a graph is an example of a complete graph invariant: every two isomorphic graphs have the same canonical form, and every two non-isomorphic graphs have different canonical forms. Conversely, every complete invariant of graphs may be used to construct a canonical form. The vertex set of an n-vertex graph may be identified with the integers from 1 to n, and using such an identification a canonical form of a graph may also be described as a permutation of its vertices. Canonical forms of a graph are also called canonical labelings, and graph canonization is also sometimes known as graph canonicalization. (en) |
| dbo:wikiPageID | 20199287 (xsd:integer) |
| dbo:wikiPageLength | 8645 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1062426239 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Probabilistic_complexity_theory dbr:Permutation dbr:Depth-first_search dbr:SMILES dbr:Chemical_database dbr:Chemical_substance dbr:Graph_labeling dbr:NP-hard dbr:László_Babai dbr:Complete_set_of_invariants dbr:Computational_complexity_theory dbr:Identifier dbr:Data_mining dbr:Adjacency_matrix dbr:Graph_isomorphism dbr:Graph_isomorphism_problem dbr:Graph_theory dbr:Isomorphism_class dbr:AC0 dbc:Graph_theory dbr:Graph_invariant dbr:Integer dbr:Canonical_form dbr:Lexicographical_order dbr:InChI dbr:Polynomial_time_equivalent dbr:Reducible_(complexity) |
| dbp:wikiPageUsesTemplate | dbt:Harvtxt dbt:Reflist |
| dct:subject | dbc:Graph_theory |
| gold:hypernym | dbr:Problem |
| rdf:type | dbo:Disease |
| rdfs:comment | In graph theory, a branch of mathematics, graph canonization is the problem of finding a canonical form of a given graph G. A canonical form is a labeled graph Canon(G) that is isomorphic to G, such that every graph that is isomorphic to G has the same canonical form as G. Thus, from a solution to the graph canonization problem, one could also solve the problem of graph isomorphism: to test whether two graphs G and H are isomorphic, compute their canonical forms Canon(G) and Canon(H), and test whether these two canonical forms are identical. (en) |
| rdfs:label | Graph canonization (en) |
| owl:sameAs | freebase:Graph canonization wikidata:Graph canonization dbpedia-et:Graph canonization dbpedia-hu:Graph canonization https://global.dbpedia.org/id/4kT6t |
| prov:wasDerivedFrom | wikipedia-en:Graph_canonization?oldid=1062426239&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Graph_canonization |
| is dbo:wikiPageRedirects of | dbr:Computational_complexity_of_graph_canonization dbr:Graph_canonicalization dbr:Canonical_labeling_of_graphs dbr:Canonical_labelling_of_graphs |
| is dbo:wikiPageWikiLink of | dbr:Computational_complexity_of_graph_canonization dbr:Chemical_graph_generator dbr:Glossary_of_graph_theory dbr:Logic_of_graphs dbr:Graph_automorphism dbr:Graph_isomorphism dbr:Graph_isomorphism_problem dbr:Graph_property dbr:Graph_canonicalization dbr:Canonicalization dbr:Canonical_labeling_of_graphs dbr:Canonical_labelling_of_graphs |
| is foaf:primaryTopic of | wikipedia-en:Graph_canonization |