Condensation Graph

释义 Definition

凝聚图 / 缩并图（condensation graph）：在有向图中，把每个强连通分量（SCC, strongly connected component）缩并成一个“超级节点”，并保留分量之间的有向边后得到的新图。凝聚图一定是一个有向无环图（DAG）。

发音 Pronunciation

/ˌkɒndenˈseɪʃən ɡræf/
/ˌkɑːndenˈseɪʃən ɡræf/

例句 Examples

We built the condensation graph to simplify the network.
我们构建了凝聚图来简化这个网络。

After computing all strongly connected components, we contract each component into a single vertex, producing a condensation graph that is a DAG and makes the partial order between components explicit.
在计算出所有强连通分量后，我们把每个分量缩并成一个顶点，得到的凝聚图是一个有向无环图，并清晰呈现了各分量之间的偏序关系。

词源 Etymology

condensation 原义是“凝结、浓缩”，来自拉丁语 condensare（使变稠、使浓密），在图论/算法语境中引申为“把一团结构压缩成一个整体”。graph 来自希腊语 graphein（书写、描画），在数学中指“图”。合起来表示“将强连通分量浓缩后的图”。

相关词 Related Words

• Component
• Contraction
• Dag
• Directed
• Edge
• Graph
• Scc
• Topological

文学/经典著作中的用例 Literary / Notable Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：在强连通分量与相关算法章节中使用并讨论凝聚图（condensation graph）的性质与用途。
• Algorithm Design（Kleinberg & Tardos）：讲解强连通分量与将其缩并成 DAG 的思想时会涉及凝聚图。
• The Design and Analysis of Computer Algorithms（Aho, Hopcroft, Ullman）：在有向图分解与强连通结构的讨论中出现“缩并/凝聚”后的图这一概念。