正在加载图片...
生成树 口定义:若图G的生成子图是树,则该子图称为G的 生成树。 口注:含有G的所有顶点的子图称为G的生成子图 口无向图G连通当且仅当G有生成树 口证明(充分性显然): →注意:若G是有简单回路的连通图,删除回路上的 一条边,G中的回路一定减少。(因此,用“破圈法” 总可以构造连通图的生成树) 口简单无向图G是树当且仅当G有唯一的生成树。生成树  定义:若图G的生成子图是树,则该子图称为G的 生成树。  注:含有G的所有顶点的子图称为G的生成子图  无向图G连通当且仅当G有生成树  证明(充分性显然):  注意:若G是有简单回路的连通图,删除回路上的 一条边,G中的回路一定减少。(因此,用“破圈法” 总可以构造连通图的生成树)  简单无向图G是树当且仅当 G有唯一的生成树
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有