2.1树及其性质 例:电话线架设、比赛程序、组织结构等。 树连通的无圈的无向图称为树。 □合
运筹学 2.1 树及其性质 例: 电话线架设、比赛程序、组织结构等。 树:连通的无圈的无向图称为树
树的性质 图G=(V,E),p个点、q条边下列说法是等价 的 (1)G是一个树 (2)G连通,且恰有p-1条边。 (3)G无圈,且恰有p-1条边。 (4)G连通,但每舍去一边就不连通。 (5)G无圈,但每增加一边即得唯一一个圈。 (6)G中任意两点之间恰有一条链简单链
运筹学 树的性质： 图G=（V，E），p个点、q条边下列说法是等价 的 （1）G是一个树 （2）G连通，且恰有p-1条边。 （3）G无圈，且恰有p-1条边。 （4）G连通，但每舍去一边就不连通。 （5）G无圈，但每增加一边即得唯一一个圈。 （6）G中任意两点之间恰有一条链(简单链)
22图的支撑树(生成树) 定义设图T=(V,E)是图G=(V,E)的支 撑子图如果T是一个树,则称T是G的 个支撑树 定理5:图G=(V,E)有支撑树的充分 必要条件是G是连通的。 □合
运筹学 2.2 图的支撑树（生成树） 定义:设图T=(V，E’) 是图G=(V,E)的支 撑子图,如果T是一个树, 则称T是G的一 个支撑树。 定理5：图G=（V，E）有支撑树的充分 必要条件是G是连通的
找图中生成树的方法 求支撑树的破圈法 -个 □合
运筹学 找图中生成树的方法： 求支撑树的破圈法
找图中生成树的方法 求支撑树的避圈法 深探法 广探法 □合
运筹学 求支撑树的避圈法 找图中生成树的方法： 深探法 广探法