哈工大集合论习题课第六章树及割集习题课

习题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 是两个集合。

哈尔滨工程大学附中2014三维设计高考数学一轮单元复习精品练习：集合与逻辑本试卷分第Ⅰ卷(选择题)和第Ⅱ卷(非选择题)两部分．满分150分．考试时间120分钟．第Ⅰ卷(选择题 共60分)一、选择题 (本大题共12个小题，每小题5分，共60分，在每小题给出的四个选项中，只有一项是符合题目要求的)1．下列有关命题的说法正确的是( )A ．命题“若1,12==x x 则”的否命题为：“若1,12≠=x x 则”；B ．“1-=x ”是“0652=--x x ”的必要不充分条件；C ．命题“01,2<-+∈∃x x R x 使得”的否定是：“01,2>-+∈∀x x R x 均有”；D ．命题“若y x y x sin sin ,==则”的逆否命题为真命题；【答案】D2．下列命题中的假命题是( )A ．x ∀∈R 120x -,>B ．x ∀∈N 2(1)0x *,->C ．0x ∃∈R,lg 01x <D ．0x ∃∈R,tan 02x =【答案】B3．设集合{1,2,3,4,5}U =，{1,3,5},{2,3,5}A B ==，则图中阴影部分表示的集合是( )A ．{1,2,4}B ．{4}C ．{3,5}D ．∅【答案】A4．如果命题“非p 为真”，命题“p 且q 为假”，那么下列选项一定正确的是( )A ．q 为真B ．q 为假C ．p 或q 为真D ．p 或q 不一定为真【答案】D5．“220a b +=”是“0a =或0b =”的( )A ．充分不必要条件B ．必要不充分条件C ．充要条件D ．既不充分又不必要条件【答案】A6． 2>x ”是“0)2)(1(>-+x x ”的( )A ．充分不必要条件B ．必要不充分条件C ．充要条件D ．既不充分也不必要条件【答案】A7．命题“若x=1，则x 2-3x+2=0”以及它的逆命题，否命题和逆否命题中，真命题的个数是( )A ．0B ．2C ．3D ．4【答案】B8．集合}20{，M =，}|{M x x P ∈=，则下列关系中，正确的是( ) A ．MP B ．P M C ． M P = D ． M P ⊆ 【答案】D9．已知集合{1,0,1},{|cos ,}M N y y x x M =-==∈，则集合N 的真子集个数为( )A ．3B ．4C ．7D ．8【答案】B10．已知命题p ：:若x ＋y ≠3，则x ≠1或y ≠2；命题q ：若b 2＝ac ，则a,b,c 成等比数列，下列选项中为真命题的是( )A ． pB ． qC ． p ∧qD ．（⌝p ）∨q【答案】A11．设集合A={x|y=x 2-1}，B={y|y=x 2-1}，C={(x,y)|y=x 2-1}，则下列关系错误．．的是( ) A ．B ∩C=Ф B ．A ∩C=ФC ．A ∩B=BD ．A ∪B=C 【答案】D12．下列说法正确的是( )A ． *N ϕ∈B ． Z ∈-2C ． Φ∈0D ．Q ⊆2【答案】B第Ⅱ卷(非选择题 共90分)二、填空题 (本大题共4个小题，每小题5分，共20分，把正确答案填在题中横线上)13．下列说法及计算不正确的是 。

第十三章 习题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 方程，并写成矩阵形式。

第六章树及割集习题课1课堂例题例1设T是一棵树,T有3个度为3顶点,1个2度顶点,其余均是1度顶点.那么(1)求T有几个1度顶点(2)画出满足上述要求的不同构的两棵树.分析：对于任一棵树T ,其顶点数p和边数q的关系是：q p 1且pdeg(v) 2q ,根据这些性质容易求解.i 1解：(1)设该树T的顶点数为p,边数为q,并设树T中有x个1 度顶点.于是pdeg(v) 3 3 12 x 2q 且p 3 1 x, q p1,得x 5.i 1(2)满足上述要求的两棵不同构的无向树,如图1所示.图1例2设G是一棵树且(G) k ,证实G中至少有k个度为1项电c 证：设T 中有p个顶点,s个树叶,那么T中其余p s个顶点的度数均大于等于2,且至少有一个顶点的度大于等于k.由握手定理可得：p2q 2 p 2deg(v i) 2( p s 1) k s,有s k.i 1所以T中至少有k个树叶.习题例1假设无向图G中有p个顶点,p 1条边,那么G为树.这个命题正确吗为什么解：不正确.K3与平凡图构成的非连通图中有四个顶点三条边,显然它不是树.例2设树T中有2n个度为1的顶点,有3n个度为2的顶点,有n个度为3的顶点,那么这棵树有多少个顶点和多少条边解：设T 有p 个顶点,q 条边,那么q p 1 2n 3n n 1 6n 1deg(v) 2q 有：1 2n 2 3n 3 n 2q 2(6n 1) 12n 2,解得：n =2. v V故 q 11, p 12.例3证实恰有两个顶点度数为1的树必为一条通路.证：设T 是一棵具有两个顶点度数为1的(p,q)树,那么q p 1且p deg(V i ) 2q 2( p 1). i 1又T 除两个顶点度数为1外,其他顶点度均大于等于2,故pp 2deg(V i ) 2deg(v . 2( p 1),即i 1i 1p 2 deg(V i ) 2( p 2).1 1因此p 2个分支点的度数都恰为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,因而可产生以下七种度数序列 (d 1,d 2,L ,d 7)：(1) 1111116；⑵ 1111125； (3) 1111134; (4) 1111224; (5) 1111233；（b ） 1112223； 〔7〕 1122222.在〔1〕中只有一个星形图,因而只能产生 1棵树T 1.在〔2〕, 〔3〕中有两个星形图,因而也只能各产生1棵非同构的 树,分别设为T 2,T 3.在〔4〕, 〔5〕中有三个星形图,但三个星形图是各有两个是同构 的,因而各可产生两棵非同构的树,分别设为T 4,T 5和丁6,丁7.在〔6〕中,有四个星形图,有三个是同构的,考虑到不同的排列情况,共可产生三棵非同构的树,设为 T 8,T 9,T 10O在〔7〕中,有五个星形图,都是同构的,因而可产生1棵树,设为T 11.七个顶点的所有非同构的树T 1：T 11如图2所示.例5设无向图G 是由k 〔k 边才能使G 成为一棵树解：设G 中的k 个连通分支为：T 1,T 2,L ,T k , V i T i , i 1,2,L ,k .在G 中添加边{M,v-} , i 1,2,L ,k 1 ,设所得新图为T ,那么T 连通且无回路, 因而T 为树.故所加边的条数k 1是使得G 为树的最小数目. 例6证实：任意一棵非平凡树都是偶图.分析：假设考虑一下数据结构中树〔即有向树〕的定义,那么可以很 简单地将树中的顶点按层次分类, 偶数层顶点归于顶点集V .,奇数层 顶点归于顶点集V 1 ,图G 中每条边的端点一个属于V o ,另一个属于V 1 , 而不可能存在关联同一个顶点集的边.同理,对于无向树,可以从任 何一个顶点V 出发,给该树的顶点标记奇偶性,例如,v 标记0,与v 相邻的顶点标记1,再给与标记为1的所有相邻的顶点标记0,依次类 推,直到把所有的顶点标记完为止.最后,根据树的性质证实,任何 边只可能关联V 1 〔标记为1的顶点集〕和V o 〔标记为0的顶点集〕之 间的顶点.T 2 T 3 T 4T 7 2〕棵树构成的森林,至少在G 中添加多少条T 1 T 9图4证1从任何一个顶点V出发,给该树的顶点做标记,v标记0,与V相邻的顶点标记1,然后再给与标记为1的所有顶点相邻的顶点标记0,……,依次类推,直到把所有的顶点标记完为止.下面证实：对于任何边只能关联V i (标记为1的顶点集)和V.(标记为0的顶点集)之间的顶点.不妨假设,假设某条边e关联V1中的两个顶点,设为V1和V2,又由于根据上述的标记法那么,有必至八的路P和V2至卜的路P2.设P1与P2离V1和v2最近的顶点为u ,所以,树中存在回路：V1PuP2V2eV) ,与树中无回路的性质矛盾.所以,任意边只能关联S (标记为1的顶点集)和V.(标记为0的顶点集)之间的顶点.所以,任意一棵非平凡树都是偶图.证2设T是任一棵非平凡树,那么T无回路,即T中所有回路长都是零.而零是偶数,故由偶图的判定定理可知T是偶图.例7(1) 一棵无向树有n个度数为i的顶点,i 1,2,L ,k.r)2,n3,L ,、均为数,问?应为多少(2)在(1)中,假设n,(3 r k)未知,n j(j r)均为数,问n r 应为多少k 解：(1)设T为有p个顶点,q条边无向树,那么q p 1, p R.i 1由握手定理：PPkdegV i 2q , 有degV i in i 2q 2p 2 , 即i 1i 1i 1kkin i 2p 2 2 n i 2o①i 1i 1由式①可知：kkkn〔n 2n i 2 (i 2)5 2.i 2i 2i 2(2)对于r 3,由①可知：1 k ,n r ——(2 i)n i 2 .r 2 i 1 i r例8证实：任一非平凡树最长路的两个端点都是树叶.证：设T为一棵非平凡的无向树,L V1V2L V k为T中最长的路,假设端点V1和V k中至少有一个不是树叶,不妨设V k不是树叶,即有deg(V k) 2 ,那么V k除与L上的顶点V k1相邻外,必存在V k1与V k相邻,而V k1 不在L上,否那么将产生回路.于是ML VM 1仍为T的一条比L更长的路, 这与L为最长的路矛盾.故V k必为树叶.同理,V1也是树叶.例9设无向图G中有p个顶点,q 1条边,那么G为连通图当且仅当G中无回路.证：必要性：由于G中有p个顶点,边数q p 1,又由于G是连通的,由定理可知G为树,因而G中无回路.充分性：由于G中无回路,又边数q p 1,由定理可知G为树, 所以G是连通的.例10设G是一个(p,g)图,证实：假设g p,那么G中必有回路.证：(1)设G是连通的,那么假设G中无回路,那么G是树,故q p 1与q p矛盾.故G中必有回路.(2)设G不连通,那么G中有k(k 2)个分支,G1,G2,L,G k.假设G中无回路,那么G的各个分支G(i 1,2,L ,k)中也无回路,于是各个分支都是树,所以有：q p i 1 , i 1,2,L , k.相加得：q p k(k 2) 与q p矛盾,故G中必有回路.综上所述,图G中必有回路. p例11设d1,d2,L ,d p是p个正整数,p 2,且d 2p 2.证实存在一棵顶点度数为d1&,L ,d p的树.i1证：对顶点p进行归纳证实.当p 2时,d〔d2 2 2 2 2,那么d〔d2 1 ,故以d1, d2为度数的树存在,即为一条边.p1设对任意p 1个正整数d1,d2,L a1,只要d i 2(p 1) 2,那么存i 1在一棵顶点度数为d1,d2,L ,d p1的树.p对p个正整数d；d,L ,d p ,假设有d； 2P 2 ,那么d；,d2,L ,d p中必有i1一个数为1,必有一个数大于等于2;不妨设d1 1,d p 2,因此对p 1p1个正整数d2,d3,L ,d p 1,d p 1,有d i' (d p 1) 2( p 1) 2 ,故存在一棵顶i2点度数为d2,d3,L ,d p 1,d p 1的树T.设T中u的度数为d p 1,在丁中增加一个顶点V及边{u,v},得到一个图T ,那么T为树.又T的顶点度数为d；,d2,L ,d p,故由归纳法知原命题成立例题例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 的任何生成树中.解：(1)在G 的任何生成树中的边应为G 中的桥.(2)不在G 的任何生成树中的边应为G 中的环.例3非平凡无向连通图G 是树当且仅当的G 的每条边都是桥.证：必要性：假设T 中存在边e VM 不是桥,那么G e 仍连通,因而v,v j 之间必另有一,条(不通过e)的路.设此路为：v »向1耳2021 年刈v j , 于是G 中有回路v i e ji v i2e j2L v j ev ,这与G 是树矛盾,故G 的每条边都是 桥.充分性：只要证实G 中无回路即可.假设G 中有回路C ,那么C 中任何边都不是桥,与题设中每条边都是 桥矛盾.例4图1给出的带权图表示7个城市a,b,c,d,e, f ,g 及架起城市间直接 通信线路的预测造价,试给出一个设计方案使得各城市间能够通信且 总造价最小,要求计算出最小总造价.图1图2图3解：该题就是求图的最小生成树问题.因此,图的最小生成树即 为所求的通信线路图,如图2所示.其权即是最小总造价,其权为： (T) 1 3 4 8 9 23 48 o例7设T 是一棵树,p 2,那么(1) p 个顶点的树T 至多有多少个割点； bb 2023 15 23g3628 1617(2)p个顶点的树T有多少个桥解：(1)树的度为1的顶点(叶子)不是割点,而树至少有2 个顶点的度为1,故树至多有p 2个顶点为割点.(2)树的每一条边都是桥,故p个顶点的树有p 1个桥.例8证实或否认断言：连通图G的任意边是G的某一棵生成树的弦.答：错误.假设e是桥,那么不成立.。