哈工大集合论习题课第六章树及割集习题课(学生).doc
- 格式：doc
- 大小：816.00 KB
- 文档页数：7
文档推荐
-
哈工大MATLAB选修课小作业2页数:14
-
哈工大matlab选修课试题页数:9
-
哈工大研究生选修课机电系统智能控制读书报告页数:19
下载文档原格式
合集下载
哈工大集合论习题课第六章树及割集习题课(学生)
第六章树及割集习题课 1讲堂例题例1 设 T 是一棵树， T 有 3 个度为 3 极点， 1 个 2 度极点，其余均是 1 度极点。
则（ 1）求 T 有几个 1 度极点？（ 2）画出知足上述要求的不一样构的两棵树。
剖析：关于任一棵树 T ，其极点数 p 和边数 q 的关系是：q p 1且pdeg(v i )2q ，依据这些性质简单求解。
i 1解：（1）设该树T的极点数为p，边数为q，并设树T中有x个 1 度极点。
于是pdeg(v i ) 3 3 1 2 x 2q 且 p 3 1 x， q p 1，得x 5 。
i 1（ 2）知足上述要求的两棵不一样构的无向树，如图 1 所示。
图1例 2 设 G 是一棵树且(G ) k ，证明G中起码有k个度为1极点。
证：设T 中有 p 个极点，s个树叶，则 T 中其余 p s 个极点的度数均大于等于 2，且起码有一个极点的度大于等于k 。
由握手定理可得：ps ，有s k 。
2q 2 p 2deg( v i ) 2( p s 1) ki 1所以 T 中起码有 k 个树叶。
习题例1 若无向图G中有p个极点，p 1条边，则G为树。
这个命题正确吗？为何？解：不正确。
K 3与平庸图构成的非连通图中有四个极点三条边，明显它不是树。
例2 设树T中有2n个度为 1 的极点，有3n个度为 2 的极点，有n个度为 3 的极点，则这棵树有多少个极点和多少条边？解：设 T 有 p 个极点， q 条边，则q p 12n 3n n 1 6n 1。
由deg(v) 2q 有： 1 2n 2 3n 3 n 2q 2(6n 1)12n 2 ，解得： n =2。
v V故 q 11, p12 。
例 3 证明恰有两个极点度数为 1 的树必为一条通路。
证：设 T 是一棵拥有两个极点度数为 1 的( p,q)树，则q p 1且p2( p 1) 。
deg(v i ) 2qi 1又 T 除两个极点度数为 1 外，其余极点度均大于等于 2，故p p 22( p 1) ，即deg(v i )2deg(v i )i 1i 1p22) 。
ch6习题及答案
习题6解答判断题：1.二叉树中每个结点有两个子女结点，而对一般的树则无此限制，因此二叉树是树的特殊情形。
( ╳ )2.二叉树就是结点度为2的树。
( ╳ )( (哈工大2000年研究生试题)3.二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。
( ╳ ) (陕西省1998年自考试题)4.当k≥1时，高度为k的二叉树至多有21 k个结点。
( ╳ )5.完全二叉树的某结点若无左孩子，则它必是叶结点。
(√)(中科院软件所1997年研究生试题)6.用一维数组存放二叉树时，总是以前序遍历顺序存储结点。
( ╳ )7.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。
( ╳ )8.存在这样的二叉树，对它采用任何次序的遍历，结果相同。
(√)(哈工大2000年研究生试题)9.中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。
(√)10.将一棵树转换成二叉树后，根结点没有左子树，( ╳ )(北邮1999年研究生试题。
)11.由树转换成二叉树，其根结点的右子树总是空的。
(√)12.前序遍历森林和前序遍历与该森林对应的二叉树其结果不同。
( ╳ )13.在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。
( ╳ )14.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。
( ╳ )15.霍夫曼树一定是满二叉树。
( ╳ )16.树的度是树内各结点的度之和。
( ╳ )17.由二叉树的结点构成的集合可以是空集合。
(√)18.一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。
( ╳ )选择题：19.树最适合用来表示( C )。
A．有序数据元素 B. 无序数据元素C．元素之间具有分支层次关系的数据 D. 元素之间无联系的数据20.如果结点A有3个兄弟，而且B是A的双亲，则B的度是( D )。
哈工大集合与图论习题
集合与图论习题第一章习题．画出具有个顶点地所有无向图(同构地只算一个).．画出具有个顶点地所有有向图(同构地只算一个).．画出具有个、个、个顶点地三次图.．某次宴会上，许多人互相握手.证明：握过奇数次手地人数为偶数(注意，是偶数).．证明：哥尼斯堡七桥问题无解.．设与是图地两个不同顶点.若与间有两条不同地通道(迹)，则中是否有回路？．证明：一个连通地(，)图中≥.．设是一个(，)图，δ()≥[]，试证是连通地.．证明：在一个连通图中，两条最长地路有一个公共地顶点.．在一个有个人地宴会上，每个人至少有个朋友(≤≤).试证：有不少于个人，使得他们按某种方法坐在一张圆桌旁，每人地左、右均是他地朋友.b5E2R。
．一个图是连通地，当且仅当将划分成两个非空子集和时，总有一条联结地一个顶点与地一个顶点地边.．设是图.证明：若δ()≥ ，则包含长至少是δ()地回路.．设是一个(，)图，证明：()≥，则中有回路；()若≥，则包含两个边不重地回路.．证明：若图不是连通图，则是连通图.．设是个(，)图，试证：()δ()·δ()≤[()]([()])，若≡，，( )() δ()·δ()≤[()]·[()]，若≡( )．证明：每一个自补图有或个顶点.．构造一个有个顶点而没有三角形地三次图，其中≥..给出一个个顶点地非哈密顿图地例子，使得每一对不邻接地顶点和，均有≥．试求中不同地哈密顿回路地个数.．试证：图四中地图不是哈密顿图.．完全偶图，为哈密顿图地充分必要条件是什么？．菱形面体地表面上有无哈密顿回路？．设是一个(≥)个顶点地图.和是地两个不邻接地顶点，并且≥.证明：是哈密顿图当且仅当是哈密顿图.．设是一个有个顶点地图.证明：若>δ()，则有长至少为δ()地路.．证明具有奇数顶点地偶图不是哈密顿图.．证明：若为奇数，则中有()个两两无公共边地哈密顿回路.．中国邮路问题：一个邮递员从邮局出发投递信件，然后返回邮局.若他必须至少一次走过他所管辖范围内地每条街道，那么如何选择投递路线，以便走尽可能少地路程.这个问题是我国数学家管梅谷于年首先提出地，国外称之为中国邮路问题.p1Ean。
哈工大集合论习题
第一章 习题1.写出方程2210x x ++=的根所构成的集合。
2.下列命题中哪些是真的，哪些为假 3设有n 个集合12,,,n A A A 且121n A A A A ⊆⊆⊆⊆，试证：12n A A A ===4.设{,{}}S φφ=，试求2S？5.设S 恰有n 个元素，证明2S有2n个元素。
6.设A 、B 是集合，证明:(\)()\A B B A B B B φ=⇔=7.设A 、B 是集合，试证A B A B φ=⇔=∆8. 设A 、B 、C 是集合，证明：()()A B C A B C ∆∆=∆∆9.设A 、B 、C 为集合，证明\()(\)\A B C A B C =10.设A ，B ，C 为集合，证明： ()\(\)(\)A B C A C B C =11.设A,B,C 为集合，证明：()\(\)(\)A B C A C B C =12.设A,B,C 都是集合，若A B A C =且A B B C =，试证B=C 。
13.设A,B,C 为集合，试证：(\)\(\)\(\)A B C A B C B =14.设X Y Z ⊆⊆，证明\(\)(\)Z Y X X Z Y =15.下列命题是否成立？ （1）(\)\(\)A B C A B C =（2）(\)()\AB C A B C =（3）\()()\A B C A B B = 16．下列命题哪个为真？ a)对任何集合A,B,C ，若AB BC =，则A=C 。
b)设A,B,C 为任何集合，若A B A C =，则B=C 。
c)对任何集合A,B ，222A BAB =。
d)对任何集合A,B ，222A B AB =。
e)对任何集合A,B ，\22\2A BA B =。
f)对任何集合A,B ，222A BAB∆=∆。
17．设R,S,T 是任何三个集合，试证：（1）()()S T S T S T ∆=∆；（2）()()()R S T R S R T ∆⊇∆∆；（3）()()()()()R S R T R ST R S R T ∆∆⊆∆⊆∆∆；（4）()()()RS T RS R T ∆⊇∆ 18．设A 为任一集，{}IB ξξ∈为任一集族（I φ≠），证明：()()IIA B A B ξξξξ∈∈=19．填空：设A,B 是两个集合。
哈工大威海校区2015春集合图论试题A
姓名: 班级: 学号:遵 守 考 试 纪 律 注意 行 为 规 范哈尔滨工业大学（威海）2014 / 2015学年春季学期集合论与图论 试题卷（A ）考试形式（开、闭卷）：闭卷 答题时间：105（分钟）本卷面成绩占课程成绩 30 %试卷说明：[1] 卷面总分100分，取卷面成绩的70%计入总分，平时成绩30%。
[2] 填空题请在答题卡内答题，其它处无效。
[3] 答卷时禁止拆开试卷钉，背面即为草稿纸。
一、填空题（每小题2分，共20分）(1) 集合的（）表示方法可能产生悖论。
(2) 映射f左可逆的充分必要条件是：（）。
(3) 设R={(a, b),(c, d),(e, f)}是一个二元关系，则R的逆记为R-1，R-1=（）。
(4) n个顶点的完全图的边的个数是( )。
(5) 一个无向图的边数为20，那么所有顶点的度数和为（）。
(6) 设G是一个有p个顶点q条边的最大可平面图,则: q=( )。
(7) 一个图是树当且仅当G是连通的且p=（）。
(8) G是一个p个顶点q条边的最大平面图,则G的每个面都是( )形。
(9) 若G是偶数个顶点的圈，则G是（）色的。
(10) 当顶点数大于2时，树的连通度是（）。
二、简答题(每小题5分，共20分)1.设集合X=｛a,b,c,d,e｝，E={a,b,c}是X的子集。
写出E的特征函数。
2.R=｛（1，b），（2,c），（3,a），（4,d）｝是集合A=｛1，2，3，4｝到集合B=｛a,b,c,d｝的一个二元关系，画出R的关系矩阵和关系图。
3.举例说明什么是偏序关系？什么是偏序集？4.简述图的连通度、边连通度、最小度之间的关系。
三、证明题（每小题10分，共20分）1. A和B是两个集合，证明：(A∪B)c=A c∩B c2. 证明：3度正则图（每个顶点的度数都是3）的顶点的数目必为偶数。
四、计算题（每小题5分，共20分）1. 集合X={a,b,c,d,e,f,g,h},X的两个子集是A=｛a,b,c,d｝,B={e,f,g,h}求：A⋃B,A⋂B,A c,A\B,A∆B2、一个学校学生总人数为336人，共有数学，物理，化学3门课。
哈工大电路习题答案
第十三章 习题13.1 在图示网络的图中，问下列支路集合哪些是割集？哪些不是割集？为什么？(1)1、3、5；(2)2、3、4、7、8；(3)4、5、6；(4)6；(5)4、7、9；(6)1、3、4、7。
图 题13.1图 题13.213.2 在图示网络的图中，任选一树，指出全部的基本回路的支路集合和全部基本割集的支路集合。
13.3 设某网络的基本回路矩阵为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--=100100010111001110B（1） 若如已知连支电流44=i A,55=i A,66=i A ，求树支电流。
（2） 若已知树支电压11=u V ，22=u V ，33=u V ，求连支电压。
（3） 画出该网络的图。
13.4 网络的图如图所示，已知部分支路电流。
若要求出全部支路电流应该怎样补充已知条件？图 题13.41u 图 题13.513.5 网络的图如图所示，已知其中的三条支路电压，应该怎样补充已知条件，才能求出全部未知支路电压？13.6 设某网络图的关联矩阵为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-----=010110000101101110001A取1,2,3支路为树支，写出基本割集矩阵。
13.7 某网络图的基本割集矩阵为⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡------=00111000011101001110001010010001C 画出对应的网络的图。
13.8 已知某网络图的基本回路矩阵⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡----=10111000011101001100001001100001B 试写出此网络的基本割集矩阵C 。
13.9 某网络有6条支路，已知3条支路的电阻分别是Ω=21R ，Ω=52R ，Ω=103R ；其余3条支路的电压分别是44=u V ，65=u V ，126-=u V 。
又知该网络的基本回路矩阵为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-----=110100*********001B试求全部支路电流。
13.10 图示网络的图，根据所选的树，列出独立的KCL 方程和独立的KVL 方程，并写成矩阵形式。
离散数学刘任任版第6章答案 优质课件
2019/12/6
6
6
题5已证。
2019/12/6
7
71
2
1
2
1
2
4
3
4
3
4
3
2
1
2
1
2
4
3
4
3
4
3
1
2
1
2
1
2
4
3
4
3
4
3
2019/12/6
8
1
2
1
2
1
2
4
34
3
4
3
1
2
1
2
1
2
4
3
4
3
4
3
1
2
4
3
2019/12/6
9
9 e
e
=
e+
=
K2,3 e
+
e
e
+
+
e
=
+
+
+e
+e+ e +
2019/12/6
2019/12/6
4
4
设u V (G),且d (u) m k.于是, 存在 若v1,v i (i ,v1m,,Vm()G不)是,使悬u挂vi点,则E(有Gv)i,i V(1G, ), , m 使vivi' E(G)如此下去, 有vi(l) V (G), 满足vi(l)不等于v j , j 1,, m,
离散数学 习题集
第六章 树
2019/12/6
1
1
由假设知，G是一个无回路的连通图，故 G是树。
哈工大集合论与图论第六章作业题答案
第六章图的基本概念P习题2061．画出具有4个顶点的所有无向图(同构的只算一个)。
11个2．画出具有3个顶点的所有有向图(同构的只算一个)。
16个3．画出具有4个、6个、8个顶点的三次图。
略4．某次宴会上，许多人互相握手。
证明：握过奇数次手的人数为偶数(注意，0是偶数)。
把实际问题转化为图论问题，然后用握手定理的推论。
P习题2091．设u与v是图G的两个不同顶点。
若u与v间有两条不同的通道(迹)，则G 中是否有圈？若u与v间有两条不同的通道，G中无圈若u与v间有两条不同的迹，G中有圈2．证明：一个连通的(p，q)图中q≥p-1。
数学归纳法3．设G是一个（p，q）图，且2/)2>p-q，则G是连通的。
p)(1(-6．在一个有n个人的宴会上，每个人至少有m个朋友(2≤m≤n)。
试证：有不少于m+1个人，使得他们按某种方法坐在一张圆桌旁，每人的左、右均是他的朋友。
证明：把实际问题转化为图论问题，就和下面的题一样了。
8．设G是图。
证明：若δ(G)≥2，则G包含长至少是δ(G)+1的圈。
这两个题和这个题一样的证明方法。
P习题2161．证明：若图G不是连通图，则G c 是连通图。
2．证明：每一个自补图有4n或4n+1个顶点。
P习题2281.给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有：degu+degv≥9。
下图中任意一对不邻接的顶点u和v，均有：degu+degv≥9。
2．试求Kp中不同的哈密顿圈的个数。
(p-1)!/24．完全偶图Km，n为哈密顿图的充分必要条件是什么？10．证明具有奇数顶点的偶图不是哈密顿图。
离散数学结构 第6章 集合代数
第六章集合代数1. 集合，相等，（真）包含，子集，空集，全集，幂集2. 交，并，（相对和绝对）补，对称差，广义交，广义并3. 文氏图，有穷集计数问题4. 集合恒等式（等幂律，交换律，结合律，分配律，德·摩根律，吸收律，零律，同一律，排中律，矛盾律，余补律，双重否定律，补交转换律等）学习要求1. 熟练掌握集合的子集、相等、空集、全集、幂集等概念及其符号化表示2. 熟练掌握集合的交、并、（相对和绝对）补、对称差、广义交、广义并的定义及其性质3. 掌握集合的文氏图的画法及利用文氏图解决有限集的计数问题的方法4. 牢记基本的集合恒等式（等幂律、交换律、结合律、分配律、德·摩根律、收律、零律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律）5. 准确地用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式6.1 集合的基本概念一．集合的表示集合是不能精确定义的基本概念。
直观地说，把一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的元素或成员。
例如：方程x2－1＝0的实数解集合；26个英文字母的集合；坐标平面上所有点的集合；……集合通常用大写的英文字母来标记，例如自然数集合N(在离散数学中认为0也是自然数)，整数集合Z，有理数集合Q，实数集合R，复数集合C等。
表示一个集合的方法有两种：列元素法和谓词表示法，前一种方法是列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。
例如A={a，b，c，…，z}Z={0，±1，±2，…}都是合法的表示。
谓词表示法是用谓词来概括集合中元素的属性，例如集合B＝{x|x∈R∧x2－1＝0}表示方程x2－1＝0的实数解集。
许多集合可以用两种方法来表示，如B也可以写成{-1，1}。
但是有些集合不可以用列元素法表示，如实数集合。
集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素，如{1，1，2，2，3}＝{1，2，3}集合的元素是无序的，如{1，2，3}＝{3，1，2}在本书所采用的体系中规定集合的元素都是集合。
哈工大2006年秋季学期《集合论与图论》试题
哈工大2006年秋季学期《集合论与图论》试题哈工大 2006年秋季学期《集合论与图论》试题本试题满分90，平时作业分满分10分。
一、（10分，每小题1分）判断下列各命题真伪（真命题打“√”号，假命题打“×”号）：1．从{1，2，3}到{4，5}共有9个不同的映射。
（）2．从{1，2，3}到{4，5}共有5个不同的满射。
（）3．从{4，5}到{1，2，3}共3个不同的单射。
（）4．集合{1，2，…，10}上共有2100个不同的二元关系。
（）5．如果A为可数集，则2A也是可数集合。
（）6．欧拉图中没有割点。
（）7．有向图的每一条弧必在某个强支中。
（）8．P为正整数，Kp的顶点连通度为P－1。
（）9．（P，P）连通图至少有2个生成树。
（）10．每个有2个支的不连通图，若每个顶点的度均大于或等于2，则该图至少有2个圈。
（）二、（20分，每小题2分）计算题。
对每一小题给出计算结果：1．{1，2，…，n}上有多少个反自反且对称的二元关系？（）2．把置换123456789579413826分解成循环置换的乘积。
（）3．计算下面两个图G1和G2的色数。
（）G1：G2：（答：G1的色数为，G2的色数为）4．设X为集合，R为X上的偏序关系，计算1iiR ∞=等于什么。
（）5．求下面的有向图D的邻接矩阵和可达矩阵。
D=-------------------：（）6．一个有向图D=(V，A)满足什么条件是V到V的一个映射的图？（）7．P个顶点的无向连通图G的邻接矩阵中至少有多少个1？（）8．设X为n 个元素的集合，X上有多少个二元运算？（）9．9个学生，每个学生向其他学生中的3个学生各送一张贺年卡。
确定能否使每个学生收到的卡均来自其送过卡的相同人？为什么？（）10．某次会议有100人参加，每人可以是诚实的，也可能是虚伪的。
已经知道下面两项事实：（1）这100人中至少有一人是诚实的；（2）任两人中至少有一人是虚伪的。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第六章 树及割集习题课1课堂例题例1 设T 是一棵树，T 有3个度为3顶点，1个2度顶点，其余均是1度顶点。
则（1）求T 有几个1度顶点？（2）画出满足上述要求的不同构的两棵树。
分析：对于任一棵树T ，其顶点数p 和边数q 的关系是：1q p =-且1deg()2ipi v q ==∑，根据这些性质容易求解。
解：（1）设该树T 的顶点数为p ，边数为q ，并设树T 中有x 个1度顶点。
于是1deg()33122ipi v x q ==⨯+⨯+=∑且31p x =++，1q p =-，得5x =。
（2）满足上述要求的两棵不同构的无向树，如图1所示。
图1例2设G 是一棵树且()G k ∆≥，证明G 中至少有k 个度为1顶点。
证：设T 中有p 个顶点，s 个树叶，则T 中其余p s -个顶点的度数均大于等于2，且至少有一个顶点的度大于等于k 。
由握手定理可得：1222()2(1)pi i q p deg v p s k s ==-=≥--++∑，有s k ≥。
所以T 中至少有k 个树叶 。
习题例1 若无向图G 中有p 个顶点，1p -条边，则G 为树。
这个命题正确吗？为什么？解：不正确。
3K 与平凡图构成的非连通图中有四个顶点三条边，显然它不是树。
例2设树T 中有2n 个度为1的顶点，有3n 个度为2的顶点，有n 个度为3的顶点，则这棵树有多少个顶点和多少条边？解：设T 有p 个顶点，q 条边，则123161q p n n n n =-=++-=-。
由deg()2v Vv q ∈=∑有：1223322(61)122n n n q n n ⨯+⨯+⨯==-=-，解得：n =2。
故11,12q p ==。
例3证明恰有两个顶点度数为1的树必为一条通路。
证：设T 是一棵具有两个顶点度数为1的(,)p q 树，则1q p =-且1deg()2pii v q ==∑2(1)p =-。
又T 除两个顶点度数为1外，其他顶点度均大于等于2，故211deg()2deg()2(1)p p iii i v v p -===+=-∑∑，即21deg()2(2)p ii v p -==-∑。
因此2p -个分支点的度数都恰为2，即T 为一条通路。
例4 画出具有4、5、6、7个顶点的所有非同构的无向树。
解：4个顶点的非同构的无向树有两棵，如图21(),()a b 所示； 5个顶点的非同构的无向树有3棵，如图21(),(),()c d e 所示。
（a ） (b) (c) (d) (e)图26个顶点的非同构的无向树有6棵，如图3所示。
图37个顶点的非同构的无向树有11棵，如图4所示。
所画出的树具有6条边，因而七个顶点的度数之和应为12。
由于每个顶点的度数均大于等于1，因而可产生以下七种度数序列127(,,,)d d d L ：（1）1111116；（2）1111125；（3）1111134；（4）1111224；（5）1111233；（6）1112223；（7）1122222。
在（1）中只有一个星形图，因而只能产生1棵树1T 。
在（2），（3）中有两个星形图，因而也只能各产生1棵非同构的树，分别设为 23,T T 。
在（4），（5）中有三个星形图，但三个星形图是各有两个是同构的，因而各可产生两棵非同构的树，分别设为45,T T 和67,T T 。
在（6）中，有四个星形图，有三个是同构的，考虑到不同的排 列情况，共可产生三棵非同构的树，设为8910,,T T T 。
在（7）中，有五个星形图，都是同构的，因而可产生1棵树， 设为11T 。
七个顶点的所有非同构的树111T T :如图2所示。
T 1 T 2 T 3 T 4 T 5 T 6T 7 T 8 T 9 T 10 T 11图4例5设无向图G 是由(2)k k ≥棵树构成的森林，至少在G 中添加多少条边才能使G 成为一棵树？解：设G 中的k 个连通分支为：12,,,k T T T L ，i v ∈i T ，1,2,,i k =L 。
在G 中添加边1{,}i i v v +，1,2,,1i k =-L ，设所得新图为T ，则T 连通且无回路，因而T 为树。
故所加边的条数1k -是使得G 为树的最小数目。
例6 证明：任意一棵非平凡树都是偶图。
分析：若考虑一下数据结构中树（即有向树）的定义，则可以很简单地将树中的顶点按层次分类，偶数层顶点归于顶点集0V ，奇数层顶点归于顶点集1V ，图G 中每条边的端点一个属于0V ，另一个属于1V ，而不可能存在关联同一个顶点集的边。
同理，对于无向树，可以从任何一个顶点V 出发，给该树的顶点标记奇偶性，例如，v 标记0，与v 相邻的顶点标记1，再给与标记为1的所有相邻的顶点标记0，依次类推，直到把所有的顶点标记完为止。
最后，根据树的性质证明，任何边只可能关联1V （标记为 1的顶点集）和0V （标记为0的顶点集）之间的顶点。
证1从任何一个顶点v 出发，给该树的顶点做标记，v 标记0，与v 相邻的顶点标记1，然后再给与标记为1的所有顶点相邻的顶点标记0，……，依次类推，直到把所有的顶点标记完为止。
下面证明：对于任何边只能关联1V （标记为1的顶点集）和0V （标记为0的顶点集）之间的顶点。
不妨假设，若某条边e 关联1V 中的两个顶点，设为1v 和2v ，又因为根据上述的标记法则，有1v 到v 的路1P 和2v 到v 的路2P 。
设1P 与2P 离1v 和2v 最近的顶点为u ，所以，树中存在回路：11221v PuP v ev ，与树中无回路的性质矛盾。
所以，任意边只能关联1V （标记为1的顶点集）和0V （标记为0的顶点集）之间的顶点。
所以，任意一棵非平凡树都是偶图。
证2 设T 是任一棵非平凡树，则T 无回路，即T 中所有回路长都是零。
而零是偶数，故由偶图的判定定理可知T 是偶图。
例7（1）一棵无向树有i n 个度数为i 的顶点，1,2,,i k =L 。
23,,,k n n n L 均为已知数，问1n 应为多少？（2）在（1）中，若(3)r n r k ≤≤未知，()j n j r ≠均为已知数，问rn 应为多少？解：（1）设T 为有p 个顶点，q 条边无向树，则1q p =-，1ki i p n ==∑。
由握手定理：1deg 2pii vq ==∑，有11deg 222p ki i i i v in q p =====-∑∑，即112222kki i i i in p n ===-=-∑∑。
①由式①可知：122222(2)2kkki i i i i i n in n i n ====-+=-+∑∑∑。
（2）对于3r ≥，由①可知：11(2)22k r i i i r n i n r =≠=---⎡⎤⎢⎥⎢⎥⎣⎦∑。
例8证明：任一非平凡树最长路的两个端点都是树叶。
证：设T 为一棵非平凡的无向树，12k L v v v =L 为T 中最长的路，若端点1v 和k v 中至少有一个不是树叶，不妨设k v 不是树叶，即有deg()2k v ≥，则k v 除与L 上的顶点1k v -相邻外，必存在1k v +与k v 相邻，而1k v +不在L 上，否则将产生回路。
于是11k k v v v +L 仍为T 的一条比L 更长的路，这与L 为最长的路矛盾。
故k v 必为树叶。
同理，1v 也是树叶。
例9设无向图G 中有p 个顶点，1q -条边，则G 为连通图当且仅当G 中无回路。
证：必要性：因为G 中有p 个顶点，边数1q p =-，又因为G 是连通的，由定理可知G 为树，因而G 中无回路。
充分性：因为G 中无回路，又边数1q p =-，由定理可知G 为树，所以G 是连通的。
例10设G 是一个(,)p g 图，证明：若g p ≥，则G 中必有回路。
证：（1）设G 是连通的，则若G 中无回路，则G 是树，故1q p =-与q p ≥矛盾。
故G 中必有回路。
（2）设G 不连通，则G 中有(2)k k ≥个分支，12,,,k G G G L 。
若G 中无回路，则G 的各个分支(1,2,,)i G i k =L 中也无回路，于是各个分支都是树，所以有：1i i q p =-，1,2,,i k =L 。
相加得：(2)q p k k =-≥与q p ≥矛盾，故G 中必有回路。
综上所述，图G 中必有回路。
例11设12,,,p d d d L 是p 个正整数，2p ≥，且122pi i d p ==-∑。
证明存在一棵顶点度数为12,,,p d d d L 的树。
证：对顶点p 进行归纳证明。
当2p =时，122222d d +=⋅-=，则121d d ==，故以12,d d 为度数的树存在，即为一条边。
设对任意1p -个正整数121,,,p d d d -L ，只要112(1)2p i i d p -==--∑，则存在一棵顶点度数为121,,,p d d d -L 的树。
对p 个正整数'''12,,,pd d d L ，若有'122pi i d p ==-∑，则'''12,,,p d d d L 中必有一个数为1，必有一个数大于等于2；不妨设''11,2p d d =≥，因此对1p -个正整数''''231,,,,1p pd d d d --L ，有1''2(1)2(1)2p i p i d d p -=+-=--∑，故存在一棵顶点度数为''''231,,,,1p p d d d d --L 的树'T 。
设'T 中u 的度数为'1p d -，在'T 中增加一个顶点v 及边{,}u v ，得到一个图T ，则T 为树。
又T 的顶点度数为'''12,,,pd d d L ，故由归纳法知原命题成立。
3.4 例题例1 G 的一条边e 不包含在G 的任一回路中当且仅当e 是G 的桥。
分析：这个题给出了判断桥的充要条件，应该记住。
证：必要性：设e 是连通图G 的桥，e 关联的两个顶点是u 和v 。
若e 包含在G 的一个回路中，那么除边e uv =外还有一条分别以u 和v 为端点的路，所以删去边e 后，G 仍是连通的，这与e 是桥相矛盾。
充分性：若边e 不包含在G 的任意回路中，则连接顶点u 和v 只有边e ，而不会有其它连接u 和v 的路。
因为若连接u 和v 还有不同于边e 的路，此路与边e 就组成了一条包含边e 的回路，从而导致矛盾。
所以，删去边e 后，u 和v 就不连通了，故边e 是桥。
例2设G 是连通图，满足下面条件之一的边应具有什么性质 ？（1）在G 的任何生成树中； （2）不在G 的任何生成树中。