Question

连通图G是一颗树，当且仅当G中（）

A.有些边不是割边
B.所有边都是割边
C.无割边集
D.每条边都不是割边

Answer 1

连通图G是一颗树，当且仅当G中每条边都是割边。

在图论中，连通图基于连通的概念。在一个无向图G中，若从顶点i到顶点j有路径相连（当然从j到i也一定有路径），则称i和j是连通的。

如果G是有向图，那么连接i和j的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图。

扩展资料

连通图的性质

命题1：对于连通图G=(V,E)，必然有|E|>=|V|-1。

证明：首先要认清一个图G=(V,E)必然是由若干个互不关联的子连通图组成的。继而，需要证明每次向图中增加一条边，或者不影响其互不关联的子连通图的数目（这条边落在了一个子连通图的内部），或者使得原图中两个子连通图相互连通，从而新的图中互不关联的子连通图的数目较原图减少1。

命题2：对于连通图G=(V,E)，若|E|=|V|-1，则G中无环路（无向图中的环路必须拥有不少于三条边）。

证明：需要证明对于一个带环连通图，移除环中任意一条边，图依旧连通，而根据命题1知道图连通的必要条件是|E|>=|V|-1，因此可以推导出原图至少有|V|条边。从而利用反证法证明命题的成立。

Answer 2

对于一棵树来说，去掉树中的任意一条边，都会变成两个不连通图，所以答案为B

Answer 3

答案是B。