生成子图 / 跨越子图（图论）：在图 (G) 中，包含 (G) 的所有顶点、但只取其中一部分边所形成的子图。也就是说，顶点集不变，边集可以减少。
（在图论里很常见；例如“生成树”就是一种特殊的生成子图。）
/ˈspænɪŋ ˈsʌbɡræf/
A spanning subgraph keeps all the vertices but may drop some edges.
生成子图保留所有顶点，但可以删去一些边。
In many proofs, we construct a spanning subgraph to simplify the graph while preserving connectivity properties.
在许多证明中，我们会构造一个生成子图，以在保留连通性等性质的同时简化原图。
spanning 来自动词 span（“跨越、覆盖”），在图论中表示“覆盖全部顶点”。
subgraph 由前缀 **sub-**（“下级的、次级的”）+ graph（“图”）构成，字面义为“子图”。合起来 spanning subgraph 即“覆盖全部顶点的子图”。
Select Language