给远方小朋友一封信-人力资源实习报告

离散数学习题解答-（)

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


ﻩ

第七章 图
7.1 图的基本知识


定义８.8 设图G＝
(１）Ｇ－e表示对G作删除边e的运算，Ｇ－e = <Ｖ,E’，Ψ’ >，其中E’＝Ｅ｛ｅ｝-,Ψ’=
Ψ
E
’
。
（2）G-v表示对G作删除顶点v的运算，G－ｖ = ，其中V’= V-{v}，E’
＝E-{e  e以v为端点}，Ψ’＝Ψ
E
’
。
（３）边e切割运算。设Ｇ中Ψ (e) = (u,v)，对G作边ｅ切割得G’＝<Ｖ’，E’，Ψ’ >，
其中，Ｖ’＝V{v’｝,E’= (E-｛e}）{e１,ｅ2}， Ψ’= （Ψ-{}){＞,}
(４)顶点v贯通运算。设Ｇ中顶点ｖ恰为边e1,ｅ２的端点,且Ψ (e1) ＝ (u,v)，Ψ （e2) =
（ｗ，v)。对G作顶点ｖ贯通得G’=,其中V’= V-｛ｖ}, Ｅ’＝ (E－｛e1,
ｅ2｝){e}, Ψ’=( Ψ－{<ｅ1,(u,v)>，}。
切割与贯通是互逆的,两者常被称为同胚运算。
定义8.９ 设G1＝,Ｇ2=为两个图，称Ｇ1与G２同构
(isomorphic),如果存在双 射ｆ:Ｖ1→V2,双射g：E1→Ｅ２，使得对每一边ｅＥ1,
Ψ1(ｅ)＝(u,ｖ）（或)当且仅当Ψ2（g(e)) = (f(u），f(v))(或＜ f（u)，ｆ(v)>)
当限于讨论简单图时,可以用顶点的偶对表示边,即当Ψ(e) ＝(ｕ,v)时，边e用(u,v)来表示。
这时两图同构的条件可以简化为
(u,v)Ｅ1当且仅当(ｆ（u),ｆ（v))E２

习题解答
练习7．1
1、 想一想,一只昆虫是否可能从立方体的一个顶点出发， 沿着棱爬行、它爬行过每条梭
一次且仅一次,并且最终回到原地?为什么？
解 不可能。可将 立方体的一个顶点看作图的一个顶点,把立方体的棱看作图的边,那么该
图的四个顶点都是三度的，因此 不可能从一个顶点出发,遍历所有的边一次且仅一次，并
且最终回到原顶点。

2、 请设想一张图，它的64个顶点表示国际象棋棋盘的64个方格,顶点间的边表示:在这
两个顶点表示的 方格之间可以进行“马步”的行走。试指出其顶点有哪几类(依其度
分类),每类各有多少个顶点。
解 其顶点有5类:二度顶点合计4个，三度顶点合计8个,四度顶点,合计20个,六度顶点，
合计16个顶点，八度顶点, 合计1６个顶点。

2 3
3 4
4 6
4 6
４ 6
4
6
8
8
8
4 4
6 6
８ 8
8 8
8 8
4
6
8
8
8
3 2
4 3
６ 4
6 4
6 4

4 ６ 8 8 8 8 6 ４
3 4 ６ 6 ６ 6 ４ 3
2 3 4 4 4 4 3 2

3、（ｌ)证明:ｎ个顶点的简单图中不会有多于
(2）n个顶点的有向完全图中恰有
n
条边。
证(l）n个顶点的简单完全图的边数总和为

(n1)(n2)21
(２）n个顶点的有向完全图的边数总和为
2
n(n1)
条边。
2
n(n1)

2
nnnnnnn
2


４、证明： 在任何n （n≥２）个顶点的简单图G中，至少有两个顶点具有相同的度。
证 如果Ｇ有两个孤立顶点，那么它们便是具有相同的度的两个顶点。
如果G恰有一个孤立顶点，那么我们可对有n – 1 个顶点但没有孤立顶点的G’(它由G
删除孤立顶点后得到)作下列讨论。
不妨设G没有孤立顶点,那么G 的n个顶点的度数应是:1，2，3,…，n–１ 这n–１种
可能之一，因此必定有两个顶点具有相同的度。

５、图8．10是一个迷宫,其中数字表示通道、和死胡同(包括目标) 。请用一个图来表示
这个迷宫(用结点表示通道、和死胡同(包括目标)),用边表示它们之间的可直接到达关系。

图8．10
解


















6、在晚会上有n个人,他们各自与自己相识的人握一次手。已知每人与别人握手的次 数
都是奇数，问n是奇数还是偶数。为什么？
解 ｎ是偶数。用ｎ个顶点表示ｎ个人， 顶点间的一条边表示一次握手，可构成一个无
向图。若n是奇数,那么该图的顶点度数之和为奇数（奇数 个奇数的和）,这是不可能的，因此
ｎ是偶数。
2 1 18
17 3
4

5 20

21 16
7、n个城市间有m条相互连接的直达公路。证明：当
m
(n1)(n2 )
时，人们便能
2
通过这些公路在任何两个城市间旅行。
证 用n个顶点表 示n个城市,顶点间的边表示直达公路，据题意需证这n个城市的公路
网络所构成的图G是连通的。反设 G不连通,那么可设G由两个不相关的子图(没有任何边关
联分别在两个子图中的顶点)G1,Ｇ2组成 ，分别有n
1
,n
2
个顶点，从而,n = n
1
+ｎ
2
,n
1

≥1，n
２

≥
1。
由于各子图的边数不超过
n
i
(n
i
1)
(见练习８．l之3)，因此G的边数m满足：
2
1
k
1

m

n
i
(n
i
1)(n
1
(n
1
1)n
2
(n
2
1))

2
i1
2


1
((n1)(n
1
1)(n1)(n
2
1))

2

1
(n1)(n
1
n
2
2)
2

1
(n1)(n2)
2

与已知
m
( n1)(n2)
矛盾，故图G是连通的。
2
（本题是定理8.8的特例，当然也可以应用这一定理和它的证明方法来解题。）

*8、(1）证明：序列(7，6,5，４,3,３， ２),（6,5,5，4,3，2，２）以及(6,6，５，4，
3,3，1）都不是简单图的度序列。
（2）若自然数序列（d
１
,d
２
,…,d
n）满足d
1
>d
2
>…＞ｄ
n
，那么当它为一简单图的 度序列
时必有
（a）

d
i1
n
i
为偶数;
(b)对任一k，1≤k≤ｎ ,

d
i1
k
i
≤ k（k-1）＋
ik1

min(k,d)
。
i
n< br>证(1)由于7个顶点的简单图中不可能有7度的顶点，因此序列（７，6，5,4，3,3， 2）不是简单图的度序列。序列(６,5，5,4，３，2，2)中有三个奇数,因此它不是简单图的度序列。< br>序列(6,6,5，４,3，3，1）中有两个6,若它是简单图的度序列,那么应有两个顶点是6度顶点 ,
于是它们都要与其它所有顶点邻接，该图就不会有一度的顶点,与序列中末尾的1冲突。故（6，6,5,4,３,3,１)也不是简单图的度序列。
证(２)

d
i1
n
i
为偶数是显然的。
考虑图中的k个顶点（ｋ=1,２,…,n)，这k个顶点的生成子图的度数总和 ≤ k（k-１),
而其余n–k 个顶点v
ｋ+1
,ｖ
k+2
, …,v
ｎ
, 可使 v
1
,v
2
, …,ｖ
ｋ
增加的度数不会超过

ik1
k
n

min(k,d)

i
n
因此我们有

d
i1
i
≤ ｋ（k－1)＋
ik1

min(k,d)
。
i
9、画出图８．1１中图的补图及它的一个生成子图。







图８.11

解 补图 生成子图

1０、一个简单图,如果同构于它的补，则该图称为自补图。
(１）给出一个4个顶点的自补图。
(2)给出一个5个顶点的自补图。
(3）是否有3个顶点或６个顶点的自补图?
（４）证明一个自补图一定有4k或4k＋1个顶点（k为正整数)。
解 (1)4个顶点的自补图： （2）５个顶点的自补图：






(3)没有。
（4)证 设Ｇ为自补图,有ｎ 个顶点。我们已知n 个顶点的完全图有
因此Ｇ应恰有
n(n1)
条边，
2
n(n1)
条边。故或者n是4的整数倍,或者n–１是４的整数倍，即图G 一定
4
有４k或4k+1个顶点（k为正整数）。

1１、(l)证明图 ８.12中(a）与（b）同构。








(a） (b)
图8.1２
(2)给出所有不同构的4个结点的简单图的图示。
(l）证 在图（a)图(ｂ)间建立双射h
A
 

D C B
v
ｈ(v)
A Ｂ D Ｉ J Ｃ E Ｇ

H

F
       
可逐一验证 （不赘)
(u,v)E（a)当且仅当 (h(u),h（v))E(b)
（2)所有不同构的4个结点的简单图的图示有如下１１个：

7.2 路径、回路及连通性

练习7．2

习题解答
1、 证明定理8．５。
证 设n个顶点的图G中,有从v到v的闭路径,表示为
(ｖ,v
1
,v
2
,…,v
k
,v)
如果ｖ,ｖ
1
,v
2
, …,ｖ
k
中没有相同顶点 (因而不多于n个),那么它便是一条从v到v的长度不大
于ｎ的回路。如果v,v
1
，ｖ
2
， …,v
k
中有相同顶点v
i
＝v
j
，例如
(v,v
1
，…， v
ｉ
,…, v
j
, v
j
＋
1
，…,v
k
,ｖ)
那么删除ｖ
i
到ｖ
ｊ
的闭路径,得到
（v,v
1
,…, v
ｉ
, ｖ
j
＋
1
,…,ｖ
k
,ｖ）
仍然为从v到v的闭路径。
如此不断删除闭路径内相同顶点构成的闭路径,最终必可得到一条从ｖ到v的长度不大
于n的回路。

2、 证明:在简单无向图G中，从结点u到结点v,如果既有奇数长度的通路又有偶数长
度的通路，那么Ｇ中必有一奇数长度的回路。
证 设G中,从结点u到结点v的奇数长度的通路为O ,偶数长度的通路为E。对O和
E的除结点u和v的相交结点的数目归纳ｋ。
k＝０,那么Ｏ和E恰好构成G的奇数长度的回路。
设奇数长度的通路与偶数长度的通路的相交结点的数目少于k时，命题成立。
设图Ｇ中，从结点u到结点v的奇数长度的通路与偶数长度的通路有k个相交结点，如
图所示:




考虑结点u到结点ｋ,如果从结点u到结点ｋ,既有奇数长度的通路又有偶数长度的通路，
那 么据归纳假设,其中有一奇数长度的回路,因而G中必有一奇数长度的回路。如果从结点u
到结点k的两 条通路均为偶数长度，或均为奇数长度，那么结点ｋ到结点v必然既有奇数长
度的通路又有偶数长度的通 路，因而构成一奇数长度的回路。

3、 证明：若简单无向图G是不连通的,那么G¯必定是连通的。
证 设简单无向图G是不连通的,那么G由两个不相关的子图(没有任何边关联分别在
两个子图中的顶点) G1,G2组成，分别有顶点，u
1
，u
２
，…,ｕ
ｋ
和v
1
，v
2
,…,v
l
。由于边
u 1
2 … k

（u
i
,v
j
）均不在Ｇ中(i=１，2,…,ｋ, j＝1,2,…，
ｌ
)
因此（u
i
,ｖ
j
)全部在G¯中,从而G¯是连通的。

4、有向图可用于表示关系，图８.18表示的二元关系是传递的吗?说说如何由有 向图判
定关系的传递性。求图8.18表示的二元关系的传递闭包,说说构作有向图传递闭包的方法。









图8.１8
解 图8.18表示的二元关系不是传递的。有向图表示的关系是传递的,当且仅当对图中
任意两个结点u,v,如果有从u到ｖ的路径，则必有从ｕ到v的边。
图8.18表 示的二元关系的传递闭包如图8．１8（b)所示。构作有向图传递闭包的方法是：
对图中任意两个结点 ｕ，v,如果有从u到v的路径,则添加从u到ｖ的边。

5、给出图8.19中有向图的强分图,单向分图和弱分图，作出它的凝聚图。


1 2


7 10






图８.19
解 图8.１9中有向图的强分图有:
<{ｖ
1
,v
2
}，{1
,v
２
>,＜v
2
,v
1
>}> ,
<{v
3
,v
4
,ｖ
5
} ,{３
,v
5
>,４
,v
3
＞， <ｖ
4
，v
5
>,＜ｖ
５
，ｖ
4
＞}>,
<{ｖ
6
},{6
,v
6
>}＞ ,
＜{ｖ
7
，ｖ
8
,v
９
｝,{７
, ｖ
8
>,8
,ｖ
９
>,９
，v< br>7
>}＞,
<｛v
1０
},{｝＞
图8.19中有向图的单向分图有：
＜{v
１
，v
2
,v
３
，v
4
，v
5
,v
6
｝,｛<ｖ
1
,v
2
＞,<ｖ
2
,ｖ
1
>,1
,v
４
>,<ｖ
2
,v
3
>，4，v
3
>,＜v
3
,v
5
＞,＜v
4
,v
5
>，<ｖ
5
，v
4
>，３
,ｖ
6
>}> ,
<{v
7
,v
8
,ｖ
9< br>，v
１0
},{<ｖ
7
,v
８
>,８< br>,v
9
>,9
,ｖ
7
>,＜ｖ
７
，v
10
>｝>
图8．19的凝聚图:

12


a
a






vv
v v
{v,v}


{v
3
,v
4
,v
5
} {v
7
,v
8
,v
9
}

6、有7人ａ,b，c,ｄ，e，f,g分别精通下列语言, 问他们7人是否可以自由交谈(必要时
借助他人作翻译)。
a 精通英语。
ｂ 精通汉语和英语。
c 精通英语、俄语和意大利语。
d 精通日语和英语。
e 精通德语和意大利语。
f 精通法语、日语和俄语。
g 精通法语和德语。
解 下图中7个顶点表示7个人，关联两个顶点的边表示两个人同时精通某一种语言:








由于该图是连通的，因此他们7人是可以自由交谈(必要时借助他人作翻译）。

7、证明:一个有向图是单向连通的,当且仅当它有一条经过每一结点的路径。
证 充分性是显然的。
必要性:设有向图G是单向连通的,Ｐ是Ｇ中的一条路径,起点为u
1,终点为u
ｋ
。如下延长
这一路径:
考虑路径外的任意顶点w，若
（1)有顶点ｗ到u
1
的路径,则我们如愿。
（2）有顶点u
k
到ｗ的路径,则我们如愿。否则,由于有向图是单向连通的, （3）有顶点w到ｕ
k
的路径,和顶点u
k-
１
到w的路径， 则我们如愿。否则，由于有向图
是单向连通的，




（4)有顶点ｗ到u
k
的路径,和顶点ｕ
k-2
到ｗ的路径， 则我们如愿。否则，



1 k-2 k-1 k



（ 5)如此等等…,有顶点ｗ到ｕ
k
的路径,和顶点u
1
到w的路径, 则我们如愿。
a

b
d

u
u
w
u u
…
u
w

1 k-2 k-1
如上不断延长这一路径，直至产生一条经过每一结点的路径。


８、称ｄ(u,v）为图G=<Ｖ, Ｅ， Ψ>中结点u,ｖ间的距离：
uu u
…
u
k
w
当uv

0


d(u,v)

当u到v不可达


u,v间最短路径 长度否则

d称为图G的直径，如果d＝maｘ｛d(u,v)  u,vV}。试求图8.20中图的直径，χ(G) ,λ
（G） ,δ(G),并指出一个点割集和一个边割集。










图8．20

解 d＝3 ,χ(G)=３ ,λ(G)=３ ，δ(G)=3 。

9、顶点ｖ是简单连通图G的割点，当且仅当G中存在两个顶点v1， v2,使v1到v2的通
路都经过顶点v 。试证明之。
证充分性是显然的。
必要 性:设顶点v是简单连通图Ｇ的割点，如果不存在两个顶点ｖ1，ｖ2,使v1到v2的
通路都经过顶点 v,那么对任意两个顶点v1，ｖ2，都有一条通路不经过顶点ｖ,因而删除顶点
v不能使G不连通,与 ｖ是简单连通图G的割点矛盾。故G中必存在两个顶点v1，v2，使v1
到v2的通路都经过顶点ｖ 。

10、边e是简单连通图G的割边，当且仅当e不在G的任一回路上。试证明之。
证 设e是简单连通图G的割边，其端点为ｕ,v 。删除边e后，u,ｖ应在两个不同的连
通 分支中。若e在Ｇ的一条回路上，那么删除边e后，u,v应仍在一条通路上,矛盾。故e不
在Ｇ的任一 回路上。
反之，设e不在G的任一回路上,而e不是简单连通图Ｇ的割边。那么G－{ｅ}仍是连通< br>的,故还有u到v的一条通路,从而这条通路连同边e构成G中的一条回路，矛盾。因此边ｅ
是简 单连通图G的割边

11、试用有向图描述下列问题的解：
某人 m带一条狗d,一只猫c和一只兔子r过河。m每次游过河时只能带一只动物，而
没人管理时，狗与兔子 不能共处,猫和兔子也不能共处。问ｍ怎样把三个动物带过河去？

(提示：用结点代表 状态，状态用序偶的人及动物集合,例如初始 状态为< {ｍ,d，c,r} ,  >。
解 描述上述问题的有向图如下：












12、有向图可以刻划一个系统的状态转 换，例如用图8．21中的有向图可以描述识别
01０

10序列的状态转换系统。其 中Ｓ为初始状态,在此读入序列，然后依序列中符号转入后
续状态(读到0进入Ｓ１，读到１进入S2, 如此等等)。S４表示读完序列010

１0应进入的最
后状态，Ｓ5表示读完一个非 01０

10序列应进入的最后状态。
试自行构作识别序列0１(10)

１0的有向图刻划的状态转换系统。
（上文中w

表示空字或重复任意多次w所得的字。)







图8.2１
解 识别序列01（１０)

1０的有向图刻划的状态转换系统如下:











<{d,r} , {m,c}>

<{c},{m,d,r}><
{m,c,r},{d} ><{r},{m,c,d}>

0

S 0 S1 1 S2
1 S3 0 S4
S3

0
1
S S1 S2
7．3欧拉图与哈密顿图
为一。

习题解答
练习7. 3
1、试作出四个图的图示,使第一个既为欧拉图又为哈密顿图；第二个是欧拉图 而非哈密
顿图；第三个是哈密顿图却非欧拉图；第四个既非欧拉图也非哈密顿图。
解（a）既 为欧拉图又为哈密顿图；（b）是欧拉图而非哈密顿图;(c）是哈密顿图却非欧
拉图;(d）既非欧拉 图也非哈密顿图。






2、像第一题要求的那样对欧拉路径和哈密顿通路作出四个图。
解(ａ）既有欧拉路径又有哈 密顿通路;（b)有欧拉路径而无哈密顿通路;(c)有哈密顿通路
却无欧拉路径;（d)既无欧拉路径 也无哈密顿通路。






3、问n为何种 数值时,K
n
既是欧拉图又是哈密顿图。问k为何值时,k-正则图既是欧拉图
又是哈 密顿图。
解 n为奇数时,Ｋ
n
既是欧拉图又是哈密顿图。k为大于或等于ｎ２的偶 数时，k－正则
图既是欧拉图又是哈密顿图。

４、证明：恰有两个奇数度顶点ｕ， v的无向图G是连通的，当且仅当在Ｇ上添加边（ｕ,v)
后所得的图Ｇ*是连通的。
证 必要性是显然的。
设G＊是恰有两个奇数度顶点ｕ，v的无向图G添加边（u，ｖ）后所得，且是连通 的,
那么图G*是一个欧拉图（每一个顶点都是偶数度的连通图),因此G*中删除边（ｕ,v)后所得
的图G仍是连通的。

5、参阅练习8.１第2题。问马可否从某处出发完成所有可 能的跳步一次且仅一次后回
到原地。
解 练习8.1第２题中的图不是欧拉图(它有三个3度 的顶点），因此马不可能从某处出发
完成所有可能的跳步一次且仅一次后回到原地。

6、参阅练习８．1第2题。问马可否从某处出发跳遍棋盘的所有方格一次且仅一次后回
到原地。
解 马可以从某处出发跳遍棋盘的所有方格一次且仅一次后回到原地。具体跳步如下图
所示：
幻方中数字n表示第n个跳步的起点。下图则表示跳步的图示。

５ 26 35
23 62 51 １
2
1
25 313
４ ５ ８
36 2
７
39 １
6
29
4
２
５
5
１
8

ｏ
ｏ
ｏ
ｏ
o
o
o
o


7、试计算K
n
(n≥３）中不同的哈密顿回路共有多少条。
解 不同的哈密顿回路共有
ｏ
o
ｏ
ｏ
o
ｏ
o
ｏ
o
o
o
o
o
o
o
o
ｏ
ｏ
ｏ
ｏ
ｏ
ｏ
o
ｏ
ｏ
o
ｏ
ｏ
ｏ
ｏ
o
o
o
o
ｏ
o
ｏ
o
ｏ
ｏ
o
o
o
ｏ
ｏ
o
ｏ
o
ｏ
ｏ
ｏ
o
o
ｏ
o
o
622 9
１
52 33 ２
8
48 ７ 60 1
54
９
6
3
45 8
５
7
20 41 ５
4
５32 １
３ 7
44 19 ３
0
５
6
４
3
４2
７
58 ５ 46 ３
1
幻方
(n1)!
条。可以用依次选取每一条边来生成哈密顿回路。因
2
为 组成回路的第一条边的选择可能是n 种， 组成回路的第二条边的选择可能是ｎ – １
种， … ， 组成回路的第n – 1条边的选择可能是２种,组成回路的第n 条边的选择可
能是１种，而每一 哈密顿回路由此生成两次，因此不同的哈密顿回路共有
(n1)!
条。
2

8、十一个学生在一张圆桌旁共进晚餐,要求在每次晚餐上每个学生的邻座都与其它各次
晚餐的 邻座不同。问这样共进晚餐能安排多少次。
解 每次晚餐上每个学生的邻座都与其它各次晚餐的邻座不 同的安排方式有
n1
种(根
2

据定理8.1５。)

９、判别图8.3１中各图是否为哈密顿图,若不是,请说明理由,并回答它是否有哈密顿通
路。








图8.３１

解(a)，（ｂ) 是为哈密顿图。（ｃ) 不是哈密顿图，也没有哈密顿通路。在图(c)中增加顶
点ｋ ，并对其顶点做二着色，构成图（d)(如下）。图(d) 不是哈密顿图，也没有哈密顿通路。
因为图中白色顶点比黑色顶点多两个。故(c) 不是哈密顿图，也 没有哈密顿通路。否则它的
哈密顿回路或哈密顿通路必定经过顶点k(ｋ在两个二度顶点之间的边上）, 从而图(d) 也是哈
密顿图,也有哈密顿通路，矛盾。










10、证明:对哈密顿图G = 删除S（V)中的所有顶点后,所得图G’的连通分
支数不大于 S 。
证 设G1是Ｇ中的哈密顿回路，显然在Ｇ１中删除Ｓ(V）中的所有顶点后,所得图G1’
的连通分支数k1,不小于在G中删除S（V）中的所有顶点后，所得图G’的连通分支数k,
即ｋ≤ k1。
由于G１是一条回路，在Ｇ1中删除S(V)中的所有顶点后,所得图G1’的连通分支数k 1
不大于 Ｓ 是显然的,即k１≤ S 。因此













k≤k1≤ Ｓ 
2
11、设G为(ｎ,m）图。证明：如果
mC
n1
2
， 那么G为哈密顿图（提示:运用定理
8.14）。
证 设G中有两个顶点ｖ1和v2的度数之和不大于ｎ – １ ,那么以v１和v２为端点
的边不多于n – １条。而其余顶点之间的边的数目不多于
(n2)(n3)
条。故G的总边数
2

m满足
1
mn1(n2)(n3)
2
1
(2n2n
2
5n6)
2
1
(n
2
3n4)

2
1
(n 1)(n2)1
2
2
C
n1
1
2
与< br>mC
n1
2
矛盾,故G中任意两个顶点的度数之和大于n 。根据定理８.14，G为哈密顿
图。

12、设有ｎ个围成一圈跳舞的孩子，每个孩子都至少与其中
n
个是朋友。试证明,总
2
可安排得使每个孩子的两边都是他的朋友。
证 设n个孩子为n个顶点，用边表示 顶点间的朋友关系构成一个图G。由于每个孩子都
nn
个是朋友，因此G的每一顶点的度数至少 是，从而G的任何两个顶点的度
22
数之和至少是
n
。根据定理８.14,G 为哈密顿图。即G有哈密顿回路，这表明,总可安排n个
至少与其中
孩子围成一圈跳舞，使每个 孩子的两边都是他的朋

7.４图的矩阵表示

习题解答
练习７.4
1、对图8．35给出的无向图Ｇ：
（1）计算其关联矩阵A（Ｇ)。
(2）计算A(G)的秩,验证定理8．17。
v
1

e
1
e
2
e
3
e
4

v
1

v
2
解 （1)其关联矩阵A（G) 为



v
3

v

4


v
5

1


1

0


0

0

010

100



110

001

001



e
1
v
4
e
3

100

(２）由于子行列式

110

非零,因此，Ａ（Ｇ）的秩为3 ＝ n – k = 5 – 2 。


001



２、对图８.36给出的有向图G:
(１)计算它的邻接矩阵A及A
2,A
3
,A
4
，说出从v
1
到v
4
的 长度为l，2,3,４的拟路径各有多
少条。
(2)计算A○Ａ
ι
，A
ι
○A,说出它们中第2,3分量及第4，4分量的意义。
(３）计算它的路径矩阵Ｂ及可达性矩阵Ｐ，并从P说出G的各强分图。

1 2


3




v
v
v

0


0
解（１） 它的 邻接矩阵Ａ=

0


0

0

条。
1010


0110

0000

v
1
到ｖ
4
的长度为1的拟路径各有1

0001

1010



0


0
A2
=

0


0

0

0


0
３
A＝

0
< br>
0

0


0


0< br>A
4
=

0


0

0< br>
0111


0001


0000

ｖ
１
到v
4
的长度为２的拟路径各有 1条。

1010

0111


1011


1010


0000

v
1< br>到v
4
的长度为3的拟路径各有1条。

0111

1011


1
0
0
1
1
1
1< br>0
0
1
2
1
0
1
2
1
1< br>0
1
1




ｖ
1
到ｖ
4
的长度为４的拟路径各有2条。






0


0
(2) A○A< br>ι
＝

0


0

0
< br>
0


1
A
ι
○Ａ＝

0


1

0

1010


0110

0000


0001

10 10



0


1

0


1

0


0


0

0


0

0

0000


0001

1000

＝

1001

0010


1010


0 110

0000

=

0001

10 10



0


0

0


0

0


2


1

0


0

2

1
2
0
0
1
0
0
0
0
0
0
0
0
1
1
2
1
0
0
2









0000


0001

1000


1001
< br>0010


0000


2020
0110



2130

0001


A○A
ι
中第２,3分量为0，表明没有两条边以v
2
，v< br>3
为起点而终止于同一终点;第4，4分
量为1,是v
４
的出度。 < br>A
ι
○Ａ中第2，3分量为0，表明没有两条边起始于同一顶点而以v
2
,v
3
为终点;第4，4
分量为3,是v
4
的入度。

0


0
（3）它的路径矩阵B=

0


0

0


1


0
可达性矩阵P＝

0


0

0

1
1
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
0
1
1
1
1
0
1
1
1
1
0
1
1
1
1
0
1
1









1


1

0



1

1


由P看出 各强分图的顶点集合分别是｛ｖ
１
}，{v
3
｝，{v
2
, v
４
，ｖ
5
}

3、 如何利用邻接矩阵来识别它们对应的无向图是欧拉图？
解 利用邻接矩阵判断各顶点的度数是 否为偶数。同时,利用邻接矩阵求出路径矩阵,用
各矩阵分量是否均为1来判断无向图是否连通。
4、 ｎ个顶点的有向图G是强连通的，说出G的路径矩阵、可达性矩阵的特点。
解 G的路径矩阵与可达性矩阵相同,它们的所有分量均为1。
5、设Ａ为不含环和平行边的有向图G的邻 接矩阵。证明：A
3
的对角线元素
a
ii
表示经
过顶点v< br>i
的“三角形”的个数，即以v
i
为一个顶点的G的子图K
3
的个数。
证 因为A
3
的对角线元素
a
ii
,表示顶点ｖ
i
到顶点v
i
长度为3的拟路径的条数,并且有向
(3)
( 3)

图G不含环和平行边,因此
a
ii
也是经过顶点ｖ
i
的“三角形”的个数，即以v
i
为一个顶点的
Ｇ的子图Ｋ
3的个数。

(3)