顶点收缩

一对顶点 和 的收缩（图的顶点收缩，也称为顶点识别）是一种操作，它产生一个图，其中两个节点 和 被替换为一个单一节点 ，使得 与 和 原本相邻的节点的并集相邻。在顶点收缩中， 和 是否被边连接并不重要；如果它们被连接，则该边在收缩时会被简单地移除（Pemmaraju 和 Skiena 2003, p. 231）。请注意，Skiena（1990, p. 91）对于顶点收缩和边收缩之间的区别含糊不清，并且令人困惑地将顶点 和 上的顶点收缩称为“收缩边 ”。

上图显示了一个随机图在顶点 和 上进行收缩。

顶点收缩在 Wolfram 语言中实现为VertexContract[g, v1, v2, ...]。