Dual approach to edge distance between graphs (Q4732497)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4118413
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Dual approach to edge distance between graphs |
scientific article; zbMATH DE number 4118413 |
Statements
1989
0 references
modelling of organic chemistry
0 references
distance between finite graphs
0 references
common subgraph
0 references
supergraph
0 references
metrics
0 references
Dual approach to edge distance between graphs (English)
0 references
0.8263115882873535
0 references
0.8263115882873535
0 references
0.8231819272041321
0 references
For mathematical modelling of organic chemistry, two concepts of distance between finite graphs has been developed. The main result of the paper is that these two concepts are identical. A common subgraph (supergraph) of two graphs \(G_ 1\) and \(G_ 2\) consists of a subgraph \(G_ 1'\subseteq G_ 1\) (supergraph \(G_ 1'\supseteq G_ 1)\) and a subgraph \(G_ 2'\subseteq G_ 2\) (supergraph \(G_ 2'\supseteq G_ 2)\) such that \(G_ 1'\cong G_ 2'\). A maximal common subgraph (minimal common supergraph) of two graphs \(G_ 1\) and \(G_ 2\) is a common subgraph (supergraph) which contains the largest (smallest) possible number of edges, it is denoted by \(G_ 1\cap G_ 2\) \((G_ 1\cup G_ 2)\). Set \(g(G,H)=| E(G)| -| E(G\cap H)|,\) \(h(G,H)=| E(G\cup H)| -| E(G)|.\) Now the two distances are \[ d(G,H)=g(G,H)+g(H,G)+| | V(G)| -| V(H)| | \quad and\quad D(G,H)=h(G,H)+h(H,G)+| | V(G)| -| V(H)| |. \] The authors prove that D and d are metrics, \(D=d\) and \(d(G,H)=d(\bar G,\bar H)\).
0 references