UC知道子图与生成子图（induced subgraph）有什么区别？
来源：百度知道 编辑：UC知道 时间：2024/05/26 04:21:22
谢谢
A subgraph H of a graph G is said to be induced if, for any pair of vertices x and y of H, xy is an edge of H if and only if xy is an edge of G. In other words, H is an induced subgraph of G if it has all the edges that appear in G over the same vertex set. If the vertex set of H is the subset S of V(G), then H can be written as G[S] and is said to be induced by S.
这个好像意思不一样啊？
A subgraph H of a graph G is said to be induced if, for any pair of vertices x and y of H, xy is an edge of H if and only if xy is an edge of G. In other words, H is an induced subgraph of G if it has all the edges that appear in G over the same vertex set. If the vertex set of H is the subset S of V(G), then H can be written as G[S] and is said to be induced by S.
这个好像意思不一样啊？
图G＝[E,V]（E为“边”集。V为“顶点”集），G′＝[E′,V′],
如果：E′≤E.（≤：借用符号，意思是包含于），V′≤V,
则G′叫G的子图。
如果：E′≤E,而V′＝V.（!!）,
则G′叫G的生成子图。
区别就是生成子图的顶点，与原图完全一样，而子图确可以少一些。
生成子图的英译是：spanning subgraph.
induced subgraph的汉译是“诱导子图”，或者“导出子图”。两者不同。。
而后者的意思是：G′＝[E′,V′].
V′≤V,（可以少，也可以不少）。对于V′的所有顶点，只要在G中有连边，这个边就在G′出现。也说G′是G的由V′诱导出的子图。记为G′＝G[V′].
（不好意思，答题时没有注意英语原文。见笑了。）