当前位置：文档之家 › 第7章+图论-3(图的矩阵表示)素材

第7章+图论-3(图的矩阵表示)素材

  • 格式：ppt
  • 大小：569.50 KB
  • 文档页数：24

下载文档原格式

  / 24

合集下载

图的矩阵表示

图的矩阵表示

4 4
2 6
6 51 215
1设G=<V,E>是简单图,令V={v1,v2,v3,…,vn}, G的
10 2 2 0 b)每行中1的个数为对应结点 1 vi与ej关联 12 0 0 2 从邻接矩阵看图的性质: 1 vi与vj邻接, 即(vi,vj)∈E 或 < vi,vj >∈E
010 01 0 0110
00010
01001
00010
01001
P=A∨A(2)∨A(3)∨A(4)∨A(5) A(5)=A(3)
11111 01011 P= 11111 01011 01011
G2 v1 v3
3*.用可达矩阵求强分图.
出有两个强分图:{v1,v3}和{v2,v4,v5} 下面看怎样用P求强分图.
例如,G2如图所示, 求它的 可达矩阵P.
G2
v1
v2
v3
v4
v5
00100
10010
01101
10010
00010
01011
01011
01011
A= 10010 A(2) = 01101 A(3) = 10010 A(4) = 01101 =A(2)
01001
00010
01000
00010
用的例v4求度如0传 数 ,0给递.0定0闭无1包0向的1图WGa1rs和ha有ll算向法1图0,G见012P如1116图610.所0示0:
21111
v1
1310
2
v2
v3
例 b这p)ij每如是= 行p,以T给中i结j定=1点1的A无与个向(结G 数图点为G1之)1对和间应有的结向邻点1图0接G1关12如系00图确00所定1示的1:矩阵.

图论

图论

• 7.6 树与生成树(Trees and Spanning Trees)
• 7.7 根树及其应用(Rooted Trees and Its Applications)
7.1 图的基本概念
• 7.1.1 图的基本概念 • 7.1.2 图的结点的度数及其计算 • 7.1.3 子图和图的同构
7.1 图的基本概念
vV vV
7.1 图的基本概念
图7.1.4
7.1.3 子图和图的同构 • 1.子图 • 在研究和描述图的性质时，子 图的概念占有重要地位。 • 定义7.1.5 设有图G=〈V , E〉和图 • G′=〈 V′, E′ 〉 。 1) 若V′ V， E′ E， 则称G′是G的子 图。 • 2) 若G′是G的子图，且E′≠E，则称G′ 是G 的真子图。
7.1 图的基本概念
• 定理 7.1.1 图G＝〈V ,E〉中结点度 数的总和等于边数的两倍， 即

V
deg( ) 2 E
• 证明: 因为每条边都与两个结点关联， 所以加上一条边就使得各结点度数的和 增加 2， 由此结论成立。 • 推论: 图G中度数为奇数的结点必为偶 数个。
7.1 图的基本概念
•
7.1 图的基本概念
我们将结点a、b的无序结点对记为(a，b）， 有 序结点对记为〈a，b〉。 一个图G可用一个图形来表示且表示是不唯 一的。
• 【例7.1.2】 设G=〈V(G),E(G)〉,其中 • V(G)={a,b,c,d},E(G)={e1,e2,e3,e4,e5,e6 ,e7},e1=(a,b), • e2=(a,c),e3=(b,d),e4=(b,c),e5=(d,c),e6= (a,d),e7=(b,b) 。 则图G可用图7.1.2(a)或(b)表示。

第七章 图论

第七章 图论

12
7.1 图及相关概念
7.1.5 子图
Graphs
图论
定义7-1.8 给定图G1=<V1,E1>和G2=<V2,E2> ， (1)若V1V2 ，E1E2 ，则称G1为G2的子图。 (2)若V1=V2 ，E1E2 ，则称G1为G2的生成子图。
上图中G1和G2都是G的子图，
但只有G2是G的生成子图。
chapter7
18
7.1 图及相关概念
7.1.6 图的同构
Graphs
图论
【例4】 设G1,G2,G3,G4均是4阶3条边的无向简单图，则
它们之间至少有几个是同构的？ 解：由下图可知，4阶3条边非同构的无向简单图共有3个， 因此G1,G2,G3,G4中至少有2个是同构的。
4/16/2014 5:10 PM
4/16/2014 5:10 PM chapter7 10
7.1 图及相关概念
7.1.3 完全图
Graphs
图论
【例2】证明在 n（n≥2 ）个人的团体中，总有两个人在 此团体中恰好有相同个数的朋友。 分析 :以结点代表人，二人若是朋友，则在结点间连上一 证明：用反证法。 条边，这样可得无向简单图G，每个人的朋友数即该结点 设 G 中各顶点的度数均不相同，则度数列为 0 ， 1 ， 2 ， …， 的度数，于是问题转化为： n 阶无向简单图 G中必有两个 n-1 ，说明图中有孤立顶点，与有 n-1 度顶点相矛盾（因 顶点的度数相同。 为是简单图），所以必有两个顶点的度数相同。
vV1
deg(v) deg(v) deg(v) 2 | E |
vV2 vV
由于 deg( v) 是偶数之和，必为偶数，
vV1

7-3 图的矩阵表示

7-3 图的矩阵表示
图的矩阵表示
中国海洋大学 计算机系
主要内容
邻接矩阵 有向图的可达矩阵 无向图的关联矩阵 有向图的关联矩阵 图的运算 学习要点与基本要求 实例分析
邻接矩阵
定义7-3.1 设G=<V,E>是一个简单图，它有 个结点 是一个简单图， 定义 是一个简单图 它有n个结点 V={v1, v2, …, vn}, 则n阶方阵 阶方阵A(G)=(aij)称为 的邻 称为G的邻 阶方阵 称为 接矩阵。其中 接矩阵。
1 从v i 到v j 至少存在一条路 pij = 0 从v i 到v j不存在路
称矩阵P是图 的可达性矩阵。 称矩阵 是图G的可达性矩阵。 是图
关于可达矩阵的说明
可达性矩阵描述任意两结点是否可达， 可达性矩阵描述任意两结点是否可达，以及对于任 意结点是否有通过它的回路。 意结点是否有通过它的回路。 由邻接矩阵A可直接得到可达性矩阵 ，方法如下： 由邻接矩阵 可直接得到可达性矩阵P，方法如下： 可直接得到可达性矩阵 方法1： 方法 ： Bn=A+A2+…An， 再把B 中的非零元均改为1， 再把 n中的非零元均改为 ，零元保持不 变，得到可达性矩阵P。 得到可达性矩阵 。 方法2： 中的非零元改为1， 方法 ：把Ai(i=1,2, …,n)中的非零元改为 ，零元保 中的非零元改为 持不变，得到布尔矩阵 持不变，得到布尔矩阵A(i)(i=1,2, …,n)， ， P= A(1) ∨ A(2) ∨… ∨ A(n)
0 1 0 0 0 2 0 0 0 2 0 1 0 0 + 0 0 0 1 0 0 0 0 0 1 0 7 3 0 0 6 7 0 0 7 3 0 0 0 0 2 3 0 0 3 2
2 0 0 0 2 0 2 0 0 0 2 0 0 0 + 2 0 0 0 1 0 0 0 1 0 0

第7章 图论 [离散数学离散数学(第四版)清华出版社]

第7章 图论 [离散数学离散数学(第四版)清华出版社]

6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
21
例：
a j i h c g d
1(a)
无 向 图
b
f
e

2(b)
7(j) 8(g) 9(d) 10(i)
6(e)
3(c) 4(h)
5(f)
6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
22
例：
1(b)
有向图
第四部分：图论（授课教师：向胜军）
6
[定义] 相邻和关联
在无向图G中，若e=(a, b)∈E，则称a与 b彼此相邻(adjacent)，或边e关联 (incident) 或联结(connect) a, b。a, b称为边e的端点或 结束顶点(endpoint)。 在有向图D中，若e=<a, b>∈E，即箭头 由a到b，称a邻接到b，或a关联或联结b。a 称为e的始点(initial vertex)，b称为e的终点 (terminal/end vertex)。
证明思路：将图中顶点的度分类，再利用定理1。
6/27/2013 6:02 PM 第四部分：图论（授课教师：向胜军） 9
[定理3] 设有向图D=<V, E>有n个顶点，m 条边，则G中所有顶点的入度之和等于所 有顶点的出度之和，也等于m。
即：
d ( v i ) d ( v i ) m.
i 1 i 1
n
n
证明思路：利用数学归纳法。
6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
10
一些特殊的简单图：
(1) 无向完全图Kn(Complete Graphs)

第七章 图论

第七章 图论
i1
本讲稿第十三页，共九十一页
§7.1 图的基本概念
例：若图Ｇ有n个顶点，（n+1）条边，则Ｇ中至少 有一个结点的度数≥３。
证明：设Ｇ中有n个结点分别为v1,v2,…,vn，则由握手
定理：
n
degvi)(2e2(n1)
i1
而结点的平均度数=
2(n1)212
n
n
∴结点中至少有一个顶点的度数≥３
本讲稿第十四页，共九十一页
▪ 若Ｇ’ Ｇ，且Ｇ’ ≠Ｇ（即Ｖ’Ｖ或Ｅ’ Ｅ），则称Ｇ’是Ｇ的真子图；
▪ 若Ｖ’＝Ｖ,Ｅ’Ｅ,则称Ｇ’是Ｇ的生成子图(支 撑子图)。
本讲稿第二十三页，共九十一页
§7.1 图的基本概念
２．子图和图的同构：
例：Ｇ图如下：Ｇ的真子图：
生成子图：
说明： （1）Ｇ也是Ｇ的生成子图； （2）Ｇ’＝〈Ｖ，〉也是Ｇ的生成子图。
（3）路径长度：若两个结点之间有一条路经Ｐ，则路 径|Ｐ|＝Ｐ中边的条数。 例：给出有向图Ｇ，求起始于１，终止于３的路径
本讲稿第三十二页，共九十一页
§7.2 路与回路
下面介绍一些专有名词：
(1)穿程全部结点的路径：经过图中所有结点的路径。 (2)简单路径：在有向图中经过边一次且仅一次的路径。
(3)基本路径：在）从一个结点到某一结点的路径，（若有的话）不 一定是唯一的； （2）路径的表示方法：
(a)边的序列表示法： 设Ｇ＝＜Ｖ，Ｅ＞为一有向图， ，则路径可以表示
成：(<v1,v2>,<v2,v3>,….<vk-1,vk>)vi V
本讲稿第三十一页，共九十一页
§7.2 路与回路
(b)结点序列表示法： (v1,v2vk)

离散数学_第7章 图论 -3-4图的矩阵表示、欧拉图与汉密尔顿图


2 0 2 0 0 0 4 0 0 0
0 1 A(G ) 1 0
0 0 1 1
1 0 0 0
1 0 1 0
第9章 图论
考察A(G)和A′(G)发现，先将A(G)的第一行与第二行对 调，再将第一列与第二列对调可得到A′(G)。称A′(G)与A(G) 是置换等价的。 一般地说，把n阶方阵A的某些行对调，再把相应的列 做同样的对调，得到一个新的n阶方阵A′，则称A′与A是置 换等价的。可以证明置换等价是n阶布尔方阵集合上的等价 关系。 虽然，对于同一个图，由于结点的标定次序不同，而 得到不同的邻接矩阵，但是这些邻接矩阵是置换等价的。 今后略去结点标定次序的任意性，取任意一个邻接矩阵表 示该图。 ④对有向简单图来说，其邻接矩阵A(G)的第i行1的个 数是vi的出度， 第j列1的个数是vj的入度。 ⑤零图的邻接矩阵的元素全为零，叫做零矩阵。反过 来，如果一个图的邻接矩阵是零矩阵，则此图一定是零图。
vi 到v j 有边 1 aij 其中： 0 vi 到v j 无边或i j
i , j=1,…,n 例如，右边无向简 单图的邻接矩阵为： 0 1 A(G ) 0 1
a11 a 即：A(G) = 21 an1
a12 a22 an 2
0 0 1 1
1 0 0 0
1 0 1 0
第9章 图论
简单图的邻接矩阵具有以下性质：
①简单图的邻接矩阵中元素全是0或1。这样的矩阵叫布 尔矩阵。简单图的邻接矩阵是布尔矩阵。 ②无向简单图的邻接矩阵是对称阵，有向简单图的邻接 矩ห้องสมุดไป่ตู้不一定是对称阵。 ③简单图邻接矩阵与结点在图中标定次序有关。例如上 页图 (a)的邻接矩阵是A(G)，若将图 (a)中的接点v1和v2的标 定次序调换，得到图 (b)，图 (b)的邻接矩阵是A′(G)。

离散数学第7章PPT课件

3 v1e1v2e5v5e6v4e4v2e5v5e7v6
…………
初级通路 简单通路 复杂通路
第38页/共94页
例1、(2)
图(2)中过v2的回路 (从 v2 到 v2 )有：
1 v2e4v4e3v3e2v2
长度3
2 v2e5v5e6v4e3v3e2v2
长度4
3 v2e4v4e3v3e2v2e5v5e6v4e3v3e2v2 长度7
第34页/共94页
一、通路，回路。 2、简单通路，简单回路。 简单通路 (迹) 简单回路 (闭迹) 复杂通路 (回路)
第35页/共94页
一、通路，回路。 3、初级通路，初级回路。 初级通路 (路径) 初级回路 (圈)
初级通路 (回路) 简单通路 (回路)，
但反之不真。
4、通路，回路的长度—— 中边的数目。
补图的概念， 5、图的同构的定义。
第4页/共94页
一、图的概念。 1、定义。
无序积 A & B (a,b) a A b B
无向图 G V , E
E V &V ， E 中元素为无向边，简称边。
有向图 D V, E
E V V ， E 中元素为有向边，简称边。
第5页/共94页
一、图的概念。 1、定义。
2、握手定理。
定理1： 设图 G V , E 为无向图或有向图，
V v1,v1,
则
,vn，E m ( m为边数)，
n
d (vi ) 2m
i 1
第20页/共94页
n
2、握手定理 d (vi ) 2m i 1
推论：任何图中，度为奇数的顶点个数为偶数。
定理2： 设D V, E 为有向图，
第36页/共94页

离散数学 7-3 图的矩阵表示

要条件，但也不是汉密尔顿图。
所以用此定理来证明某一特定图不是汉密尔顿图并不是
总是有效的。例如，著名的彼得森(Petersen)图，在图中删 去任一个结点或任意两个结点，不能使它不连通；删去3个结 点，最多只能得到有两个连通分支的子图；删去4个结点，只 能得到最多三个连通分支的子图；删去5个或5个以上的结点，
e3
v3
1 1 0 0 0
0 1 1 0 0
0 0 1 1 0
1 0 0 1 0
1 0 1 0 0
v3 0 v4 0 v5 0
无向图的关联矩阵反映出来图的性质:
每一条边关联两个结点,故每一列中只有两个1。
每一行中元素之和等于该行对应的结点的度数。
一行中元素全为0，其对应结点为孤立点。
两个平行边其对应的两列相同。 同一个图当结点或边的编号不同时，其对应的矩 阵只有行序列序的差别。
证明思路：1) 先证必要性: G有欧拉路 G连通 且（有0个 或 2个奇数度结点） 设G的欧拉路是点边序列v0e1v1e2… ekvk，其中结点可能重复， 但边不重复。因欧拉路经过（所有边）所有结点，所以图G 是连通的。 对于任一非端点结点vi，在欧拉路中每当vi出现一次，必关 联两条边，故vi虽可重复出现，但是deg(vi)必是偶数。对于端 点,若v0=vk ，则deg(v0)必是偶数，即G中无奇数度结点 。若 v0≠vk ，则deg(v0)必是奇数， deg(vk)必是奇数,即G中有两个奇 数度结点 。必要性证完。
e3
v3
0 0 0
-1 1 0 0
-1 1 0 0
有向图的关联矩阵的特点：
(1)每一列中有一个1和一个-1，对应一边一个始 点、一个终点，元素和为零。 (2)每一行元素的绝对值之和为对应点的度数。-1 的个数等于入度，1的个数等于出度。

第7章 图论-3(图的矩阵表示)讲述



无向图的关联矩阵
E e1 , e2 , eq
V v1 , v2 , , v p
定义 1.6.1 设 G (V , E ) 的顶点集和边集分别为
， 。用 bij表示顶点 vi 与边e j 关联的次数(0，1 或2)，称矩阵 B(G) (bij ) pq 为 G 的关联矩阵。
0 e j 与xi 不关联
返回 结束
7.3.2 关联矩阵

20
例2
有向图
D (下图所示)，求 A(D) M ( D )。
1 1 0 0 0 1 0 1 1 1 解：M ( D) A(D) 0 0 0 0 1 0 1 1 1 0
返回 结束


判别定理：图G1 ，G2同构的充要条件是：存在置换矩阵P，使得： A1＝PA2P。 其中A1，A2分别是G1 ，G2的邻接矩阵。 如何判断两图同构是图论中一个困难问题
返回 结束
7.3.1 邻接矩阵

6
在邻接矩阵A的幂A2， A3， …矩阵中， 每个元素有特 定的含义。
定理 :设G是具有n个结点集｛v1， v2， …， vn｝ 的图， 其邻接矩 阵为A， 则Al（l＝1， 2， …）的（i， j）项元素a(l)ij是从vi到vj的长 度等于l的路的总数。 证明 : 归纳法 当l＝1时， A1＝A， 由A的定义， 定理显然成立。 若l＝k时定理成立， aij (1)等于G中 联结vi与vj的长 则当l＝k＋1时， A k+1＝ A · Ak ， 度为1的路径条 数。 n 所以 aij (l+1) = aik × akj (l) k=1
1.无向图的邻接矩阵
ij a表示 定义 1.6.2设 G (V , E )的顶点集为 V v1 , v2 , , v p，用 (G) (aij ) p p为 G 的邻 G 中顶点 vi与v j 之间的边数。称矩阵M A(G) 接矩阵。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

返回 结束
7.3.1 邻接矩阵
13
３４２３ ５５４６ B4 A1 A2 A3 A4 ７７４７ ３２１２
bij表示从结点vi到vj有长度分别为1，2，3， 4的不同通路总数。 此时， bij0，表示从vi到vj是可达的。
返回 结束


判别定理：图G1 ，G2同构的充要条件是：存在置换矩阵P，使得： A1＝PA2P。 其中A1，A2分别是G1 ，G2的邻接矩阵。 如何判断两图同构是图论中一个困难问题
返回 结束
7.3.1 邻接矩阵

6
在邻接矩阵A的幂A2， A3， …矩阵中， 每个元素有特 定的含义。
定理 :设G是具有n个结点集｛v1， v2， …， vn｝ 的图， 其邻接矩 阵为A， 则Al（l＝1， 2， …）的（i， j）项元素a(l)ij是从vi到vj的长 度等于l的路的总数。 证明 : 归纳法 当l＝1时， A1＝A， 由A的定义， 定理显然成立。 若l＝k时定理成立， aij (1)等于G中 联结vi与vj的长 则当l＝k＋1时， A k+1＝ A · Ak ， 度为1的路径条 数。 n 所以 aij (l+1) = aik × akj (l) k=1
返回 结束
7.3.2 关联矩阵

18
例1
下图所示
的关联矩阵为：
e1 e2 e3 e4 e5 e6 e7 e8 e9 v1 0 0 0 0 1 0 0 1 1 对应的关联矩阵 v2 1 1 1 0 0 0 1 0 1 B(G ) e v3 1 1 0 0 0 0 0 0 0 v4 4 v4 0 0 1 2 1 1 0 0 0 v5 0 0 0 0 0 1 1 1 0
长度=l 长度=1 共akj (l)条

vi
vk
vj
返回 结束
7.3.1 邻接矩阵

7
结论：
(1) 如果对l＝1， 2， …， n-1， Al的（i， j）项元素 （i≠j）都为零， 那么vi和vj之间无任何路相连接， 即vi和 vj不连通。 因此， vi和vj必属于G的不同的连通分支。
(2) 结点vi 到vj （i≠j）间的距离d（vi， vj）是使Al（l＝
(1)
M (G) 是一个对称矩阵； A(G) (G) 中第i 行(列)的元素之和等于顶点 vi 的度数； (2) 若M (G)为无环图。则M A(G) A(G)
(3) 两个图G 与H 同构的充要条件是存在一个置换矩阵 P ，使得
相当于将单位 矩阵中相应的 行与行，或者 列与列互换的 矩阵
A(G) M (G) PT M ( H ) P 。
第七章 图论
引言 7.1 图的基本概念 7.2 路与连通 7.3 图的矩阵表示 7.4 最短路径问题 7.5 图的匹配 8.1 Euler图和Hamilton图 8.2 树 8.3 生成树 8.4 平面图
1
返回 结束
7.3 图的矩阵表示

2
图的矩阵表示 图的数学抽象是三元组，其形象直观的表 示即图的图形表示。为便于计算，特别为便 于用计算机处理图，下面介绍图的第三种表 示方法—图的矩阵表示。利用矩阵的运算还 可以了解到它的一些有关性质。
v2
v1
e3
v1
e9 e5
e8
对应的邻接矩阵
v4 e4
e7
v5
A(G)
M (G )
v2 v3 v4 v5
e6
v1 0 1 0 1 1
v2 1 0 2 1 1
v3 0 2 0 0 0
v4 1 1 0 1 1
v5 1 1 0 1 0
从图的邻接矩阵的定义容易得出以下性质：
7.3.3 有向图的可达性矩阵

21
有向图的可达性矩阵。(了解)
设 D V , E 为有向图， V v1, v2 , 令 pii 1 ，i 1, 2,
, vn ，
,n
1 vi可达v j pij (i j ) 0 否则
可达性矩阵 P ( pij )nn
( n 1) 其中元素 pij (i j)可由 Bn 1 bij
返回 结束
7.3.1 邻接矩阵
(1) 由A中a(1)12＝1知， v1和v2是邻接的； 由A3中a(3)12＝ 2知， v1到v2长度为3的路有两条， 从图中可看出是v1 v2 v1 v2和v1 v2 v3 v2 。 (2) 由A2的主对角线上元素知， 每个结点都有长度为２ 的回路， 其中结点v2有两条： v2 v1 v2和v2 v3 v2 ， 其余 结点只有一条。 (3) 由于A3的主对角线上元素全为零， 所以G中没有长 度为３的回路。 (4) 由于a（１）34＝a（２）34＝a（３）34＝a（４）34＝０， 所以 结点v3和v4间无路， 它们属于不同的连通分支。 (5) d（v1， v3）＝２。 对其他元素读者自己可以找出它的意义。
7.3.1 邻接矩阵
2.有向图的邻接矩阵
1、设有向图 D V , E ， V v1, v2 ,
14
, vn ，
(1) E m ，D 的邻接矩阵 A( D ) aij nn ，
其中 a 指 vi 邻接到 v j 的边的条数 (非负整数)。
(1) ij
返回 结束
7.3.1 图的矩阵表示
10
返回 结束
7.3.1 邻接矩阵
矩阵的计算：
０１００ ００１１ A １１０１ １０００
11
００１１ １０１０ AT ０１００ ０１１０
２１０１ １２０１ AT A ００１１ １１１２
1.无向图的邻接矩阵
ij a表示 定义 1.6.2设 G (V , E )的顶点集为 V v1 , v2 , , v p，用 (G) (aij ) p p为 G 的邻 G 中顶点 vi与v j 之间的边数。称矩阵M A(G) 接矩阵。
4
G 的邻接矩阵为： 例2下图所示 v
3
e1
e2
返回 结束
7.3.1 邻接矩阵

5
同构图
v1
v3 v4
图G1 1 A1＝ 0 1 1 1 2 1 0 1 1 3 1 1 0 1 4 1 1 1 0
v1<->va
va
v2<->vb
v3<->vc v4<->vd
v2
vb
vc
图G2
vd
a A2 ＝ 0 1 1 1
b 1 0 1 1
c 1 1 0 1
d 1 1 1 0
１０１０ ０２１０ A AT １１３１ ００１１
主对角线上的数表 示结点i（或j）的 引出次数。
主对角线上的数表示结 点i（或j）的引入次数。
返回 结束
7.3.1 邻接矩阵
００１１ ２１０１ A2 A A １１１１ ０１００
返回 结束
(4) 重边所对应的列完全相同。
7.3.2 关联矩阵

19
有向图的关联矩阵
1、设有向图
D V, E ， V v1, v2 , , em ，D 的关联矩阵
, vn ，
E e1 , e2 ,
M (D) (mij )nm ，
为 e j的始点 2 vie xi 1 j 是自环，且关联与 1 在D中e 以x 为起点，e 不是自环 0 vi与e j不关联 j i j 其中 mij 1 在D中e j以xi 为终点，e j 不是自环 1 vi为e j的终点
内容：关联矩阵，邻接矩阵，可达矩阵。 重点：1、有向图，无向图的关联矩阵， 2、有向图的邻接矩阵。 了解：有向图的可达矩阵。
返回 结束
7.3.1 图的矩阵表示
3
存储原则: 存储结点集和边集的信息.
（1）存储结点集； （2）存储边集： 存储每两个结点 是否有关系。
返回 结束
邻接矩阵
7.3.1 邻接矩阵
2
12
２１０１ １２１１ A3 A2 A ２２１２ ００１１
１２１１ ２２２３ A4 A3 A ３３２３ ２１０１
表示 i 和 j 之间具有长度为 2 A 的通路数， 3 表示i和j之间具有长度为3 A 的通路数， A4 表示i和j之间具有长度为4 的通路数，


n n
求得：
( n 1) 1 b 0 ij pij 0 否则
返回 结束
7.3.3 有向图的可达性矩阵
根据可达性矩阵， 可知图中任意两个结点 之间是否至少存在一条路以及是否存在回路。 利用有向图的邻接矩阵A， 分以下两步可得 到可达性矩阵。

无向图的关联矩阵
E e1 , e2 , eq
V v1 , v2 , , vp
定义 1.6.1 设 G (V , E ) 的顶点集和边集分别为
， 。用 bij表示顶点 vi 与边e j 关联的次数(0，1 或2)，称矩阵 B(G) (bij ) pq 为 G 的关联矩阵。
15
有向图的邻接 矩阵
返回 结束
7.3.2 邻接矩阵

16
例1
有向图 D (下图所示)，求 A( D) 。
1 0 解：A( D) 0 0
2 0 0 0
1 1 0 1
0 0 1 0
返回 结束
7.3.2 关联矩阵

17
关联矩阵多用于简单无向图
一个图 G (V , E ) 由它的顶点与边的关联关系唯一 确定；