第七章图与网络(1) 树与最短路问题 1)树的定义:无圈的联通图 (2)树的性质1:树至少有两个悬挂点 树的性质2:是树充分必要条件:不含圈并且边数=点数 树的性质3:是树充分必要条件:联通图并且边数=点数-1 树的性质4:是树充分必要条件:任意两个点正好一条链 (3)图的支撑树及性质: 图的支撑树:图的支承?子图是树 图的支撑树性质:图有支撑树充分必要条件:图联通 (4)求图的支撑树方法: 破圈法 避圈法 运学 狼中描教运筹学 熊中楷教授 第七章 图与网络（1） 树与最短路问题 (1) 树的定义：无圈的联通图 (2) 树的性质1：树至少有两个悬挂点 树的性质2：是树充分必要条件： 不含圈并且 边数＝点数－1 树的性质3：是树充分必要条件： 联通图并且 边数＝点数－1 树的性质4：是树充分必要条件：任意两个点正好一条链 （ 3）图的支撑树及性质： 图的支撑树：图的支承? 子图是树 图的支撑树性质：图有支撑树充分必要条件：图联通 （4）求图的支撑树方法： 破圈法 避圈法