edge contraction

English

Noun

edge contraction (plural edge contractions)

  1. (graph theory) An operation performed on an edge in a graph which deletes the edge, replaces its endpoints with a single new vertex, and replaces edges incident to either endpoint with an edge incident to the new vertex.
    Performing an edge contraction on an edge in a path graph results in a path graph with one fewer vertex.

References

This article is issued from Wiktionary. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.