Graph operations

Graph operations produce new graphs from initial ones. They may be separated into the following major categories.

Unary operations

Unary operations create a new graph from one initial one.

Elementary operations

Elementary operations or editing operations create a new graph from one initial one by a simple local change, such as addition or deletion of a vertex or of an edge, merging and splitting of vertices, edge contraction, etc. The graph edit distance between a pair of graphs is the minimum number of elementary operations required to transform one graph into the other.

Advanced operations

Advanced operations create a new graph from one initial one by a complex changes, such as:

Binary operations

Binary operations create a new graph from two initial ones G1 = (V1, E1) and G2 = (V2, E2), such as:

Notes

  1. 1 2 Bondy, J. A.; Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics. Springer. p. 29. ISBN 978-1-84628-969-9.
  2. 1 2 3 Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.
  3. Reingold, O.; Vadhan, S.; Wigderson, A. (2002). "Entropy waves, the zig-zag graph product, and new constant-degree expanders". Annals of Mathematics 155 (1): 157–187. doi:10.2307/3062153. JSTOR 3062153. MR 1888797.
  4. Robert Frucht and Frank Harary. "On the coronas of two graphs", Aequationes Math., 4:322–324, 1970.
This article is issued from Wikipedia - version of the Sunday, January 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.