[哈尔滨工业大学]哈工大计算机复试资料汇总-集合论与图论2008f

哈工大 2008 年 秋季学期

集合论与图论 试题

题号 一 二 三 四 五 六 总分 分数

班号 姓名

本试卷满分90分

（计算机科学与技术学院07级）

一、填空（本题满分10分，每小题各1分）

1.设B A ,是集合，若B B A =?，则A 等于什么？ （ Φ=A ）

2．设X 为集合，R 为X 上的偏序关系，计算1i i R ∞

= 等于什么？

（ R ） 3．把置换?

??

?

??436987251123456789分解成循环置换的乘积。 （（149）（2367）（58）

） 4．什么是无穷集合？

（凡能与自身的一个真子集对等的集称为无穷集合） 5．设T 是一棵树，2p ≥，则p 个顶点的树T 至多有多少个割点？ （p -2 ）

6．设D 是一个有p 个顶点q 条弧的有向图，若D 是连通的，则q 至少是多大？（ p -1 ） 7．设},,2,1{n V

=，则以

V 为顶点集的无向图共有多少个？

（2/)1(2-p p ） 8．设},,2,1{n V

=，则以

V 为顶点集的有向图共有多少个？)1(2-p p ）

9．每个有3个支的不连通图，若每个顶点的度均大于或等于2，则该图至少有多少个圈？ （ 3 ）

10．设T 是一个正则二元树，它有0n 个叶子，则T 有多少条弧？（2（0n -1））

二、判断对错（本题满分10分，每小题各1分）

1.设B A ,是两个集合，则A B ?且A B ∈不可能同时成立。 （ 错 ） 2．在集合}10,,2,1{ 上可以定义102个二元运算。 （ 错 ） 3．设:f X Y →，若存在唯一一个映射:g Y X →，使得X g f

I =，则一定是可逆的。

（ 错 ） 4．设X 是一个集合，则X 上的自反和反自反的二元关系个数相同。 （ 对 ） 5.设∑为一个有限字母表，∑上所有字（包括空字）之集记为*∑。则*∑不是可数集。 （ 错 ） 6.设G 是一个(,)p q 图，若q p ≥，则G 中必有圈。 （ 对 ） 7.若G 是一个),(p p 连通图，则G 至多有p 个生成树。 （ 对 ) 8.设2≥r ，G 是-r 正则图且顶点连通度为1，则≤)(G λr 。（ 对 ） 9．把平面分成p 个区域，每两个区域都相邻，则p 最大为5。（ 错 ） 10.有向图的每一条弧必在某个强支中。 （ 错 ）

三、证明下列各题(本题满分18分，每小题各6分)

1．设,,A B C 是三个任意的集合，则

（1）证明：()()\\\\A B C A B C ?；（2） 举例说明)\(\\)\(C B A C B A ≠。

证：(1) 证明：?()\\x A B C ∈，有()\,x A B x C ∈?，即x A ∈但,x B x C ??， 从而\x B C ?，于是()\\x A B C ∈，即()()\\\\A B C A B C ?。 (2) 若{}{}1,2,3,2A B C ===，则()()\\\\A B C A B C ?。 2．设C B A ,,是三个任意的集合，证明：(\)()\()A B C A B A C ?=??。

证明：设 (,)(\)x y A B C ∈?，则x A ∈，\y B C ∈，从而x A ∈,y B ∈,y C ?。 于是(,)x y A B ∈?，(,)x y A C ??,因此(,)()\()x y A B A C ∈??，即

(\)()\()A B C A B A C ????。

反之，设(,)()\()x y A B A C ∈??，有(,)()x y A B ∈?，(,)()x y A C ??，从而

x A ∈，

y B ∈，y C ?，故x A ∈且\y B C ∈。于是(,)(\)x y A B C ∈?，

即()\()(\)A B A C A B C ????。 因此，(\)()\()A B C A B A C ?=??。

3．设T S ,是两个任意的集合，证明：()()S T S T S T ?=? 。

证：x S T ?∈?，则

若x S ∈，则x T ?。因而()x S T ∈ 且()x S T ? ，故

()\()x S T S T ∈ ()()S T S T =? ；

若x S ?，则x T ∈，同理可得()()x S T S T ∈? 。 因此 S T ??()()S T S T ? 。

反之，因为()()S T S T ? ，故()()S T S T ? ＝()\()S T S T 。于是 ()()x S T S T ?∈? ()\()S T S T = ，有(),()x S T x S T ∈? 。

若x S ∈，则x T ?，故x ∈S T ?；

若x S ?，则x T ∈，故x ∈S T ?。 因此()()S T S T ? ?S T ?。 从而S T ?＝()()S T S T ? 。

四、回答下列各题(本题满分14分)

1．如图1所示是彼德森图G ，回答下列问题：（6分） （1）G 是否是偶图？ （不是 ） （2）G 是否是欧拉图？ （不是 ） （3）G 是否是平面图？ （不是 ） （4）G 是否是哈密顿图？ （不是 ） （5）G 的色数为多少？ （ 3 ）

图1 2．设G 是如图2所示的有向图，则（8分）

（1）写出G 的邻接矩阵。

（2）求顶点1v 到4v 间长为10的有向通道的条数的方法是什么？

（不必算出具体的数） （3）写出G 的可达矩阵。

（4）画出对应于表达式（A ＋B*C ）/（A-C ）的二元树表示。

解：（1）??????? ??=0110010000110101B ；（2）1410

)(B 元素的值；（3）??????

?

??0111011101111111 （4）

五、证明下列各题(本题满分18分, 每小题各6分)

1．设f Y g →→：X ，：Y Z 。若g f 是单射，则f 与g 哪个是单射？请证明之。

解：f 是单射。

因为g f 是单射，所以12,x x X ?∈，若12x x ≠，则12(())(())g f x g f x ≠。 因此，12()()f x f x ≠，故f

是单射。

2．设X X S n X

?==},,,2,1{ 。“?”是S 上如下的二元关系：(,),(,)i j k l S ?∈，

(,)(,)i j k l ?当且仅当i j k l +=+。

则(1) 证明：?是等价关系；(2)求等价类数。 证：(1)等价关系显然；

(2)等价类数为：21n -。

3．令{1,2,3,}N = ，{:{0,1}},S f f N =→利用康托对角线法证明

S 是不可

数集。

证:假设从N 到{0, 1}的所有映射之集可数，则可排成无重复项的无穷序列123,,,f f f 。每个函数i f 确定了一个0,1序列123,,,i i i a a a 。构造序列123,,,,1i b b b b = ，若0ii a =；否则0i b =。该序列对应的函数()i f i b =，

i N ∈，不为12,,f f 任一个，矛盾。

六、证明下列各题（本题满分20分，每小题各5分）

1.设G 是一个恰有两个不邻接的奇度顶点u 和v 的无向图，证明：

G 连通G uv ?+连通。

证：? 显然成立。

? 假设G 不连通，则G 恰有

2个分支：21,G G 。由题意u v 与不在一

个分支上，于是含有()u v 或的顶点的分支只有一个奇度数顶点与握手定理的推论矛盾。于是假设不成立，即G 是连通的。 2．证明：任意一棵非平凡树至少有两个树叶。

证明：设T 为一棵非平凡的无向树，T 中最长的路为12k L v v v = 。若端点1v 和k v 中至少有

一个不是树叶，不妨设k v 不是树叶，即有deg()2k v ≥，则k v 除与L 上的顶点1k v -相邻外，

必存在1k v +与k v 相邻，而1k v +不在L 上，否则将产生回路。于是11

k k v v v + 仍为T 的一条比

L 更长的路，这与L 为最长的路矛盾。故k v 必为树叶。 同理，1v 也是树叶。

3．证明：若每个顶点的度数大于或等于3，则不存在有7条边的平面连通图。

证明：假设存在这样的平面图，则由2p q f

-+=，有

()291p f q +=+=

而由214deg 2,32,33v V

v q p q p q ∈∑=≤≤

=；由214

2,32,33

nf q f q f q =≤≤=； ,p f

为整数，故,4p f ≤，于是8p f +≤与(1)矛盾。

4．证明每个比赛图中必有有向哈密顿路。（用数学归纳法证明） 证：设D 是p 个顶点的比赛图。施归纳于p ： 当p=1，2时,结论显然成立。

假设当≥p 2时结论成立，往证对p+1个顶点的比赛图D 也成立。从D 中

去掉一个顶点u ，则得

到一个具有p 个顶点的比赛图D-u 。由归纳假设D-u 有哈密顿路

12p u ，u ，，u 。

在D 中，若1uu 或p u u 为D 的弧，则结论成立。今设1u u 及p uu 为D 的弧，由于D 比赛图，所以u 与k u （k=2，，p-1）之间有且仅有一条弧，于是必有一个最大i 使i u u 为弧，从而i+1uu 为D 的弧。于是， 1i i+1p u u uu u 为

D 的哈密顿路。由归纳法原理知对任何p 本题结论成立。

集合论与图论 试题A

本试卷满分90分 （06级计算机、信息安全专业、实验学院） 一、判断对错（本题满分10分，每小题各1分） （ 正确画“√”，错误画“×”） 1．对每个集合A ，A A 2}{∈。 （×） 2．对集合Q P ,，若?==Q P Q Q P ,，则P =?。 （√） 3．设,,:X A Y X f ?→若)()(A f x f ∈，则A x ∈。 （×） 4．设,,:Y B Y X f ?→则有B B f f ?-))((1。 （×） 5．若R 是集合X 上的等价关系，则2R 也是集合X 上的等价关系。 （√） 6．若:f X Y →且f 是满射，则只要X 是可数的，那么Y 至多可数的。（√） 7．设G 是有10个顶点的无向图，对于G 中任意两个不邻接的顶点u 和v, 均有9deg deg ≥+v u ，则G 是哈密顿图。 （×） 8．设)(ij a A =是 p 个顶点的无向图G 的邻接矩阵，则对于G 的顶点i v , 有∑==p j ij i a v 1deg 成立。 （√） 9. 设G 是一个),(q p 图，若1-≥p q ，则]/2[)(q p G ≤χ。 （×） 10．图G 和1G 同构当且仅当G 和1G 的顶点和边分别存在一一对应关系。（×）

二.填空(本题40分，每空各2分) 1．设}},{,{φφ=S 则=S 2 }}}{,{}},{{},{,{φφφφφ 。 2．设B A ,是任意集合，若B B A =\，则A 与B 关系为 φ==B A 。 3．设1)(,0)()(,:};3,2{},1,0{},,,{===→===c f b f a f Y X f Z Y c b a X , 3)1(,2)0(,:==→g g Z Y g ,则)()(c f g a f g ，分别为 2，3 。 4．设X 和Y 是集合且X m =，Y n =，若n m ≤，则从X 到Y 的单射的 个数为 !m C m n 。 5．设}2,1{},,,2,1{==B n X ，则从X 到Y 的满射的个数为 22-n 。 6．设)}2,4(),1,3(),3,2{()},4,3(),2,2(),2,1{(},4,3,2,1{===S R X ，则 =)(R S R )}2,3(),4,2(),4,1{( 。 7． 设???? ??=???? ??=5123454321,415235432121σσ，则???? ??=235411234521σσ 。 8. 设)},(),,(),,{(},,,,{a c c b b a R d c b a X ==，则 )},(),,(),,(),,(),,(),,(),,(),,(),,{(b c a c a b c b c a b a c c b b a a R =+ 。 9. 设X 为集合且X n =，则X 上不同的自反或对称的二元关系的个数 为 22222222n n n n n n +--+- 。 10．设}}{},{},,{{},,,,{d c b a A d c b a X ==是X 的一个划分，则由A 确定的 X 上的等价关系为 )},(),,(),,(),,(),,(),,{(d d c c a b b a b b a a 。 11．}10,,2,1{ =S ，在偏序关系“整除”下的极大元为 6，7，8，9，10 。 12．给出一个初等函数)(x f ，使得它是从)1,0(到实数集合R 的一一对应， 这个函数为 x ctg π或-x ctg π或)2/(ππ-x tg 。 13. 设G 是),(p p 连通图，则G 的生成树的个数至多为 p 。

2004图论复习题答案

图论复习题答案 一、判断题，对打，错打 1．无向完全图是正则图。 () 2．零图是平凡图。() 3．连通图的补图是连通图.() 4．非连通图的补图是非连通图。() 5．若连通无向简单图G中无圈，则每条边都是割边。() 6．若无向简单图G是（n，m）图，并且m=n-1，则G是树。() 7．任何树都至少有2片树叶。() 8．任何无向图G都至少有一个生成树。() 9．非平凡树是二分图。() 10．所有树叶的级均相同的二元树是完全二元树。() 11．任何一个位置二元树的树叶都对应唯一一个前缀码。() 12． K是欧拉图也是哈密顿图。() 3,3 13．二分图的对偶图是欧拉图。() 14．平面图的对偶图是连通图。() 页脚内容1

15．设G*是平面图G的对偶图，则G*的面数等于G的顶点数。() 二、填空题 1．无向完全图K6有15条边。 2．有三个顶点的所有互不同构的简单无向图有4个。 3．设树T中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T中有10片树叶。 4．若连通无向图G是（n，m）图，T是G的生成树，则基本割集有n-1个，基本圈有m-n+1个。 5．设连通无向图G有k个奇顶点，要使G变成欧拉图，在G中至少要加k/2条边。 6．连通无向图G是（n，m）图，若G是平面图，则G有m-n+2个面。 三、解答题 1．有向图D如图1所示，利用D的邻接矩阵及其幂运算 求解下列问题： （1）D中长度等于3的通路和回路各有多少条。 （2）求D的可达性矩阵。 （3）求D的强分图。 解：（1） a b c d e 图1 页脚内容2

页脚内容3 M=????????????????000101000000001 010*******M 2=?? ? ? ??????? ?????010******* 000101000001000 M 3=????????????????10000 01000010000001010000M 4=??? ???? ? ??? ?????00010 01000 100000100000010 由M 3可知，D 中长度等于3的通路有5条，长度等于3的回路有3条。 （2） I+M+M 2+M 3+M 4=????????????? ???100000100000100 0001000001 +??????????? ?? ???000101000000001 010******* +??????????? ?? ???010000001000010 1000001000 +??? ???? ? ??? ?? ???100000100001000 0001010000 + ????????????????00010 01000100000100000010 =??? ???? ???? ?? ???21020 1301011111 020******* D 的可达性矩阵为 R=B （I+M+M 2+M 3+M 4）=??? ???? ? ????? ???110101********* 1101011011 b c d e 图1

哈工大集合与图论习题

集合与图论习题 第一章习题 ．画出具有个顶点地所有无向图(同构地只算一个). ．画出具有个顶点地所有有向图(同构地只算一个). ．画出具有个、个、个顶点地三次图. ．某次宴会上，许多人互相握手.证明：握过奇数次手地人数为偶数(注意，是偶数). ．证明：哥尼斯堡七桥问题无解. ．设与是图地两个不同顶点.若与间有两条不同地通道(迹)，则中是否有回路？ ．证明：一个连通地(，)图中≥. ．设是一个(，)图，δ()≥[]，试证是连通地. ．证明：在一个连通图中，两条最长地路有一个公共地顶点. ．在一个有个人地宴会上，每个人至少有个朋友(≤≤).试证：有不少于个人，使得他们按某种方法坐在一张圆桌旁，每人地左、右均是他地朋友.b5E2R。 ．一个图是连通地，当且仅当将划分成两个非空子集和时，总有一条联结地一个顶点与地一个顶点地边. ．设是图.证明：若δ()≥ ，则包含长至少是δ()地回路. ．设是一个(，)图，证明： ()≥，则中有回路； ()若≥，则包含两个边不重地回路. ．证明：若图不是连通图，则是连通图. ．设是个(，)图，试证： ()δ()·δ()≤[()]([()])，若≡，，( ) () δ()·δ()≤[()]·[()]，若≡( ) ．证明：每一个自补图有或个顶点. ．构造一个有个顶点而没有三角形地三次图，其中≥. .给出一个个顶点地非哈密顿图地例子，使得每一对不邻接地顶点和，均有 ≥ ．试求中不同地哈密顿回路地个数. ．试证：图四中地图不是哈密顿图. ．完全偶图，为哈密顿图地充分必要条件是什么？

．菱形面体地表面上有无哈密顿回路？ ．设是一个(≥)个顶点地图.和是地两个不邻接地顶点，并且≥.证明：是哈密顿图当且仅当是哈密顿图. ．设是一个有个顶点地图.证明：若>δ()，则有长至少为δ()地路. ．证明具有奇数顶点地偶图不是哈密顿图. ．证明：若为奇数，则中有()个两两无公共边地哈密顿回路. ．中国邮路问题：一个邮递员从邮局出发投递信件，然后返回邮局.若他必须至少一次走过他所管辖范围内地每条街道，那么如何选择投递路线，以便走尽可能少地路程.这个问题是我国数学家管梅谷于年首先提出地，国外称之为中国邮路问题.p1Ean。 ()试将中国邮路问题用图论述语描述出来. ()中国邮路问题、欧拉图问题及最短路问题之间有何联系. 第三章习题 ．分别画出具有、、个顶点地所有树(同构地只算一个). ．证明：每个非平凡树是偶图. ．设是一棵树且Δ()≥，证明：中至少有个度为地顶点. ．令是一个有个顶点，个支地森林，证明：有条边. ．设是一个个顶点地树.证明：若图地最小度δ()≥，则有一个同构于地子图. ．一棵树有个度为地顶点，个度为地顶点，…，个度为地顶点，则有多少个度为地顶点？ .设是一个连通图.试证：地子图是地某个生成树地子图，当且仅当 没有回路. ．证明：连通图地任一条边必是它地某个生成树地一条边. ．设是一个边带权连通图，地每条边均在地某个回路上.试证：若地边地权大于地任一其他边地权，则不在地任一最小生成树中.DXDiT。 . 设(，，)是一个边带权连通图，对任意∈，()≥.试证：地一个生成树是地最小生成树，当且仅当时地任一与地距离为地生成树′′满足条件：在中而不在′′中地边地权()不大于在′′中而不在中地边′地权(′).RTCrp。 .某镇有人，每天他们中地每个人把昨天听到地消息告诉他认识地人.已知任何 消息，只要镇上有人知道，都会经这种方式逐渐地为全镇上所有人知道.试证：可选出个居民代表使得只要同时向他们传达某一消息，经天就会为全镇居民知道.5PCzV。 个顶点地图中，最多有多少个割点？ ．证明：恰有两个顶点不是割点地连通图是一条路.

2017年哈工大计算机科学与技术专业854考研真题

2016年哈工大计算机科学与技术专业854考研真题 I．数据结构 一、选择题 1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。 Int x = n * n; While (x >= 1) { X = x / 2; } A.O(log2n) B.O(n) C.O(nlog2n) D.O(n1/2) 2.需要分配一个较大的存储空间并且插入和删除操作不需要移动，元素满足以上特点的线 性表存储结构是（）。 A.单向链表 B.静态链表 C.线性链表 D.顺序表 3.已知字符串S为”ababcabcacbab”，模式串T为”abcac”。若采用KMP算法进行模式匹配， 则需要（）遍（趟匹配），就能确定T是S的子串。 A. 3 B. 4 C. 5 D. 6 4.已知某棵二叉树的前序序列是1,2,3,4，则不可能为该二叉树的中序序列的是（）。 A.1,2,3,4 B.2,3,4,1 C.1,4,3,2 D.3,1,4,2 5.将森林F转换为对应的二叉树T，F中任何一个没有右兄弟的结点，在T中（）。 A.没有左子树 B.没有右子树 C.没有左子树和右子树 D.以上都不对 6.一个含有n个顶点和e条边的无向图，在其邻接矩阵存储结构中共有（）个零元素。 A. e B.2e C.n2-2e D.n2-e 7.在一棵高度为2和7阶B树中，所含关键字的个数最少是（）。 A. 5 B.7 C.8 D.14

8.设待排序的元素个数为n，则基于比较的排序最坏情况下的时间复杂度的下界为（）。 A.log2n B.n C.nlog2n D.n2 9.下面关于B树和B+树的叙述中，不正确的是（）。 A.B树和B+树都能有效地支持随机检索 B.B树和B+树都能有效地支持顺序检索 C.B树和B+树都是平衡的多路树 D.B树和B+树都可以用于文件的索引结构 10.若待排序关键字序列在排序前已按其关键字递增顺序排列，则采用（）方法比较次数最 少。 A.插入排序 B.快速排序 C.堆排序 D.选择排序 二、填空题 11.在一棵n个结点的二叉树中，所有结点的空子树个数为11 。 12.若二叉树的一个叶结点是其某子树的中序遍历序列中的第一个结点，则它必是该子树的 后序遍历序列中的第12 个结点。 13.在有n个选手参加的单循环赛中，总共将进行13 场比赛。 14.在有4033个叶子结点的完全二叉树中，叶子结点的个数为14 个。 15.一个有向图G1的反向图是将G1的所有有向边取反而得到的有向图G2，若G1和G2 的邻接矩阵分别为A，B，则A与B的关系为15 。 16.N个顶点e条边的无环路有向图，若采用邻接表作为存储结构，则拓扑排序算法的时间 复杂度为16 。 17.在10阶B树中根结点所包含的关键字最多有17 个，最少有18 个。 18.在具有12个结点的平衡二叉树（A VL树）中，查找A VL树中的一个关键字最多需要 （18）次比较。 19.对初态有序的表，最少时间的排序算法是（19）。 三、简答题 20.在n个数据中找出前K个最大元素，可以采用堆排序或败者树来实现。分别说明上述两 种实现方法的基础步骤，并分析每种方法的时间复杂度和空间复杂度。 21.假设举办一个1000人参加的学术会议，作为会议报道组的负责人，你会收到会务组为 每名参会者开具的包含其英文名字的注册费发票，同时还会收到为每位参会者提供的印有其英文名字的参会胸牌和其他会议资料。请回答以下问题： （1）如何有效地把每个参会者注册费发票和参会胸牌等其他会议资料放在一起形成一份参会资料？ （2）如何在会议报道日更有效地把每份资料发放给参会者？ 要求：说明你所使用的主要技术和相关步骤。 四、算法设计题 按以下要求设计算法： （1）描述算法设计的基本思想； （2）根据设计思想，采用C或C++或Java语言描述算法；

北大集合论与图论往年考题.pdf

一、用真值表证明德*摩根律（证明其中一条即可）。 二、设A,B,C是集合，试问在什么条件下(A-B)-C=A-(B-C)？给出证明。 三、设A={a,b,c}，问A上有多少种不同的：二元关系？自反关系？对称关系？传递关系？等价关系？偏序关系？良序关系？ 四、用花括号和空集来表示1?2（注意?表示集合的叉乘）. 五、设R是实数集，Q是有理数集，试构造出R-Q与R之间的双射. 1．简单叙述构造的思路； 2．给出双射f：R-Q -> R 或f：R -> R-Q的严格定义。 2008年期末考题： 一、在有向图中，如果存在从顶点u到顶点v的有向通路，则说u可达v；如果顶点u和顶点v互相可达，则说u双向可达v。回答下列问题： 1．顶点集上的可达关系是不是等价关系？为什么？ 2．顶点集上的双向可达关系是不是等价关系？为什么？ 3．对于上述两个关系，如果是等价关系，其等价类的导出子图称为什么？ 二、一棵树有13个顶点，除了3个2度顶点和若干个树叶之外，其余顶点都是5度。 1．求出5度顶点的个数（写出计算过程）； 2．画出所有互不同构的这种树。 三、计算出右图中v1到v4长度为4的通路数（要写出计算过程 的主要步骤），并写出一个最小支配集、一个最大团、一个最小 边覆盖、一个最大匹配。 四、如果一个图中所有顶点度数都为k，则称为k正则图。8阶3 正则简单图一定是平面图吗？一定不是平面图吗？为什么？ 五、证明：如果正则简单图G和补图G都是连通图，则G和G中至少有一个是欧拉图。 六、证明：如果n阶（n≥3）简单图G中，对于任何1≤j,<2,3>,<3,2>, <3,4>}. (1) 给出R的矩阵表示, 画出R的关系图; (2) 判断R具有哪些关系性质(自反,反自反,对称,反对称,传递); (3) 求出R的自反闭包r(R), 对称闭包s(R), 传递闭包t(R). (用关系图表示) 三、设X,Y,Z是任意集合, 构造下列集合对之间的双射, 并给出是双射的证明. (1) Z(X?Y)与(Z X)Y ; (2) P(X?Y) 与P(X)?P(Y). (假设X?Y=?) 四、已知对每个自然数n, 都存在唯一后继n+=n?{n}. 证明: 对于每个非零自然数n, 都存在唯一前驱n-, 满足n=(n-)+. 五、设f: A→B是单射, g: B→A是单射, 证明: 存在集合C,D,E,F, 使得A=C?D, C?D=?, B=E?F, E?F=?, 并且f(C)=E, g(F)=D.

图论1-3藏习题解答

学号：0441 姓名：张倩 习题1 4．证明图1-28中的两图是同构的 证明：将图1-28的两图顶点标号为如下的(a)与(b)图 作映射f : f(v i )?u i (1? i ? 10) 容易证明，对?v i v j ?E((a)),有f(v i v j )?u i u j ?E((b)) (1? i ? 10, 1?j? 10 ) 由图的同构定义知，图1-27的两个图是同构的。 5.证明：四个顶点的非同构简单图有11个。 证明：设四个顶点中边的个数为m ，则有： m=0: m=1 ： m=2： m=3： (a) v 1 v 2 v 3 v v 5 v 6 v 7 v 8 v 9 v 10 u 1 u 2 u 3 u 4 u 5 u 6 u 7 u 8 u 9 u 10 (b)

m=4： m=5： m=6： 因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1）不是图序列。 证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列； （6,6,5,4,3,3,1）是图序列 ()1 1 123121,1,,1,,,=d d n d d d d d π++---是图序列 （5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 12.证明：若δ≥2，则G 包含圈。 证明 只就连通图证明即可。设V(G)=｛v1,v2,…,vn｝,对于G 中的路v1v2…vk,若vk 与v1邻接，则构成一个圈。若vi1vi2…vin 是一条路，由于?? 2，因此，对vin ，存在点vik 与之邻接，则vik?vinvik 构成一个圈 。 17.证明：若G 不连通，则G 连通。 证明 对)(,_ G V v u ∈?,若u 与v 属于G 的不同连通分支，显然u 与v 在_ G 中连通；若u 与v 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶点，则u 与w ，v 与w 分别在_ G 中连通，因此，u 与v 在_ G 中连通。

计算机组成原理第二章习题哈工大

计算机组成原理第二章习题 1.以真空管为主要器件的是______。 A. 第一代计算机 B. 第二代计算机 C. 第三代计算机 D. 第四代计算机 2.所谓第二代计算机是以______为主要器件。 A. 超大规模集成电路 B. 集成电路 C. 晶体管 D. 电子管 3.第三代计算机是以______为主要器件。 A. 超大规模集成电路 B. 集成电路 C. 晶体管 D. 电子管 4.ENIAC用的主要元件的是______。 A. 集成电路 B. 晶体管 C. 电子管 D. 以上都不对 5.目前被广泛使用的计算机是______。 A. 数字计算机 B. 模拟计算机 C. 数字模拟混合式计算机 D. 特殊用途的计算机 6.个人计算机（PC）属于______类计算机。 A. 大型机 B. 小型机 C. 微型机 D. 超级计算机 7.通常计算机的更新换代以______为依据。 A. 电子器件 B. 电子管 C. 半导体 D. 延迟线

8.目前大多数集成电路生产中，所采用的基本材料为______。 A. 单晶硅 B. 非晶硅 C. 锑化钼 D. 硫化镉 9.计算机科技文献中，英文缩写CAD代表______。 A. 计算机辅助制造 B. 计算机辅助教学 C. 计算机辅助设计 D. 计算机辅助管理 10.邮局把信件进行自动分拣，使用的计算机技术是______。 A. 机器翻译 B. 自然语言理解 C. 机器证明 D. 模式识别 11.微型计算机的发展通常以______为技术标志。 A. 操作系统 B. 磁盘 C. 软件 D. 微处理器 12.目前我们所说的个人台式商用机属于______。 A.巨型机 B.中型机 C.小型机 D.微型机 13. 电子邮件是指______。 A. 用计算机管理邮政信件 B. 通过计算机网络收发消息 C. 用计算机管理电话系统 D. 用计算机处理收发报业务

哈工大计算机组成大作业完整版

哈工大计算机组成大作业 哈工大计算机组成原理自主实验 计算机组成原理自主实验报告 第四章‐实验1 一个2114 存储芯片的实现 要求：外特性与2114 芯片一致（P77，图4.12），可以设计成为64*64 个存储单元的堆。 A0-A9：地址线 I/O：数据输入输出线 CS：片选信号 R/W：读写信号 VHDL代码： library IEEE;

use IEEE.STD_LOGIC_1164.ALL; USE IEEE.STD_LOGIC_UNSIGNED.ALL; entity shiyan41 is PORT(clk, we, cs,reset: in STD_LOGIC; data: inout STD_LOGIC_VECTOR(3 downto 0); adr: in STD_LOGIC_VECTOR(9 downto 0)); end shiyan41; architecture Behavioral of shiyan41 is typemem is array (63 downto 0) of STD_LOGIC_VECTOR(63 downto 0); signal data_in: STD_LOGIC_VECTOR(3 downto 0); signaldata_out: STD_LOGIC_VECTOR(3 downto 0); signalsram : mem; signalcs_s : std_logic; signalwe_s : std_logic; signaladdr_in_row: std_logic_vector(5 downto 0);

集合论与图论

集合论与图论习题册 软件基础教研室 刘峰 2015.02

第一章 集合及其运算 8P 习题 1. 写出方程2210x x ++=的根所构成的集合。 2.下列命题中哪些是真的，哪些为假 a)对每个集A ，A φ∈； b)对每个集A ，A φ?； c)对每个集A ，{}A A ∈； d)对每个集A ，A A ∈； e)对每个集A ，A A ?； f)对每个集A ，{}A A ?； g)对每个集A ，2A A ∈； h)对每个集A ，2A A ?； i)对每个集A ，{}2A A ?； j)对每个集A ，{}2A A ∈； k)对每个集A ，2A φ∈； l)对每个集A ，2A φ?； m)对每个集A ，{}A A =； n) {}φφ=； o){}φ中没有任何元素； p)若A B ?，则22A B ? q)对任何集A ，{|}A x x A =∈； r)对任何集A ，{|}{|}x x A y y A ∈=∈； s)对任何集A ，{|}y A y x x A ∈?∈∈； t)对任何集A ，{|}{|}x x A A A A ∈≠∈。 答案： 3.设有n 个集合12,,,n A A A 且121n A A A A ???? ，试证：12n A A A === 。 4.设{,{}}S φφ=，试求2S ？ 5.设S 恰有n 个元素，证明2S 有2n 个元素。

16P 习题 6.设A 、B 是集合，证明:(\)()\A B B A B B B φ=?= 。 7.设A 、B 是集合，试证A B A B φ=?=?。 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 。 15.下列命题是否成立？说明理由（举例）。 (1)(\)\(\)A B C A B C = ；(2)(\)()\A B C A B C = ； (3)\()()\A B C A B B = 。（答案：都不正确）

哈工大图论习题

哈工大图论习题

————————————————————————————————作者：————————————————————————————————日期：

1．画出具有4个顶点的所有无向图(同构的只算一个)。 2．画出具有3个顶点的所有有向图(同构的只算一个)。 3．画出具有4个、6个、8个顶点的三次图。 4．某次宴会上，许多人互相握手。证明：握过奇数次手的人数为偶数(注意，0是偶数)。 5．证明：哥尼斯堡七桥问题无解。 6．设u与v是图G的两个不同顶点。若u与v间有两条不同的通道(迹)，则G中是否有回路？ 7．证明：一个连通的(p，q)图中q ≥p-1。 8．设G是一个(p，q)图，δ(G)≥[p/2]，试证G是连通的。 9．证明：在一个连通图中，两条最长的路有一个公共的顶点。 10．在一个有n个人的宴会上，每个人至少有m个朋友(2≤m≤n)。试证：有不少于m+1个人，使得他们按某种方法坐在一张圆桌旁，每人的左、右均是他的朋友。 11．一个图G是连通的，当且仅当将V划分成两个非空子集V1和V2时，G总有一条联结V1的一个顶点与V2的一个顶点的边。 12．设G是图。证明：若δ(G)≥ 2，则G包含长至少是δ(G)+1的回路。 13．设G是一个(p，q)图，证明： (a)q≥p，则G中有回路； (b)若q≥p+4，则G包含两个边不重的回路。 14．证明：若图G不是连通图，则G c 是连通图。 15．设G是个(p，q)图，试证： (a)δ(G)·δ(G C)≤[(p-1)/2]([(p+1)/2]+1)，若p≡0，1，2(mod 4) (b) δ(G)·δ(G C)≤[(p-3)/2]·[(p+1)/2]，若p≡3(mod 4) 16．证明：每一个自补图有4n或4n+1个顶点。 17．构造一个有2n个顶点而没有三角形的三次图，其中n≥3。 18.给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有 degu+degv≥9 19．试求Kp中不同的哈密顿回路的个数。 20．试证：图四中的图不是哈密顿图。 21．完全偶图Km，n为哈密顿图的充分必要条件是什么？ 22．菱形12面体的表面上有无哈密顿回路？ 23．设G是一个p(p≥3)个顶点的图。u和v是G的两个不邻接的顶点，并且degu+degv ≥p。证明：G是哈密顿图当且仅当G+uv是哈密顿图。 24．设G是一个有p个顶点的图。证明：若p>2δ(G)，则有长至少为2δ(G)的路。 25．证明具有奇数顶点的偶图不是哈密顿图。 26．证明：若p为奇数，则Kp中有(p-1)/2个两两无公共边的哈密顿回路。 28．中国邮路问题：一个邮递员从邮局出发投递信件，然后返回邮局。若他必须至少一次走过他所管辖范围内的每条街道，那么如何选择投递路线，以便走尽可能少的路程。这个问题是我国数学家管梅谷于1962年首先提出的，国外称之为中国邮路问题。 (1)试将中国邮路问题用图论述语描述出来。 (2)中国邮路问题、欧拉图问题及最短路问题之间有何联系。

2019年哈工大计算机基础考生大纲

2019年硕士研究生入学考试大纲 考试科目名称：计算机基础考试科目代码：[854] 本考试科目考试时间180分钟，满分150分。包括数据结构与计算机组成原理两部分，每部分各75分。 数据结构部分（75分） 一、考试要求 1. 要求考生全面系统地掌握数据结构与算法的基本概念、数据的逻辑结构和 存储结构及操作算法，并能灵活运用；能够利用数据结构和算法的基本知识，为应用问题设计有效的数据结构和算法；能够分析算法的复杂性。 2. 要求能够用C/C++/Java等程序设计语言描述数据结构和算法。 注：考试内容范围主要以参考书目1为标准，带*号部分不在考试范围之内。 二、考试内容 1）数据结构与算法的概念 a:数据结构与算法及其相关的基本概念 b: 算法及其复杂性分析 2)线性表 a:线性结构及其操作算法 b: 线性表的应用及算法 3)树与二叉树 a:二叉树的定义、性质、表示、遍历算法 b: 树的表示、操作算法 c: 森林与二叉树关系 d: 树与二叉树的应用及算法 4)图及其相关算法 a:图的相关概念 b: 图的存储结构与搜索算法 c: 图的应用及算法 5)查找与排序

a:查找与排序的相关概念 b:典型算法的描述及复杂性分析 c: 查找与排序算法的应用 6)外部排序与文件 a:外部排序的相关概念及其基本方法 b:文件的组织方式、特点及应用 三、试卷结构 1)题型结构 a:填空题(0—15分) b:选择题(0—30分) c:简答题(0—30分) d:算法设计题(0—30分) 注：题型分数在以上范围内浮动，总分为75分 2)注意事项 算法设计题，必须包含算法的基本思想、存储结构设计和算法的描述四、参考书目 1．廖明宏，郭福顺，张岩，李秀坤，数据结构与算法（第4版），高等教育出版社，2007.11 2．严蔚敏，吴伟民，数据结构（C语言版），清华大学出版社，2002.09 计算机组成原理部分（75分） 一、考试要求 要求考生全面掌握计算机组成的基本原理、概念和方法，系统深入地理解计算机系统中总线、存储器、运算器、控制器、I/O系统等的组织结构和工作原理，掌握计算机硬件系统的基本分析与逻辑设计方法，理解计算机硬件系统各组成部分之间的关系，建立计算机系统的整体概念。 二、考试内容 1）计算机系统的基本概念

哈工大威海校区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.简述图的连通度、边连通度、最小度之间的关系。

哈工大计算机组成原理试卷1及答案

哈工大学年秋季学期 计算机组成原理试题

一、填空（12分） 1.某浮点数基值为2，阶符1位，阶码3位，数符1位，尾数7位， 阶码和尾数均用补码表示，尾数采用规格化形式，用十进制数写 出它所能表示的最大正数，非0最小正 数，最大负数，最 小负数。 2.变址寻址和基址寻址的区别是：在基址寻址中，基址寄存器提 供，指令提供；而在变址寻址中，变址 寄存器提供，指令提供。 3.影响流水线性能的因素主要反映在和 两个方面。 4.设机器数字长为16位（含1位符号位）。若1次移位需10ns，一 次加法需10ns，则补码除法需时间，补码BOOTH 算法最多需要时间。 5.CPU从主存取出一条指令并执行该指令的时间 叫，它通常包含若干个，而 后者又包含若干个。组成 多级时序系统。 二、名词解释(8分) 1.微程序控制 2.存储器带宽 3.RISC 4.中断隐指令及功能

三、简答（18分） 1. 完整的总线传输周期包括哪几个阶段？简要叙述每个阶段的工作。 2. 设主存容量为1MB，Cache容量为16KB，每字块有16个字，每字32位。 (1)若Cache采用直接相联映像，求出主存地址字段中各段的位数。 (2)若Cache采用四路组相联映像，求出主存地址字段中各段的位数。 3. 某机有五个中断源，按中断响应的优先顺序由高到低为L0,L1,L2,L3,L4，现要求优先顺序改为L3,L2,L4,L0,L1，写出各中断源的屏蔽字。

4. 某机主存容量为4M ×16位，且存储字长等于指令字长，若该机的指令系统具备120种操作。操作码位数固定，且具有直接、间接、立即、相对四种寻址方式。 （1）画出一地址指令格式并指出各字段的作用； （2）该指令直接寻址的最大范围； （3）一次间址的寻址范围； （4）相对寻址的寻址范围。 四、（6分） 设阶码取3位，尾数取6位（均不包括符号位），按浮点补码运算规则 计算 [25169?] + [24)16 11(-?] 五、画出DMA 方式接口电路的基本组成框图，并说明其工作过程（以输入设备为例）。（8分）

哈工大年集合论与图论试卷

-- 本试卷满分90分 (计算机科学与技术学院0９级各专业) 一、填空（本题满分１0分,每空各1分) 1.设B A ,为集合,则A B B A = )\(成立的充分必要条件是什么？(A B ?) ２.设}2,1{},,,2,1{==Y n X ,则从X 到Y 的满射的个数为多少?（22-n ) ３．在集合}11,10,9,8,4,3,2{=A 上定义的整除关系“|”是A 上的偏序关系， 则 最大元是什么? ( 无 ） 4．设{,,}A a b c =，给出A 上的一个二元关系,使其同时不满足自反性、反自 反性、对称性、反对称和传递性的二元关系。({(,),(,),(,),(,)}R a a b c c b a c =） ５．设∑为一个有限字母表,∑上所有字(包括空字）之集记为*∑，则*∑是 否是可数集? （ 是 ) ６.含5个顶点、3条边的不同构的无向图个数为多少？ （ ４ ） 7.若G 是一个),(p p 连通图，则G 至少有多少个生成树? （ 3 ） 8. 如图所示图G ,回答下列问题： (１）图G 是否是偶图? ( 不是 ) (2）图G 是否是欧拉图? ( 不是 ） (3)图G 的色数为多少？ ( 4 ) 二、简答下列各题（本题满分40分） 1．设D C B A ,,,为任意集合，判断下列等式是否成立?若成立给出证明，若不 成立举出反例。(6分) (1))()()()(D B C A D C B A ??=? ； （2）()()()()A B C D A C B D ?=??。 解:（1）不成立。例如}{,a c B D A ====φ即可。 （2）成立。(,)x y ?∈()()A B C D ?，有,x A B y C D ∈∈，即 ,,,x A x B y C y D ∈∈∈∈。所以(,),(,)x y A C x y B D ∈?∈?,因此 (,)()()x y A C B D ∈??,从而()()A B C D ??()()A C B D ??。 反之,(,)x y ?∈()()A C B D ??，有,,,x A x B y C y D ∈∈∈∈。即 (,)x y ∈()()A B C D ?，从而()()A C B D ???()()A B C D ?。

哈工大计算机组成原理试卷1及答案

而兴奋不已。 哈工大学年秋季学期 计算机组成原理试题 只有凭借毅力，坚持到底，才有可能成为最后的赢家。这些磨练与考验使成长中的青少年受益匪浅。在种种历练之后，他们可以学会如何独立处理问题；如何调节情绪与心境，直面挫折，抵御压力；如何保持积极进取的

而兴奋不已。 一、填空（12分） 1.某浮点数基值为2，阶符1位，阶码3位，数符1位，尾数7位， 阶码和尾数均用补码表示，尾数采用规格化形式，用十进制数写 出它所能表示的最大正数，非0最小正 数，最大负数，最 小负数。 2.变址寻址和基址寻址的区别是：在基址寻址中，基址寄存器提 供，指令提供；而在变址寻址中，变址 寄存器提供，指令提供。 3.影响流水线性能的因素主要反映在和 两个方面。 4.设机器数字长为16位（含1位符号位）。若1次移位需10ns，一 次加法需10ns，则补码除法需时间，补码BOOTH 算法最多需要时间。 5.CPU从主存取出一条指令并执行该指令的时间 叫，它通常包含若干个，而 后者又包含若干个。组成 多级时序系统。 二、名词解释(8分) 1.微程序控制 2.存储器带宽 3.RISC 4.中断隐指令及功能 只有凭借毅力，坚持到底，才有可能成为最后的赢家。这些磨练与考验使成长中的青少年受益匪浅。在种种历练之后，他们可以学会如何独立处理问题；如何调节情绪与心境，直面挫折，抵御压力；如何保持积极进取的

而兴奋不已。 三、简答（18分） 1. 完整的总线传输周期包括哪几个阶段？简要叙述每个阶段的工作。 2. 设主存容量为1MB，Cache容量为16KB，每字块有16个字，每字32位。 (1)若Cache采用直接相联映像，求出主存地址字段中各段的位数。 (2)若Cache采用四路组相联映像，求出主存地址字段中各段的位数。 3. 某机有五个中断源，按中断响应的优先顺序由高到低为L0,L1,L2,L3,L4，现要求优先顺序改为L3,L2,L4,L0,L1，写出各中断源的屏蔽字。 只有凭借毅力，坚持到底，才有可能成为最后的赢家。这些磨练与考验使成长中的青少年受益匪浅。在种种历练之后，他们可以学会如何独立处理问题；如何调节情绪与心境，直面挫折，抵御压力；如何保持积极进取的

集合论与图论SG2017-期中试题-答案(1)

一、（20分）对于任意集合A和B， （1）证明：P(A)?P(B) = P(A?B)；（14分） 对任意的x∈P(A)?P(B)，有x∈P(A)且x∈P(B)。即x?A并且x?B，则x?A?B。所以x∈P(A?B)。故P(A)?P(B)?P(A?B)。（7分）对任意的x∈P(A?B)，有x?A?B，即x?A并且x?B，所以x∈P(A)且x∈P(B)。因此P(A?B)?P(A)?P(B)。（7分）综上所述，P(A)?P(B)=P(A?B) （2）举例说明P(A)?P(B) ≠ P(A?B). （6分） A={1}, B={2}, A?B={1, 2}; P(A)={?, {1}}, P(B)={?, {2}}, P(A)?P(B)= {?, {1}, {2}}, P(A?B)= {?, {1}, {2}, {1, 2}}; 所以P(A)?P(B)≠P(A?B) 二、（20分）设R, S是A上的等价关系且R?S=S?R，证明： R?S是A上的等价关系. 自反性和对称性容易证明，略。（5分） 传递性证明： 对任意a, b, c∈A，如果(a, b)∈R?S, (b, c)∈R?S，要证明(a, c)∈R?S。 因为R?S=S?R，则有(b, c)∈S?R，即存在e, f∈A，使(a, e)∈R，(e, b)∈S，(b, f)∈S，(f, c)∈R。 因为S是传递的，(e, b)∈S，(b, f)∈S，所以(e, f)∈S；因为(a, e)∈R，所以(a, f)∈R?S；R?S是对称的，则(f, a)∈R?S；因为R是对称的，(f, c)∈R，则(c, f)∈R。因为(f, a)∈R?S，则存在g∈A，使得(f, g)∈R，(g, a)∈S；因为R是传递的，

图论习题参考答案

二、应用题 题0：（1996年全国数学联赛） 有n（n≥6）个人聚会，已知每个人至少认识其中的[n/2]个人，而对任意的[n/2]个人，或者其中有两个人相互认识，或者余下的n-[n/2]个人中有两个人相互认识。证明这n个人中必有3个人互相认识。 注：[n/2]表示不超过n/2的最大整数。 证明将n个人用n个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G。由条件可知，G是具有n个顶点的简单图，并且有 （1）对每个顶点x，) N G≥[n/2]； (x （2）对V的任一个子集S，只要S＝[n/2]，S中有两个顶点相邻或V-S中有 两个顶点相邻。 需要证明G中有三个顶点两两相邻。 反证，若G中不存在三个两两相邻的顶点。在G中取两个相邻的顶点x1和y1,记N G(x1)＝{y1,y2,……,y t}和N G(y1)={x1,x2,……,x k},则N G(x1)和N G(y1)不相交，并且N G(x1)（N G(y1)）中没有相邻的顶点对。 情况一；n=2r：此时[n/2]＝r，由（1）和上述假设，t=k=r且N G(y1)＝V-N G(x1)，但N G(x1)中没有相邻的顶点对，由（2），N G(y1)中有相邻的顶点对，矛盾。 情况二；n=2r+1: 此时[n/2]＝r，由于N G(x1)和N G(y1)不相交，t≥r,k≥r,所以r+1≥t,r+1≥k。若t=r+1,则k=r，即N G(y1)=r，N G(x1)＝V-N G(y1)，由（2），N G(x1)或N G(y1)中有相邻的顶点对，矛盾。故k≠r+1，同理t≠r+1。所以t=r,k=r。记w∈V- N G(x1) ∪N G(y1),由（2），w分别与N G(x1)和N G(y1)中一个顶点相邻，设wx i0∈E, wy j0∈E。若x i0y j0∈E，则w，x i0, y j0两两相邻，矛盾。若x i0y j0?E，则与x i0相邻的顶点只能是(N G(x1)-{y j0})∪{w},与y j0相邻的顶点只能是(N G(y1)-{x j0})∪{w}。但与w相邻的点至少是3，故N G(x1)∪N G(y1)中存在一个不同于x i0和y j0顶点z与w相邻，不妨设z∈N G(x1)，则z，w，x i0两两相邻，矛盾。 题1：已知图的结点集V={a,b,c,d}以及图G和图D的边集合分别为： E(G)={(a,a), (a,b), (b,c), (a,c)} E(D)={, , , , } 试作图G和图D，写出各结点的度数，回答图G、图D是简单图还是多重图？ 解：a d a d b c b c 图G图D 例2图