《集合论与图论》课堂理解理解练习2

集合练习题加答案集合是数学中的基本概念之一，它提供了一种描述对象集合的方式。

在集合论中，集合是由一些明确的或不明确的确定的对象构成的整体。

这些对象被称为集合的元素。

集合论是现代数学的基础之一，它在各个数学领域都有广泛的应用。

以下是一些集合练习题，以及相应的答案，供学习者练习和检验自己的理解。

练习题1：确定以下集合的元素。

- A = {x | x 是一个偶数}- B = {y | y > 5}- C = {z | z 是一个质数}答案1：- A的元素是所有偶数，例如2, 4, 6, 8等。

- B的元素是所有大于5的实数。

- C的元素是所有质数，如2, 3, 5, 7, 11等。

练习题2：判断以下集合是否相等。

- X = {1, 2, 3}- Y = {1, 3, 2}答案2：- X和Y是相等的，因为集合的元素是无序的，只考虑元素的种类和数量。

练习题3：计算以下集合的并集。

- A = {1, 2, 3}- B = {3, 4, 5}- C = {2, 5, 6}答案3：- A ∪ B ∪ C = {1, 2, 3, 4, 5, 6}练习题4：计算以下集合的交集。

- D = {1, 2, 3, 4}- E = {3, 4, 5}答案4：- D ∩ E = {3, 4}练习题5：计算集合D的补集，假设全集U包含所有自然数。

- D = {1, 2, 3, 4}答案5：- D' = U - D = {所有自然数除了1, 2, 3, 4}练习题6：如果A = {x | x 是一个偶数}，B = {x | x 是一个奇数}，计算A和B的差集。

答案6：- A - B = {x | x 是一个偶数但不是奇数}，即A本身，因为奇数和偶数是互补的。

练习题7：给定集合F = {x | x 是一个整数，且 -3 ≤ x ≤ 3}，计算F的幂集。

答案7：- F的幂集包含F的所有子集，共有2^7个子集，因为F有7个元素（-3, -2, -1, 0, 1, 2, 3）。

集合与图论习题第一章习题．画出具有个顶点地所有无向图(同构地只算一个).．画出具有个顶点地所有有向图(同构地只算一个).．画出具有个、个、个顶点地三次图.．某次宴会上，许多人互相握手.证明：握过奇数次手地人数为偶数(注意，是偶数).．证明：哥尼斯堡七桥问题无解.．设与是图地两个不同顶点.若与间有两条不同地通道(迹)，则中是否有回路？．证明：一个连通地(，)图中≥.．设是一个(，)图，δ()≥[]，试证是连通地.．证明：在一个连通图中，两条最长地路有一个公共地顶点.．在一个有个人地宴会上，每个人至少有个朋友(≤≤).试证：有不少于个人，使得他们按某种方法坐在一张圆桌旁，每人地左、右均是他地朋友.b5E2R。

．一个图是连通地，当且仅当将划分成两个非空子集和时，总有一条联结地一个顶点与地一个顶点地边.．设是图.证明：若δ()≥ ，则包含长至少是δ()地回路.．设是一个(，)图，证明：()≥，则中有回路；()若≥，则包含两个边不重地回路.．证明：若图不是连通图，则是连通图.．设是个(，)图，试证：()δ()·δ()≤[()]([()])，若≡，，( )() δ()·δ()≤[()]·[()]，若≡( )．证明：每一个自补图有或个顶点.．构造一个有个顶点而没有三角形地三次图，其中≥..给出一个个顶点地非哈密顿图地例子，使得每一对不邻接地顶点和，均有≥．试求中不同地哈密顿回路地个数.．试证：图四中地图不是哈密顿图.．完全偶图，为哈密顿图地充分必要条件是什么？．菱形面体地表面上有无哈密顿回路？．设是一个(≥)个顶点地图.和是地两个不邻接地顶点，并且≥.证明：是哈密顿图当且仅当是哈密顿图.．设是一个有个顶点地图.证明：若>δ()，则有长至少为δ()地路.．证明具有奇数顶点地偶图不是哈密顿图.．证明：若为奇数，则中有()个两两无公共边地哈密顿回路.．中国邮路问题：一个邮递员从邮局出发投递信件，然后返回邮局.若他必须至少一次走过他所管辖范围内地每条街道，那么如何选择投递路线，以便走尽可能少地路程.这个问题是我国数学家管梅谷于年首先提出地，国外称之为中国邮路问题.p1Ean。

习题集（一） 一、填空1．设}7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =⋃B A 。

2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。

6．设A={1，2，3，4}，A 上关系图为则 R 2 = 。

7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为则 R= 。

8．图的补图为 。

二、选择2、下列集合中相等的有（ ）A ．{4，3}Φ⋃；B ．{Φ，3，4}；C ．{4，Φ，3，3}；D ． {3，4}。

3、设A={1，2，3}，则A上的二元关系有（）个。

A．23 ；B．32 ；C．332⨯；D．223⨯。

4、设R，S是集合A上的关系，则下列说法正确的是（）R 是自反的；A．若R，S 是自反的，则SR 是反自反的；B．若R，S 是反自反的，则SR 是对称的；C．若R，S 是对称的，则SR 是传递的。

D．若R，S 是传递的，则S5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下t st spR=∈=则P（A）/ R=（）<>A∧s(||||})(,{t|,A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}}6、设A={Φ，{1}，{1，3}，{1，2，3}}则A上包含关系“⊆”的哈斯图为（）7、下列函数是双射的为（）A．f : I→E , f (x) = 2x ；B．f : N→N⨯N, f (n) = <n , n+1> ；C．f : R→I , f (x) = [x] ；D．f :I→N, f (x) = | x | 。

（注：I—整数集，E—偶数集，N—自然数集，R—实数集）8、图中从v1到v3长度为3 的通路有（）条。

A．0；B．1；C．2；D．3。

图论习题二答案图论习题二答案图论是数学中的一个分支，研究的是图的性质和图之间的关系。

在图论中，有很多经典的习题可以帮助我们更好地理解和应用图的概念。

本文将探讨一些图论习题二的答案，帮助读者更好地理解和掌握图论的知识。

1. 习题：给定一个无向图G=(V,E)，其中V={1,2,3,4,5,6}，E={(1,2),(1,3),(2,3),(2,4),(3,4),(4,5),(4,6)}，求图G的邻接矩阵和关联矩阵。

答案：邻接矩阵是一个n×n的矩阵，其中n是图的顶点数。

对于无向图G，邻接矩阵的元素a[i][j]表示顶点i和顶点j之间是否存在边。

如果存在边，则a[i][j]=1，否则a[i][j]=0。

对于给定的图G，邻接矩阵为：0 1 1 0 0 01 0 1 1 0 01 1 0 1 0 00 1 1 0 1 10 0 0 1 0 00 0 0 1 0 0关联矩阵是一个n×m的矩阵，其中n是图的顶点数，m是图的边数。

对于无向图G，关联矩阵的元素b[i][j]表示顶点i和边j之间的关系。

如果顶点i是边j 的起点，则b[i][j]=-1；如果顶点i是边j的终点，则b[i][j]=1；否则b[i][j]=0。

对于给定的图G，关联矩阵为：-1 -1 0 0 0 01 0 -1 -1 0 00 1 1 0 0 00 0 0 1 -1 -10 0 0 0 1 00 0 0 0 0 12. 习题：给定一个有向图G=(V,E)，其中V={1,2,3,4,5}，E={(1,2),(1,3),(2,3),(2,4),(3,4),(4,1),(5,4)}，求图G的邻接表和深度优先搜索遍历结果。

答案：邻接表是一种图的表示方法，用于存储图中每个顶点的邻接顶点。

对于有向图G，邻接表中的每个元素表示该顶点的出边。

对于给定的图G，邻接表为：1: 2, 32: 3, 43: 44: 15: 4深度优先搜索（DFS）是一种图的遍历算法，用于遍历图中的所有顶点。

《集合论与图论》课堂练习3（2013年12月18日 13:20-15:00 复旦大学计算机学院2012级）学号姓名一、判断下列命题是否正确，并说明理由。

（括号内写“是”或“否”）（40分，每题8分，是非判断4分，证明或反例4分）1 存在7个结点的自补图。

（否）/*西安交通大学1999*/自补图对应的完全图的边数必须是偶数，而7个结点的完全图的边数为21。

n≥的连通图。

则G没有割点当且仅当G的剖分也没有割点。

2 设G是顶点数3（真）如果G的剖分有割点，则G有割点，矛盾；所以G没有割点，则G的剖分也没有割点。

如果G有割点，则该割点为G的剖分的割点，所以G的剖分有割点，矛盾；所以G的剖分也没有割点则G没有割点。

3 若G是简单连通图，边数为e，结点数为n。

若e≥n，则G至少有3棵生成树。

（是）/*复旦大学1998*//*只需证明e=n时，命题成立*/若e=n-1，因为G是连通的，所以为一棵树；再添加一边时，因为G是简单图，所以图中必存在一个长度大于等于3的回路，则在这个回路上任意删除一条边就得到一棵树。

4 一个有向图D中仅有一个顶点的入度为0，其余顶点的入度均为1，则D是有根树。

（否）一个自环和孤立点/*北京大学1991*/5 设C是简单连通图G的回路，若删去C中任一边后所得到的路C’为G中的最长路，则C是图G的哈密顿回路。

（是）/*复旦大学1999*//*反证法证明*/令C的长度为m。

若C不是哈密顿回路，则圈外必存在一点u，它与圈上一点v邻接（因为G是连通图）。

圈上与v关联的一边为e，则C-e的长度为m-1；而C-e+uv的长度为m；得C-e不是最长路。

矛盾。

二、综合题（60分）1．证明：任何平面图是5-可着色的。

证明：p125-1262．如果有一群人，其中有k个人彼此认识或者有l个人彼此不认识。

我们用r(k, l)表示这群人至少是有几个人的人数，称为Ramsey数。

证明：r(3, 3)=6。

证明：6个点v1, v2, v3, v4, v5, v6表示6个人，两人认识时，在对应的两点连一条绿边，否则连一条红边。

第六章图的根本概念P206习题1.画出具有4个顶点的所有无向图(同构的只算一个).11个2.画出具有3个顶点的所有有向图(同构的只算一个)o16个3.画出具有4个、6个、8个顶点的三次图.略4.某次宴会上,许多人互相握手.证实：握过奇数次手的人数为偶数(注意,0是偶数)o把实际问题转化为图论问题,然后用握手定理的推论.P209习题1.设u与v是图G的两个不同顶点.假设u与v间有两条不同的通道(迹),那么G 中是否有圈假设u与v间有两条不同的通道,G中无圈假设u与v间有两条不同的迹,G中有圈2.证实：一个连通的(p , q)图中q?p-1.数学归纳法3.设G是一个(p, q)图,且q (p 1)(p 2)/2,那么G是连通的.征2用反征法口假咬囹G是小庄逋叼,那么图G至少狂仕两?逢逋分支.尸⑵⑼)和&二仇必)时,G 的最大可能边数勺二名+公式T)'2 +p式1)/2 ,其中曲三户一］,1 < < p-1 ?所以〞(pZp-W2,与题设矛盾n所以假设.是简单图,那么仃是连通的.6.在一个有n个人的宴会上,每个人至少有m个朋友(2&m< n).试证：有不少于m+1个人,使得他们按某种方法坐在一张圆桌旁, 每人的左、右均是他的朋友. 证实：把实际问题转化为图论问题,就和下面的题一样了.8.设G是图.证实：假设5 (G) >2,那么G包含长至少是6(G)+1的圈.这两个题和这个题一样的证实方法.例3设行=(匕均是无向图,证实：假设久⑴之出,那么行包含长至少为中+ 1的|口1路, iiF：设上是G中最长的路, £:v t P2L v…a由于WE—d次置之所以必自Z上的m个顶点工门,,…,叫(2 = «o,VQ与耳邻接,干是马巧…%巧便是G中的一个回路,且长至少为2去晨假设上上不存在陋个顶点与耳邻接,那么在最长路L外必有一个顶点与巧邻接,于是有更长路矛盾.P216习题1.证实：假设图G不是连通图,那么GC是连通图.由于G不连通,故G至少有两个分支对于G,中任意两个顶点把和v ：(1)假设"匕匕,¥曰匕,那么仃与野不在G中邻接.由补图的定义可知：N与F必在T中邻接；(2)假设以廿三艮(或匕),取WE匕(或昨),那么廿与w, w与在G都不邻接,故"与1#, w与廿在G'必邻接.于是ww窜就是G'中的一条踏.综上可知,由于对G『中任意两个加点〞和% .和y之间都有路连接,故G, 连通.2.证实：每一个自补图有4n或4n+1个顶点.(3)由于每个自补图G的对应的完全图的边数必为偶数,即q-p(p-1)/2为偶数.而当p二123时,图G无自补图,只有p之4时,图G才有自补图;于是「可写成如下形式,4/4〃+ L4叱2刈】+3,其中〃为正整数；代入〞风p -1)2中,只有加也十1才能使&为偶数r故每个自补图必有4“成4"】个顶点.例4证实：在一个连通图中,两条最长的路有一个公共的顶点口证】设乙与乙是图中的两条最长的路r 4飞打4 J上上：叫的力—但设心与心没有公共顶点*由于<7是连通的,所以心与上上之间必TT一条路尸连接且|尸岸1 0令尸与4上的匕连接,与&上的2连接,那么假设,之J*那么路先岭次〃产产1%比4长,矛盾：假设,,J f那么路修/…%7VM.I…/比4长,矛盾.故假设不成立,即两条最长的路必有公共顶点,P228习题1.给出一个10个顶点的非哈密顿图的例子,使得每一对不邻接的顶点u和v,均有：degu+degv> 9.下列图中任意一对不邻接的顶点u和v ,均有：degu+degv> 9 .2.试求Kp中不同的哈密顿圈的个数.〔p-1〕!/2 4.完全偶图Km n为哈密顿图的充分必要条件是什么?〔2〕=＞假设|匕＜|匕,有〔1〕可知区门不是哈密顿图；假设IRWI/I,同理有K〞不是哈密顿图.故&◎是哈密顿图时只有14 1=1/ I,即一-*U假设加二〃,那么匕扇即斗廛gv=|1I/2+|炉］,2二/卜由定理知：?明,是哈密顿图二10.证实具有奇数顶点的偶图不是哈密顿图.证：〔1〕设G是,个具有奇数顶点的偶图,那么G的顶点集了有•个二划分, 即展的匕｝H有因周匕I,不妨设| - K彩|,那么有印〔0—=1七忸匕I,由哈密顿图的必要条件可知：G不是哈密顿图.。