哈工大图论习题
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)中国邮路问题、欧拉图问题及最短路问题之间有何联系。
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．在图1.4.5中，一只车从位置A出发，在半张棋盘上走，每步走一格，走了若干步后到了位置B。证明：至少有一个格点，没有车走过，或被走过不至一次。
19.给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有
degu+degv≥9
20．试求Kp中不同的哈密顿回路的个数。
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个两两无公共边的哈密顿回路。
27．中国邮路问题：一个邮递员从邮局出发投递信件，然后返回邮局。若他必须至少一次走过他所管辖范围内的每条街道，那么如何选择投递路线，以便走尽可能少的路程。这个问题是我国数学家管梅谷于1962年首先提出的，国外称之为中国邮路问题。
(1)试将中国邮路问题用图论述语描述出来。
(2)中国邮路问题、欧拉图问题及最短路问题之间有何联系。
第三章习题
1．分别画出具有4、5、6个顶点的所有树(同构的只算一个)。
2．证明：每个非平凡树是偶图。
3．设G是一棵树且Δ(G)≥k，证明：G中至少有k个度为1的顶点。
4．令G是一个有p个顶点，k个支的森林，证明：G有p-k条边。
5．设T是一个k+1个顶点的树。证明：若图G的最小度δ(G)≥k，则G有一个同构于T的子图。
6．一棵树T有n2个度为2的顶点，n3个度为3的顶点，…，n k个度为k的顶点，则T 有多少个度为1的顶点？
是G的某个生成树的子图，当且仅当G1
7.设G是一个连通图。试证：G的子图G
1
没有回路。
8．证明：连通图的任一条边必是它的某个生成树的一条边。
9．设G是一个边带权连通图，G的每条边均在G的某个回路上。试证：若G的边e的权大于G的任一其他边的权，则e不在G的任一最小生成树中。
10. 设G=(V，E，w)是一个边带权连通图，对任意x∈E，w(x)≥0。试证：G的一个生成树T是G的最小生成树，当且仅当时G的任一与T的距离为1的生成树T′′满足条件：在T中而不在T′′中的边e的权w(e)不大于在T′′中而不在T中的边e′的权w(e′)。
11.某镇有1000人，每天他们中的每个人把昨天听到的消息告诉他认识的人。已知任何消息，只要镇上有人知道，都会经这种方式逐渐地为全镇上所有人知道。试证：可选出90个居民代表使得只要同时向他们传达某一消息，经10天就会为全镇居民知道。
12.P个顶点的图中，最多有多少个割点？
13．证明：恰有两个顶点不是割点的连通图是一条路。
14．证明：有一座桥的三次图中至少有10个顶点。
15．设v是图G的一个割点，证明v不是G的补图G c的割点。
16．设v是图G的一个顶点。证明：v是G的割点当且仅当有邻接v的两个不同的顶点u和w，使得v在u与w间的每一条路上。
17.割点的连通图是否一定不是欧拉图？是否一定不是哈密顿图？有桥的连通图是否
一定不欧拉图和哈密顿图。
18.L是连通图G的一个回路，x和y是L上的两条边。证明：G有个割集S使得x与y 恰好是L与S的公共边。
第四章习题
1．设G是一个有p个顶点的图，δ(G)≥((p+k)-1)/2，试证：G是k-连通的。
2．若(p，q)图G是k-边连通的，试证：q≥kp/2。
3．设G是k-边连通的，k>0，E′是G的k条边的集合。证明：G-E′的支数小于或等于2。
4．构造一个(p，q)图G使得δ(G)=[p/2-1]，λ(G)<δ(G).
5．设k>0。构造一个k-连通图G，以及G的k个顶点之集V′，使得G-V′的支数大于2。
6．G是一个三次正则图，试证：χ(G)=λ(G)。
7．设r≥2，G是r正则图。证明：λ(G)≥[r/2]。
8．构造一个图G，使得χ(G)=3，λ(G)=4，δ(G)=5。
9．证明：图G是2-边连通的当且仅当任两个不同顶点间至少有两条边不重路。
10．设G=(V，E)是2-边连通图，X和Y是V的子集，|X|≥2，|Y|≥2且X∩Y=Φ。在G
中加入两个新的顶点s和t，s与X的每个顶点之间联成一条边，t与Y的每个顶点间加一条边，这样得到的图记为G′。试证：G′是2-连通的。
11. 若G是顶点数p≥11的平面图，试证G c不是平面图。
12 设S＝{x
1，x
2
，x
3
，…，x
n
}是平面上n个顶点的集合，n≥3，其中任两顶点的距离
至少是1。证明：S中至多有3n-6对顶点，其距离为1。
13．证明：不存在7条棱的凸多面体。
14. 图G的最短回路的长度称为G的围长；若G中无回路，则定义G的围长为无穷大。
(ⅰ)证明：围长为r的平面连通图G中有
q≤r(p-2)/(r-2)，r≥3
(ⅱ)利用(ⅰ )证明Petersen图(见图3.6.4)不是平面图。
15.设G是一个没有三角形的平面图。应用欧拉公式证明G中有一个顶点v使得degv ≤3。
16．设G是一个平面图。证明：G**同构于G当且仅当G是连通的。
17．证明：若G是自对偶的，则q=2p-2.
18.设G是一个没有三角形的图。应用教学归纲法证明G是4－可着色的(事实上，可以证明G是3－可着色的)。
19.设G是一个有p个顶点的d-正则图，证明：k(G)≥p/(p-d)。
20.试用5-色定理的证明方法来证明4色定理，在哪一点证明会失败呢？
21.设G是一个(p，q)图，证明：k(G)≥p2/(p2-2p)。
22.证明：若G的任两个奇数长的回路都有一个公共顶点，则k(G)≤5。
23.证明：每个哈密顿平面图都是4-可着色的。
24.设G是一个立方体哈密顿图，证明：k′(G)=3。
25.若r是奇数且G是r-正则图，证明：k′(G)=r+1。
26.若G是彼德森图，证明：k′(G)=4。
第五章习题
1.给出有向图的子图、生成子图、导出子图的定义。
2.画出具有三个顶点的所有互不同构的有向图的图解。
3.具有p个顶点的完全有向图中有多少条弧？
4.设D是一个有p个顶点q条弧的有向图。若D是连通的，证明
p-1≤q≤p(p-1)。
5.设D是一个有p个顶点q条弧的强连通的有向图，则q至少是多大？
6.在有向图中，含有所有顶点和所有弧的有向闭迹称为有向欧拉闭迹。一个有向图若含有有向欧闰闭迹，则称此有向图为有向欧拉图。证明：有向图D=(V，A)是有向欧拉图当且仅当D是连通的且对任意的v∈V，总有id(v)=od(v)。
7.证明：有向图D是单向连通的当且仅当D有一条生成通道。
8.设A是一个n×n布尔矩阵，试证：
(I∨A)(2)=(I∨A)(I∨A)=I∨A∨A(2)
其中I是n×n单位矩阵。其次，证明：对任意的正整数r，有
(I∨A)(r)=I∨A ∨A(2)∨…∨A(r)
9.设B是有向图D=(V，A)的邻接矩阵，|V|=p。试证D的可达矩阵R为R=(I∨B)(p)
10.有向图D的图解如图一所示
(1)写出D的邻接矩阵及可达矩阵。
(2)写出D 关联矩阵。
v 1 D
22
11.设D 为图二中的有向图，试求v 2到其余每个顶点的长≤4的所有通道的条数。
12.已知有向图D 的邻接矩阵B ，如何从B 求D 的可达矩阵R ？
13.设T 是一个正则m 元有序树，它有n 0个叶子，T 有多有多少条弧？
14．令T 是一个正则m 元树，它有i 个内顶点(出度为m)。若E 为所有内顶点深度之和，i 为所有叶顶点深度之和， 证明：I=(m-1)I+mi 。
15.设T 是一个有n 0个叶子的二元树，出度为2的顶点为n2，试证：n 0=n 2+1。
16.具有三个顶点的有序树共有多少个？具有三个顶点的有根树有多个？注意，同构的只算一个。
17.一个有序树称为一个2-3树，若每个内顶点有2个或3个儿子，并且从根顶点到每个叶子的路长均相等。试证：若T 是一个高为h 的2-3树，则
(1)T 的顶点数p 满足2h+1-1≤ p ≤3h+1-1。
(2)T 的叶子数在2h 与3h 之间。
18．T 是一个正则二元树，它有i 个内顶点(出度为2)。若E 为所有内顶点深度之和，I 为所叶顶点的深度之和，证明：I=E+2i 。
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
离散数学图论与系中有图题目
离散数学图论与系中有图题目
————————————————————————————————作者：————————————————————————————————日期：
图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8个结点的三次正则图 (2) (1) (3) (2)(1)
课后习题答案
第一章 液压传动概述 液压传动系统由哪几部分组成各组成部分的作用是什么 解答：液压传动由以下四部分组成： （1）动力元件(液压泵)：它是把原动机输出的机械能转换成油液压力能的元件。作用:给液压系统提供压力油，是液压系统的心脏。 （2）执行元件：包括液压缸和液压马达等。 作用:把油液的压力能转换成机械能以驱动工作机构的元件。 （3）控制元件：包括压力、方向、流量控制阀。作用:是对液压系统中油液的压力、流量和流动方向进行控制和调节的元件。 （4）辅助元件：除上述三项以外的、液压系统中所需的其它装置。如油箱、滤油器、油管、管接头等。作用:保证液压系统有效工作，寿命长。 第二章 液压泵和液压马达 要提高齿轮泵的压力需解决哪些关键问题通常都采用哪些措施 解答：（1）困油现象： 采取措施：在两端盖板上开卸荷槽。（2）径向不平衡力：采取措施：缩小压油口直径；增大扫膛处的径向间隙； 过渡区连通；支撑上采用滚针轴承或滑动轴承。（3）齿轮泵的泄漏： 采取措施：采用断面间隙自动补偿装置。 齿轮泵的模数 mm m 4=，齿数9=z ，齿宽mm B 18=，在额定压力下，转速min 2000r n =时，泵的 实际输出流量min 30L Q =，求泵的容积效率。 解答：()() 2 2630 0.876.6~7 6.69418200010v t q q q zm bn η-= ===????? YB63型叶片泵的最高压力MPa P 3.6max =，叶片宽度mm B 24=，叶片厚度mm 25.2=δ，叶片数 12=Z ，叶片倾角?=13θ,定子曲线长径mm R 49=，短径mm r 43=，泵的容积效率9.0=v η，机械效率 90.0=m η，泵轴转速min 960r n =，试求：(1) 叶片泵的实际流量是多少(2)叶片泵的输出功率是多少 解答： （1） ()()()()() 22 223 322cos 20.0490.04320.0490.0430.024120.0249600.9cos131.0210v R r q R r bz Bn m s πηφπ-??=--???? ?-?? =--?????????? =? （2） 633 6.310 1.0210 6.4210N pq -==???=?出 斜盘式轴向柱塞泵的斜盘倾角?=20β，柱塞直径mm d 22=，柱塞分布圆直径mm D 68=，柱塞数7=z ，机械效率90.0=m η，容积效率97.0=v η，泵转速min 1450r n =，泵输出压力MPa p 28=，试计算：(1)平
图论 张先迪 李正良 课后习题答案
习题一 作者---寒江独钓 1.证明：在n 阶连通图中 (1) 至少有n-1条边； (2) 如果边数大于n-1，则至少有一条闭迹； (3) 如果恰有n-1条边，则至少有一个奇度点。 证明: (1) 若G 中没有1度顶点，由握手定理： ()2()21v V G m d v n m n m n ∈= ≥?≥?>-∑ 若G 中有1度顶点u ，对G 的顶点数作数学归纳。 当n=2时，结论显然；设结论对n=k 时成立。 当n=k+1时，考虑G-u,它仍然为连通图，所以，边数≥k-1.于是G 的边数≥k. (2) 考虑G 中途径： 121:n n W v v v v -→→→→L 若W 是路，则长为n-1;但由于G 的边数大于n-1,因此，存在v i 与v j ,它们相异，但邻接。于是： 1i i j i v v v v +→→→→L 为G 中一闭途径，于是 也就存在闭迹。 (3) 若不然，G 中顶点度数至少为2，于是由握手定理： ()2()21v V G m d v n m n m n ∈= ≥?≥?>-∑ 这与G 中恰有n-1条边矛盾！ 2.(1)2n ?12n 2?12n ?1 (2)2n?2?1 (3) 2n?2 。 证明 :u 1的两个邻接点与v 1的两个邻接点状况不同。所以， 两图不同构。 4.证明下面两图同构。 u 1 v 1
证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对?v i v j ∈E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 5.指出4个顶点的非同构的所有简单图。 分析：四个顶点的简单图最少边数为0，最多边数为6，所以 可按边数进行枚举。 (a) v 2 v 3 u 4 u (b)
离散数学测验题--图论部分(优选.)
离散数学图论单元测验题 一、单项选择题(本大题共10小题，每小题2分，共20分) 1、在图G ＝
课后习题及答案
1 文件系统阶段的数据管理有些什么缺陷试举例说明。 文件系统有三个缺陷： （1）数据冗余性（redundancy)。由于文件之间缺乏联系，造成每个应用程序都有对应的文件，有可能同样的数据在多个文件中重复存储。 （2）数据不一致性（inconsistency)。这往往是由数据冗余造成的，在进行更新操作时，稍不谨慎，就可能使同样的数据在不同的文件中不一样。 （3）数据联系弱(poor data relationship)。这是由文件之间相互独立，缺乏联系造成的。 2 计算机系统安全性 （1）为计算机系统建立和采取的各种安全保护措施，以保护计算机系统中的硬件、软件及数据； （2）防止其因偶然或恶意的原因使系统遭到破坏，数据遭到更改或泄露等。 3. 自主存取控制缺点 （1）可能存在数据的“无意泄露” （2）原因：这种机制仅仅通过对数据的存取权限来进行安全控制，而数据本身并无安全性标记 （3）解决：对系统控制下的所有主客体实施强制存取控制策略 4. 数据字典的内容和作用是什么 数据项、数据结构 数据流数据存储和加工过程。 5. 一条完整性规则可以用一个五元组（D，O，A，C，P）来形式化地表示。 对于“学号不能为空”的这条完整性约束用五元组描述 D：代表约束作用的数据对象为SNO属性； O（operation）：当用户插入或修改数据时需要检查该完整性规则； A（assertion）：SNO不能为空； C（condition）：A可作用于所有记录的SNO属性； P（procdure）：拒绝执行用户请求。 6.数据库管理系统（DBMS）
：①即数据库管理系统（Database Management System)，是位于用户与操作系统之间的 一层数据管理软件，②为用户或应用程序提供访问DB的方法，包括DB的建立、查询、更 新及各种数据控制。 DBMS总是基于某种数据模型，可以分为层次型、网状型、关系型、面 向对象型DBMS。 7.关系模型：①用二维表格结构表示实体集，②外键表示实体间联系的数据模型称为关系模 型。 8.联接查询：①查询时先对表进行笛卡尔积操作，②然后再做等值联接、选择、投影等操作。 联接查询的效率比嵌套查询低。 9. 数据库设计：①数据库设计是指对于一个给定的应用环境，②提供一个确定最优数据模 型与处理模式的逻辑设计，以及一个确定数据库存储结构与存取方法的物理设计，建立起 既能反映现实世界信息和信息联系，满足用户数据要求和加工要求，又能被某个数据库管 理系统所接受，同时能实现系统目标，并有效存取数据的数据库。 10．事务的特征有哪些 事务概念 原子性一致性隔离性持续性 11．已知3个域： D1=商品集合=电脑，打印机 D3=生产厂=联想，惠普 求D1，D2，D3的卡尔积为： 12.数据库的恢复技术有哪些 数据转储和和登录日志文件是数据库恢复的
图论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 中连通。
图论习题参考答案
二、应用题 题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 ， )(x N G ≥[n /2]； （2）对V 的任一个子集S ，只要S ＝[n /2]，S 中有两个顶点相邻或V-S 中有 两个顶点相邻。 需要证明G 中有三个顶点两两相邻。 反证，若G 中不存在三个两两相邻的顶点。在G 中取两个相邻的顶点x 1和y 1,记N G (x 1)＝{y 1,y 2,……,y t }和N G (y 1)={x 1,x 2,……,x k },则N G (x 1)和N G (y 1)不相交，并且N G (x 1)（N G (y 1)）中没有相邻的顶点对。 情况一；n=2r ：此时[n /2]＝r ，由（1）和上述假设，t=k=r 且N G (y 1)＝V-N G (x 1)，但N G (x 1)中没有相邻的顶点对，由（2），N G (y 1)中有相邻的顶点对，矛盾。 情况二；n=2r+1: 此时[n /2]＝r ，由于N G (x 1)和N G (y 1)不相交，t ≥r,k ≥r,所以r+1≥t,r+1≥k 。若t=r+1,则k=r ，即N G (y 1)=r ，N G (x 1)＝V-N G (y 1)，由（2），N G (x 1)或N G (y 1)中有相邻的顶点对，矛盾。故k ≠r+1，同理t ≠r+1。所以t=r,k=r 。记w ∈V- N G (x 1) ∪N G (y 1),由（2），w 分别与N G (x 1)和N G (y 1)中一个顶点相邻，设wx i0∈E, wy j0∈E 。若x i0y j0∈E ，则w ，x i0, y j0两两相邻，矛盾。若x i0y j0?E ，则与x i0相邻的顶点只能是(N G (x 1)-{y j0})∪{w},与y j0相邻的顶点只能是(N G (y 1)-{x j0})∪{w}。但与w 相邻的点至少是3，故N G (x 1)∪N G (y 1)中存在一个不同于x i0和y j0顶点z 与w 相邻，不妨设z ∈N G (x 1)，则z ，w ，x i0两两相邻，矛盾。 题1：已知图的结点集V ={a ,b ,c ,d }以及图G 和图D 的边集合分别为： E (G )={(a ,a ), (a ,b ), (b ,c ), (a ,c )} E (D)={, ,
习题参考解答图论部分
习题十 1. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。 证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v)) ≤ n-1, G图的总点度上限为 max(Σ(d(v)) ≤ n﹒max(d(v)) ≤ n(n-1) 。根据握手定理，G图边的上限为 max(m) ≤ n(n-1)/2,所以。 （2） =〉G是完全图 因为G具有上限边数，假设有结点的点度小于n-1,那么G的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G的每个结点的点度都为n-1，G为完全图。 G是完全图 =〉 因为G是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G的边数。■ 2. 设G是一个（n，n+1）的无向图，证明G中存在顶点u，d（u）≥3。证明：反证法，假设,则G的总点度上限为max(Σ(d(u)) ≤2 n，根据握手定理，图边的上限为max(m) ≤2n/2=n。与题设m = n+1，矛盾。因此，G中存在顶点u，d（u）≥3。■ 3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来:
（1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5） 解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。 可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明： (6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5} 每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)
张清华图论课后题答案.
第1章 图论预备知识 1.1 解：(1) p={φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} (2) p={,{a},{{b,c}},{a,{b,c}}} (3) p={,{}} (4) p={,{},{{}},{,{}}} (5)p={,{{a,b}},{{a,a,b}},{{a,b,a,b}},{{a,b},{a,a,b}},{{a,b},{a,b,a,b}},{{a,b},{a,a,b},{a,b,a,b}}} 1.2 解：(1) 真 (2) 假 (3)假 (4)假 1.3 解：(1) 不成立，A={1} B={1,2} C={2} (2) 不成立，A={1} B={1,2} C={1,3} 1.4 证明：设(x,y)∈(A ∩B)X(C ∩D) 说明x ∈A ∩B,y ∈C ∩D 由于 x ∈A,y ∈C 所以 (x,y) ∈A X C 由于x ∈B,y ∈D 所以 (x,y) ∈B X D 所以 (x,y) ∈（A X C ）∩（B X D ） 反过来，如果（x,y ）∈(A X C) ∩（B X D ） 由于 (x,y) ∈（A X C ）所以 x ∈A,y ∈C 由于 (x,y) ∈（B X D ）所以x ∈B,y ∈D 所以x ∈(A ∩B) y ∈(C ∩D) 所以 (x,y) ∈(A ∩B)X(C ∩D) 所以(A ∩B)X(C ∩D)= (A X C) ∩（B X D ） 1.5 解：Hasse 图 φφφφφφφφφ
极大元{9,24,10,7} 极小元{3,2,5,7} 最大元{24} 最小元{2} 1.6 解 (2)关系图为： (3)不存在最大元，最小元为{2} 1.7 解：(1)R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>} (2)略 (3)I A ?R 故R 是自反的。 <1,2>∈R <2,3>R 但是<1,3> ?R 故不满足传递性 1.8 解：(1) 不成立 A={1} B={2} C={3} D={4} 则左式={<1,3>，<1,4>,<2,3>,<2,4>} 右式={<1,3>,<2,4>} (2) 不成立 A={1,3} B={1} C={2,4} D={2} 则左式={<3,4>} 右式={<1,4>,<3,2>,<3,4>} (3) 不成立 A={1} B={2} C={3} D={4} 则左式={<1,3>,<1,4>,<2,3>,<2,4>} 右式={<1,3>,<2,4>} (4) 成立 证明：设
组合数学与图论复习题与参考答案
组合数学与图论复习题及答案 1．Show that if n+1 integers are chosen form the set {1,2, …,2n},then there are always two which differ by at most 2. 从{1,2, …,2n}中选出n+1个数，在这n+1个数中，一定存在两个数，其中一个整数能整除另外一个整数。 任何一个数都可以写成2k*L，其中k是非负数，L是正奇数。现在从1到2n 之间只有n个奇数。由于有n+1个数都能表示成2k*L，而L的取值只有n中，所以有鸽子洞原理知道，至少有两个数的L是一样的，于是对应k小的那个就可以整除k大的另一个数。 2．Show that for any given 52 integers there are exist two of them whose sum, or else difference, is divisible 100. 设52个整数a 1，a 2 ，…，a 52 被100除的余数分别是r 1 ,r 2 ,…,r 52 ，而任意一 个数被100除余数为0，1，2，…，99，一共100个。他们可以分为51个类{0},{1,99},{2,98},…,{49,51},{50}。将这51个集合视为鸽笼，则将 r 1,r 2 ,…,r 52 放入51个笼子中，至少有两个属于同一个笼子，所以要么有ri＝rj， 要么有ri＋rj＝100，也就是说ai－aj|100或者ai＋aj|100。 3．从1，2，3，…，2n中任选n+1个数，证明在这n+1个数中至少有一对数互质。 鸽子洞原理，必有两个数相邻，相邻的两个数互质 4．Prove that Ramsey number R(p,q)≤R(p,q-1)+R(p-1,q). 令N＝R(p,q-1)+R(p-1,q)，从N个人中中随意选取一个a，F表示与a相识的人，S表示与a不相识的人。 在剩下的R(p,q-1)+R(p-1,q)－2＋1个人中，由鸽子洞原理有，或者F中有R(p,q-1)人，或者S中有R(p-1,q)人。如果F中有R(p,q-1)人，则与a相识的人为p个；如果S中有R(p-1,q)人，则与a不相识的人有p个。所以有R(p,q)≤R(p,q-1)+R(p-1,q) 5．There are 10 people, either there are 3 each pair of whom are acquainted, or there are 4 each pair of whom are unacquainted。 从10人中随意选一个人p，F表示与p相识的人，S表示与p不相识的人若F中至少有4人，如果至少有4人不相识，则满足题设；如果有2人相识，则加上p有3人相识，也满足题设。 若F中至多有3人，则S中至少有6人，6人中至少有3人相识，或者不相识。如果相识则满足题设，如果不相识加上p不相识的人就有4个，也满足题设。6．In how many ways can six men and six ladies be seated at round table if the men and ladies to sit in alternate seats? 6个男的先进行圆排列，然后6个女的插入空位。 7．In how many ways can 15 people be seated at round table if B refuses to sit next to A? What if B only refuses to sit on A right?
离散数学图论练习题
图论练习题 一.选择题 1、设G是一个哈密尔顿图，则G一定是( )。 (1) 欧拉图(2) 树(3) 平面图(4)连通图 2、下面给出的集合中，哪一个是前缀码？() (1) {0，10，110，101111}(2) {01，001，000，1} (3) {b，c，aa，ab，aba}(4) {1，11，101，001，0011} 3、一个图的哈密尔顿路是一条通过图中()的路。 4、设G是一棵树，则G 的生成树有( )棵。 (1) 0(2) 1(3) 2(4) 不能确定 5、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。 6、一棵无向树的顶点数n与边数m关系是()。 7、一个图的欧拉回路是一条通过图中( )的回路。 8、有n个结点的树，其结点度数之和是()。 9、下面给出的集合中，哪一个不是前缀码( )。 (1) {a，ab，110，a1b11} (2) {01，001，000，1} (3) {1，2，00，01，0210} (4) {12，11，101，002，0011} 10、n个结点的有向完全图边数是( )，每个结点的度数是( )。 11、一个无向图有生成树的充分必要条件是( )。 12、设G是一棵树，n,m分别表示顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 13、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。 14、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。 15、设G是有n个结点m条边的连通平面图，且有k个面，则k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 16、设T是一棵树，则T是一个连通且( )图。 17、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 18、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12
1 《邓稼先》课后习题参考答案
1 《邓稼先》课后习题参考答案 思考探究 一、通读全文，把握文意，回答下列问题。 1.初读课文时，哪些句段最让你感动？反复细读后，再想想这些内容是否最 能体现全文所要表达的思想情感。 2.找出文中表现奥本海默与邓稼先两人不同个性、品质的词语及细节，思考 作者为什么要进行对比，通过对比得出了怎样的结论。 参考答案：1.作者饱含真情，于字里行间高度赞扬了邓稼先深沉的爱国主义精神和将个人生命奉献给祖国国防事业的崇高情怀。这样的句段很多，如：“对这一转变做出了巨大贡献的,有一位长期以来鲜为人知的科学家——邓稼先。”“一次井下突然有一个信号测不到了，大家十分焦虑，人们劝他回去，他只说了一句话：‘我不能走。’”…… 2.文中的奥本海默与邓稼先两人的个性、品质截然不同。奥本海默是 锋芒毕露，读研究生时就常打断别人的报告，即便到了中年，成了名人，有时还会这样。而邓稼先“是一个最不要引人注目的人物”“忠厚平实”“真诚坦白，从不骄人”“没有小心眼儿，一生喜欢‘纯’字所代表的品格”“最有中国农民的朴实气质”；“他没有私心，人们绝对相信他”，“文革”中能说服两派群众组织，能说服工宣队、军宣队。作者把奥本海默与邓稼先进行对比，鲜明地突出邓稼先的精神品质，自然而然地得出结论：“邓稼先是中国几千年传统文化孕育出来的有最高奉献精神的儿子”“邓稼先是中国共产党的理想党员”。 二、有感情地朗读课文第五部分，想一想：这部分开头引用《吊古战场文》， 有什么作用？结尾处又引用儿时学到的“‘五四’时代的一首歌”，表达了怎样的情感？ 参考答案：课文第五部分开头引用《吊古战场文》，把读者引入中国历史的深处，让人从中国传统文化的角度去思考。结尾处引用自己儿时学到的“‘五四’时代的一首歌”，说明了邓稼先就是一个典型的中国男儿，他有着为祖国而献身的崇高的精神品质。
图论与组合数学期末复习题含答案
组合数学部分 第1章 排列与组合 例1： 1)、求小于10000的含1的正整数的个数； 2、)求小于10000的含0的正整数的个数； 解：1)、小于10000的不含1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个 2)、“含0”和“含1”不可直接套用。0019含1但不含0。在组合的习题中有许多类似的隐含的规定，要特别留神。不含0的1位数有19个，2位数有29个，3位数有39个，4位数有49个 不含0小于10000的正整数有() ()73801919999954321=--=+++个含0小于10000的正整数9999－7380=2619个。 例2： 从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？ 解：将[1,300]分成3类： A={i|i ≡1(mod 3)}={1,4,7,…,298}, B={i|i ≡2(mod 3)}={2,5,8,…,299}, C={i|i ≡0(mod 3)}={3,6,9,…,300}. 要满足条件，有四种解法： 1)、3个数同属于A; 2)、3个数同属于B ； 3)、3个数同属于C; 4)、A,B,C 各取一数；故共有3C(100,3)+1003=485100+1000000=1485100。 例3：（Cayley 定理：过n 个有标志顶点的数的数目等于2-n n ） 1）、写出右图所对应的序列； 2）、写出序列22314所对应的序列； 解： 1）、按照叶子节点从小到大的顺序依次去掉节点（包含与此叶子 节点相连接的线），而与这个去掉的叶子节点相邻的另外一个点值则记入序列。如上图所示，先去掉最小的叶子节点②，与其相邻的点为⑤，然后去掉叶子节点③，与其相邻的点为①，直到只剩下两个节点相邻为止，则最终序列为51155.。 2）、首先依据给定序列写出（序列长度+2）个递增序列，即1234567，再将给出序列按从小到大顺序依次排列并插入递增序列得到：7。我们再将给出序列22314写在第一行，插入后的递增序列写在第二行。如下图第一行所示： ??→????? ??--②⑤67112223344522314??→???? ? ??--②⑥11223344672314 ??→????? ??--③②11233447314??→???? ? ??--①③11344714
习题参考解答(图论部分)
习题十 1. 设G 是一个(n ，m)简单图。证明：，等号成立当且仅当G 是完全图。 证明：（1）先证结论： 因为G 是简单图，所以G 的结点度上限 max(d(v)) ≤ n-1, G 图的总点度上限为 max(Σ(d(v)) ≤ n ﹒max(d(v)) ≤ n(n-1) 。根据握手定理，G 图边的上限为 max(m) ≤ n(n-1)/2,所以。 （2） =〉G 是完全图 因为G 具有上限边数，假设有结点的点度小于n-1,那么G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G 的每个结点的点度都为n-1，G 为完全图。 G 是完全图 =〉 因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G 的边数 。■ 2. 设G 是一个（n ，n +1）的无向图，证明G 中存在顶点u ，d （u ）≥3。 证明：反证法，假设,则G 的总点度上限为max(Σ(d(u)) ≤2 n ，根据握手定理，图边的上限为max(m) ≤ 2n/2=n 。与题设m = n+1，矛盾。因此，G 中存在顶点u ，d （u ）≥3。■ 3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5） 解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。 可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明： (6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5} 每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)
课后题答案
第七章 一、填空 1．柯尔伯格经长期研究，发现儿童和成人道德判断的发展经历三个水平：A〃前习俗-水平，B、习俗水平，c。后习俗水平，大多数少年的道德评价处于习俗--水平。 2．克拉斯沃尔等人提出的价值内化经历了五个阶段。它们是A〃----注意-，B〃—反应-，C〃----评价--，D〃---组织--，E〃--价值性格化--。 3．心理学认为态度和品德都包括：A。----认知-- ，B．----情感-，C。--行为三个成分。 4．态度与品德的区别在于；A．--态度的范围大于品德—，B〃价值内化程度不同--。 5．社会心理学家凯尔曼提出的态度改变需要经历的三个阶段为：A。--顺从--，B．------认同----，C。---内化---- 。 6．态度的功能有：A。----价值表现--，B。-------调节--和C。---过滤----。7．社会学习理论是由----班杜拉---提出来的，适合解释------社会--行为。8．费斯廷格提出的四种认知失调情境是：A．----逻辑不一致---，B。-----与社会风气不一致--，C。------与一贯行为不一致---，D。--与过去经验不一致---。 二、概念与原理的解释和运用 1．某些教科书把态度和品德分别安排在两章教授。这两个概念可能的关系 是：A c．态度是 一种比品德更稳定的心理品质；D．品德是态度形成与改变的条件。 2．让寝室里的同学共同讨论制订出寝室守则，这种方法是：A.说服 用群体规定;C.价值观辨析;D.角色扮演。 3．在一个好的集体里，差生的不良言行很少有市场；在一个不好的集体里， 好学生也会附和不良言行。这一现象的适当解释是A． 众；c老师的威信；D．认知失调。 4．甲孩子因偷吃东西，打破一只碗；乙孩子因帮妈妈洗碗，打破15只碗。 童；B．小学儿童；C．中学生；D．无法确定。 5．假如家长想用看电视作为强化物奖励儿童认真按时完成家庭作业的行为，最适合的安排是：A.让儿童看完电视后立即督促他们完成作业；B．规定每周看 电视的适当时间；c. 看电视。 6．国外有座收费的桥。当局规定，凡乘一人的车收税，乘两人以上的车可免收税，于是人们纷纷多人乘一辆车过桥。根据强化原理，这种行为最适当的解
2004图论复习题答案
图论复习题答案 一、 判断题，对打√，错打 1．无向完全图是正则图。( √ ) 2．零图是平凡图。( ) 3．连通图的补图是连通图. ( ) 4．非连通图的补图是非连通图。( ) 5．若连通无向简单图G中无圈，则每条边都是割边。( √ ) 6．若无向简单图G是（n，m）图，并且m=n-1，则G是树。( ) 7．任何树都至少有2片树叶。( ) 8．任何无向图G都至少有一个生成树。( ) 9．非平凡树是二分图。( √ ) 10．所有树叶的级均相同的二元树是完全二元树。( ) 11．任何一个位置二元树的树叶都对应唯一一个前缀码。( √ ) 12．3,3 K是欧拉图也是哈密顿图。( ) 13．二分图的对偶图是欧拉图。( ) 14．平面图的对偶图是连通图。( √ ) 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的强分图。 a b e 图1
解： （1） M=????????????????00010 1000000001 010******* M 2 =?? ?? ??? ? ??? ?????010******* 00010 1000001000 M 3=????????????????1000001000010000001010000 M 4=??????? ?????????0001001000100000100000010 由M 3可知，D 中长度等于3的通路有5条，长度等于3的回路有3条。 （2） I+M+M 2+M 3+M 4 =????????????? ???100000100000100 0001000001 +??????????? ?? ???000101000000001 010******* +??? ???? ? ??? ?? ???010000001000010 1000001000 + ????????????????1000001000010000001010000 +??? ?? ???????????0001001000100000100000010 = ??? ???? ? ????????21020 13010111110202011021 D 的可达性矩阵为 R=B （I+M+M 2+M 3+M 4 ）=??? ???? ? ????? ???110101********* 1101011011 （3）R T =????????????????11111 1111100100 1111100101 R×R T =??? ???? ? ??? ?????11010 11010 001001101000001 由矩阵R×R T 可知，该有向图的强分图有：{a}，{ b ，d ，e}， { c} a b e 图1