推论:若G是n个顶点o个分支的森林,则G 有n-0条边 定理72在任一棵非平凡树T中,至少有两片 树叶。 证明:由于T是连通的,对T的任一顶点 v;,d(v)≥1,并且e=n-1,即所有顶点度数之和 =2(m-1) 下面证明T中至少有两个顶点的度数为1
推论：若G是n个顶点个分支的森林, 则G 有n-条边。 定理7.2:在任一棵非平凡树T中, 至少有两片 树叶。 证 明 : 由 于 T是 连 通 的 , 对 T的 任 一 顶 点 vi ,d(vi )1,并且e=n-1,即所有顶点度数之和 =2(n-1). 下面证明T中至少有两个顶点的度数为 1
72生成树与割集 前面讨论了树本身的性质,下面讨论树作为一个图的子图的情 况,特别是“生成树”。 定义72:图G的生成子图是树T,称T为G的生成树。从G中 删去T的边,得到的图称G的余树,记为7。T中的边称为树 枝(或枝)。7中的边称为G的弦(或连枝)。 由定义可知T与成对出现但不一定是树
7.2生成树与割集 前面讨论了树本身的性质, 下面讨论树作为一个图的子图的情 况,特别是“生成树”。 定义 7.2：图 G 的生成子图是树 T,称 T 为 G 的生成树。从 G 中 删去 T 的边,得到的图称 G 的余树,记为 T 。T 中的边称为树 枝(或枝)。T 中的边称为 G 的弦(或连枝)。 由定义可知 T 与T 成对出现 , 但T 不一定是树
例如下图中给定图G粗线表示G的生成 树T,它的边集是{e1,e4,e5,6},的边集是 {e2,e3,e7,e8} el g3 e6 5 e7
例如下图中给定图G,粗线表示G的生成 树T,它的边集是{e1,e4,e5,e6},的边集是 {e2,e3,e7,e8}
定理73:G是连通图当且仅当G有生成树。 证明:1)G有生成树证明G是连通图。因为 生成树是连通图,生成子图连通,则原图 定连通。 2)G是连通图证明G有生成树 设G是连通图若G没有回路,则G本身就是生 成树; 若G只有一条回路,从这条回路中删去一条 边,仍保持连通,得到一棵生成树; 若G中有多条回路,则重复上述过程,直到得 到一棵生成树为止
定理7.3：G是连通图当且仅当G有生成树。 证明：1) G有生成树证明G是连通图。因为 生成树是连通图,生成子图连通，则原图一 定连通。 2) G是连通图证明G有生成树 设G是连通图,若G没有回路,则G本身就是生 成树； 若G只有一条回路,从这条回路中删去一条 边, 仍保持连通, 得到一棵生成树； 若G中有多条回路, 则重复上述过程, 直到得 到一棵生成树为止
设连通图G有n个顶点,e条边,那么G的任一棵 生成树有n-1条枝,e-n+1条连枝。 设图G有n个顶点,e条边,o个分支,n,e,O之间有 两个简单的关系式: n-O≥0 e-n+o≥0。 定义73:设图G有n个顶点,e条边,o个分支,称 n-O为G的秩,称en+o为图G的零度 显然G的秩是G的各分支中生成树的枝数之和, G的零度是G的各分支中生成树的连枝数之和。 对于连通图G来说,它的秩为n-1,零度为e-n+1
设连通图G有n个顶点, e条边, 那么G的任一棵 生成树有n-1条枝, e-n+1条连枝。 设图G有n个顶点,e条边, 个分支, n,e,之间有 两个简单的关系式: n-0; e-n+0。 定义 7.3:设图G有n个顶点, e条边, 个分支, 称 n-为G的秩, 称e-n+为图G的零度。 显然G的秩是G的各分支中生成树的枝数之和, G的零度是G的各分支中生成树的连枝数之和。 对于连通图G来说, 它的秩为n-1, 零度为e-n+1