计算机应用数学基础 教学 作者 王学军 计算机应用数学课件 第10章 图论

第10章图论

06/14/2013

原版教学配套课件

学习目标:

通过本章的学习，要掌握如下内容,

活运用的程度:

基本概念

路与回路

图的矩阵表示

有向图和可达性矩阵

欧拉图与哈密尔顿图

•树

根树及其应用

二部图和平面图

06/14/2013*^^^

2013-3-13

原版教学配套课件

10.1基本概念

f10.1.1图的基本概念

现实世界中很多状态可以用某种图形来描述，这种图形

是由一些点和一些连接两点间的连线所组成，对于点的

位置及连线的长度无关紧要。

例如，有〃、b、C、d四个足球队进行友谊比赛。为了描

述4个队之间比赛的情况，可以用图104来表示。

在图104中4个小圆圈分别表示这

四个足球队，称之为结点。如果两

队进行过比赛，则在表示这两队的

结点之间用一条线连接起来，称之

为边。

06/14/2013*^^^^

2013-3-133

原版教学配套课件

10.1基本概念

设A,5为任意的｛(a,八〃£5｝两个集合，称为A

和5的无序偶集。同理，｛<a,A〃£5｝为A和5

为有序偶集。

定义10-1一个图G是一个三元组，G=<V(G),E(G),

66,其中V(G)是一个非空的结点集合，£(G)是边的集

合，0G是从边集合£到结点无序偶集或有序偶集合上的

函数。

一般情况下，G=<V(G),£(G),简写为G=vV(G),

£(G)>或G=<匕E>

以上是无向图与有向图的集合定义，若用图形表示它

们，即用小圆圈(或实心点)表示结点，用结点之间的连

线表示无向边，用有方向的连线表示有向边。

()6/14/201

2013-3-134

原版教学配套课件

<•例10”图举例。

⑴给定无向图G=vHG),E(G),0G>,其中b,

c,d}9E(G)={g,e2,eve5,e6],0G(4)=(〃，

0G应)=(〃，b),久(——(a,c),<^G(e4)=(a,d),

0G⑷8，或，0G(%)=(。，砌。

(2)给定有向图。=vV(O),E(D),①金,其中V心)={〃,

b,c,d,e,f},E(D)={et,e2,e4,e5,e6,勺},

0o(eP=va,a>,①D(e)=〈a,b>,(^3)=<b,a>,

<c

①D(Q)=<d,〃>,①口&)-，b>,①0储6)-<c'd>，

%(C7)=vc，d>,(^8)=</,,f>o

()6/14/201

2013-3-135

原版教学配套课件

•画出G与O的图形。

解图10・2中3),S)分别给出了无向图G和有向图。的图

形。

()6/14/201

计算机应用数学基础

定义10・2如果两个结点之间有多条边(对于有向图，则有

多条同方向的边)，则称这些边为平行边，两相结点〃，b

间平行边的条数称为边的重数。含有平行边的图称为多

重图，不含平行边和自回路的图称为简单图。

10.1.2图中结点的度数

我们常常需要关心图中有多少条边与某一结点关联，这

就引出了图的一个重要概念一一结点的度。

定义10・3设图G是无向图，u是图G中的结点，所有与u关

联的边的条数(有自回路时计算两次)，称为点u的度数，

记作deg")。

如图10-2(〃)中，deg(a)=59deg(b)=2,deg(c)=2,deg(d)

=3o06/14/2013*^^^^

2013-3-137

原版教学配套课件

算机应用数学基础

定理104设图G=vV(G),E(G),0G＞是具有〃个点，m条

边的无向图，其中结点集合为{匕，v2,vn},贝！J

工deg(匕)=2m

证明因为G中每条边都与两个结点关联，每条边均提供2

度，所以在计算G所有结点度数之和时，加条边共提供了

2见度，由此结论成立。

定理10・2设图G=vV(G),E(G),①G＞是具有n个点，m

条边的有向图，其中结点集合为V={vl,v2,vn),

贝IJ

〃nn

ydeg(v,)=2几且£deg+(v,)=^deg一(匕)nn

如图10.2(办)甲，deg+(a)—2,deg“8)=3,deg+(b)=1,deg"

(A)=2,deg+(c)=3,deg-(c)=0,deg+(d)=1,deg(d)=

+

2,deg+(e)=0,deg(e)=0,deg(f)=1,deg(f)=lo

()6/14/20

2013-3-138

原版教学配套课件

计算机应用数学基础

推论图G中度数为奇数的结点必为偶数个。

证明设G二vV(G),E(G)＞为任意图，VI和V2分别是G中

奇数度数和偶数度数的结点集，VIUV2=V,

VinV2=O,由定理10・1知

Z〃g(v)=Z〃g(v)+Zdeg(v)=2m

由于是寓数之和二必为偶教？而21ml也为偶数，故是偶

数。由此IV1I必为偶数。

定义10・4在图中，度数为0的结点称为孤立点。

如图101(b)中，结点e为0度，是一个孤立点。

10.1.3几种常见的图

定义10・5具有〃个结点和机条边的图称为(〃，帆)图。一个

(〃，0)图称为零图(即该图只有〃个孤立结点)。只有一个

结点的图，即(1,0)图称为平凡图。06/14/2013*^^^^

2013-3-139

原版教学配套课件

定义10・6任意两个不同的结点都是邻接的简单图称为完

全图。〃个结点的无向完全图记为屋〃其边的条数为〃（小

1）/2o

从图10・3中的吗和（看出吗有3条边，（有6条边。容

易证明（有n（n・l）/2条边。

定义10・7设G=vV（G）,E（G）＞是一个具有n个结点的简单

图。以V为结点集，以从完全图（中删去G的所有边后得

到的图称为G的补图（或称为G的补），记为。G

如图10・4给出了一个图G和G的补3。

()6/14/201

2013-3-1310

原版教学配套课件

计算机应用数学基础

定义10・8给每条边赋以一个实数(称为该边的权)的图叫

有权图。边e的权常记为沙G(e)。有权图G=vV(G),

£(G)＞中所有边的权之和称作图G的权，记为WG(G)O

例10・2证明在任何一个有6个人的小组中，存在3个人

互相认识，或者存在3个人互相不认识(拉姆齐问题)。

分析用6个结点来代表人，并用邻接性来表示两人之间

认识关系。这样一来，该例就是要证明：任意一个有6

个结点的图G中，或者有3个互相邻接的点，或者有3

个互相不邻接的点。即，对任何一个有6个结点的图

G,G或中含有一个三角形(即()。

()6/14/20

2013-3-1311

原版教学配套课件

证明^G=<V(G),E(G)>,\V\=6,u是G中一结点。因为

u与G的其余5个结点或者在G中邻接，或者在中邻接。

故可假定，有3个结点匕，v2,匕在G中与u邻接。

如果这3个结点中有两个结点(如匕，匕)邻接，则它们与u

就是G中一个三角形的3个顶点。如果这3个结点中任意

两个在G中均不邻接，贝Wi，v2,匕就是G中一个三角形

的3个顶点。

10.1.4子图

在描述和研究图的性质时，还涉及到另一重要概念子

图。

定义10.9设有图G=vV,和图G=vH,E，>。

(1)若V，V,E，E,则称G是G的子图。

(2)若G是G的子图，且?中E,则称G是G的真子图。

(3)若v，=y,E'E,则称G，是G的生成子图。()6/14/201

2013-3-1312

原版教学配套课件

图10・5给出了图G以及它的真子图5和生成子图G2。

V\V4p.P4

G&G?

图10-5图G以及其具干图&和生成千图俏

()6/14/201

2013-3-1313

原版教学配套课件

定义10.10如果图G中的一个子图是通过删去图G的结点集V的一个

子集匕的所有结点及与其关联的所有边得到的，则将该子图记为G-

匕。

•如图10如中,G7=G-{V4}O

定义10-11如果图G中的一个子图是通过删去图G的边集£的一个子

集约的所有边，而不删去它们的端点而得到的，则将该子图记为G-

EjO

如图10-5中，G2=G-{(vPv5)}o

10.1.5图的同构

从图的定义可以看出，图的最本质的内容是结点与结点的邻接关

系。例如图也可以用图10-6中几种不同形状的图形表示。它们

与图10-1一样，都同样表示4个队之间的比赛情况。从这个意义上

讲，我们说它们是同一个图，并称图10-1与图10-6的(加和(b)是同

构的。

()6/14/201

2013-3-1314

原版教学配套课件

计算机应用数学基础

图10-6图同料示例

()6/14/201

■B1LH2013-3-1315

原版教学配套课件

定义1042设有图G=vV,和图G，=vV"球＞。如果

存在双射g：使得e=（〃，v）eE,?，=（&（〃），

1一））££',且包,刃与（g（〃），g⑺）有相同的重数，则

称G与G，同构。记作G2G、

例10・3考察图例，中的两个图G=（V,£）和G，=（—,

很容易看出，定义g：g（匕•）=吟，可以验证g

满足定义10・12的双射，所以GgG，。

()6/14/201

16

/10.2.1路、路和连通性

定义10・13给定图G=(V,E)o设%,匕，…，vkey,

办，。2，…，/££,其中G是关联于结点匕1和匕的边，称

交替序列%々呼2…冬也为连接％到雁的路，路中边的数目

女称作路的长度。

定义又・14设〃=%产及2…7限是图G中连接以0到限的路。

(1)若｛=限，则称路〃为回路；

(2)若与，⑦，…，叫都不相同，则称路〃为迹；

(3)若为，匕，…，也都不相同，则称路〃为通路；

(4)长度大于2的闭的通路(即除吗=咋外，其余结点均

不相同的路)〃称作回路。

.

例如在图10・8,其中，连接匕到女的路有喔。6y/，5,

这也是一条迹，还是一条通路；

路V/O47V是一条回路，但不是回路；

路U/O4为是一条回路，也是回路。

在简单图中，一条路与e产/与…,唳完全由它的结点序列

与匕…唳确定。所以简单图的路可由结点序列表示。

如图10.l表示的简单图中,

路可写成O

06/14/20LW

2013-3-1318

原版教学配套课件

（下面我们利用通路的概念解决一个古老的著名问题。

例10・4（渡河问题）一个摆渡人，要把一只狼、一只羊和

一捆干草运过河去，河上有一只木船，每次除了人以

夕卜，只能带一样东西。并且，如果人不在旁时，狼就要

吃羊，羊就要吃干草。问这人应该怎样才能把它们运过

河去？

解用F表示摆渡人，W表示狼，S表示羊，H表示干

草。

如果用尸表示人和其他三样东西在河的左岸。这

样，在FWSFWHFSH

FSFH

磔WHSHF

WSH

()6/14/201

2013-3-1319

原版教学配套课件

这里0表示左岸是空集，即人、狼、羊、干草都已运到

右岸去了O

根据题意，考查一下这16种情况就可以知道，其中有6

种情况不允许出现。它们分别是：WSH.FW.FH、

WS.SH、Fo如尸H表示人和干草在左岸，而羊和狼在

右岸，狼要吃羊，这当然是不行的。因此，允许出现的

情况只有10种，如图10・9所示。

WH

图10.9河在你允许世去

定义10-15在图G中，若结点匕到匕有路连接（这时称匕和匕是连通的），

则其中长度最短的路称为从匕到匕的短程。短程的长度称为匕到匕的距

离，用符号〃（匕，咛）表示。

•例如在图10-8中，d（yv匕）=2。

定理10-3设G是具有〃个结点的图，如果从结点匕到另一结点匕存在

一条路，则其短程是一条长度不大于的通路。

证明设从结点匕.到结点匕存在一条路〃，该路上的结点序列为

匕.…女…可用反证法证明，当〃是短程时，〃一定是通路。

推论设图G=（V,E）,\V\=n,则G中任一回路长度不大于〃。

定义10-17如果一个图的任何两个结点之间都有一条路，那么我们称

这个图是连通的，否则是不连通的。

()6/14/201

2013-3-1321

原版教学配套课件

定义10・18图G的一个连通的子图（称为连通子图）若不包

含在G的任何更大的连通子图中，它就被称作G的连通分

支，常把图G的连通分支数记作W（G）。

在图10・10中，G是不连通的，W（G）=2,而G，是连通

的，W（G，）=L

任何一个图都可划分为若干个连通分支。显然，仅当图

G的连通分支数W（G）=1时，图G是连通的。

S10-10图连遹分文示例

()6/14/201

2013-3-1322

原版教学配套课件

计算机应用数学基础

(10.2.2有权图的最短路径问题

有权图经常出现在图的应用中。如在交通图中，权可以

表示两地的距离；在通讯图中，权可以表示各种通讯线

路的建造或维修费用等等。

定义1049有权图G中，连接两个结点匕和，的路〃的权是

〃中各边的权之和，记为WG(〃)。

首先，用反证法证明边权为正的最短路径有这样的性

U

质：若〃0%…是从〃。到〃加的最短路径，则〃…m-

7是从〃。到〃3］的最短路径。

这样，假设S为图G中按长度递增的次序已求出的最短路

径的终点的集合，则下一条长度较长的最短路径的终点〃

(如下:06/14/20^^^^^

2013-3-1323

原版教学配套课件

计算机应用数学基础

令二对于考虑每个七es,若有这样的边，将从

结点壬到结点，的边连接在从〃。到天的最短路径后面，这样

就构成了从〃。至〃的1条不同的路（若图中有边（即,则

是其中的一条路）。选出这1条路中的最短路，并设该

路长为0（，令0（〃）=加质{£＞（，）〃£},则由上面所述性质

知，〃即为所求结点。由此可知，即到所求结点〃的最短

路径或是路〃0〃，或是以S中的点作为中间结点的路。

综上所述，可得迪克斯特拉算法步骤如下：

（1）把V分成两个子集3和=%3,初始时S={〃。},

•令D①昨）为

WG(〃0,i)(〃0,/)eE=

■M1LH

其中WG(〃o,i)是G中的边(“0,i)的权，而为表示某个足够大的数。

(2)找中的点〃，使。(〃)=机加{。⑶植右，则。(〃)就是〃。到〃的最短路径

长度。

(3)将点〃从中删除并加入集合S中，即置S为SU{〃/置为-{u}。

(4)若SWV,则修改的值，其方法是：若有(〃，£)££(〃是由

步骤2选出的)，则置为相加{。(。，O(〃)+WG(〃，/)},转2。

•(5)若8=匕则算法结束。

因为该算法每执行一次(以执行算法步骤2〜4一遍为一次)，选取一

个有最短路径的结点U,所以图中结点全部处理完要执行IVI-1次。

为清楚起见，将本算法用流程图表示，见图10-11。

()6/14/201

2013-3-1325

原版教学配套课件

计算机应用数学基础

图10-11他克斯特技算法流程图

()6/14/201

2013-3-1326

原版教学配套课件

例10・5在图1042所示的有权图中，用迪克斯特拉算法求

结点vO到其余各点的最短路径。

解初始状态为

•S={vO},

•S={vl,v2,v3,v4,v5,v6},

•D(vl)=2,

•D(v2)=3,

•D(v3)=5,

•D(V4)=8,

•D(v5)=°°,

•D(v6)=5o

BIO-12例io4品短骼役

()6/14/201

2013-3-1327

原版教学配套课件

计算机应用数学基础

算法共执行6次，求解示意图如图1043所示。

•第1次

•(1)S中有最小D值的结点为vL选=丫1。置S为SU{u}

={v0,vl)；

•⑵置S为S・{u}={v2,v3,v4,v5,v6}o

•⑶修改S中诸元素的D值如下：

•D(v2)-min{D(v2),D(vl)+WG(vl,v2)}=min{3,

2+00}=3

•D(v3)-min{D(v3),D(vl)+WG(vl,v3)}=min{5,

2+2}=4

•D(v4)-min{D(v4),D(vl)+WG(vl,v4)}=min{0°,

2+oo}=°o

06/14/2013*^^^^

•同理有D(v5)=9,D(v6)=5o

2013-3-1328

原版教学配套课件

计算机应用数学基础

v.(s)

S・%ls-I**.»1Is”、»».•*!

(5)

()6/14/201

■BILH2013-3-1329

原版教学配套课件

vt（2）

v/））

-k*•.、AC

第2次（6）

图10-13例10-5农解

•(1)S中有最小D值的结点为V2,选U=V2。

•⑵置S为SU{u}={vO,vl,v2},置S为S-{u}={v3,

v4,v5,v6}o

•⑶修改S中诸元素的D值，求得

•D(v3)=4,D(v4)=8,D(v5)=9,D(v6)=5o

第3次到第6次的过程请读者自己试着补出来。

（）6/14/2叩）

2013-3-1330

原版教学配套课件

10.3图的矩阵表示

上面介绍了图的一种表示方法一一用图形表示图。它的

优点是形象直观，但是这种表示在结点与边的数目很多

时是不方便的。下面介绍另一种表示方法一一用矩阵表

示图。利用这种方法，可以把图用矩阵存储在计算机

中，利用矩阵的运算还可以了解到它的一些有关性质。

定义10・20设G=(V,E)是有n个结点的图，贝!jn阶方阵A

=(%)称为G的邻接矩阵。其中

1(V.,V;)GE

(J..=<

0(vz.,vy)E

06/14/2013^^^^

j2013-3-1331

原版教学配套课件

如图1044所示的图G,其邻接矩阵A为

,01010、

1o111

A=01001

11000

"1100,

显然，无向图的邻接矩阵一定是对称的。

在邻接矩阵A的幕A2,A3,…矩阵中，每个元素有特定

的含义，下面定理10・4进行了说明。

()6/14/201

2013-3-1332

原版教学配套课件

计算机应用数学基础

定理10-4设G是具有n个结点集｛vLv2,vn｝的图，其邻接矩阵

为A,则A1(1=L2,…)的(i,j)项元素a(l)ij是从vi到vj的长度等于1

的路的总数。

证明对1用数学归纳法。

当1=1时，A1=A,由A的定义，定理显然成立。

若l=k时定理成立，则当l=k+l时，Ak+l=AkXA,所以

•若包=£d)%

r=l

由定理10-4和定理10-3可得出以下结论：

(1)如果对1=1,2,•••,n-1,Al的(i,j)项元素(i#j)都为零,那么

vi和vj之间无任何路相连接，即vi和vj不连通。因此，vi和vj必属

于G的不同的连通分支。

(2)结点vi到vj(iWj)间的距离d(vi,vj)是使A1(1=L2,n・l)的

(i,j)项元素不为零的最小整数1。

⑶A1的(i,i)项元素a(l)ii表示开始并结束于vi长度为1的回路的数

目。

()6/14/20

2013-3-1333

原版教学配套课件

例10・6图G=（匕£）的图形如图10・15,求邻接矩阵A和

A2,A3,A4,并分析其元素的图论意义。

•解：

(01000、,01000、’01oooWi0100、

10100101001010002000

A=01000A2=01000X0100010100

00001000010000100001

00107<00010,<0001070010,

'02000、(20200、

2020004000

A'=02000AJ20200

0000100010

^00010；(.00001；

()6/14/201

2013-3-1334

原版教学配套课件

(1)由A中〃⑴12=1知，匕和-是邻接的;由43中〃(3)12=2

知，匕到匕长度为3的路有两条，从图中可看出是u产217产2

和U产2y3y2。

(2)由A2的主对角线上元素可知，每个结点都有长度为2

的回路，其中结点匕有两条：U2V产2和叱匕乙，其余结点只

有一条。

(3)由于A3的主对角线上元素全为零，所以山

为3的回路。/u

(4)由于屈1)34=/2)34=〃(3)34=〃")34=。，所L

无路，它们属于不同的连通分支。⑸或匕，I1,

对于其他元素读者自己找出其意义。\

VJ

图10-15米锦结矩阵

()6/14/203

原版教学配套课件

10.4有向图和可达性矩阵

/10.4.1有向图

在动态状态中，例如计算机的流程系统中，有向图常常

比无向图更有应用价值。因此，了解有向图的相关概念

和性质是非常必要的。

定义10・21设G是一个有向图，结点u的出度和入度分别

是以u为弧尾和以u为弧头的弧的条数，分别记作"空+⑺

与血夕⑴)。结点u的出度和入度之和称作结点u的度，记作

deg")°

06/14/2013*^^^

2013-3-1336

原版教学配套课件

如在图10・16所表示的有向图中，有

血夕(匕)=2,deg-(y^=l,4"(匕)=3

deg+(>2)=l，degiy^)=1,deg(v2)=2

+

deg(y^=1,deg,(匕)=1,deg(y3)=2

deg+W/=l,%(乙)=2,deg(v^=3

无向图中的路、迹、通路和回路的

概念都适用于有向图中，只是弧的

方向必须与路的方向相一致。即有

向图G中一条（有向）路是结点和弧

的交替序列

W=r0eirie2V2--ekVkf使得每条弧《从

匕」开诏匕处结束。图10-16有向图示例

06/14/2QU/

2013-3-1337

原版教学配套课件

计算机应用数学基础

定义10-22在有向图中，若有一条从结点匕到结点匕的路，则称匕到匕

是可达的。

例如，图10-16中结点匕到结点』有匕』和匕2匕/两条路，故匕到匕可

达的。

•定义10-23设有有向图G,

(1)若略去弧的方向后，G成为连通的无向图，则称G是弱连通的；

(2)若G中任意两个结点之间，至少有一个结点到另一个结点是可达

的，则称G是单向连通的；

(3)若G中任意两个结点之间是相互可达的，则称G是强连通的。

从定义可知：若图G是单向连通的，则必是弱连通的；若图G是强连

通的，则必是单向连通的，且也是弱连通的。但反之不成立。

06/14/2013*^^^^

■M1LH2013-3-1338

原版教学配套课件

如图1047所示，根据定义10・23可以得出3个有向图中:

（加是强连通的，是单向连通的，（c）是弱连通的。

S10-17育同图连遹性的示例

()6/14/201

2013-3-1339

原版教学配套课件

计算机应用数学基础

定理10・5一个有向图G是强连通的，当且仅当G中有一个

(有向)回路，它至少包含每个结点一次。

•证明

(1)必要性：如果有向图G是强连通的，则任意两个结点

都是相互可达的。故必有一回路经过图中所有各结点。

否则，必有一条回路不包含某一结点匕。这样，匕与回路

上各结点就不能相互可达，这与G是强连通矛盾。

(2)充分性：如果G中有一个回路，那么它至少包含每个

结点一次，则G中任意两个结点是相互可达的，故G是强

连通的。

例如，图中图(〃)是强连通的，有一回路为

匕方匕匕，它包含图中所有结点。06/14/2013*^^^^

2013-3-1340

原版教学配套课件

定义10.24在有向图G=（V,£）中，设G，是G的子图。若

G，是强连通的（单向连通的、弱连通的），G中没有包含G，

的更大的子图是强连通的（单向连通的、弱连通的），则称

G，是G的强分图（单向分图、弱分图）。

在图10・18的有向图中，因为结点诃与任何别的结点都不

相互可达，也可称为（｛%｝,。）是一个强分图。

可以看出该有向图的强分图的集是：

｛（｛匕/2/3｝，｛与《2，％｝），（｛也｝，°），（｛%｝，0），（｛如，°）｝；

•弱分图的集是：人飞.引

｛（｛》，叱，勺匕，%与｝，。/'\打

算机应用数学基础

若在结点集V上定义关系。为：匕夕！当且仅当4和匕♦在同

一强(弱)分图中。容易证明，。是一个等价关索。这

种等价关系把V中的结点分成若干个等价类，等价类的集

合是V上的一个划分。每一个等价类的结点以及相应的边

导出一个强(弱)分图。由此有下面的定理。

定理10・6在有向图6=(V,E)中，G的每一个结点都

在也只在一个强(弱)分图中。

10.4.2有向图的可达性

下面用矩阵来研究有向图的可达性。

与无向图一样，有向图也能用相应的邻接矩阵4=(4.)

表示，其中p(<匕，勺〉£均

“"jo(<vz.,vy>^E)

注意，这里A不一定是对称的。

()6/14/201A

2013-3-1342

原版教学配套课件

计算机应用数学基础

则〃阶方阵。=%）称为图G的可达性矩阵。其中

1（匕到v-可达）

IzJ

Pij\o（匕到匕不可达）

IJ

根据可达性矩阵，可知图中任意两个结点之间是否至少

存在一条路以及是否存在回路。

由10.2节定理10・3及其推论可知，利用有向图的邻接矩阵

A,分以下两步可得到可达性矩阵。

•（1）令5〃=A+A2+…+4%

（2）将矩阵3〃中不为零的元素均改为1,为零的元素

不变，所得的矩阵P就是可达性矩阵。

（）6/14/2013<^^

2013-3-1343

原版教学配套课件

计算机应用数学基础

一种简便的方法。

因为可达性矩阵是一个元素仅为I或0的矩阵（称为布

尔矩阵），而在研究可达性问题时，对两个结点间有路

的数目并不感兴趣，所关心的只是两结点间是否存在

路，所以，可将矩阵A,A2,A"分别改为布尔矩阵A

⑴，A⑵，…，A⑻o

说明集合｛0,1｝中的二元运算八和V定义如下：

0V0=0OV1=1VO=1V1=1

1A1=11AO=OA1=OAO=O

分别称八、V为布尔加和布尔乘积运算。

()6/14/20

2013-3-1344

原版教学配套课件

定义10・26两个布尔矩阵中，若将矩阵运算中元素的相加

和相乘均规定为布尔加和布尔乘，则这种矩阵运算称为

布尔矩阵运算，相应的矩阵加法和乘法称为矩阵的布尔

加V和布尔乘八。

•由此有

A⑵=A(1)AA(1)=AAA

A(3)=A(2)AA(0

A(n)=A(n-1)AA⑴

P=A⑴VA⑵V...VA⑺

例10・7求出图10・19所示图的可达性矩阵。

解该根据图示，可得邻接矩阵为：

"0100"

0010

A=

1100

J110,

A⑴-A图10-19戏可达矩阵

<0100］仅100、'0010、,1100、'0110、

0100010110001101110

A心=4（钓=

1001100011011101110

11»U110?J110；U1107(1110,

‘1110、

人心+人⑵+心+心二1,10

1110

U11oj

()6/14/201

2013-3-1346

原版教学配套课件

计算机应用数学基础

定理10・7有向图G是强连通的当且仅当其可达性矩阵P除

主对角线外，其他元素均为1。

下面介绍如何利用一个图的可达性矩阵，求出这个图的

强分图。

设尸=(pQ是图G的〃阶可达性矩阵，P'是P的转置矩

阵，定义矩阵运算P尸为

由定义，如果从结点匕到，是可达的，则应有

〃=1；如果从结点，到匕是可达的，则应有P7=1o因

此，结点匕.和匕.是相互可达的，当且仅当矩阵PO尸的

(i,J)项元素(，壬/)PijPji=1。这样，若矩阵PP的第

i行的非零元素在第打…，/洌，则结点匕，%，

vj2,力为强连通子图的结点。

()6/14/20

2013-3-1347

原版教学配套课件

(p〃p…PQP：Pl2P21…PP

12(%P2I…P3lnnl

P21022…P2nP12022P〃2P21Pl2P；…02"尸"2

Pop'=0—

・•・・♦・•・.・・・・•・・・・

<Pn2…PJHI><^2n••P〃n>5//〃Pn2P2”…「I

如对本节图10・18的图可求出的可达性矩阵P为:

’111110、q11110、111000、q11000、

111110111110111000111000

111110111110111000111000

P°P=0——

000010000010111000000000

000000000000111101000000

、000010,<000010)、000000,00000,

由此也可求出该有向图的强分图点集是：

V9

｛匕，2匕｝，仇｝'｛也｝'｛中O

()6/14/201

2013-3-1348

原版教学配套课件

例10・8在操作系统中，设在时亥！有多道程序尸「

尸2,…，尸皿运行，系统的资源，J々，…，〃被运行中的

程序所占用。若占用八的程序尸及又对资源勺提出要求时，

则从结点外出发引一秦有向边写0相连，用〃个结点占，

々，…，却分别表示〃个资源，这伴得到有〃个结点的有向

图，它是某一时刻机器内的资源分配状态图。

假如有资源分配状态如图10・20所示，对该图讨论“死锁”

问题。

图10.如计算机和讴分配伏态图

()6/14/2£J.

2013-3-1349

原版教学配套课件

在该图中，4占有也对6提出要求；尸2占有，2,对

心，Q提出要象；尸3占有，3，对rpQ提出要求;尸4占有

Q，对0，提出要求。这时资嬴勺，心，Q无法从被

占有的状态中释放出来，我们说此刻系统处于“死锁”状

O

可以看出，当且仅当资源分配状态图G包含多于一个结

点的强分图时，系统才在，时刻发生“死锁”，故可用前述

的矩阵方法去识别是否包含多于一个结点的强分图，从

而检查出“死锁”状态。

()6/14/20LW

2013-3-1350

原版教学配套课件

10.5欧拉图与哈密尔顿图

/10・5.1欧拉图

哥尼斯堡七桥问题是历史上著名的图论问题。

问题是这样的：在18世纪的东普鲁士的个哥尼斯堡城

市，有条横贯全城的普雷格尔河和两个岛屿，在河的两

岸与岛屿之间架设了7座桥，把它们连接起来（如图

21所示）。

每逢假日，城中居民进行环城游玩，人们对此提出了一

个“遍游”问题：能否设计一种走法，使得从某地出发通

过且只通过每座桥一次后又回到原地呢？

可以将图10.21中的哥尼斯堡城的4块陆地分别标以A,

B,C,D,将陆地设想为图的结点，而把桥画成相应的

l连接边，所以，图10-21可简化为图10.22所示。06/14/2013*^^^^

2013-3-1351

原版教学配套课件

c

于是，七桥“遍游”问题等价于在图io・22中，从某一结点

出发找到一条迹，通过它的每条边一次且仅一次，并回

到原来的结点。

下面通过介绍几个定义和定理来讨论七桥问题的求解。

()6/14/201

2013-3-1352

原版教学配套课件

定义10・27给定无孤立结点的图G,若存在一条经过G中

每边一次且仅一次的回路，则该回路为欧拉回路。具有

欧拉回路的图称为欧拉图。

例如，给出如图10・23所示的两个图，根据定义10・25可以

得出，（〃）是欧拉图，而S不是欧拉图。

S10-23次位图示例

()6/14/201

2013-3-1353

原版教学配套课件

定理10.8连通图G是欧拉图的充要条件是G的所有结点的

度数都是偶数（这样的结点称为偶度结点）。

证明

•必要性：设G是一欧拉图，a是G中的一条欧拉回

路。当a通过G的任一结点时，必通过关联于该点的

两条边。又因为G中的每条边仅出现一次，所以a所

通过的每个结点必定是偶度结点。

•充分性：我们可以这样来作一个封闭的迹万，假设它

从某结点Z开始，沿着一条边到另一结点，接着再从

这个结点，沿着没有走过的边前进，如此继续走下

去。因为总是沿着先前没有走过的新边走，又由于图

©边数有限，所以