海南司法厅-社会实践报告怎么写

第七章 图
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＝为两个图，称G1与G2同构
（isomorphic），如果存在双 射f：V1→V2，双射g：E1→E2，使得对每一边eE1，
Ψ1(e)＝(u,v)（或）当且仅当Ψ2(g(e)) = (f(u),f(v))（或< f(u),f(v)>）
当限于讨论简单图时，可以用顶点的偶对表示边，即当Ψ(e) ＝(u,v)时，边e用(u,v)来表
示。这时两图同构的条件可以简化为
(u,v)E1当且仅当(f(u),f(v))E2

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

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

2
3
4
4
4
4
3

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

2 3 4 4 4 4 3 2

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

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

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


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
2

解

2 1 18

3 17


4


5 20 21 16

15



6 19 22 14



7 13

8



9 10 11 12





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

（本题是定理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）满足d
1
>d
2
>„>d
n
，那么当它为一简单图的 度序列时必
有
（a）

d
i1
n
i
为偶数；
（b）对任一k，1≤k≤n ,

d
i1
k
i
≤ k(k-1)+
ik1

min(k,d)
。
i
n< br>证（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1
n
i
为偶数是显然的。
考虑图中的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
增加的度数不会超过

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

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







图8.11

解 补图 生成子图





4

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






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

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


A  



D C B 

E F     

G H 



I J  
(a) (b)
图8.12
（2）给出所有不同构的4个结点的简单图的图示。
（l）证 在图（a）图（b）间建立双射h
v A B D I J C E G
h(v)
       
可逐一验证 (不赘)
(u,v)E(a)当且仅当 (h(u),h(v))E(b)
（2）所有不同构的4个结点的简单图的图示有如下11个：






5
H

F


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的回路。如果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的奇数长度的通路与偶数长度的通路有k个相交结点，如
图所示：

u 1 2 „ k v



考虑结点u到结点k,如果从结点u到结点k,既有奇数长度的通路又有偶数长度的通路，
那 么据归纳假设，其中有一奇数长度的回路，因而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）
因此（u
i
,v
j
）全部在G¯中，从而G¯是连通的。

6

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

a

a















b c

b c

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

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

v
1
v
2
v
7
v
10






v
4
v
3
v
8
v
9






v
5
v
6

图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中有向图的单向分图有：
<{v
1
,v
2
,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
6
>}> ,
<{v
7
,v
8
,v9
,v
10
},{7
,v
8
>,8
,v
9
>,9
,v
7
>, 7
,v
10
>}>
图8.19的凝聚图：
{v
1
,v
2
}





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





{v
6
}

7

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

a



b d

c

e g



f

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

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

u
k-1


u
1
„

u
k
w




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


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


„
w


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

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


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

8、称d(u,v)为图G＝中结点u，v间的距离：
当uv

0

当u到v不可达

d(u,v)



u,v间最短路径长度否则

d称为图G的直径，如果d＝max{d(u,v)  u,vV}。试求图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}仍是连通< br>的，故还有u到v的一条通路，从而这条通路连同边e构成G中的一条回路，矛盾。因此边
e是简 单连通图G的割边

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

<{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中的有向图可以描述识别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

1 0 1

S5




























































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

S3



0 1

S S1 S2 S4 S5

0 1 1 0



1 0 1



S6


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

习题解答
练习7. 3
10

1、试作出四个图的图示，使第一个既为欧拉 图又为哈密顿图；第二个是欧拉图而非哈密
顿图；第三个是哈密顿图却非欧拉图；第四个既非欧拉图也非 哈密顿图。
解（a）既为欧拉图又为哈密顿图；（b）是欧拉图而非哈密顿图；（c）是哈密顿图却非
欧拉图；（d）既非欧拉图也非哈密顿图。










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









（a） (b) (c) (d)

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度的顶点)，因此马不可能从某处出发
完成所有可能的跳步一次 且仅一次后回到原地。

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

50 11 24 63 14 37 26 35
23 62 51 12 25 34 15 38
11

10 49 64 21 40 13 36 27
61 22 9
48 7
59 4
6
3
52 33 28 39 16
20 41 54 29
53 32 17 42
60 1
45 8
47 2
58 5
57 44 19 30 55
46 31 56 43 18

幻方
ｏ
ｏ
ｏ
ｏ
ｏ
ｏ
ｏ
ｏ


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

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

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












(b) (c)

（a）
12

图8.31

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












k








（d）

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 

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

2
与
mC
n
故G中任意两个顶点的度数之和大于n 。根据定理8.14，G为哈密顿
1
2
矛盾，
图。

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

7.4图的矩阵表示

习题解答
练习7.4
1、对图8.35给出的无向图G:
（1）计算其关联矩阵A(G)。
（2）计算A(G)的秩，验证定理8.17。
v
1


e
1
v
4
e
3

e
4
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


v
5
v
2
e
2
v
3

图8.35

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

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，并从P说出G的各强分图。
v
1
v
2
v
3








14
v
4
v
5

图8.36

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


1 010

0111


1011


10 10


0000

v
1
到v
4
的长度为3的拟路径各有1条。

0111

1011


1121


0111

0000

v
1
到v
4
的长度为4的拟路径各有2条。

1011< br>
1121


1010

0

0110

1
0000

0

0001< br>
1

1010


0

0< br>

0

0


0

0< br>




=

1001

0010


0000
0001
1000

2< br>

1

0


0

2< br>
1002


2001


0000

0010

1012



0< br>

0
(2) A○A
ι
=

0


0

0


0


1
A
ι
○A=

0


1
0


0000


0001

10 00


1001

0010


101 0


0110

0000

=

0001

1010


15

0


0

0


0

0

0000


2020

0110

< br>
2130

0001



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


1111

1111


由P看出各强分图的顶点集合分别是{v
1
}，{v
3
}，{v
2
，v
4
，v
5
}

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

16