树的有关定义-Read.PPTVIP

第三章 树 3.1 树的定义及性质 定义：树是不含回路的连通图。 　树的边称为树枝, 度的1的结点称为树叶。 　若e 是图G的一条边，当G－e比G的连通支数增多时，称e 是G的割边。 2. 割边的性质 　定理　 边e是G的割边当且仅当e不属于G的任何回路. 　证明: (1)必要性. 　 若e属于某个回路C，则去掉e后e所在的连通支仍是一个连通支，即连通支个数没有变化，故e不是割边，矛盾。 (2)充分性. 若e不属于G的任何回路，则e所在的连通支将分为两个不同连通支，从而e是G的割边。否则，设e=(u,v), 则u,v仍在同一连通支内，即u,v之间有一条路L 相连，因此L+e 是G的一个回路，从e属于回路L＋e, 与题设矛盾。 3. 树的等价定义 定理 设n=2, 树T 的以下性质相互等价： 1) T 连通且无回路; 2) T 连通且每条边都是割边; 3) T 连通有n-1条边;(返回34) 4) T 有n-1条边且无回路; 5) T 的任意两结点间有唯一的道路; (返回5) 6) T 无回路,但在任意不相邻两点间加上一边后恰有一个回路。 (返回5) 证：1) ?2): 由上一定理即得。 　2) ?3): (察看)对n作归纳法。n=2时显然成立，设n=k时成立。对n=k+1，由于T必存在树叶(否则必存在回路，从而无割边存在，矛盾)，删除一个树叶及相关联的树枝后，应用归纳假设即知命题成立。 　3) ?4): (察看)对n作归纳法。n=2时显然成立，设n=k时成立。对n=k+1，若T有度为1的点，则删除此点及关联的一边后，应用归纳假设即知结论成立。 　若T的所有结点度数均大于1，则T中存在回路。因为在回路中删去一边后，剩下的图 仍然连通；若剩下的图仍含回路，再在此回路上删去一边，…，如此下去，作若干次边的删除后，最后剩下的图T’仍连通且结点个数仍为n, 但已不含回路. 　　此时必有度为1的点，且删去此点及相关联的边后，剩下的图也必有度为1的点(否则就含有回路) 。 　一次删去 一个度为1的点及相关联的边，n-1次后删除后只剩一个孤立点。于是原图的边数超过n-1, 矛盾。 　4) ?5): (察看)先证T的任意两点连通，否则T至少有两个连通支。设T的全部连通支为： T1，T2，…, Tk (k=2), 则Ti 连通且无回路，因此仿前可证Ti 的边数为ni –1 ( ni为Ti 的结点个数), i =1,2,…,n. 于是，T的边数为 (n1 –1 )+(n2–1 )+…+(nk –1 ) = (n1 + n2+…+nk) –k=n-kn-1, 矛盾。 　　再证两结点间的路是唯一的。若不唯一，则T中必含一个回路(参见下图)，矛盾。 　5) ?6): (察看)若T含一个回路，则此回路上的任意两点间的路不唯一，矛盾。 　对于任意不相邻的两点u,v, 它们之间有一条唯一的路L，于是 L＋(u,v) 就是一个回路，而且过边(u,v)的回路仅这一个(否则u到v的路不唯一)。 6) ?1): 显然。 　 小 结 一个图是否构成一棵树的判断条件 1.连通性：任去一边不连通(边最少的连通图) 2.无回路：任加一边有回路(边最多的无回路的图) 3.恰有n-1条边 4. 任意两点间有唯一路存在。 这四个条件中任意有二个成立即构成树。尤其是前三个条件，更直观、更简单。 4. 定理 树中一定有叶子结点。 证明:若无叶子结点存在, 则每个结点的度数不小2,则从任一结点出发，可以一直往前行走。 因为结点个数是有限的，故总会遇到一个已到过的结点，这样就得到一个回路，与树的定义矛盾。 定义 若图G的一个支撑子图T是一棵树，则称树T是G的一棵支撑树或生成树。 图G有支撑树的充要条件是G是连通的。 3.2 基本关联矩阵与支撑树 关联矩阵与基本关联矩阵 关联矩阵中，图G的一条边对应一列，一个结点对应一行。 在图G的关联矩阵B中，删去点vk 对应的第k行，所得矩阵称为G的一个基本关联矩阵Bk 。 基本关联矩阵与图的支撑树之间有密切关系。 2. 关联矩阵及基本关联矩阵的秩 矩阵的秩= 矩阵线性无关行的最大行数 = 矩阵线性无关列的最大列数 = 矩阵中非奇异子方阵的最大阶数 定理1 设B为有向图G的关联矩阵，则 秩(B) n . 证：因为B的全部行相加，结果为零向量，即n 个行向量线性相关，故秩(B) n . 定理2 设B0 是有向图G的任一基本关联矩阵B的任一k 阶子方阵，则