当前位置：文档之家 › 哈工大集合论习题课-第五章 图的基本概念习题课

哈工大集合论习题课-第五章 图的基本概念习题课

  • 格式：doc
  • 大小：1.31 MB
  • 文档页数：13

第五章 图的基本概念 习 题 课 1 1. 画出具有 6、8、10、…、2n个顶点的三次图；是否有7个顶点的三次图？

2. 无向图G有21条边，12个3度数顶点，其余顶点的度数均为2，求G的顶点数p。

解：设图的顶点为p，根据握手定理：1deg()2piivq，有 212)12(2312p，得15302pp，。 3. 下列各无向图中有几个顶点？ （1）16条边，每个顶点的度为2； （2）21条边，3个4度顶点，其余的都为3度数顶点； （3）24条边，各顶点的度数相同。 解： 设图的顶点为p，根据握手定理：

（1）1deg()2piivq，即2221632pq；所以16p，即有16个顶点。

（2）1deg()2piivq，即433(3)222142pq，所以13p。 （3）各点的度数为k，则1deg()2ipivq，即222448kpq，于是 ① 若1k，48p； ② 若2k，24p； ③ 若3k，16p； ④ 若4k，12p； ⑤ 若6k，8p； ⑥ 若8k，16p； ⑦ 若12k，4p； ⑧ 若16k，3p； ⑨ 若24k，2p； ⑩ 若48k，1p。 4．设图G中9个顶点，每个顶点的度不是5就是6。证明G中至少有5个6度顶点或至少有6个5度顶点。 证：由握手定理的推论可知，G中5度顶点数只能是0，2，6，8五种情况，此时6度顶点数分别为9，7，5，3，1个。以上五种情况都满足至少5个6度顶点或至少6个5度顶点的情况。 5．有n个药箱，若每两个药箱里有一种相同的药，而每种药恰好放在两个药箱中，问药箱里共有多少种药？[就是求一个完全图nK的边数(1)(2)/2qppg]

6.设G是有p个顶点，q条边的无向图，各顶点的度数均为3。则 （1）若36qp，证明G同构意义下唯一，并求,pq； （2）若6p，证明G在同构的意义下不唯一。 分析：在图论中，对于简单无向图和简单有向图，若涉及到边q与顶点p的问题，握手定理是十分有用的。 解：（1）由于各顶点的度数均为3，现在有p个顶点，q条边，所以由握手

定理知：1deg()2ipivq，即33nq，故2/3nm； 又3632/3626qpqq，故6q，则2/364p。 即4q，4p，此时所得的无向图如图1所示，该图是4个顶点的简单无向图中边最多的图，即为无向完全图4K。 对于4个顶点的完全图，在同构意义下，4个顶点的完全图是唯一的。 （2）若6p，由握手定理：1deg()2ipivq，即362q。 故9q，此时有6,9pq，且每个顶点的度数为3；此时对于简单无向图，6个顶点，9条边及每个度数为3的有如图2所示两个非同构的图；()a与()b是非同构的图，所以6,9pq，度数为3的无向图G在同构的意义下是不唯一的。

（a） (b)

图1 图2 7.已知p阶简单图G中有q条边，各顶点的度数均为3，又23qp，试画出满足条件的所有不同构的G。

解：由握手定理：1deg()32ipivpq，又23pq，即23qp。故 322(23)46pqppg，即6p，239qp。 此时有6p，9q且每个顶点的度数都为3，则不同构的无向图有两个，如图3所示。

图3

8．9个学生，每个学生向其他学生中的3个学生各送一张贺年卡。确定能否使每个学生收到的卡均来自其送过卡的相同人？为什么？ 解：否，因为不存在9（奇数）个顶点的3－正则图

习题课2 例3设,pq为正整数，则 （1）p为何值时，无向完全图pK是欧拉图？p为何值时pK为半欧拉图？ （2）,pq为何值时,pqK为欧拉图？ （3）,pq为何值时,pqK为哈密整图？ （3）p为何值时，轮图pW为欧拉图？ 证：（1）一般情况下，不考虑无向图1K。因此 因为pK各顶点的度均为1p，若使pK为欧拉图，1p必为偶数，因而p必为奇数。即(3)pp为奇数时，完全图pK是欧拉图。 若2p或(3)pp为奇数时，pK是半欧拉图。 （2）当,2pq均为偶数时，,pqK为欧拉图。 （3）当pq时，,pqK为哈密整图。 （4）设(4)pWp为轮图，在pW中，有1p个顶点的度为3，因而对于任意 取值(4)pp，轮图pW都不是欧拉图。 例1 判断图5所示的图是否为哈密顿图，若是写出哈密顿回路，否则证明其不是哈密顿图。

ihjg

f

ed

cb

a ji

hgf

e

dcba

(a) (b) 图3 图4

例2 给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，

均有degdeg9uv。

例3 试求pK中不同的哈密顿回路的个数。 例4 (1) 证明具有奇数顶点的偶图不是哈密顿图；用此结论证明图8所示的图不是哈密顿图。 (2) 完全偶图,mnK为哈密顿图的充分必要条件是什么？ 证：(1) 设G是一个具有奇数顶点的偶图，则G的顶点集V有一个二划分， 即22{,}VVV且有12||||VV。 不妨设12||||VV，则有121()||||WGVVV。 由哈密顿图的必要条件可知：G不是哈密顿图。 题中所给的图中无奇数长的回路，因而此图是偶图。而且此图中有13个顶 点，因此它不是哈密顿图。 (2) 若12||||VV，有(1)可知,mnK不是哈密顿图；

若12||||VV，同理有,mnK不是哈密顿图。 故,mnK是哈密顿图时只有12||||VV，即mn

。

若mn，则,,||/2||/2||uvVdegudegvVVV，由定理知：

,mnK是哈密顿图。

例5 菱形12面体的表面上有无哈密顿回路？

例6设(,)GVE是连通图且顶点数为p，最小度数为2p，则G中有一长至少为2的路。 分析: 采用最长路法，设连通图的最长路为L且||2L。再看这条路的端点，端点只能与L上的顶点相邻，这样就可以构成一个回路，对于回路外的顶点，因为仍与此回路上的某些顶点相邻，所以可以把这个顶点连到回路上，然后再打开回路，显然这时有一条路比假设时的路更长了，所以假设不成立。 证：假设G中的最长路为L：01lLvvvL，其长度为2l。因为0degv，

1degv，所以存在01il，使01ivv 与1ivv在G中相邻，得一长为1l的回路：0111110iivvvvvvvLL。

又因为G连通，且G的顶点数2p，故存在(0)ivvil与回路上(0)jvjl相邻，则把回路在jv处断开，并把v连入回路中，得到一条长为1l

的路，矛盾。 所以G中有一长至少为2的路。 例7 证明：彼德森(Petersen)图不是哈密顿图。

例8 某工厂生产由6种不同颜色的纱织成的双色布。双色布中，每一种颜色至少和其他3种颜色搭配。证明：可以挑出3种不同的双色布，它们含有所有6种颜色。 证：用6个不同的点分别表示6种不同颜色的纱，两个点间联一条线当且仅当用这两点所表示的两种不同颜色的纱织成一种双色布。于是，我们得到一个有6个点的图G。由于每种颜色的纱至少和3种其他颜色的纱搭配，所以G的每个顶点的度至少是3。于是，由定理1，G有哈密顿回路。回路上有6条边，对应了6种不同的双色布。间隔取出3条边，它们包含了全部6种颜色。 与例8等价的例题： 例9 今要将6个人分成3组（每组2个人）去完成3项任务，已知每个人至少与其余5个人中的3个人能相互合作，问： (1)能否使得每组2个人都能相互合作？(2)你能给出集中方案？（两种） 例10 某公司来了9名新雇员，工作时间不能互相交谈。为了尽快互相了解，他们决定利用每天吃午饭时间相互交谈。于是，每天在吃午饭时他们围在一张圆桌旁坐下，他们是这样安排的，每一次每人的左、右邻均与以前的人不同。问这样的安排法能坚持多久？ 解：平面上9个互不相同的点分别代表9个新雇员。因为每个人都可以为其他每个人的左或右邻，所以用两点的联线表示相应的两个人互为左右邻。于是得到了有9个顶点的完全图K9。于是，我们的问题中的一种坐法就是K9的一个哈密顿回路。由于每次的安排中，每人的左、右邻均与以前的人不同，所以我们的问题就是求K9中有多少个两两无公共边的哈密顿回路。由图1.6.5不难发现，K9中恰有4个两两无公共边的哈密顿回路。它们是：91，81，61，71。 于是，他们的这种安排法仅能维持4天。 例10可推广为n个雇员的一般情况问题。这时， 当n为奇数时，这种安排法仅能维持(n-1)/2天； 当n为偶数时，这种安排法仅能维持(n-2)/2天。 习题课3

例2设d12(,,,)ndddL，其中id为正整数，1,2,,inL。若存在n个顶点的简单图，使得顶点iv的度为id，则称d是可图解的。下面给出的各序列中哪些是可图解的？哪些不是，为什么？ （1） （1，1，1，2，3）； （6） （1，3，3，3）； （2） （0，1，1，2，3，3）； （7） （2，3，3，4，5，6）； （3） （3，3，3，3）； （8） （1，3，3，4，5，6，6）； （4） （2，3，3，4，4，5）； （9） （2，2，4）； （5） （2，3，4，4，5）； （10） （1，2，2，3，4，5）。 解：（1），（2），（3）全是可图解的，它们对应的图分别如图3中(),(),()abc所示；其余的各序列都不是可图解的。 在（4），（7），（10）中均有奇数个奇度顶点，根据握手定理的推论，它们自然都不是可图解的。 另外在p阶简单图中，每个顶点的度至多为1p，因而（5）和（9）均不可图解。 若（6）是可图解的，则设1234deg1,degdegdeg3vvvv，因为234,,vvv的度都是3，因而要求1v与234,,vvv之间有边关联，但因1v的度为1，这是不可能的，所以（6）也是不可图解的。 在（8）中，7n，因而每个顶点至多6度。若（8）是可图解的，设1deg1v，

67degdeg6vv，因而67,vv均应与1v相邻，这也是不可能的， 因而（8）也不可图解。

合集下载

集合论与图论答案 第一章习题

集合论与图论答案 第一章习题


若存在 Gfi ,Gf j (i j) ，使得 Gfi Gf j 且 Gf j Gfi ，则结论成立。
反证法：假设不存在 G fi 和 G f j 满足 Gfi Gf j 且 Gf j Gfi 。于是
i, j(i j),Gfi与Gf j 应满足： Gfi Gf j 或 Gf j Gfi 必有一个成立。
设 A 1, B 2，则 2A ,1, 2B ,2 。 2A 2B ,1,2，而 A B 1, 2, 2A B ,1,2,1, 2，
所以 2A 2B 2A B 。 例 5 (多项选择)设集合 A 是以空集 为唯一元素的集合，集合 B 22A ，则下列 各式那个正确？
(1) B ；(2) B ；(3) B ；(4), B ；(5), B 。
i 1
n
x Mn \ Nn MnNn (NiMi ) 。
i 1
n
综上可得： NnQn (NiMi ) 。
i 1
例 4 (P225 ) 设 A, B 为集合，证明： A B B A 充要条件是下列三个条件至少一个 成立：（1） A ；（2） B ；（3） A B 。
1．若 A B B A ，则 A 或 B 。
即{x} B ，所以 x B ，即 A B 。
（2） P(A) P(B) (P(A) P(B)) (P(B) P(A)) ABB A AB。
例 4 设 A, B 是两个任意集合，证明： (1) 2A 2B 2A B ；(2) 2A 2B 2A B ；(3) 举例说明 2A 2B 2A B 。 其中 2A 表示集合 A 的幂集。 证：(1) 证 2A 2B 2A B 。 x 2A 2B ，有 x 2A 或 x 2B 。 若 x 2A ，则 x A ，而 A A B ，故 x A B ，因此 x 2A B 。 同理，若 x 2B ，也有 x 2A B 。 因此 2A 2B 2A B 。 (2) 证 2A 2B 2A B 。 证 x 2A 2B x 2A 且 x 2B x A且 x B x A B x2A B 。 所以 2A 2B 2A B 。 (3) 下面举例说明 2A 2B 2A B 。
哈工大《离散数学》教科书习题答案

哈工大《离散数学》教科书习题答案

教材习题解答第一章 集合及其运算习题8P 3. 写出方程的根所构成的集合。

2210x x ++=解：的根为，故所求集合为2210x x ++=1x =-{1}-4.下列命题中哪些是真的，哪些为假a)对每个集A ，；b)对每个集A ，；A φ∈A φ⊆c)对每个集A ，；d)对每个集A ，；{}A A ∈A A ∈e)对每个集A ，；f)对每个集A ，；A A ⊆{}A A ⊆g)对每个集A ，；h)对每个集A ，；2A A ∈2A A ⊆i)对每个集A ，；j)对每个集A ，；{}2A A ⊆{}2A A ∈k)对每个集A ，；l)对每个集A ，；2A φ∈2A φ⊆m)对每个集A ，；n)；{}A A ={}φφ=o)中没有任何元素；p)若，则{}φA B ⊆22A B ⊆q)对任何集A ，；r)对任何集A ，； {|}A x x A =∈{|}{|}x x A y y A ∈=∈s)对任何集A ，；t)对任何集A ，{|}y A y x x A ∈⇔∈∈；{|}{|}x x A A A A ∈≠∈答案：假真真假真假真假真假真真假假假真真真真真5.设有n 个集合且，试证：12,,,n A A A 121n A A A A ⊆⊆⊆⊆12n A A A === 证明：由，可得且，故。

1241n A A A A A ⊆⊆⊆⊆⊆ 12A A ⊆21A A ⊆12A A =同理可得：134n A A A A ==== 因此123n A A A A ====1．设A,B,C 为集合，并且，则下列断言哪个成立？A B A C = (1)；(2)；(3)；(4)。

B C =A B A C = C C A B A C = C C A B A C = 答案：d 。

在两边同时并上A 即得。

C C A B A C = A B A C = 2．设A,B,C 为任意集合，化简()()()()()()()C C C C C C C C C A B C A B C A B C A B C A B C A B C A B C证：证1：原式＝()()()()C C C C B C A B B C A B C()()()()()(())C C C C C C B A B A B C A B A B C A B A B C A B C ==== 证2：令原式＝T ，全集为S ，则且，()C C C S T A B C = ()C C C T A B C φ= 故 。

答案08秋季集合论与图论试题A

答案08秋季集合论与图论试题A

本试卷满分90分(计算机科学与技术学院07级)10分，每小题各1 分)B ，则A 等于什么？2. 设X 为集合，R 为X 上的偏序关系，计算U R ，等于什么?i 1(R )3. 把置换123456789分解成循环置换的乘积。

436987251((149) (2367) (58))4. 什么是无穷集合？(凡能与自身的一个真子集对等的集称为无穷集合)5 .设T 是一棵树，p 2，贝U p 个顶点的树T 至多有多少个割点？(p -2 )6. 设D 是一个有p 个顶点q 条弧的有向图，若D 是连通的，则q 至 少是多大？ ( p -17. 设V {1,2, , n}，则以V 为顶点集的无向图共有多少个？8.设V {1,2, , n}，则以V 为顶点集的有向图共有多少个？ 2p(p1))哈工大2008年秋季学期注 意 行 为 规 范一、填空(本题满分1.设A,B 是集合，若A B遵 守 考场纪 律(2 P (P 1)/29.每个有3个支的不连通图，若每个顶点的度均大于或等于2,则该图至少有多少个圈？（ 3 ）10.设T是一个正则二元树，它有n。

个叶子，则T有多少条弧？（2（n0-1 ））二、判断对错（本题满分10分，每小题各1分）1.设A,B是两个集合，则A B且A B不可能同时成立。

（错）2.在集合｛1,2, ,10｝上可以定义210个二元运算。

（错）3 . 设f：X Y , 若是可逆的。

（错）是一个集合，则上的自反和反自反的二元关系个数相同。

（对）5.设为一个有限字母表，上所有字（包括空字）之集记为。

则不是可数集。

（错）6.设G是一个（p,q）图，若q p，则G中必有圈。

（对）7.若G是一个(p,p)连通图，则G至多有p个生成树。

(对)8.设r 2，G是r正则图且顶点连通度为1，贝U (G) r。

(对)9.把平面分成p个区域，每两个区域都相邻，则p最大为5。

(错)10.有向图的每一条弧必在某个强支中。

北工大-集合与图论习题整理版

北工大-集合与图论习题整理版

习题集（一） 一、填空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。