頂點收縮

一對頂點 和 的收縮（圖的頂點收縮，也稱為頂點識別）是一種操作，它產生一個圖，其中兩個節點 和 被替換為一個單一節點 ，使得 與 和 原本相鄰的節點的並集相鄰。在頂點收縮中， 和 是否被邊連線並不重要；如果它們被連線，則該邊在收縮時會被簡單地移除（Pemmaraju 和 Skiena 2003, p. 231）。請注意，Skiena（1990, p. 91）對於頂點收縮和邊收縮之間的區別含糊不清，並且令人困惑地將頂點 和 上的頂點收縮稱為“收縮邊 ”。

上圖顯示了一個隨機圖在頂點 和 上進行收縮。

頂點收縮在 Wolfram 語言中實現為VertexContract[g, v1, v2, ...]。