第八单元 图论(第1-3节).pptVIP

≤p(G)-2 p(G)-1 同已知条件 q(G) = p(G) -1矛盾，故假设错误。 充分性得证。 必要性：图 G 是一个树 → G 连通，且 q(G)=p(G)-1 → q (G) = p(G) - 1 略（同上，已证毕） 充分性：图 G 连通，且 q(G)= p(G)-1 → 图 G 是一个树 → 图 G 中不含圈 （2）图 G 是一个树 G 连通，且 q (G) = p (G) -1。 ① 先来证明： 图 G 连通，且 q(G) = p(G)-1 → 图G中必有悬挂点 用反证法证明。 设 G 中无悬挂点。 则 G 中所有点的次数都大于等于 2，即 d( vi )≥2，从而可得 （任何图中，顶点次数的总和等于边数的 2 倍，即 ） 从而可知： 关系式 q(G) ≥ p(G) 和已知条件 q(G) = p(G)-1相互矛盾。 从而可知 G 中必有悬挂点。 ② 用数学归纳法证明： 图 G 连通，且 q(G) = p(G)-1 → 图 G 中不含圈 p(G1)=1，q(G1)=0时，G1显然不含圈，结论显然成立； p(G2)=2，q(G1)=1时，G2显然不含圈，结论显然成立； 假设 p(Gn)=n，q(Gn)=n-1时，Gn中不含圈，即结论成立。 下面来证明 p(Gn+1)=n+1，q(Gn+1)=n 时，Gn+1中也不含圈。 Gn+1 中含有悬挂点 设 v 为Gn+1中的悬挂点，考虑图Gn+1-v（图Gn+1中去掉点 v 及 v 的关联边后得到的图）为一个顶点数量为 n 的连通图，且满足 p(Gn+1-v) = p(Gn+1) -1 = n， q(Gn+1-v)= q(Gn+1) -1 = n-1。 从而可知图 Gn+1-v 中不含圈 Gn+1中也不含圈 命题得证 （3） 图 G 是一个树 G 中任意两点之间有唯一一条链相连 必要性：图 G 是一个树 → G 中任意两点之间有唯一一条链相连。 因 G 是连通的：任两个点之间，至少有一条链； 因 G 是无圈的：任两个点之间，只能有一条链，否则则形成了圈。 充分性：G 中任意两点之间有唯一一条链相连 → 图 G 是一个树 G 中任意两点之间有唯一一条链：G 是连通的。 再来证明 G 是无圈的。 反证法。 设 G 中有圈，则这个圈上的两个顶点之间有两条链，与“G中任意两点之间有唯一一条链”相矛盾。故 G 中是无圈的。 命题得证。 （4） 图 G 是一个树 G 无圈，但每加一新边即得唯一一个圈 命题得证。 G 中任意两点之间有唯一一条链相连 G 无圈，但每加一新边即得唯一一个圈 图 G 是一个树 G 连通，但每舍去一边就不连通 （5） 命题得证。 G 中任意两点之间有唯一一条链相连 G 连通，但每舍去一边就不连通 二、图的生成树（支撑树） 1. 定义 （1）生成树 设图 是图 G = ( V, E ) 的生成子图 是一个树，则称 T 是 G 的 如果图 一个生成树。 例： v1 v3 v5 v4 v2 v1 v5 v4 v3 v2 是上图的生成图，但不是生成树。 v1 v5 v4 v3 v2 是上图的生成图，而且是生成树。 v1 v3 v5 v2 v4 （2）树枝 图 G 中，属于生成树的边称为树枝。 （3）弦 图 G 中，不属于生成树的边称为弦。 v1 v5 v4 v3 v2 是上图的生成图，而且是生成树。 v1 v3 v5 v2 v4 弦 树枝 （4）性质 ① p( T ) = p( G ) ② q ( T ) = p ( T ) -1 = p ( G ) -1（树枝数 = 点数 -1）； ③ 弦数（G 中不属于树 T 的边数）= q (G ) –q (T )= q( G ) - [ p( G )-1] = q(G) - p(G) + 1 （弦数= 边数 - 点数 + 1 ） v1 v5 v4 v3 v2 v1 v3 v5 v2 v4 弦 树枝 树枝数= 点数 -1= 5 – 1 = 4 弦数= 边数 - 点数 + 1= 7 - 5 + 1 = 3 2. 定理 图 G 有生成树的充分必要条件是图 G 是连通的。 证明： 必要性：图 G 有生成树 → 图 G 是连通的 图 G 有生成树 T，生成树 T 必是连通，从而图 G 也必是连通的。 充分性：图 G 是连通的 → 图 G 有生成树 如果图 G 是连通的、且无圈，则图 G 本身就是一个树，从而图 G 是它自身的一个生成树。 如果图 G 是连通的、且含有圈（破圈法）： （1）则任取一个圈，从圈中任意去掉一条边，得到图 G 的一个生成子图 G1，如果 G1不含圈，那么 G1 就是 G 的一个生成树； （2）如果 G1 仍含圈，那么从 G1 中任取