离散数学习题解答9汇总Word文件下载.docx
《离散数学习题解答9汇总Word文件下载.docx》由会员分享，可在线阅读，更多相关《离散数学习题解答9汇总Word文件下载.docx（23页珍藏版）》请在冰点文库上搜索。
可将立方体的一个顶点看作图的一个顶点，把立方体的棱看作图的边，那么该图的四个顶点都是三度的，因此不可能从一个顶点出发，遍历所有的边一次且仅一次，并且最终回到原顶点。
2、请设想一张图，它的64个顶点表示国际象棋棋盘的64个方格，顶点间的边表示:
在这两个顶点表示的方格之间可以进行“马步”的行走。
试指出其顶点有哪几类（依其度分类），每类各有多少个顶点。
解其顶点有5类：
二度顶点合计4个,三度顶点合计8个,四度顶点,合计20个,六度顶点,合计16个顶点,八度顶点,合计16个顶点。
2
3
4
6
8
3、（l）证明：
n个顶点的简单图中不会有多于
条边。
（2）n个顶点的有向完全图中恰有
证（l）n个顶点的简单完全图的边数总和为
（2）n个顶点的有向完全图的边数总和为
4、证明:
在任何n（n≥2）个顶点的简单图G中，至少有两个顶点具有相同的度。
证如果G有两个孤立顶点，那么它们便是具有相同的度的两个顶点。
如果G恰有一个孤立顶点，那么我们可对有n–1个顶点但没有孤立顶点的G’（它由G删除孤立顶点后得到）作下列讨论。
不妨设G没有孤立顶点，那么G的n个顶点的度数应是：
1，2，3，…，n–1这n–1种
可能之一，因此必定有两个顶点具有相同的度。
5、图8.10是一个迷宫,其中数字表示通道、和死胡同（包括目标）。
请用一个图来表示这个迷宫（用结点表示通道、和死胡同（包括目标））,用边表示它们之间的可直接到达关系。
图8.10
解
2118
317
4
5202116
15
6192214
713
8
9101112
6、在晚会上有n个人，他们各自与自己相识的人握一次手。
已知每人与别人握手的次数都是奇数，问n是奇数还是偶数。
解n是偶数。
用n个顶点表示n个人，顶点间的一条边表示一次握手，可构成一个无向图。
若n是奇数，那么该图的顶点度数之和为奇数（奇数个奇数的和），这是不可能的，因此n是偶数。
7、n个城市间有m条相互连接的直达公路。
证明：
当
时，人们便能通过这些公路在任何两个城市间旅行。
证用n个顶点表示n个城市，顶点间的边表示直达公路，据题意需证这n个城市的公路网络所构成的图G是连通的。
反设G不连通，那么可设G由两个不相关的子图（没有任何边关联分别在两个子图中的顶点）G1，G2组成，分别有n1，n2个顶点，从而，n=n1+n2，n1≥1，n2≥1。
由于各子图的边数不超过
（见练习8.l之3），因此G的边数m满足：
与已知
矛盾，故图G是连通的。
（本题是定理8.8的特例，当然也可以应用这一定理和它的证明方法来解题。
*8、
（1）证明：
序列（7，6，5，4，3，3,2），（6，5，5，4，3，2，2）以及（6，6，5，4，3，3，1）都不是简单图的度序列。
（2）若自然数序列（d1,d2,…,dn）满足d1>
d2>
…>
dn，那么当它为一简单图的度序列时必有
（a）
为偶数；
（b）对任一k，1≤k≤n,
≤k（k-1）+
。
证
（1）由于7个顶点的简单图中不可能有7度的顶点，因此序列（7，6，5，4，3，3,2）不是简单图的度序列。
序列（6，5，5，4，3，2，2）中有三个奇数，因此它不是简单图的度序列。
序列（6，6，5，4，3，3，1）中有两个6，若它是简单图的度序列，那么应有两个顶点是6度顶点，于是它们都要与其它所有顶点邻接，该图就不会有一度的顶点，与序列中末尾的1冲突。
故（6，6，5，4，3，3，1）也不是简单图的度序列。
证
（2）
为偶数是显然的。
考虑图中的k个顶点（k=1,2,…,n）,这k个顶点的生成子图的度数总和≤k（k-1），而其余n–k个顶点vk+1,vk+2,…,vn,可使v1,v2,…,vk增加的度数不会超过
因此我们有
9、画出图8.11中图的补图及它的一个生成子图。
图8.11
解补图生成子图
10、一个简单图，如果同构于它的补，则该图称为自补图。
（1）给出一个4个顶点的自补图。
（2）给出一个5个顶点的自补图。
（3）是否有3个顶点或6个顶点的自补图？
（4）证明一个自补图一定有4k或4k＋1个顶点（k为正整数）。
解
（1）4个顶点的自补图：
（2）5个顶点的自补图：
（3）没有。
（4）证设G为自补图，有n个顶点。
我们已知n个顶点的完全图有
条边，因此G应恰有
故或者n是4的整数倍，或者n–1是4的整数倍，即图G一定有4k或4k＋1个顶点（k为正整数）。
11、（l）证明图8.12中（a）与（b）同构。
A
DCB
EF
GH
IJ
（a）（b）
图8.12
（2）给出所有不同构的4个结点的简单图的图示。
（l）证在图（a）图（b）间建立双射h
v
A
B
D
I
J
C
E
G
H
F
h（v）
可逐一验证（不赘）
（u,v）E（a）当且仅当（h（u）,h（v））E（b）
（2）所有不同构的4个结点的简单图的图示有如下11个：
7.2路径、回路及连通性
练习7.2
1、证明定理8.5。
证设n个顶点的图G中，有从v到v的闭路径，表示为
（v,v1,v2,…,vk,v）
如果v,v1,v2,…,vk中没有相同顶点（因而不多于n个），那么它便是一条从v到v的长度不大于n的回路。
如果v,v1,v2,…,vk中有相同顶点vi=vj，例如
（v,v1,…,vi,…,vj,vj+1,…,vk,v）
那么删除vi到vj的闭路径，得到
（v,v1,…,vi,vj+1,…,vk,v）
仍然为从v到v的闭路径。
如此不断删除闭路径内相同顶点构成的闭路径，最终必可得到一条从v到v的长度不大
于n的回路。
2、证明：
在简单无向图G中，从结点u到结点v,如果既有奇数长度的通路又有偶数长
度的通路，那么G中必有一奇数长度的回路。
证设G中，从结点u到结点v的奇数长度的通路为O，偶数长度的通路为E。
对O和
E的除结点u和v的相交结点的数目归纳k。
k=0,那么O和E恰好构成G的奇数长度的回路。
设奇数长度的通路与偶数长度的通路的相交结点的数目少于k时，命题成立。
u12…kv
设图G中，从结点u到结点v的奇数长度的通路与偶数长度的通路有k个相交结点，如图所示：
考虑结点u到结点k,如果从结点u到结点k,既有奇数长度的通路又有偶数长度的通路，
那么据归纳假设，其中有一奇数长度的回路，因而G中必有一奇数长度的回路。
如果从结点u到结点k的两条通路均为偶数长度，或均为奇数长度，那么结点k到结点v必然既有奇数长度的通路又有偶数长度的通路，因而构成一奇数长度的回路。
3、证明：
若简单无向图G是不连通的，那么G¯
必定是连通的。
证设简单无向图G是不连通的，那么G由两个不相关的子图（没有任何边关联分别在
两个子图中的顶点）G1，G2组成，分别有顶点，u1,u2,…,uk和v1,v2,…,vl。
由于边
（ui,vj）均不在G中（i=1,2,…,k,j=1,2,…,l）
因此（ui,vj）全部在G¯
中，从而G¯
是连通的。
4、有向图可用于表示关系，图8.18表示的二元关系是传递的吗？
说说如何由有向图判定关系的传递性。
求图8.18表示的二元关系的传递闭包，说说构作有向图传递闭包的方法。
a
bc
图8.18
解图8.18表示的二元关系不是传递的。
有向图表示的关系是传递的，当且仅当对图中任意两个结点u,v，如果有从u到v的路径，则必有从u到v的边。
图8.18表示的二元关系的传递闭包如图8.18（b）所示。
构作有向图传递闭包的方法是：
对图中任意两个结点u,v，如果有从u到v的路径，则添加从u到v的边。
5、给出图8.19中有向图的强分图，单向分图和弱分图，作出它的凝聚图。
v1v2v7v10
v4v3v8v9
v5v6
图8.19
解图8.19中有向图的强分图有：
<
{v1,v2},{<
v1,v2>
v2,v1>
}>
{v3,v4,v5},{<
v3,v5>
v4,v3>
v4,v5>
v5,v4>
{v6},{<
v6,v6>
{v7,v8,v9},{<
v7,v8>
v8,v9>
v9,v7>
{v10},{}>
图8.19中有向图的单向分图有：
{v1,v2,v3,v4,v5,v6},{<
v1,v4>
v2,v3>
v3,v6>
{v7,v8,v9,v10},{<
v7,v10>
{v1,v2}
{v3,v4,v5}{v7,v8,v9}{v10}
{v6}
图8.19的凝聚图：
6、有7人a，b，c，d，e，f，g分别精通下列语言，问他们7人是否可以自由交谈（必要时借助他人作翻译）。
a精通英语。
b精通汉语和英语。
c精通英语、俄语和意大利语。
d精通日语和英语。
e精通德语和意大利语。
f精通法语、日语和俄语。
g精通法语和德语。
bd
c
eg
f
解下图中7个顶点表示7个人，关联两个顶点的边表示两个人同时精通某一种语言：
由于该图是连通的，因此他们7人是可以自由交谈（必要时借助他人作翻译）。
7、证明：
一个有向图是单向连通的，当且仅当它有一条经过每一结点的路径。
证充分性是显然的。
必要性：
设有向图G是单向连通的，P是G中的一条路径，起点为u1,终点为uk。
如下延长这一路径：
考虑路径外的任意顶点w,若
（1）有顶点w到u1的路径,则我们如愿。
（2）有顶点uk到w的路径,则我们如愿。
否则，由于有向图是单向连通的，
（3）有顶点w到uk的路径,和顶点uk-1到w的路径,则我们如愿。
w
（4）有顶点w到uk的路径,和顶点uk-2到w的路径,则我们如愿。
否则，
u1uk-2uk-1uk
…
（5）如此等等…，有顶点w到uk的路径,和顶点u1到w的路径,则我们如愿。
如上不断延长这一路径，直至产生一条经过每一结点的路径。
8、称d（u,v）为图G＝<
V,E,Ψ>
中结点u，v间的距离：
d称为图G的直径，如果d＝max{d（u,v）u,vV}。
试求图8.20中图的直径，χ（G）,λ（G）,δ（G），并指出一个点割集和一个边割集。
图8.20
解d＝3，χ（G）=3,λ（G）=3,δ（G）=3。
9、顶点v是简单连通图G的割点，当且仅当G中存在两个顶点v1，v2，使v1到v2的通路都经过顶点v。
试证明之。
证充分性是显然的。
设顶点v是简单连通图G的割点，如果不存在两个顶点v1，v2，使v1到v2的通路都经过顶点v，那么对任意两个顶点v1，v2，都有一条通路不经过顶点v，因而删除顶点v不能使G不连通，与v是简单连通图G的割点矛盾。
故G中必存在两个顶点v1，v2，使v1到v2的通路都经过顶点v。
10、边e是简单连通图G的割边，当且仅当e不在G的任一回路上。
证设e是简单连通图G的割边，其端点为u,v。
删除边e后，u,v应在两个不同的连通分支中。
若e在G的一条回路上，那么删除边e后，u,v应仍在一条通路上，矛盾。
故e不在G的任一回路上。
反之，设e不在G的任一回路上，而e不是简单连通图G的割边。
那么G-{e}仍是连通的，故还有u到v的一条通路，从而这条通路连同边e构成G中的一条回路，矛盾。
因此边e是简单连通图G的割边
11、试用有向图描述下列问题的解：
某人m带一条狗d，一只猫c和一只兔子r过河。
m每次游过河时只能带一只动物，而没人管理时，狗与兔子不能共处，猫和兔子也不能共处。
问m怎样把三个动物带过河去？
（提示：
用结点代表状态，状态用序偶<
S1，S2>
来表示，这里S1，S2分别是左岸和右岸的人及动物集合，例如初始状态为<
{m,d,c,r},>
解描述上述问题的有向图如下：
{d,r},{m,c}>
<
{c},{m,d,r}>
{m,c,r},{d}>
{r},{m,c,d}>
{m,d,c,r},>
{d,c},{m,r}>
{m,d,c},{r}>
{m,r},{c,d}>
{m,d,c,r}>
{d},{m,c,r}>
{m,d,r},{c}>
{r},{m,c,d}>
{c,r},{m,d}>
12、有向图可以刻划一个系统的状态转换，例如用图8.21中的有向图可以描述识别01010序列的状态转换系统。
其中S为初始状态，在此读入序列，然后依序列中符号转入后续状态（读到0进入S1，读到1进入S2，如此等等）。
S4表示读完序列01010应进入的最后状态，S5表示读完一个非01010序列应进入的最后状态。
试自行构作识别序列01（10）10的有向图刻划的状态转换系统。
0
S0S11S21S30S4
101
S5
（上文中w表示空字或重复任意多次w所得的字。
图8.21
S3
01
SS1S2S4S5
0110
S6
解识别序列01（10）10的有向图刻划的状态转换系统如下：
7.3欧拉图与哈密顿图为一。
练习7.3
1、试作出四个图的图示，使第一个既为欧拉图又为哈密顿图；
第二个是欧拉图而非哈密顿图；
第三个是哈密顿图却非欧拉图；
第四个既非欧拉图也非哈密顿图。
解（a）既为欧拉图又为哈密顿图；
（b）是欧拉图而非哈密顿图；
（c）是哈密顿图却非欧拉图；
（d）既非欧拉图也非哈密顿图。
（a）（b）（c）（d）
2、像第一题要求的那样对欧拉路径和哈密顿通路作出四个图。
解（a）既有欧拉路径又有哈密顿通路；
（b）有欧拉路径而无哈密顿通路；
（c）有哈密顿通路却无欧拉路径；
（d）既无欧拉路径也无哈密顿通路。
3、问n为何种数值时，Kn既是欧拉图又是哈密顿图。
问k为何值时，k-正则图既是欧拉图又是哈密顿图。
解n为奇数时，Kn既是欧拉图又是哈密顿图。
k为大于或等于n/2的偶数时，k-正则图既是欧拉图又是哈密顿图。
4、证明：
恰有两个奇数度顶点u,v的无向图G是连通的,当且仅当在G上添加边（u，v）后所得的图G*是连通的。
证必要性是显然的。
设G*是恰有两个奇数度顶点u,v的无向图G添加边（u，v）后所得，且是连通的,那么图G*是一个欧拉图（每一个顶点都是偶数度的连通图），因此G*中删除边（u，v）后所得的图G仍是连通的。
5、参阅练习8.1第2题。
问马可否从某处出发完成所有可能的跳步一次且仅一次后回到原地。
解练习8.1第2题中的图不是欧拉图（它有三个3度的顶点），因此马不可能从某处出发完成所有可能的跳步一次且仅一次后回到原地。
6、参阅练习8.1第2题。
问马可否从某处出发跳遍棋盘的所有方格一次且仅一次后回到原地。
解马可以从某处出发跳遍棋盘的所有方格一次且仅一次后回到原地。
具体跳步如下图所示:
幻方中数字n表示第n个跳步的起点。
下图则表示跳步的图示。
50
11
24
63
14
37
26
35
23
62
51
12
25
34
15
38
10
49
64
21
40
13
36
27
61
22
9
52
33
28
39
16
48
7
60
1
20
41
54
29
59
45
53
32
17
42
47
57
44
19
30
55
58
5
46
31
56
43
18
幻方
ｏ
7、试计算Kn（n≥3）中不同的哈密顿回路共有多少条。
解不同的哈密顿回路共有
条。
可以用依次选取每一条边来生成哈密顿回路。
因为组成回路的第一条边的选择可能是n种,组成回路的第二条边的选择可能是n–1种,…,组成回路的第n–1条边的选择可能是2种，组成回路的第n条边的选择可能是1种，而每一哈密顿回路由此生成两次，因此不同的哈密顿回路共有
8、十一个学生在一张圆桌旁共进晚餐，要求在每次晚餐上每个学生的邻座都与其它各次晚餐的邻座不同。
问这样共进晚餐能安排多少次。
解每次晚餐上每个学生的邻座都与其它各次晚餐的邻座不同的安排方式有
种（根据定理8.15。
9、判别图8.31中各图是否为哈密顿图，若不是，请说明理由，并回答它是否有哈密顿通路。
（a）（b）（c）
图8.31
解（a），（b）是为哈密顿图。
（c）不是哈密顿图，也没有哈密顿通路。
在图（c）中增加顶点k，并对其顶点做二着色，构成图（d）（如下）。
图（d）不是哈密顿图，也没有哈密顿通路。
因为图中白色顶点比黑色顶点多两个。
故（c）不是哈密顿图，也没有哈密顿通路。
否则它的哈密顿回路或哈密顿通路必定经过顶点k（k在两个二度顶点之间的边上），从而图（d）也是哈密顿图，也有哈密顿通路，矛盾。
（d）
10、证明：
对哈密顿图G=<
V，E，Ψ>
删除S（V）中的所有顶点后，所得图G’的连通分支数不大于S。
证设G1是G中的哈密顿回路，显然在G1中删除S（V）中的所有顶点后，所得图G1’的连通分支数k1，不小于在G中删除S（V）中的所有顶点后，所得图G’的连通分支数k，即k≤k1。
由于G1是一条回路，在G1中删除S（V）中的所有顶点后，所得图G1’的连通分支数k1不大于S是显然的，即k1≤S。
因此
k≤k1≤S
11、设G为（n，m）图。
如果
，那么G为哈密顿图（提示：
运用定理8.14）。
证设G中有两个顶点v1和v2的度数之和不大于n–1，那么以v1和v2为端点的边不多于n–1条。
而其余顶点之间的边的数目不多于
故G的总边数m满足
与
矛盾，故G中任意两个顶点的度数之和大于n。
根据定理8.14，G为哈密顿图。
12、设有n个围成一圈跳舞的孩子，每个孩子都至少与其中
个是朋友。
试证明，总
可安排得使每个孩子的两边都是他的朋友。
证设n个孩子为n个顶点，用边表示顶点间的朋友关系构成一个图G。
由于每个孩子都至少与其中
个是朋友，因此G的每一顶点的度数至少是
，从而G的任何两个顶点的度数之和至少是
即G有哈密顿回路，这表明，总可安排n个孩子围成一圈跳舞，使每个孩子的两边都是他的朋
7.4图的矩阵表示
习题解答
v1
e1v4e3
e4
v5
v2e2v3
图8.35
练习7.4
1、对图8.35给出的无向图G:
（1）计算其关联矩阵A（G）。
（2）计算A（G）的秩，验证定理8.17。
解
（1）其关联矩阵A（G）为
（2）由于子行列式
非零，因此，A（G）的秩为3=n–k=5–2。
2、对图8.36给出的有向图G:
（1）计算它的邻接矩阵A及A2，A3，A4，说出从v1到v4的长度为l，2，3，4的拟路径各有多少条。
（2）计算A○Aι，Aι○A，说出它们中第2，3分量及第4，4分量的意义。
（3）计算它的路径矩阵B及可达性矩阵P，并从P说出G的各强分图。
v1v2v3
v4v5
图8.36
解
（1）它的邻接矩阵A=
v1到v4的长度为1的拟路径各有1条。
A2=
v1到v4的长度为2的拟路径各有1条。
A3=
v1到v4的长度为3的拟路径各有1条。
A4=
v1到v4的长度为4
升级会员 