社区

数据结构与算法 帖子详情 连通图和树的关系 softwood 2008-07-14 07:09:43 G(V,E)是一个有n个节点的连通图,如果G中有n-1条边,那么G就是一个树.

请问上面假设成立吗?我感觉是成立的,但说不准是为什么.

哪位高人给讲讲啊

...全文

1806 6 打赏 收藏 连通图和树的关系 G(V,E)是一个有n个节点的连通图,如果G中有n-1条边,那么G就是一个树. 请问上面假设成立吗?我感觉是成立的,但说不准是为什么. 哪位高人给讲讲啊 复制链接

扫一扫 分享 转发到动态 举报

写回复 配置赞助广告取 消

确 定

用AI写文章 6 条回复 切换为时间正序 请发表友善的回复… 发表回复 打赏红包 需支付: 0.00 元 取 消 确 定 njwangchuan 2008-07-15 打赏举报 回复 不是成立不成立的问题，树就是按楼主说的“要证明的内容”定义的 Endels 2008-07-15 打赏举报 回复 树的定义就是：没有回路的连通图。

1）n个结点的简单图有n-1条边，必然是连通图，否则是多重图，不符合题意。

2）假设存在1条回路，设这条回路包含的结点数为i,其余结点数为j，可知，需要构成该图的边数为i + j（k个结点构成回路需要k条边），而i + j = n，不符合题意有n-1条边。

3）假设有两条以上的回路，令除其中一条回路以外的所有回路断开一条边，即是(2)所描述的情况，所以其边数>n，不符合题意。

综上，该图是连通图，且没有回路，为树。不过就像3楼说的，原本就差不多是定义了。 hityct1 2008-07-15 打赏举报 回复 再想了一下：数学归纳法就应该可以了。 hityct1 2008-07-15 打赏举报 回复 个人认为：

先证明：n个节点的连通图,至少有n-1条边

再证明：n个节点的连通图有环路，至少有n条边

估计书上都有以上两个证明。 softwood 2008-07-14 打赏举报 回复 谁能给个证明过程啊 tailzhou 2008-07-14 打赏举报 回复 当然是成立的；

自由树就是连通的，无环无向的图；

有n个节点的连通图，如果只有n-1条边，则肯定是无环的；

liantongtu.rar_连通图的判断 本程序是学习图论连通图的极佳案例，可以清楚地进行任意建立集合图，并且随意选取点来自动进行判断连通。 图论- 图的连通性.rar 图论- 图的连通性.rar 建立一个带权无向图用邻接矩阵表示，判断此图是否连通 建立一个带权无向图用邻接矩阵表示，判断此图是否连通，若是连通图，用Prim算法输出该图的最小生成树 数据结构的无向图的连通分量 数据结构的无向图的连通分量

生成树：DFS生成树和BFS生成树以及相关算法

数据结构与算法

33,025

社区成员

35,334

社区内容

发帖 与我相关 我的任务 数据结构与算法 数据结构与算法相关内容讨论专区 复制链接

扫一扫 分享 确定 社区描述 数据结构与算法相关内容讨论专区 社区管理员

加入社区

获取链接或二维码

近7日

近30日

至今

加载中

查看更多榜单

社区公告

暂无公告 试试用AI创作助手写篇文章吧

+ 用AI写文章