广州中医药大学录取分数线-西安政治学院

离散数学习题解答-(9)

第七章 图
7.1 图的基本知识


定义8.8 设图G＝
（1）G－e表示对G作删除边e的运算，G
－e = ，其中E’＝E－{e}，Ψ’= Ψ
E
’
。
（2）G－v表示对G作删除顶点v的运算，
G－v = ，其中V’= V－{v}，E’＝
E－{e  e以v为端点}，Ψ’＝Ψ
E
’
。
（3）边e切割运算。设G中Ψ (e) = (u,v),
对G作边e切割得G’＝，其中，
V’＝V{v’}，E’= (E－{e}){e1,e2}, Ψ’= (Ψ－
{}){，}
（4）顶点v贯通运算。设G中顶点v恰为
边e1,e2的端点，且Ψ (e1) = (u,v)，Ψ (e2) = (w,v)。
对G作顶点v贯通得G’＝，其中
V’= V－{v}, E’= (E－{e1,e2}){e}, Ψ’=( Ψ－
{,}){}。
切割与贯通是互逆的，两者常被称为同胚运
算。
定义8.9 设G1＝，G2＝E2，Ψ2>为两个图，称G1与G2同构
0

0

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

2
3
4
4
4
4
3
2
3
4
6
6
6
6
4
3
4
6
8
8
8
8
6
4
4
6
8
8
8
8
6
4
4
6
8
8
8
8
6
4
4
6
8
8
8
8
6
4
3
4
6
6
6
6
4
3
2
3
4
4
4
4
3
2

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

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

（2）n个顶点的有向完全图的边数总和为
nnnnnnn

2
0

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

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

1

解




4




21 16




图8.10
2 1 18
3 17
20
2

5

6、在晚会上有n个人，他们各自与自己相识
的人握一次手。已知每人与别人 握手的次数都是
奇数，问n是奇数还是偶数。为什么？
解 n是偶数。用n个顶点表示 n个人，顶点
间的一条边表示一次握手，可构成一个无向图。
若n是奇数，那么该图的顶点度数 之和为奇数（奇
数个奇数的和），这是不可能的，因此n是偶数。
7、n个城市间有m条相互 连接的直达公路。
n2)
证明：当
m
(n1)(
时，人们便能 通过这些公路在
2
任何两个城市间旅行。
证 用n个顶点表示n个城市，顶点间的边
表示直达公路，据题意需证这n个城市的公路网
络所构成的图G是连通的。反设G不连通，那< br>么可设G由两个不相关的子图（没有任何边关联
3

分别在 两个子图中的顶点）G1，G2组成，分别
有n
1
，n
2
个顶点，从 而，n = n
1
+n
2
，n
1
≥1，n
2
≥
1。
由于各子图的边数不超过
n(n
2
1)
(见练习
ii
8.l之3)，因此G的边数m满足：

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)(n1)(n1))

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

n2)
与已知
m
(n1)(
矛盾，故图G是连通的。
2
（本题是定理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）若自然数序列（d
1
,d
2
,…,d
n
）满足
4

d
1
>d
2
>…>d
n
，那么当它为一简单图的度序列时必
有
（a）

d
为偶数；
i
i1
n
（b）对任一k，1≤k≤n ,

d
≤
i
i1
k
k(k-1)+

min(k,d)
。
i
ik1
n
证（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）

d
为偶数是显然的。
i
i1
n
考虑图中的k个顶点（k=1,2,…,n）,这k个顶
点的生 成子图的度数总和 ≤ k(k-1)，而其余
n–k 个顶点v
k+1
,v
k+2
, …,v
n
, 可使 v
1
,v
2
, …,v
k
增加的度数不会超过
5


min(k,d)

i
ik1
n
因此我们有

d
≤ k(k-1)+

min(k,d)
。
i
i
i1
ik1
k
n
9、画出图8.11中图的补图及它的一个生成
子图。







图8.11

解 补图
生成子图






6

10、一个简单图，如果同构于它的补，则该
图称为自补图。
（1）给出一个4个顶点的自补图。
（2）给出一个5个顶点的自补图。
（3）是否有3个顶点或6个顶点的自补图？
（4）证明一个自补图一定有4k或4k＋1个顶
点（k为正整数）。
解 （1）4个顶点的自补图： （2）
5个顶点的自补图：






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

点（k为正整数）。

11、（l）证明图 8.12中（a）与（b）同构。








(a)
(b)
图8.12
（2）给出所有不同构的4个结点的简单图的
图示。
（l）证 在图（a）图（b）间建立双射h
v
)
可逐一验证 (不赘)
(u,v)E(a)当且仅当
8
A
 

D C B
A B

D I
 
J

C E
 
G H F
  
h(v


(h(u),h(v))E(b)
（2）所有不同构的4个结点的简单图的图示
有如下11个：









7.2 路径、回路及连通性


习题解答
练习7.2
1、 证明定理8.5。
证 设n个顶点的图G中，有从v到v的闭路
径，表示为
（v,v
1
,v
2
,…,v
k
,v）
如果v,v
1
,v
2
, …,v
k
中没有相同顶点 （因而不多于
n个），那么它便是一条从v到v的长度不大于n
9

的回路。如果v,v
1
,v
2
, …,v
k
中有相同顶点v
i
=v
j
，
例如
（v,v
1
,…, v
i
,…, v
j
,
v
j+1
,…,v
k
,v）
那么删除v
i
到v
j
的闭路径，得到
（v,v
1
,…, v
i
, v
j+1
,…,v
k
,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时，命题成立。
设图G中，从结点u到结点v的奇数长度的通

u
10
1
2 … k

路与偶数长度的通路有k个相交结点，如图所示：




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

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

因此（u
i
,v
j
）全部在G¯中，从而G¯是连通的。

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

a

a











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

图中任意两个结点u,v，如果有从u到v的路径，
则添加从u到v的边。

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








图8.19
解 图8.19中有向图的强分图有：
<{v
1
,v
2
},{1
,v
2
>,2
,v
1
>}> ,
<{v
3
,v
4
,v
5
} ,{3
,v
5
>,4
,v
3
>, 4
,v
5
>,5
,v
4
>}>,
<{v
6
},{6
,v
6
>}> ,
<{v
7
,v
8
,v
9
},{7
, v
8
>,8
,v
9
>,9
,v< br>7
>}>,
<{v
10
},{}>
图8.19中有向图的单向分图有：
13
v
1
v
2

v
7
v
10

<{v
1
,v2
,v
3
,v
4
,v
5
,v
6
},{1
,v
2
>,2
,v
1
>,1
,v
4
>,2
,v
3
>, 4
,v
3
>,3
,v
5
>,4
,v
5
>,5
,v
4
>,3
,
<{v
7
,v
8
,v
9
,v10
},{7
,v
8
>,8
,v9
>,9
,v
7
>,v
6
> }> ,
,v
10
>}>
图8.19的凝聚图：
{v
1
,v
2
}







6、有7人a，b，c，d，e，f，g分别精通下
列语言，问他们7人是否可以自由交谈（必要时
借助他人作翻译）。
a 精通英语。
b 精通汉语和英语。
c 精通英语、俄语和意大利语。
d 精通日语和英语。
e 精通德语和意大利语。
f 精通法语、日语和俄语。
14
7


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

g 精通法语和德语。
解 下图中7个顶点表示7个人，关联两个顶
a
点的边表示两个人同时精通某一种语言：


b

d






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

7、证明：一个有向图是单向连通的，当且仅
当它有一条经过每一结点的路径。
证 充分性是显然的。
必要性：设有向图G是单向连通的，P是G
中的一条路径，起点为u
1
,终点为u
k
。如下延长
这一路径：
考虑路径外的任意顶点w,若
（1）有顶点w到u
1
的路径,则我们如愿。
15

（2）有顶点u
k
到w的路径,则我们如 愿。否则，
由于有向图是单向连通的，
（3）有顶点w到u
k
的路径,和顶 点u
k-1
到w
的路径, 则我们如愿。否则，由于有向图是单向
连通的，




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





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

u
1
u
k-2
u
k-1
u
k
w


…
如上不断延长这一路径，直至产生一条经过每
一结点的路径。
16

u
w
u
1
u
k-2
u
k-1
u
k
w

…

8、称d(u,v)为图G＝中结点u，v
间的距离：


0

d(u,v)



u,v间最 短路径长度

当uv
当u到v不可达
否则

d称为图G的直径，如果d＝max{d(u,v) 
u,vV}。试求图8.20中图的直径，
χ(G) ,λ(G) ,δ(G)，并指出一个点割集和一个边
割集。











图8.20
17

解 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，都< br>有一条通路不经过顶点v，因而删除顶点v不能
使G不连通，与v是简单连通图G的割点矛盾。< br>故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的任
一回路上。
18

反之，设e不在G的任一回路上，而e不是 简
单连通图G的割边。那么G-{e}仍是连通的，故
还有u到v的一条通路，从而这条通路连 同边e
构成G中的一条回路，矛盾。因此边e是简单连
通图G的割边

11、试用有向图描述下列问题的解：
某人m带一条狗d，一只猫c和一只兔子r
过 河。m每次游过河时只能带一只动物，而没人
管理时，狗与兔子不能共处，猫和兔子也不能共
处 。问m怎样把三个动物带过河去？
（提示：用结点代表状态，状态用序偶S2>来表 示，这里S1，S2分别是左岸和右岸的人
及动物集合，例如初始状态为< {m,d,c,r} ,  >。
解 描述上述问题的有向图如下：


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



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

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



19

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


S 0 S1 1 S2

1 S3 0 S4




20

图
8.21
解 识别序列01(10)

10的有向图刻划的状态
S3
转换系统如下：


0

1

S S1 S2








7.3欧拉图与哈密顿图
为一。

习题解答
练习7. 3 1、试作出四个图的图示，使第一个既为欧
拉图又为哈密顿图；第二个是欧拉图而非哈密顿
21

图；第三个是哈密顿图却非欧拉图；第四个既非
欧拉图也非哈密顿图。
解（a）既为 欧拉图又为哈密顿图；（b）是
欧拉图而非哈密顿图；（c）是哈密顿图却非欧拉
图；（d）既 非欧拉图也非哈密顿图。









2、像第一题要求的那样对欧拉路径和哈密
顿通路作出四个图。
解（a）既有欧拉路径又有哈密顿通路；（b）

有欧拉路径而无哈密顿通路；（c）有哈密顿通路

却无欧拉路径；（d）既无欧拉路径也无哈密顿通

路。





22

3、问n为何 种数值时，K
n
既是欧拉图又是
哈密顿图。问k为何值时，k-正则图既是欧拉图又是哈密顿图。
解 n为奇数时，K
n
既是欧拉图又是哈密顿
图。k为 大于或等于n2的偶数时，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度的顶点)，因此马不可能从某处出发完成所
23

有可能的跳步一次且仅一次后回到原地。

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

51261323
0 1 4 3 4 7 6 5
26512313
3 2 1 2 5 4 5 8
14624132
0 9 4 1 0 3 6 7
629 53231
1 2
8
9
0
5
2 3 8 9 6
0 1 4 9
3 2 7 2
47 61 2452
54 48 5314
6 42 54135
24

7
8
7 4 9 0 5
6 1 6 3 8

3 55 43541
幻方
ｏ ｏ ｏ ｏ ｏ ｏ ｏ ｏ
ｏ ｏ ｏ ｏ ｏ ｏ ｏ ｏ
ｏ ｏ ｏ ｏ ｏ ｏ ｏ ｏ
ｏ ｏ ｏ ｏ ｏ ｏ ｏ ｏ
ｏ ｏ ｏ ｏ ｏ ｏ ｏ ｏ
ｏ ｏ ｏ ｏ ｏ ｏ ｏ ｏ
ｏ ｏ ｏ ｏ ｏ ｏ ｏ ｏ
ｏ ｏ ｏ ｏ ｏ ｏ ｏ ｏ


7、试计算K
n
（n≥3）中不同的哈密顿回路共
有多少条。
1)!
解 不同的哈密顿回路共有
(n
条。可以用依
2
次 选取每一条边来生成哈密顿回路。因为组成回
路的第一条边的选择可能是n 种, 组成回路的
第二条边的选择可能是n – 1 种, … , 组成
25

回路的第n – 1条边的选择可能是2种，组成回
路的第n 条边 的选择可能是1种，而每一哈密顿
回路由此生成两次，因此不同的哈密顿回路共有
(n1)!
2
条。

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

9、判别图8.31中各图是否为哈密顿图，若
不是，请说明理由，并回答它是否有哈密顿通路。











26

图8.31

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










27

10、证明：对哈密顿图G = 删除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）图。证明：如果
mC
2
n1
2
，
那么G为哈密顿图（提示：运用定理8.14）。
证 设G中有两个顶点v1和v2的度数之和不
大于n – 1 ，那么以v1和v2为端点的边不多于
n – 1条。而其余顶点之间的边的数目不多于
(n 2)(n3)
2
条。故G的总边数m满足
28

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
22
C
n1
1

与
mC

2
n1
2
矛盾，故G中任意两个顶点的度数之和
大于n 。根据定理8.14，G为哈密顿图。
12、设有n个围成一圈跳舞的孩子，每个孩
子都至少与其中
n
个是朋友。试证明，总
2
可安排得使每个孩子的两边都是他的朋友。
证 设n个孩子为n个顶点，用边表示 顶点间
的朋友关系构成一个图G。由于每个孩子都至少
与其中
n
个是朋友，因 此G的每一顶点的度数至
2
少是
n
，从而G的任何两个顶点的度数之和至少< br>2
是
n
。根据定理8.14，G为哈密顿图。即G有哈
密顿回路，这表 明，总可安排n个孩子围成一圈
跳舞，使每个孩子的两边都是他的朋

7.4图的矩阵表示

习题解答
29

练习7.4
v
1
1、对图8.35给出的无向图G:

（1）计算其关联矩阵A(G)。
e
1
v
4
（2）计算A(G)的秩，验证定理8.17。
e

3
e
1
e
2
e
3
e
4
解 （1）其 关联矩阵A(G)为

v
1

v
2

< br>
v
3

v

4


v< br>5

1


1

0

< br>0

0

010


100
110


001

001



（2）由于子行列式

100


110


001


非零，因此，A(G)
的秩为3 = n – k = 5 – 2 。

2、对图8.36给出的有向图G:
（1 ）计算它的邻接矩阵A及A
2
，A
3
，A
4
，
说出 从v
1
到v
4
的长度为l，2，3，4的拟路径各
有多少条。
（2）计算A○A
ι
，A
ι
○A，说出它们中第2，
3分量及第4，4分量的意义。
（3）计算它的路径矩阵B及可达性矩阵P，
v
1
v
2

并从P说出G的各强分图。
v
3


30

解(1) 它的邻接矩阵A=

0


0

0


0

0

1010


0110

0000


0001

10 10


v
1
到v
4
的
长度为1的拟路径各有1条。
A
2
=

0


0

0


0

0

0111


0001

0000


1010

0111


v
1
到v
4
的长度为2的拟路径各
有1条。
< br>A
3
=

0


0

0< br>

0

0

1011


1010

0000


0111

1011< br>

v
1
到v
4
的长度为3的拟路径各
有1条。

A< br>4
=

0


0

0
< br>
0

0

1121


0111

0000


1011

1121
< br>
v
1
到v
4
的长度为4的拟路径各
有2条。
31

(2) A○A
ι
=

0


0

0


0

0

1010


0110

0000


0001

1010



0


0

0


0

0


0


1

0


1

0

0000


0001

1000


1001

0010


=

2


1

0


0

2

1002


2001



0000

0010

1012


A
ι
○A=

0


1
< br>0


1

0

0000


0001

1000


1001

0010


1010


0110

0 000


0001

1010


=< br>
0


0

0


0< br>
0

0000


2020

0 110


2130

0001



A○A
ι
中第2，3分量为0，表明没有两条边以
v
2
， v
3
为起点而终止于同一终点；第4，4分量
为1,是v
4
的出度。
A
ι
○A中第2，3分量为0，表明没有两条边起
始于同一顶点而以v
2
，v
3
为终点；第4，4分量
为3,是v
4
的入度。
（3）它的路径矩阵B=

0


0

0


0

0

1111

1111

0000


1111

1111



可达性矩阵P=

1


0

0


0

0

1111< br>

1111

0100


1111
1111



由P看出各强分图的顶点集合分别是{v1
}，
{v
3
}，{v
2
，v
4
，v
5
}
32

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

33