图论 第7章树和割集.ppt

集合与图论 * 第七章 树和割集 主要内容： 树及其性质 生成树 割点、桥和割集 7.1 树及其性质 仅有一个顶点的树称为平凡树。 定义7.1.1 连通且无圈的无向图称为无向树，简 称树。 ? ? ? ? ? ? ? ? ? 图1 一个没有圈的不连通的无向图称为无向森林，简 称森林。 ? ? ? ? ? ? ? ? ? ? 图2 ? 定理7.1.1 设G=(V,E)是一个(p,q)图，则下列各命题等价: (1)G是树。 (2)G的任意两个不同顶点间有唯一的一条路联结。 (3)G是连通的且p=q+1。 (4)G中无圈且p=q+1。 (5)G中无圈且G中任意两个不邻接的顶点间加一条边，则得到一个有唯一的一个圈的图。 (6)G是连通的,并且若p≥3，则G不是Kp,G中任意两个不邻接的顶点间加一条边，则得到一个有唯一的一个圈的图。 证 (1)?(2) (1)G是树。 (2)G的任意两个不同顶点间有唯一的一条路联结。 其次，用反证法，如果G中存在两点，这两点之间 有两条不同的路。 定理6.3.4 ：如果图G中的两个不同顶点u与v间有 两条不同路联结，则G中有圈。 这与G是树矛盾。 首先，因为G是连通的，所以G中任意两顶点间有路联结； 所以G中任意两顶点间有唯一的路联结。 (2)?(3) 对G的顶点数p进行归纳证明： 假设p≤k时结论成立，考虑p=k+1时的情况： p1=q1+1，p2=q2+1 p=p1+p2=q1+q2+2 (2)G的任意两个不同顶点间有唯一的一条路联结。 (3)G是连通的且p=q+1。 当p为1或2时，连通图G中显然有p=q+1。 从G中去掉一条边x, 　　由于G的任意两个不同顶点间有唯一的路，则G-x恰有两个支，设这两个支分别为(p1,q1),(p2,q2)。 =(q1+q2+1)+1 =q+1。 (3)?(4) 只须证G中无圈即可。(用反证法) (3)G是连通的且p=q+1。 (4)G中无圈且p=q+1。 首先G是连通的，若G中有圈，任选G中一个圈， 去掉圈上一条边x，设G1=G-x，则G1还是连通的。 如此下去经有限步可得一个无圈的连通图Gn。 Gn的边数等于q-n， 这与已知条件p=q+1矛盾。 若G1中还有圈，再去掉圈上一条边y，设 G2=G1-y，G2还是连通的。 Gn是树并且p=q-n+1， Gn的顶点数p， 所以G中无圈。 (4)?(5) (4)G中无圈且p=q+1。 (5)G中无圈且G中任意两个不邻接的顶点间加一条边，则得到一个只有一个圈的图。 只需证明G是树。 需证G的任意两个不同顶点间有唯一的一条路联结。 证明：只须证明G连通即可, 假设G不连通，则必有k个支且k≥2，每个 支都是连通的且无圈，故每个支是树。 由假设k≥2，这与p=q+1相矛盾，因此G是连通的。 对每个支(1)成立，从而(2)和(3)也成立。 所以，在每个支中有pi=qi+1，i=1,2,...,k, 因此G是树。 G的任意两个不同顶点间有唯一的一条路联结; G中无圈且G中任意两个不邻接的顶点间加一条边，则得到一个只有一个圈的图; (5)?(6) (5)G中无圈且G中任意两个不邻接的顶点间加一条边，则得到一个有唯一的一个圈的图。 (6)G是连通的，并且若p≥3，则G不是Kp，G中 任意两个不邻接的顶点间加一条边，则得到一个有 唯一的一个圈的图。 2、假设(5)成立， G中无圈，因此，当p≥3时，G 不是Kp，因为Kp中有圈。 证：1、G是连通的，用反证法。 设G至少有两个支，在两支中各选一顶点，并在此 二顶点间加一条边，则得到的图中仍无圈。 这与(5)成立相矛盾，所以G是连通的。 (6)?(1) 设(6)成立。要证G是树。只须证明G中无圈即可。 (6)G是连通的,并且若p≥3，则G不是Kp，又若G的任两个不邻接的顶点间加一条边，则得到一个恰有唯一的一个圈的图。 ①当p=1或2时。显然G中没圈。 ②当p=3时。由于G不是K3，所以G中无圈。 ③当p≥4时, 若这时G中有长为n的圈，则3≤np。 (1)G是树。 如果n=3，由于p≥4，已知条件中G不是Kp，则