第十章 图的概念与表示
10.1 图的基本概念
10.2 链 (或路 )与圈 (或回路 )
10.3 图的矩阵表示退出
10.1 图的基本概念什么是图?可用一句话概括,即：图是用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型 。 因为它显得太抽象,
不便于理解,所以有必要给出另外的回答 。 下面便是把图作为代数结构的一个定义 。
定义 10.1.1 一个图 G定义为一个三元组 <V，
E,φ>，记作 G=<V,E,φ>。其中 V是个非空有限集合，它的元素称为结点； E也是个有限集合，其元素称为边，而 φ是从 E到 V中的有序对或无序对的映射。
由定义可知，图 G中的每条边都与图中的无序或有序结点对相联系的。若边 e∈ E与无序结点对 〔 vi,vj〕 相联系，则 φ(e)=〔 vi,vj〕,
这时边 e称为无向边，有时简称为边；若边 e∈ E
与有序结点对 <vi,vj>相联系，则 φ(e)=<vi,vj>，
此时边 e称为有向边或弧,vi称为弧 e的始结点，
vj称为弧 e的终结点。
若结点 vi与 vj由一条边 (或弧 )e所联结，则称结点 vi和 vj是边 (或弧 )e的端结点；同时也称结点
vi与 vj是邻接结点，记作 vi adj vj；否则为非邻接结点，记作 vi nadj vj；也说边 (或弧 )e关联 vi与 vj
或说结点 vi与 vj关联边 (或弧 )e。关联同一个结点的两条边或弧称为邻接边或弧。而联结一结点与它自身的一条边，称为环。环的方向是无意义的。
如果把图 G中的弧或边总看作联结两个结点，则图 G可简记为 G=<V,E>，其中 V是非空结点集,E是联结结点的边集或弧集。
定义 10.1.2 在图 G=<V,E>中，如果每条边都是弧，该图称为有向图；若每条边都是无向边，该图 G称为无向图；如果有些边是有向边，
另一些边是无向边，图 G称为混合图。
定义 10.1.3 在图 G=<V,E>中,如果任何两结点间不多于一条边 (对于有向图中,任何两结点间不多于一条同向弧 ),并且任何结点无环,
则图 G称为简单图；若两结点间多于一条边 (对于有向图中,两结点间多于一条同向弧 )图 G称为多重图,并把联结两结点之间的多条边或弧,
称为平行边或弧,平行边或弧的条数称为重数 。
定义 10.1.4 给每条边或弧都赋予权的图
G=<V,E>,称为加权图,记为 G=<V,E,W>，
其中 W表示各边之权的集合 。
加权图在实际中有许多应用,如在输油管系统图中权表示单位时间流经管中的石油数量；
在城市街道中,权表示表示通行车辆密度；在航空交通图中,权表示两城市的距离等等 。
定义 10.1.5 在无向图 G=<V,E>中,如果 V
中的每个结点都与其余的所有结点邻接,即
(?vi)(?vj)(vi,vj∈ V→ 〔 vi,vj〕 ∈ E)
则该图称为无向完全图,记作 K|V| 。 若
|V|=n,该图记作 Kn。
在一个图中,如果一个结点不与任何其他结点邻接,则该结点称为孤立结点 。
仅有孤立结点的图称为零图 。 显然,在零图中边集为空集 。 若一个图中只含一个孤立结点,该图称为平凡图 。
定义 10.1.6 在有向图 G=<V,E>中,对任意结点 v∈ V,以 v为始结点的弧的条数,称为结点 v的出度,记为 d+(v)；以 v为终结点的弧的条条数,称为 v的入度,记作 d-(v)；结点 v的出度与入度之和,称为结点的度数,记为 d(v),显然
d(v)=d+(v)+d-(v)。
对于无向图 G=<V,E>,结点 v∈ V的度数等于联结它的边数,也记为 d(v)。 若 v点有环,
规定该点度因环而增加 2。
显然，对于孤立结点的度数为零。
此外，对于无向图 G=<V,E>，记
Δ(G)或 Δ=max{d(v)|v∈ V}
δ(G)或 δ=min{d(v)|v∈ V}
它们分别称为图 G的最大度和最小度。
关于无向图中的结点的度，欧拉给出一个定理，这是图论中的第一个定理。
定理 10.1.1 给定无向图 G=<V,E>，则定理 10.1.2 在任何无向图中，奇度结点的数目为偶数。
定义 10.1.7 在无向图 G=<V,E>中,如果每个结点的度是 k,即 (?v)(v∈ V→ d(v)=k),则图 G称为 k度正则图 。
显然,对于 k度正则图 G,Δ(G)=δ(G)=k。
定义 10.1.8 给定无向图 G1=<V1,E1>和
G2=<V2,E2>,于是
(1) 如果 V2?V1和 E2?E1,则称 G2为 G1的子图,记为 G2?G1。
(2) 如果 V2?V1,E2?E1且 E2≠E1,则称 G2为
G1的真子图,记为 G2?G1。
(3) 如果 V2=V1,E2?E1,则称 G2为 G1的生成子图,记为 G2 G1。
定义 10.1.9 设图 G2=<V2,E2>是图 G1=<V1，
E1>的子图 。 若对任意结点 u和 v,如果 〔 u,v〕
∈ E1,有 〔 u,v〕 ∈ E2,则 G2由 V2唯一地确定,
并称 G2是结点集合 V2的诱导子图,记作 <V2>或
G〔 V2〕 ；如果 G2无孤立结点,且由 E2所唯一确定,则称 G2是边集 E2的诱导子图,记为 <E2>
或 G〔 E2〕 。
定义 10.1.10 设图 G1=<V1,E1>和图
G2=<V2,E2>是图 G=<V,E>的子图 。 如果 E2=E-E1且 G2=<E2>,则称图 G2是相对于图 G的子图 G1的补图 。
定义 10.1.11 给定图 G=<V,E>,若存在图
G1=<V,E1>,并且 E1∩E=?和图 <V,E1∪ E>是完全图,则 G1称为相对于完全图的 G的补图,
简称 G1是 G的补图,并记为 G1= 。
显然,G与 互为补图 。
在图的定义中,强调的是结点集,边集以及边与结点的关联关系,既没有涉及到联结两个结点的边的长度,形状和位置,也没有给出结点的位置或者规定任何次序 。 因此,对于给定的两个图,在它们的图形表示中,即在用小圆圈表示结点和用直线或曲线表示联结两个结点的边的图解中,看起来很不一样,但实际上却是表示同一个图 。 因而,引入两图的同构概念便是十分必要的了 。
定义 10.1.12 给定无向图 (或有向图 )G1=<V1，
E1>和 G2=<V2,E2>。 若存在双射 f∈ V2V1,使得对任意 v,u∈ V1,有 〔 u,v〕 ∈ E1?〔 f(u)，
f(v)〕 ∈ E2(或 <u,v>∈ E1<f(u),f(v)>∈ E2)则称
G1同构于 G2,记为 G1?G2。
显然,两图的同构是相互的,即 G1同构于
G2,G2同构于 G1。
由同构的定义可知,不仅结点之间要具有一一对应关系,而且要求这种对应关系保持结点间的邻接关系 。 对于有向图的同构还要求保持边的方向 。
一般说来,证明两个图是同构的并非是轻而易举的事情,往往需要花些气力 。
请读者证明图 10.1.13中两个图是同构的 。
根据图的同构定义，可以给出图同构的必要条件如下：
(1) 结点数目相等；
(2) 边数相等；
(3) 度数相同的结点数目相等。
但这仅仅是必要条件而不是充分条件。
满足上述三个条件，然而并不同构。因此在 (a)中度数为 3的结点 x与两个度数为 1
的结点邻接，而 (b)中度数为 3的结点 y仅与一个度数为 1的结点邻接。
寻找一种简单有效的方法来判定图的同构，
至今仍是图论中悬而未决的重要课题。
例如图 10.1.14中 (a)与 (b)
图 10.1.13
返回返回图 1.1.14
10.2 链 (或路 )与圈 (或回路 )
在无向图 (或有向图 )的研究中,常常考虑从一个结点出发,沿着一些边 (或弧 )连续移动而达到另一个指定结点,这种依次由结点和边 (或弧 )组成的序列,便形成了链 (或路 )的概念 。
定义 10.2.1 给定无向图 (或有向图 )G=<V，
E>。令 v0,v1,…,vm∈ V，边 (或弧 )e1,e2,…,
em∈ E，其中 vi-1,vi是 ei的结点，交替序列
v0e1v1e2v2… emvm称为连接 v0到 vm的链 (或路 )。 v0
和 vm分别称为链 (或路 )的始结点和终结点，而边
(或弧 )的数目称为链 (或路 )的长度。若 v0=vm时，
该链 (或路 )称为圈 (或回路 )。
定义 10.2.2 在一条链 (或路 )中，若出现的边 (或弧 )都是不相同的，称该链 (或路 )为简单链
(或简单路 )；若出现的结点都是不相同的，称该链 (或路 )为基本链 (或基本路 )。
显然，每条基本链 (或基本路 )必定是简单链 (或简单路 )。
定义 10.2.3 在一圈 (或回路 )中，若出现的每条边 (或弧 )恰好一次，称该圈 (或回路 )为简单圈 (或简单回路 )；若出现的每个结点恰好一次，
称该圈 (或回路 )为基本圈 (或基本回路 )。
可以看出，对于简单图来说，链 (或路 )和圈 (或回路 )能够仅用结点序列表示之。
定理 10.2.1 在一个图中,若从结点 vi到结点 vj存在一条链 (或路 ),则必有一条从 vi到 vj的基本链 (或基本路 )。
定理 10.2.2 在一个具有 n个结点的图中,则
(1) 任何基本链 (或路 )的长度均不大于 n-1。
(2) 任何基本圈 (或路 )的长度均不大于 n。
定义 10.2.4 在一个图中,若从 vi到 vj存在任何一条链 (或路 ),则称从 vi到 vj是可达的,或简称 vi可达 vj。
为完全起见,规定每个结点到其自身是可达的 。
对于无向图 G来说,不难证明结点间的可达性是结点集合上的等价关系 。 因此它将结点集合给出一个划分,并且划分中的每个元素形成一个诱导子图；两结点之间是可达的当且仅当它们属于同一个子图,称这种子图为图 G的连通分图,图 G的连通分图的个数,记为 ω(G)。
定义 10.2.5 若图 G只有一个连通分图，则称 G是连通图；否则，称图 G为非连通图或分离图。
在图的研究中,常常需要考虑删去与增加结点,结点集,边和边集 （ 或弧集 ） 的问题 。
所谓从图 G=<V,E>中删去结点集 S,是指作 V-S
以及从 E中删去与 S中的全部结点相联结的边而得到的子图,记作 G-S；特别当 S=|v|时,简记为
G-v；所谓从图 G=<V,E>中删去边集 （ 或弧集 ）
T,是指作 E-T,且 T中的全部边所关联的结点仍在 V中而得到的子图,记为 G-T；特别当 T={e}
时,简记作 G-e。
所谓图 G=<V,E>增加结点集 S，是指作
V∪ T以及向 E中并入 S中,S与 V中所成的边而得到的图，记作 G+S；特别当 S={v}时，简记为
G+v；图 G=<V,E>增加边集（或弧集） T是指作
E∪ T所得到的图，记作 G+T，这里 T中全部边
（或弧）的关联结点属于 V。
定义 10.2.6 给定连通无向图 G=<V,E>，
S?V。若 ω(G-S)＞ ω(G)，但?T?S有?(G-
T)=?(G)，则称 S是 G的一个分离结点集。若图 G
的分离结点集 S={v}，则称 v是 G的割点。
类似地可定义图 G的分离边集 T；若图 G的分离边集 T={e}，则称 e是 G的割边或桥。
对于连通的非平凡图 G,称?(G)= {|S||S
是 G的分离结点集 }为图 G的结点连通度,它表明产生不连通图而需要删去结点的最少数目 。
于是,对于分离图 G,?(G)=0；对于存在割点的连通图 G,?(G)=1。
类似地定义边连通度?(G)= {|T||T是 G
的分离边集 }，它表明产生不连通图而需要删去边的最少数目。可见，对于分离图 G,?(G)=0；
对于完全图 G,?(G)=0；对于图 K1,?(K1)=0；
对于存在割边的连通图 G,?(G)=1；对于完全图
Kn,?(Kn)=n-1。
下面是由惠特尼 (H.Whitney)于 1932年得到的关于结点连通度、边连通度和最小度的不等式联系的定理：
定理 10.2.3 对于任何一个无向图 G，有
(G)≤?(G)≤δ(G)。
定理 10.2.4 一个连通无向图 G中的结点 v是割点?存在两个结点 u和 w,使得联结 u和 w的每条链都经过 v。
定理 10.2.5 一个连通无向图 G中的边 e是割
u和 w,使得联结 u与 w的每条链都经过 e。
下面再给出一个判定一条边是割边的充要条件 。
定理 10.2.6 连通无向图 G中的一条边 e是割边?e不包含在图的任何基本圈中 。
对于有向图而言,结点间的可达性不再是等价关系,它仅仅是自反的和传递的 。 一般说来,不是对称的 。 因此,有向图的连通概念较之无向图要复杂得多 。
对于给定的有向力 G,要略去 G中每条边的方向便得到一个无向图 G1,称 G1是 G的基础图 。
定义 10.2.7 在简单有向图 G中，若 G中任何两个结点间都是可达的，则称 G是强连通的；若任何两个结点间至少是从一个结点可达另一个结点，则称 G是单向连通的；若有向图 G不是单向连通的，但其基础图是连通的，则称 G是弱连通的。
从上面定义可知,若图 G是强连通的,则它必是单向连通的,但反之未必真；若图 G是单向连通的,则它必是弱连通的,反之不真 。
定理 10.2.7 有向图 G是强连通的?G中有一回路,它至少通过每个结点一次 。
令 G是简单有向图,对于某种性质而言,
若 G中再没有其它包含子图 G1的真子图具有这种性质,则称 G1是 G的关于该性质的极大子图 。
定义 10.2.8 在简单有向图中,具有强连通性质的极大子图,称为强分图；具有单向连通性质的极大子图,称为单向分图；具有弱连通性质的极大子图,称为弱分图 。
定理 10.2.8 简单有向图中的任一个结点恰位于一个强分图中 。
注意,有向图中的任意一弧未必恰位于一个强分图中,例如,在图 10.2.6中,弧 <v1,v2>位于 结 点 集 合 {v1,v2,v3} 的 诱 导 子 图 中,但弧
<v3,v4>不位于任何强分图之中 。
类似地可以证明下面两个定理：
定理 10.2.9 简单有向图中的每个结点和每条弧至少位于一个单向分图中。
定理 10.2.10 简单有向图中的每个结点和每条弧恰位于一个弱分图中。
如果结点 u可达结点 v，它们之间可能存在不止一条链 (或路 )。在所有这些链 (或路 )中，最短链 (或路 )的长度称为结点 u和 v之间的距离或短程线或测地线，记作 d<u,v>。
距离满足下列性质：
d<u,v>≥0
d<u,u>=0
d<u,v>+d<v,w>≥d<u,w>
如果 u不可达 v，则 d<u,v>=+∞。
此外，要注意，即使 u与 v相互可达,d<u，
v>未必等于 d<v,u>。
下面给出简单有向图的一个应用 —— 资源分配图。
在多道程序的计算机系统中，可以同时执行多个程序。实际上，程序共享计算机系统中的资源，如磁带机、磁盘设备,CPU、主存贮器和编译程序等。操作系统对这些资源负责分配给各个程序。当一个程序要求使用某种资源，
它要发出请求，操作系统必须保证这一请求得到满足。
对资源的请求可能发生冲突。如程序 A控制着资源 r1，请求资源 r2；但程序 B控制着资源
r2，请求资源 r1。这种情况称为处于死锁状态。
然而冲突的请求必须解决，资源分配图有助发现和纠正死锁。
假设某一程序对一些资源的请求，在该程序运行完之前必须都得到满足。在请求的时间里，被请求的资源是不能利用的，程序控制着可利用的资源，但对不可利用的资源则必须等待。
令 Pt={p1,p2,…,pm}表示计算机系统在时间 t的程序集合,Qt?Pt是运行的程序集合，或者说在时刻 t至少分配一部分所请求的资源的程序集合。 Rt={r1,r2,…,rn}是系统在时刻 t的资源集合。资源分配图 Gt=<Rt,E>是有向图，
它表示了时间 t系统中资源分配状态。把每个资源 ri看作图中一个结点，其中 i=1,2,…,n。
<ri,rj>表示有向边,<ri,rj>∈ E当且仅当程序
pk∈ Qt已分配到资源 ri且等待资源 rj。
例如，令 Rt={r1,r2,r3,r4},Qt={p1,p2,p3,p4}。
资源分配状态是：
p1占用资源 r4且请求资源 r1；
p2占用资源 r1且请求资源 r2和 r3；
p3占用资源 r2且请求资源 r3；
p4占用资源 r3且请求资源 r1和 r4。
于是，可得到资源分配图 Gt=<Rt,E>，如图
10.2.7所示。
能够证明，在时刻 t计算机系统处于死锁状态?资源分配图 Gt中包含强分图。于是，对于图 10.2.7,Gt是强连通的，即处于死锁状态。
图 10.2.7
10.3 图的矩阵表示给定一个图 G=<V,E>,使用图形表示法很容易把图的结构展现出来,而且这种表示直观明了 。 但这只在结点和边 (或弧 )的数目相当小的情况下才是可行的 。 显然这限制了图的利用 。
本节提供另一种图的表示法 —— 图的矩阵表示法 。 它不仅克服了图形表示法的不足,而且这种表示可以充分利用现代工具电子计算机,以达到研究图的目的 。
一个简单图 G=<V,E>由 V中每两个结点间的邻接关系唯一地确定，这种关系可以用一个矩阵给出，而矩阵形式与图中结点的编序有密切关系，这是用矩阵表示图值得注意的一点。
定义 10.3.1 给定简单图 G=<V,E>,V={v1，
v2,…,vn},V中的结点按下标由小到大编序，
则 n阶方阵 A=(aij)称为图 G的邻接矩阵。其中
i,j=1,2,…,n。
有时为强调邻接矩阵依赖于图 G，把图 G的邻接矩阵记为 A(G)。
对于给定图 G,显然不会因结点编序不同而使其结构发生任何变化,即图的结点所有不同的编序实际上仍表示同一个图 。 换句话说,
这些结点的不同编序的图都是同构的,并且它们的邻接矩阵都是相似的 。 于是
G?H?存在置换矩阵 P,使 A(H)=P-1A(G)P
今后将略去这种由于 V中结点编序而引起邻接矩阵的任意性,而取该图的任一个邻接矩阵作为该图的矩阵表示 。
邻接矩阵可展示相应图的一些性质：
若邻接矩阵的元素全为零，则其对应的图是零图；
若邻接矩阵的元素除主对角线元素外全为 1，
则其对应的图是连通的且为简单完全图。
此外，当给定的简单图是无向图时，邻接矩阵是对称矩阵；反之，若给定任何对称矩阵 A，
显然可以唯一地作出以 A为其邻接矩阵的简单图
G。于是，所有 n个结点的不同编序的简单图的集合与所有 n阶对称矩阵的集合可建立一一对应。
当给一的图是简单有向图时，其邻接矩阵并非一定是对称矩阵，但所有 n个结点的不同编序的简单图的集合，与所有 n阶邻接矩阵的集合亦可建立一一对应。
不仅如此，通过对矩阵元素的一些计算还可以得到对应图的某些数量的特征。
在给定简单有向图的邻接矩阵中，第 i行元素是由结点 vi出发的弧所确定，故第 i行中值为 1
的元素数目等于结点 vi的出度。同理，第 j列中值为 1的元素数目等于结点 vj的入度。即 d+(vi)=
和 d-(vj)= 。
由给定简单图 G的邻接矩阵 A可计算出矩阵
A的 l次幂，即 Al。若第 i行第 j列上的元素 alij便是
G中从第 i个结点 vi到第 j个结点 vj长度为 l的链
（或路）的数目。为说明此事实，今给出下面定理。
定理 10.3.1 设 A为简单图 G的邻接矩阵，则
Al中的 i行 j列元素 alij等于 G中联结 vi到 vj的长度为 l
的链 (或路 )的数目。
在一些实际问题中,有时要判定图中结点
vi到结点 vj是否可达,或者说 vi到 vj是否存在一要链 （ 或路 ） 。 如果要利用图 G的邻接矩阵 A,则应计算 A2,A3,···,An,··。 当发现其中某个 Ar
中 ≥1,就表明 vi可达 vj或 vi到 vj存在一条链
（ 或路 ） 。 但这种计算繁琐量大,又不知计算
Ar到何时为止 。
根据定理 10.2.2可知，对于有 n个结点的图，
任何基本链（或路）的长度不大于 n-1和任何基本圈（或回路）的长度不大于 n。因此，只需考虑 就可以了，其中 1≤r≤n。即只要计算
Bn=A+A2+A3+··+An。
如果关心的是结点间可达性或结点间是否有链（或路），至于结点间的链存在多少条及长度是多少无关紧要，那么便可用下面的定义图的可达矩阵来表示结点间可达性。
定义 10.3.2 给定图 G=<V,E>，将其结点按下标编序得 V={v1,v2,…,vn}。定义一个 n
阶方阵 P=(pij)，其中
1 vi到 vj可达
Pij=
0 否则则称矩阵 P是图 G的可达矩阵。
{
可见，可达矩阵表明了图中任意两结点间是否至少存在一条链 (或路 )以及在结点处是否有圈 (或回路 )。
从图 G的邻接矩阵 A可以得到可达矩阵 P，
即令 Bn=A+A2+A3+…+ An，再从 Bn中非零元素改为 1而零元素不变，这种变换后的矩阵即是可达矩阵 P。
假 设 矩 阵 中 的 元 素 是 属 于 布 尔 代 数
<B,?,?,ˉ,0,1>的 B中元素,其中 B={0,1},则称该矩阵为布尔矩阵 。 显然邻接矩阵是一个布尔矩阵,同样可达矩阵也是布尔矩阵 。 下面定义两个布尔矩阵 B与 C的运算：
令 B和 C的布尔和、布尔积分别记为 B?C和
BoC，其定义为
(B?C)ij=bij?cij
(BoC)ij= (bik?ckj)
i,j=1,2,··,n。其中 bij,cij分别是 B和 C的 i行 j
列元素。
特别地，对于邻接矩阵 A，记 AoA=A(2)，对任何 r=2,3,··,有
A(r-1)oA=A(r)
要注意的是 Ar与 A(r)的差别。 Ar中 表明从
vi到 vj长度为 r的链（或路）的数目，而 A(r)中是指出：若 vi到 vj至少存在一条链（或路）时，
=1，否则,=0。
由上说明，便得到可达矩阵 P为：
P=A?A(2)?A(3)?···?A(n)= A(k)
对于简单有向图 G=<V,E>,显然有
E?V?V。 因此,弧集合 E可解释成 B中的二元关系,而二元关系是可用矩阵表示的,
通常称这种矩阵为关系矩阵,其定义如下：
设两个有限集合 X={x1,x2,··,xm}和
Y={y1,y2,··,yn}，则关系 R?X?Y的关系矩阵
MR=(rij)，其中
1,<xi,yi>?R
rij=
0,否则
i=1,2,··,m； j=1,2,··,n。
{
由定义可知，关系 R与其关系矩阵 MR是一一对应的，即可以相互确定。
根据集合论可知，对于域 F(R)=V而 |V|=n的关系 R的传递闭包 R+可计算如下：
R+=R∪ R2∪ R3∪ ···∪ Rk (k≤n)
于是，关系 R1和 R2的关系矩阵分别为 A1和
A2，则关系 R1∪ R2的关系矩阵为 A1?A2。用归纳法可以证明 R+的关系矩阵是
=···?
对于 G=<V,E>的邻接矩阵 A是关系 E的关系矩阵，因为 E2=EoE，即若存在一个结点 vk，使得 viEvk，和 vkEvj，则必有 viE2vj，亦即从 vi到 vj若至少存在一条长度为 2的链（或路），那么 E2的关系矩阵中的 (i,j)元素值为 1。这表明矩阵 A(2)是关系 E2的关系矩阵。以此类推,A(k)是 Ek的关系矩阵,k=2,3,··,n。因此
A+=A?A(2)?A(3)?···?A(n)
亦即 A+=A?A(2)?A(3)?···?A(n)=P
可见，关系 E的传递闭包 E+的关系矩阵 A+
与可达矩阵相同。
为了计算 A+或 P，自然可先依次求得 A(2)，
A(3),···,A(n)，然后再计算 A(k)，其结果即为所求，这是计算 A+或 P的一种方法，还可介绍一种现有效的方法 — Warshall算法，它由邻接矩阵 A依下面给出的步骤便能计算 A+。其步骤如下：
(1) P?A
(2) k?1
(3) i?1
(4) 若 pik=1，对 j=1,2,··,n作 pij?pij?pkj
(5) i?i+1，若 i≤n则转 (4)
(6) k?k+1，若 k≤n则转到 (3)，否则停止。
该算法的关键的一步是 (4)，它判定如果
pik=1，将第 i行和第 k行的各对应元素作布尔和或逻辑加后送到第 i行中去。
给定关系 E1和关系 E2,它们的关系矩阵分别为 A=(aij)和 B=(bij),则关系交 E1∩E2的关系矩阵记为 A∧ B,其定义如下：
(A∧ B)ij=aij∧ bij
于是,由可达矩阵和利用关系交的关系矩阵可求出包含图中任何指定结点的强分图 。
定理 10.3.2 给定简单有向图 G中的任意结点 vi,若 P=(pij)是 G的可达矩阵,PT=(pji)是 P的转置矩阵,则 P∧ PT的第 i行元素为 1的列号为下标的结点构成了包含 vi的强分图 。
利用简单有向图的可达矩阵,能够确定某过程是否为递归的 。
假设 VP={p1,p2,··,pn}是程序 P中的过程集合,
做有向图 G=<VP,E>,其中 pi?VP,i=1,2,··,n；
<pi,pj>?E?pi调用 pj。 如果图 G中有包含 pi的回路,则可断言 pi是递归的 。 为此,由图 G的邻接矩阵 A=(aij)计算出可达矩阵 A+=( )。 如果 A+中的主对角线上的某元素 =1,则 pi是递归的 。
在图的矩阵表示中,除邻接矩阵外,
还有关联矩阵,圈 （ 或回路 ） 矩阵,权矩阵等,在此就不都予涉及了,只是再给出权矩阵的概念以结束本小节 。
已知加权的简单图 G=<V,E>，定义一个矩阵 W=(wij)，其中：
w,w是边 [vi,vj]（或弧 <vi,vj>）?E
的权
wij=
0,vi与 vj不相邻则称 W为图 G的权矩阵
{
10.1 图的基本概念
10.2 链 (或路 )与圈 (或回路 )
10.3 图的矩阵表示退出
10.1 图的基本概念什么是图?可用一句话概括,即：图是用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型 。 因为它显得太抽象,
不便于理解,所以有必要给出另外的回答 。 下面便是把图作为代数结构的一个定义 。
定义 10.1.1 一个图 G定义为一个三元组 <V，
E,φ>，记作 G=<V,E,φ>。其中 V是个非空有限集合，它的元素称为结点； E也是个有限集合，其元素称为边，而 φ是从 E到 V中的有序对或无序对的映射。
由定义可知，图 G中的每条边都与图中的无序或有序结点对相联系的。若边 e∈ E与无序结点对 〔 vi,vj〕 相联系，则 φ(e)=〔 vi,vj〕,
这时边 e称为无向边，有时简称为边；若边 e∈ E
与有序结点对 <vi,vj>相联系，则 φ(e)=<vi,vj>，
此时边 e称为有向边或弧,vi称为弧 e的始结点，
vj称为弧 e的终结点。
若结点 vi与 vj由一条边 (或弧 )e所联结，则称结点 vi和 vj是边 (或弧 )e的端结点；同时也称结点
vi与 vj是邻接结点，记作 vi adj vj；否则为非邻接结点，记作 vi nadj vj；也说边 (或弧 )e关联 vi与 vj
或说结点 vi与 vj关联边 (或弧 )e。关联同一个结点的两条边或弧称为邻接边或弧。而联结一结点与它自身的一条边，称为环。环的方向是无意义的。
如果把图 G中的弧或边总看作联结两个结点，则图 G可简记为 G=<V,E>，其中 V是非空结点集,E是联结结点的边集或弧集。
定义 10.1.2 在图 G=<V,E>中，如果每条边都是弧，该图称为有向图；若每条边都是无向边，该图 G称为无向图；如果有些边是有向边，
另一些边是无向边，图 G称为混合图。
定义 10.1.3 在图 G=<V,E>中,如果任何两结点间不多于一条边 (对于有向图中,任何两结点间不多于一条同向弧 ),并且任何结点无环,
则图 G称为简单图；若两结点间多于一条边 (对于有向图中,两结点间多于一条同向弧 )图 G称为多重图,并把联结两结点之间的多条边或弧,
称为平行边或弧,平行边或弧的条数称为重数 。
定义 10.1.4 给每条边或弧都赋予权的图
G=<V,E>,称为加权图,记为 G=<V,E,W>，
其中 W表示各边之权的集合 。
加权图在实际中有许多应用,如在输油管系统图中权表示单位时间流经管中的石油数量；
在城市街道中,权表示表示通行车辆密度；在航空交通图中,权表示两城市的距离等等 。
定义 10.1.5 在无向图 G=<V,E>中,如果 V
中的每个结点都与其余的所有结点邻接,即
(?vi)(?vj)(vi,vj∈ V→ 〔 vi,vj〕 ∈ E)
则该图称为无向完全图,记作 K|V| 。 若
|V|=n,该图记作 Kn。
在一个图中,如果一个结点不与任何其他结点邻接,则该结点称为孤立结点 。
仅有孤立结点的图称为零图 。 显然,在零图中边集为空集 。 若一个图中只含一个孤立结点,该图称为平凡图 。
定义 10.1.6 在有向图 G=<V,E>中,对任意结点 v∈ V,以 v为始结点的弧的条数,称为结点 v的出度,记为 d+(v)；以 v为终结点的弧的条条数,称为 v的入度,记作 d-(v)；结点 v的出度与入度之和,称为结点的度数,记为 d(v),显然
d(v)=d+(v)+d-(v)。
对于无向图 G=<V,E>,结点 v∈ V的度数等于联结它的边数,也记为 d(v)。 若 v点有环,
规定该点度因环而增加 2。
显然，对于孤立结点的度数为零。
此外，对于无向图 G=<V,E>，记
Δ(G)或 Δ=max{d(v)|v∈ V}
δ(G)或 δ=min{d(v)|v∈ V}
它们分别称为图 G的最大度和最小度。
关于无向图中的结点的度，欧拉给出一个定理，这是图论中的第一个定理。
定理 10.1.1 给定无向图 G=<V,E>，则定理 10.1.2 在任何无向图中，奇度结点的数目为偶数。
定义 10.1.7 在无向图 G=<V,E>中,如果每个结点的度是 k,即 (?v)(v∈ V→ d(v)=k),则图 G称为 k度正则图 。
显然,对于 k度正则图 G,Δ(G)=δ(G)=k。
定义 10.1.8 给定无向图 G1=<V1,E1>和
G2=<V2,E2>,于是
(1) 如果 V2?V1和 E2?E1,则称 G2为 G1的子图,记为 G2?G1。
(2) 如果 V2?V1,E2?E1且 E2≠E1,则称 G2为
G1的真子图,记为 G2?G1。
(3) 如果 V2=V1,E2?E1,则称 G2为 G1的生成子图,记为 G2 G1。
定义 10.1.9 设图 G2=<V2,E2>是图 G1=<V1，
E1>的子图 。 若对任意结点 u和 v,如果 〔 u,v〕
∈ E1,有 〔 u,v〕 ∈ E2,则 G2由 V2唯一地确定,
并称 G2是结点集合 V2的诱导子图,记作 <V2>或
G〔 V2〕 ；如果 G2无孤立结点,且由 E2所唯一确定,则称 G2是边集 E2的诱导子图,记为 <E2>
或 G〔 E2〕 。
定义 10.1.10 设图 G1=<V1,E1>和图
G2=<V2,E2>是图 G=<V,E>的子图 。 如果 E2=E-E1且 G2=<E2>,则称图 G2是相对于图 G的子图 G1的补图 。
定义 10.1.11 给定图 G=<V,E>,若存在图
G1=<V,E1>,并且 E1∩E=?和图 <V,E1∪ E>是完全图,则 G1称为相对于完全图的 G的补图,
简称 G1是 G的补图,并记为 G1= 。
显然,G与 互为补图 。
在图的定义中,强调的是结点集,边集以及边与结点的关联关系,既没有涉及到联结两个结点的边的长度,形状和位置,也没有给出结点的位置或者规定任何次序 。 因此,对于给定的两个图,在它们的图形表示中,即在用小圆圈表示结点和用直线或曲线表示联结两个结点的边的图解中,看起来很不一样,但实际上却是表示同一个图 。 因而,引入两图的同构概念便是十分必要的了 。
定义 10.1.12 给定无向图 (或有向图 )G1=<V1，
E1>和 G2=<V2,E2>。 若存在双射 f∈ V2V1,使得对任意 v,u∈ V1,有 〔 u,v〕 ∈ E1?〔 f(u)，
f(v)〕 ∈ E2(或 <u,v>∈ E1<f(u),f(v)>∈ E2)则称
G1同构于 G2,记为 G1?G2。
显然,两图的同构是相互的,即 G1同构于
G2,G2同构于 G1。
由同构的定义可知,不仅结点之间要具有一一对应关系,而且要求这种对应关系保持结点间的邻接关系 。 对于有向图的同构还要求保持边的方向 。
一般说来,证明两个图是同构的并非是轻而易举的事情,往往需要花些气力 。
请读者证明图 10.1.13中两个图是同构的 。
根据图的同构定义，可以给出图同构的必要条件如下：
(1) 结点数目相等；
(2) 边数相等；
(3) 度数相同的结点数目相等。
但这仅仅是必要条件而不是充分条件。
满足上述三个条件，然而并不同构。因此在 (a)中度数为 3的结点 x与两个度数为 1
的结点邻接，而 (b)中度数为 3的结点 y仅与一个度数为 1的结点邻接。
寻找一种简单有效的方法来判定图的同构，
至今仍是图论中悬而未决的重要课题。
例如图 10.1.14中 (a)与 (b)
图 10.1.13
返回返回图 1.1.14
10.2 链 (或路 )与圈 (或回路 )
在无向图 (或有向图 )的研究中,常常考虑从一个结点出发,沿着一些边 (或弧 )连续移动而达到另一个指定结点,这种依次由结点和边 (或弧 )组成的序列,便形成了链 (或路 )的概念 。
定义 10.2.1 给定无向图 (或有向图 )G=<V，
E>。令 v0,v1,…,vm∈ V，边 (或弧 )e1,e2,…,
em∈ E，其中 vi-1,vi是 ei的结点，交替序列
v0e1v1e2v2… emvm称为连接 v0到 vm的链 (或路 )。 v0
和 vm分别称为链 (或路 )的始结点和终结点，而边
(或弧 )的数目称为链 (或路 )的长度。若 v0=vm时，
该链 (或路 )称为圈 (或回路 )。
定义 10.2.2 在一条链 (或路 )中，若出现的边 (或弧 )都是不相同的，称该链 (或路 )为简单链
(或简单路 )；若出现的结点都是不相同的，称该链 (或路 )为基本链 (或基本路 )。
显然，每条基本链 (或基本路 )必定是简单链 (或简单路 )。
定义 10.2.3 在一圈 (或回路 )中，若出现的每条边 (或弧 )恰好一次，称该圈 (或回路 )为简单圈 (或简单回路 )；若出现的每个结点恰好一次，
称该圈 (或回路 )为基本圈 (或基本回路 )。
可以看出，对于简单图来说，链 (或路 )和圈 (或回路 )能够仅用结点序列表示之。
定理 10.2.1 在一个图中,若从结点 vi到结点 vj存在一条链 (或路 ),则必有一条从 vi到 vj的基本链 (或基本路 )。
定理 10.2.2 在一个具有 n个结点的图中,则
(1) 任何基本链 (或路 )的长度均不大于 n-1。
(2) 任何基本圈 (或路 )的长度均不大于 n。
定义 10.2.4 在一个图中,若从 vi到 vj存在任何一条链 (或路 ),则称从 vi到 vj是可达的,或简称 vi可达 vj。
为完全起见,规定每个结点到其自身是可达的 。
对于无向图 G来说,不难证明结点间的可达性是结点集合上的等价关系 。 因此它将结点集合给出一个划分,并且划分中的每个元素形成一个诱导子图；两结点之间是可达的当且仅当它们属于同一个子图,称这种子图为图 G的连通分图,图 G的连通分图的个数,记为 ω(G)。
定义 10.2.5 若图 G只有一个连通分图，则称 G是连通图；否则，称图 G为非连通图或分离图。
在图的研究中,常常需要考虑删去与增加结点,结点集,边和边集 （ 或弧集 ） 的问题 。
所谓从图 G=<V,E>中删去结点集 S,是指作 V-S
以及从 E中删去与 S中的全部结点相联结的边而得到的子图,记作 G-S；特别当 S=|v|时,简记为
G-v；所谓从图 G=<V,E>中删去边集 （ 或弧集 ）
T,是指作 E-T,且 T中的全部边所关联的结点仍在 V中而得到的子图,记为 G-T；特别当 T={e}
时,简记作 G-e。
所谓图 G=<V,E>增加结点集 S，是指作
V∪ T以及向 E中并入 S中,S与 V中所成的边而得到的图，记作 G+S；特别当 S={v}时，简记为
G+v；图 G=<V,E>增加边集（或弧集） T是指作
E∪ T所得到的图，记作 G+T，这里 T中全部边
（或弧）的关联结点属于 V。
定义 10.2.6 给定连通无向图 G=<V,E>，
S?V。若 ω(G-S)＞ ω(G)，但?T?S有?(G-
T)=?(G)，则称 S是 G的一个分离结点集。若图 G
的分离结点集 S={v}，则称 v是 G的割点。
类似地可定义图 G的分离边集 T；若图 G的分离边集 T={e}，则称 e是 G的割边或桥。
对于连通的非平凡图 G,称?(G)= {|S||S
是 G的分离结点集 }为图 G的结点连通度,它表明产生不连通图而需要删去结点的最少数目 。
于是,对于分离图 G,?(G)=0；对于存在割点的连通图 G,?(G)=1。
类似地定义边连通度?(G)= {|T||T是 G
的分离边集 }，它表明产生不连通图而需要删去边的最少数目。可见，对于分离图 G,?(G)=0；
对于完全图 G,?(G)=0；对于图 K1,?(K1)=0；
对于存在割边的连通图 G,?(G)=1；对于完全图
Kn,?(Kn)=n-1。
下面是由惠特尼 (H.Whitney)于 1932年得到的关于结点连通度、边连通度和最小度的不等式联系的定理：
定理 10.2.3 对于任何一个无向图 G，有
(G)≤?(G)≤δ(G)。
定理 10.2.4 一个连通无向图 G中的结点 v是割点?存在两个结点 u和 w,使得联结 u和 w的每条链都经过 v。
定理 10.2.5 一个连通无向图 G中的边 e是割
u和 w,使得联结 u与 w的每条链都经过 e。
下面再给出一个判定一条边是割边的充要条件 。
定理 10.2.6 连通无向图 G中的一条边 e是割边?e不包含在图的任何基本圈中 。
对于有向图而言,结点间的可达性不再是等价关系,它仅仅是自反的和传递的 。 一般说来,不是对称的 。 因此,有向图的连通概念较之无向图要复杂得多 。
对于给定的有向力 G,要略去 G中每条边的方向便得到一个无向图 G1,称 G1是 G的基础图 。
定义 10.2.7 在简单有向图 G中，若 G中任何两个结点间都是可达的，则称 G是强连通的；若任何两个结点间至少是从一个结点可达另一个结点，则称 G是单向连通的；若有向图 G不是单向连通的，但其基础图是连通的，则称 G是弱连通的。
从上面定义可知,若图 G是强连通的,则它必是单向连通的,但反之未必真；若图 G是单向连通的,则它必是弱连通的,反之不真 。
定理 10.2.7 有向图 G是强连通的?G中有一回路,它至少通过每个结点一次 。
令 G是简单有向图,对于某种性质而言,
若 G中再没有其它包含子图 G1的真子图具有这种性质,则称 G1是 G的关于该性质的极大子图 。
定义 10.2.8 在简单有向图中,具有强连通性质的极大子图,称为强分图；具有单向连通性质的极大子图,称为单向分图；具有弱连通性质的极大子图,称为弱分图 。
定理 10.2.8 简单有向图中的任一个结点恰位于一个强分图中 。
注意,有向图中的任意一弧未必恰位于一个强分图中,例如,在图 10.2.6中,弧 <v1,v2>位于 结 点 集 合 {v1,v2,v3} 的 诱 导 子 图 中,但弧
<v3,v4>不位于任何强分图之中 。
类似地可以证明下面两个定理：
定理 10.2.9 简单有向图中的每个结点和每条弧至少位于一个单向分图中。
定理 10.2.10 简单有向图中的每个结点和每条弧恰位于一个弱分图中。
如果结点 u可达结点 v，它们之间可能存在不止一条链 (或路 )。在所有这些链 (或路 )中，最短链 (或路 )的长度称为结点 u和 v之间的距离或短程线或测地线，记作 d<u,v>。
距离满足下列性质：
d<u,v>≥0
d<u,u>=0
d<u,v>+d<v,w>≥d<u,w>
如果 u不可达 v，则 d<u,v>=+∞。
此外，要注意，即使 u与 v相互可达,d<u，
v>未必等于 d<v,u>。
下面给出简单有向图的一个应用 —— 资源分配图。
在多道程序的计算机系统中，可以同时执行多个程序。实际上，程序共享计算机系统中的资源，如磁带机、磁盘设备,CPU、主存贮器和编译程序等。操作系统对这些资源负责分配给各个程序。当一个程序要求使用某种资源，
它要发出请求，操作系统必须保证这一请求得到满足。
对资源的请求可能发生冲突。如程序 A控制着资源 r1，请求资源 r2；但程序 B控制着资源
r2，请求资源 r1。这种情况称为处于死锁状态。
然而冲突的请求必须解决，资源分配图有助发现和纠正死锁。
假设某一程序对一些资源的请求，在该程序运行完之前必须都得到满足。在请求的时间里，被请求的资源是不能利用的，程序控制着可利用的资源，但对不可利用的资源则必须等待。
令 Pt={p1,p2,…,pm}表示计算机系统在时间 t的程序集合,Qt?Pt是运行的程序集合，或者说在时刻 t至少分配一部分所请求的资源的程序集合。 Rt={r1,r2,…,rn}是系统在时刻 t的资源集合。资源分配图 Gt=<Rt,E>是有向图，
它表示了时间 t系统中资源分配状态。把每个资源 ri看作图中一个结点，其中 i=1,2,…,n。
<ri,rj>表示有向边,<ri,rj>∈ E当且仅当程序
pk∈ Qt已分配到资源 ri且等待资源 rj。
例如，令 Rt={r1,r2,r3,r4},Qt={p1,p2,p3,p4}。
资源分配状态是：
p1占用资源 r4且请求资源 r1；
p2占用资源 r1且请求资源 r2和 r3；
p3占用资源 r2且请求资源 r3；
p4占用资源 r3且请求资源 r1和 r4。
于是，可得到资源分配图 Gt=<Rt,E>，如图
10.2.7所示。
能够证明，在时刻 t计算机系统处于死锁状态?资源分配图 Gt中包含强分图。于是，对于图 10.2.7,Gt是强连通的，即处于死锁状态。
图 10.2.7
10.3 图的矩阵表示给定一个图 G=<V,E>,使用图形表示法很容易把图的结构展现出来,而且这种表示直观明了 。 但这只在结点和边 (或弧 )的数目相当小的情况下才是可行的 。 显然这限制了图的利用 。
本节提供另一种图的表示法 —— 图的矩阵表示法 。 它不仅克服了图形表示法的不足,而且这种表示可以充分利用现代工具电子计算机,以达到研究图的目的 。
一个简单图 G=<V,E>由 V中每两个结点间的邻接关系唯一地确定，这种关系可以用一个矩阵给出，而矩阵形式与图中结点的编序有密切关系，这是用矩阵表示图值得注意的一点。
定义 10.3.1 给定简单图 G=<V,E>,V={v1，
v2,…,vn},V中的结点按下标由小到大编序，
则 n阶方阵 A=(aij)称为图 G的邻接矩阵。其中
i,j=1,2,…,n。
有时为强调邻接矩阵依赖于图 G，把图 G的邻接矩阵记为 A(G)。
对于给定图 G,显然不会因结点编序不同而使其结构发生任何变化,即图的结点所有不同的编序实际上仍表示同一个图 。 换句话说,
这些结点的不同编序的图都是同构的,并且它们的邻接矩阵都是相似的 。 于是
G?H?存在置换矩阵 P,使 A(H)=P-1A(G)P
今后将略去这种由于 V中结点编序而引起邻接矩阵的任意性,而取该图的任一个邻接矩阵作为该图的矩阵表示 。
邻接矩阵可展示相应图的一些性质：
若邻接矩阵的元素全为零，则其对应的图是零图；
若邻接矩阵的元素除主对角线元素外全为 1，
则其对应的图是连通的且为简单完全图。
此外，当给定的简单图是无向图时，邻接矩阵是对称矩阵；反之，若给定任何对称矩阵 A，
显然可以唯一地作出以 A为其邻接矩阵的简单图
G。于是，所有 n个结点的不同编序的简单图的集合与所有 n阶对称矩阵的集合可建立一一对应。
当给一的图是简单有向图时，其邻接矩阵并非一定是对称矩阵，但所有 n个结点的不同编序的简单图的集合，与所有 n阶邻接矩阵的集合亦可建立一一对应。
不仅如此，通过对矩阵元素的一些计算还可以得到对应图的某些数量的特征。
在给定简单有向图的邻接矩阵中，第 i行元素是由结点 vi出发的弧所确定，故第 i行中值为 1
的元素数目等于结点 vi的出度。同理，第 j列中值为 1的元素数目等于结点 vj的入度。即 d+(vi)=
和 d-(vj)= 。
由给定简单图 G的邻接矩阵 A可计算出矩阵
A的 l次幂，即 Al。若第 i行第 j列上的元素 alij便是
G中从第 i个结点 vi到第 j个结点 vj长度为 l的链
（或路）的数目。为说明此事实，今给出下面定理。
定理 10.3.1 设 A为简单图 G的邻接矩阵，则
Al中的 i行 j列元素 alij等于 G中联结 vi到 vj的长度为 l
的链 (或路 )的数目。
在一些实际问题中,有时要判定图中结点
vi到结点 vj是否可达,或者说 vi到 vj是否存在一要链 （ 或路 ） 。 如果要利用图 G的邻接矩阵 A,则应计算 A2,A3,···,An,··。 当发现其中某个 Ar
中 ≥1,就表明 vi可达 vj或 vi到 vj存在一条链
（ 或路 ） 。 但这种计算繁琐量大,又不知计算
Ar到何时为止 。
根据定理 10.2.2可知，对于有 n个结点的图，
任何基本链（或路）的长度不大于 n-1和任何基本圈（或回路）的长度不大于 n。因此，只需考虑 就可以了，其中 1≤r≤n。即只要计算
Bn=A+A2+A3+··+An。
如果关心的是结点间可达性或结点间是否有链（或路），至于结点间的链存在多少条及长度是多少无关紧要，那么便可用下面的定义图的可达矩阵来表示结点间可达性。
定义 10.3.2 给定图 G=<V,E>，将其结点按下标编序得 V={v1,v2,…,vn}。定义一个 n
阶方阵 P=(pij)，其中
1 vi到 vj可达
Pij=
0 否则则称矩阵 P是图 G的可达矩阵。
{
可见，可达矩阵表明了图中任意两结点间是否至少存在一条链 (或路 )以及在结点处是否有圈 (或回路 )。
从图 G的邻接矩阵 A可以得到可达矩阵 P，
即令 Bn=A+A2+A3+…+ An，再从 Bn中非零元素改为 1而零元素不变，这种变换后的矩阵即是可达矩阵 P。
假 设 矩 阵 中 的 元 素 是 属 于 布 尔 代 数
<B,?,?,ˉ,0,1>的 B中元素,其中 B={0,1},则称该矩阵为布尔矩阵 。 显然邻接矩阵是一个布尔矩阵,同样可达矩阵也是布尔矩阵 。 下面定义两个布尔矩阵 B与 C的运算：
令 B和 C的布尔和、布尔积分别记为 B?C和
BoC，其定义为
(B?C)ij=bij?cij
(BoC)ij= (bik?ckj)
i,j=1,2,··,n。其中 bij,cij分别是 B和 C的 i行 j
列元素。
特别地，对于邻接矩阵 A，记 AoA=A(2)，对任何 r=2,3,··,有
A(r-1)oA=A(r)
要注意的是 Ar与 A(r)的差别。 Ar中 表明从
vi到 vj长度为 r的链（或路）的数目，而 A(r)中是指出：若 vi到 vj至少存在一条链（或路）时，
=1，否则,=0。
由上说明，便得到可达矩阵 P为：
P=A?A(2)?A(3)?···?A(n)= A(k)
对于简单有向图 G=<V,E>,显然有
E?V?V。 因此,弧集合 E可解释成 B中的二元关系,而二元关系是可用矩阵表示的,
通常称这种矩阵为关系矩阵,其定义如下：
设两个有限集合 X={x1,x2,··,xm}和
Y={y1,y2,··,yn}，则关系 R?X?Y的关系矩阵
MR=(rij)，其中
1,<xi,yi>?R
rij=
0,否则
i=1,2,··,m； j=1,2,··,n。
{
由定义可知，关系 R与其关系矩阵 MR是一一对应的，即可以相互确定。
根据集合论可知，对于域 F(R)=V而 |V|=n的关系 R的传递闭包 R+可计算如下：
R+=R∪ R2∪ R3∪ ···∪ Rk (k≤n)
于是，关系 R1和 R2的关系矩阵分别为 A1和
A2，则关系 R1∪ R2的关系矩阵为 A1?A2。用归纳法可以证明 R+的关系矩阵是
=···?
对于 G=<V,E>的邻接矩阵 A是关系 E的关系矩阵，因为 E2=EoE，即若存在一个结点 vk，使得 viEvk，和 vkEvj，则必有 viE2vj，亦即从 vi到 vj若至少存在一条长度为 2的链（或路），那么 E2的关系矩阵中的 (i,j)元素值为 1。这表明矩阵 A(2)是关系 E2的关系矩阵。以此类推,A(k)是 Ek的关系矩阵,k=2,3,··,n。因此
A+=A?A(2)?A(3)?···?A(n)
亦即 A+=A?A(2)?A(3)?···?A(n)=P
可见，关系 E的传递闭包 E+的关系矩阵 A+
与可达矩阵相同。
为了计算 A+或 P，自然可先依次求得 A(2)，
A(3),···,A(n)，然后再计算 A(k)，其结果即为所求，这是计算 A+或 P的一种方法，还可介绍一种现有效的方法 — Warshall算法，它由邻接矩阵 A依下面给出的步骤便能计算 A+。其步骤如下：
(1) P?A
(2) k?1
(3) i?1
(4) 若 pik=1，对 j=1,2,··,n作 pij?pij?pkj
(5) i?i+1，若 i≤n则转 (4)
(6) k?k+1，若 k≤n则转到 (3)，否则停止。
该算法的关键的一步是 (4)，它判定如果
pik=1，将第 i行和第 k行的各对应元素作布尔和或逻辑加后送到第 i行中去。
给定关系 E1和关系 E2,它们的关系矩阵分别为 A=(aij)和 B=(bij),则关系交 E1∩E2的关系矩阵记为 A∧ B,其定义如下：
(A∧ B)ij=aij∧ bij
于是,由可达矩阵和利用关系交的关系矩阵可求出包含图中任何指定结点的强分图 。
定理 10.3.2 给定简单有向图 G中的任意结点 vi,若 P=(pij)是 G的可达矩阵,PT=(pji)是 P的转置矩阵,则 P∧ PT的第 i行元素为 1的列号为下标的结点构成了包含 vi的强分图 。
利用简单有向图的可达矩阵,能够确定某过程是否为递归的 。
假设 VP={p1,p2,··,pn}是程序 P中的过程集合,
做有向图 G=<VP,E>,其中 pi?VP,i=1,2,··,n；
<pi,pj>?E?pi调用 pj。 如果图 G中有包含 pi的回路,则可断言 pi是递归的 。 为此,由图 G的邻接矩阵 A=(aij)计算出可达矩阵 A+=( )。 如果 A+中的主对角线上的某元素 =1,则 pi是递归的 。
在图的矩阵表示中,除邻接矩阵外,
还有关联矩阵,圈 （ 或回路 ） 矩阵,权矩阵等,在此就不都予涉及了,只是再给出权矩阵的概念以结束本小节 。
已知加权的简单图 G=<V,E>，定义一个矩阵 W=(wij)，其中：
w,w是边 [vi,vj]（或弧 <vi,vj>）?E
的权
wij=
0,vi与 vj不相邻则称 W为图 G的权矩阵
{
