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

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

  • 格式：ppt
  • 大小：452.50 KB
  • 文档页数：22

下载文档原格式

  / 22

合集下载

图论

图论

• 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图的矩阵表示、欧拉图与汉密尔顿图

离散数学_第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)。

第七章图论

第七章图论

以上三个条件并 不是两图同构的 充分条件，如：
a
b
c
d
e
(a)
a'
c'
b'
e'
d'
(b)
第七章 图论
图的基本概念 路与回路 图的矩阵表示 欧拉图与哈密尔顿图
7-2 路与回路
1、路的基本概念：
路： 图G=<V, E>，设 v0, v1, …, vn∊V, e1, e2, …, en∊E, 其中
ei是关联于结点vi-1, vi的边，交替序列设 v0 e1 v1 e2 … en vn称为
若 连 通 图 G中 某 两 个 结 点 都 通 过 v， 则 删 去 v 得 到 子 图 G ， 在 G 中 这 两个结点必定不连通，故v是图G的割点。
7-2 路与回路
deg(v)为偶数 vV1
|V1|为偶数
定理： 有向图中所有结点的入度之和等于所有结点的出度之和
7-1 图的基本概念
（5）多重图：含有平行边的图
简单图：不含有平行边和环的图
完全图：每一对结点之间都有边关联的简单图
有向完全图：完全图中每条边任意确定一个方向所得的图
a
e
b
d
f
h
c
g
定理： n个结点的无向（有向）完全图Kn的边数为n(n-1)/2
证明： 在完全图中，每个结点的度数应为n－1，则n个结点的
度数之和为n(n-1)，因此|E|＝n(n-1)/2
7-1 图的基本概念
（6）子图：
G V , E ， 有 G ' V ', E ' ， 且 E ' E ， V ' V ，

大连海事大学离散数学期末复习纲要

大连海事大学离散数学期末复习纲要
注意：合成关系和合成函数书写格式的区别。
本章要点（续）
3、掌握反函数的概念及其存在的条件： 设 f: X→Y是双射函数，则f的逆关系称
f的反函数，记作f-1
注意：只有双射函数才有反函数。
本章要点（续）
4、掌握特种函数的定义（单射、满射、双 射）及证明：
①滿射函数：设函数f: X→Y，若 f(X)=Rf=Y（值域＝陪域）。
即：Df = X； (2)唯一性：对任意的xX，必存在唯一的
yY，使<x，y>f，即： 对 任 意 的 xX ， y ， zY ， 有 ： <x ，
y>f∧<x，z>f y = z。
3、特种函数
设函数f: X→Y,则：
(1)若f(X)=Rf=Y, 则称f是滿射的； (2)对任意x1,x2X，如果: x1≠x2f(x)≠f(y), 或:f(x1)=f(x2)x1 =x2； 则称f是单射的；
数。
9.半群和群
半群：设<S,*>是代数系统，*运算是S上的二元 运算，若*运算是可结合的，则称<S,*>为一个 半群。
群：（1）<S，*>是代数系统； （2） “*”运算满足结合律；
（3）<A，*>中存在幺元e；
（4）<A，*>中任意一个元素都有逆元素；
则称代数系统<A，*>是群。
子群
设<A，*>是一个群，H是A的非空子 集，若<H，*>也是一个群，则称<H， *>是<A，*>的子群。
7. 代换性质和同余关系
代换性质：给定代数系统<X，*>，其中是个二元 运算。设R是X中的等价关系，如果对任意的x1， x2X和y1，y2X有： (x1Rx2)∧(y1Ry2)(x1*y1)R(x2*y2)

离散数学第七章图的基本概念

离散数学第七章图的基本概念

4.无向图的连通性
若无向图G中任何两顶点都连通,则称G是连通图.
对于任意的无向图G.设V1,V2,…,Vk是顶点之间连通关系的 等价类,则称他们的导出子图为G的连通分支.用p(G)表示G 的连通分支数.
V1 e1
e2 e3
V3
e4 V2
V4
a
de
h
i
b
c
f
g
5.有向图的连通性
若略去有向图D中各边的键头,所得无向图是无向连通图,则 称D是弱连通图(或称D是连通图).
(2) mij d (vi )(i 1,2,..., n)
j 1
mn
nm
n
(3) mij mij d(vi ) 2m
j1 i1
i1 j1
i 1
m
(4) mij 0 vi是孤立点 j 1
(5)若第j列与第k列相同, 则说明e j与ek为平行边.
2.有向图的关联矩阵
设有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em} 1, vi为ej的始点
e1,e2,e3},{e1,e2,
e2
e4},{e9}等边割集 ,e9是桥.
e3 V4
e5 e6
V5 e4
V6
e9
V7
7.3 图的矩阵表示
1.无向图的关联矩阵
设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}
令mij为顶点vi与ej的关联次数, 则称(mij)n×m为G的关联矩阵.记为M(G)
若Γ 满足:vi-1,vi为ei的端点(若G为有向图,vi-1是ei的始 点,vi是ei的终点)i=1,2,…,k,则称Γ 为G中通路,v0,vk分 别称为通路的始点和终点,Γ 中边的数目k称为通路长度.

图论图的矩阵表示

图论图的矩阵表示
定理 :设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.1 图的矩阵表示
2
存储原则:ቤተ መጻሕፍቲ ባይዱ存储结点集和边集的信息.
（1）存储结点集； （2）存储边集： 存储每两个结点 是否有关系。
返回 结束
邻接矩阵
7.3.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)
M (G) 是一个对称矩阵； A(G) (G) 中第i 行(列)的元素之和等于顶点 vi 的度数； (2) 若M (G)为无环图。则M A(G) A(G)
(3) 两个图G 与H 同构的充要条件是存在一个置换矩阵 P ，使得
相当于将单位 矩阵中相应的 行与行，或者 列与列互换的 矩阵
3
G 的邻接矩阵为： 例2下图所示 v
3
e1
e2
v2
v1
e3
v1
e9 e5
e8
对应的邻接矩阵

第七章 图论

第七章 图论

• 对于有向图 G中的任意结点 u,v 和w，结点间的距离有以下 的性质： ① du,v≥0 ② du,u=0 ③ du,v＋dv,w≥du,w • 注：一般来说， du,v不一定等于dv,u • 定义D=max du,v为图的直径 • 关于有向图两个结点间的距离可以很容易的推广到无向图 中
【例】如右图所示是一个图，其中 v1e1v2e3v3e4v2e3v3e7v5是一条从v1到v5的路 v1e1v2e3v3e4v2e5v4e8v5是一条从v1到v5的迹 v1e1v2e3v3e7v5是一条从v1到v5的通路 v3e3v2e5v4e8v5e6v2e4v3是一个回路 v3e3v2e5v4e8v5e7v3是一个圈
• 定义 7-1.9 设图 G=V,E 与图 G′=V′,E′ ，如果存 在一一对应的映射g: vi→vi′且e=(vi,vj)是G的一条 边当且仅当e′=(vi′,vj′)是G′的一条边,则称G与G′同 构,记为G≌G′.
• 通俗的讲两个图同构当且仅当两个图的结点和边存在着一 一对应,且保持关联关系
• 如果一对结点间的边多于一条，则称这些边为平行边
• 定义 7-1.4 含有平行边的任何一个图称为多重图
• 不含平行边和环的图称为简单图
• 定义 7-1.5 简单图G=<V,E>中, 若每一对结点都有 边相连，则称该图为完全图。
• n个结点的无向完全图记为Kn
• 定理7-1.4 • 定义7-1.6 给定一个图G，由G中所有结点和所有 能使G成为完全图的添加边组成的图，称为图G的 相对于完全图的补图，简称为G的补图，记为 G 。
1 n个结点的无向完全图Kn的边数为2 n(n 1)
• 定义7-1.7 设图G=<V,E>, 如果有图G′=<V′,E′>, 且 E′ E, V′ V, 则称G′为G的子图

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

离散数学 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. 1无向图及有向图无向图与有向图多重集合：元素可以重复出现的集合无序积：{(x, y) |定义无向图Q<K£>,其中(1) 顶点集$0,元素称为顶点(2) 边集F为k&f的多重子集，其元素称为无向边，简称边.例如，如图所示，其中心⑷，…，心，&{(旳，匕)，(匕，匕),(迫，方)，(乃，方)，(迫，％), (s, %),(必，％)} 定艾有向图E>,其中(1) $同无向图的顶点集，元素也称为顶点(2) 边集F为的多重子集，其元素称为有向边，简称边.用无向边代替0的所有有向边所得到的无向图称作Q的基图，右图是有向图, 试写出它的！/和F注意：图的数学定艾与图形表示，在同构(待叙)的意狡下是一一对应的通常用G表示无向图，0表示有向图，也常用G泛指无向图和有向图，用6表示无向边或有向边.K6), E(G, Eg G和D的顶点、集,边集.77阶图：”个顶点的图有限图：K F都是有穷集合的图零图：吕0平凡图：1阶零图空图：^=0顶点和边的关联与相邻：定狡设e*,v)是无向图G^<V f E>的一条边，称v…匕为e*的端点，©与v, ( 16)关联.若Vi H V”则称故与Vi ( v)的关联次数为1;若匕=匕，则称6为环，此时称◎与匕的关联次数为2;若匕不是鸟端点, 则称鼓与匕的关联次数为0.无边关联的顶点称作孤立点.定义设无向图=<V, E>, v if K e“e《E,若©，匕)e£；则称乙匕相邻；若％ &至少有一个公共端点，则称6, 8/相邻.对有向图有类似定义.设6二〈乙匕〉是有向图的一条边，又称匕是牧的始点，V」是6的终点，K邻接到Vj.匕邻接于Vi.邻域和关联集邻域和关联集设无向图^veV(G)”的邻域谑克匕(6A3"(G)A亦}1 的闪邻域2V(V)=M V)U{V)丫的关联集7(v)=fej族要(G>e与咲联}设有向图空厲蚀)1的后绅元集石(护{边煖玖刀人今炉訪⑹付妙、的先驱元集纭(忙甸頰匕(D)人Y细>“(C)人T1的邻域E(v)=“e)u巧(巧'的丙邻域jv D(v) = 1V23(v)U{v}顶点的度数设G=<V,E>为无向图，keKy的度数(度)〃3): #作为边的端点次数之和悬挂顶点：度数为1的顶点悬挂边：与悬挂顶点关联的边G 的最大度zl(Q 二max {〃(“)| i/e HG的最小度&Q=min{d(访| keH例如〃(％)二3, 〃(乃)二4, 6/(I/.) =4,zl(6)=4, J(6)=1, r4是悬挂顶点，g是悬挂边,设^=<K £>为有向图，reKi/的出度dW: y作为边的始点次数之和1/的入度力3) ：#作为边的终点次数之和1/的度数(度)〃3)：#作为边的端点次数之和d(v)~ / (#) + d(v)。

《离散数学》第七章_图论-第3-4节

《离散数学》第七章_图论-第3-4节

图的可达性矩阵计算方法 （3） 无向图的可达性矩阵称为连通矩阵，也是对称的。 Warshall算法
例7-3.3 求右图中图G中的可达性矩 阵。 分析：先计算图的邻接矩阵A布尔乘法的的2、 v1
3、4、5次幂，然后做布尔加即可。
解：
v4
v2
v3 v5
P=A∨ A(2) ∨ A(3) ∨A(4)∨A(5)
图的可达性矩阵计算方法（2）
由邻接矩阵A求可达性矩阵P的另一方法： 将邻接矩阵A看作是布尔矩阵，矩阵的乘法运算和加 法运算中，元素之间的加法与乘法采用布尔运算 布尔乘：只有1∧1=1 布尔加：只有0∨0=0 计算过程： 1．由A，计算A2，A3，…，An。 2．计算P=A ∨ A2 ∨ … ∨ An P便是所要求的可达性矩阵。
v4
v3
v2
G中从结点v2到结点v3长度 为2通路数目为0，G中长 度为2的路（含回路）总数 为8，其中6条为回路。 G中从结点v2到结点v3长度 为3的通路数目为2， G中 长度为3的路（含回路）总

图的邻接矩阵的 应用 (2)计算结点vi与vj之间的距离。
中不为0的最小的L即为d<vi,vj>。
（一）有向图的可达性矩阵
可达性矩阵表明了图中任意两个结点间是否至少存在一条 路以及在任何结点上是否存在回路。
定义7-3.2 设简单有向图G=（V，E），其中V={v1， v2，…，vn }，n阶方阵P=（pij）nn ，称为图G的可达 性矩阵，其中第i行j列的元素
p ij =
1 1 1 1 P v3 1 1 v4 0 0 v5 0 0 v1 v2 1 1 1 1 1 1
0 1 A(G)= 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0

离散数学-图的矩阵表示

离散数学-图的矩阵表示

使用压缩矩阵
对于稠密图（边数较多的 图），可以使用压缩矩阵 来减少存储空间和计算时 间。
使用动态规划
对于某些特定的问题，可 以使用动态规划来优化算 法，提高计算效率。
05
离散数学-图的矩阵表示的挑战和未
来发展方向
离散数学-图的矩阵表示的挑战
计算复杂性
图的矩阵表示的计算复杂性较高， 特别是对于大规模图，需要消耗 大量的计算资源和时间。
表示图中任意两个顶点之间距离的矩阵， 距离矩阵中的元素d[i][ j]表示顶点i和顶点j 之间的最短路径长度。
图的邻接矩阵
1
邻接矩阵是表示图中顶点之间连接关系的常用方 法，其优点是简单直观，容易理解和计算。
2
邻接矩阵的行和列都对应图中的顶点，如果顶点i 和顶点j之间存在一条边，则矩阵中第i行第j列的 元素为1，否则为0。
THANKS
感谢观看
3
通过邻接矩阵可以快速判断任意两个顶点之间是 否存在边以及边的数量。
图的关联矩阵
01
关联矩阵是表示图中边和顶点之间关系的常用方法，
其优点是能够清晰地展示图中边的连接关系。
02
关联矩阵的行和列都对应图中的边，如果边e与顶点i相
关联，则矩阵中第i行第e列的元素为1，否则为0。
03
通过关联矩阵可以快速判断任意一条边与哪些顶点相
图的矩阵表示的算法复杂度分析
创建邻接矩阵的时间复杂 度：O(n^2)，其中n是顶 点的数量。
查找顶点之间是否存在边 的复杂度：O(1)。
创建关联矩阵的时间复杂 度：O(m)，其中m是边的 数量。
查找边的权重复杂度： O(1)。
图的矩阵表示的算法优化策略
01
02
03

图论 矩阵表示

图论 矩阵表示

21100
定义：设有向图D＝<V，E>中无环，V＝{v1，v2，…，Mv(nG}。)= 0 1 1 0 0
E＝{el，e2,…，em}，
00011
令
1 vi为边ej的起点
mij = 0 vi为边ej不关联
00001
－1 vi为边ej的终点

-1 1 0 0 0
则称(mij)nxm，为D的关联矩阵，记作M(D）
（4）A2中的元素值bij是结点vi到vj长度为2 的通路条数： 说明：由矩阵的乘积定义 bij = ∑k aik * akj
短程线的长度称为u，v之间的距离，记作 d(u，v）
3）结点的可达性： ∀ vi,vj ∈V，若从vi到vj存在通路，则称vi可达vj, 记作vi → vj 规定vi总是可达自身的，即vi → vi结点的可达关系为V上的二元关系 ，但不是等价关系（不满足对称性） 若vi → vj 且vj → vi 则称vi与vj是相互可达的，记作: vi ↔ vj 规定vi ↔ vi ． 相互可达关系为V上的二元关系，且是V上的等价关系．
§14.4 图的矩阵表示
一、图的矩阵表示 用矩阵表示图之前，必须将图的顶点或边标定成顺序，使其成为标定图
1、无向图的关联矩阵 1）定义14．24 设无向图G＝<V，E>，V＝{v1,v2,…，vn}。
E={e1,e2,e3，…em} 令mij为顶点vi与边ej的关联次数，则称(mij)nxm为G的关联矩阵，记作
令aij为顶点vi邻接到顶点vj边的条数，称(aij)nxn为D的 邻接矩阵，记作A(D)，或简记为A．
2）邻接矩阵的性质
（1）每列元素之和为结点的入度，即 ∑aij ＝ d+(vi)，i＝1，2，…，n， 所有列的和 ∑∑aij ＝ ∑d+(vi) ＝ m ，等于边数 每行元素之和为结点的出度，所有行的和也等于边数

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

第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) 接矩阵。

图的矩阵表示

图的矩阵表示

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:矩阵.
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

返回 结束
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
G
e1
v3
e2
v2
e3
v1
e9 e5
e8
e7
v5

e6
bij =
从图的关联矩阵的定义容易得出以下性质：
2 e j 关联于xi，e j 是自环 1 e j 关联于xi，e j 不是自环 0 e 不关联与x j i
(1) B (G ) 的每一列元素之和均为2；
(2) B (G ) 的每一行元素之和等于对应顶点的度数。 (3) 若某行元素全为0，则对应的顶点为孤立点。
返回 结束
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）＝２。 对其他元素读者自己可以找出它的意义。
内容：关联矩阵，邻接矩阵，可达矩阵。 重点：1、有向图，无向图的关联矩阵， 2、有向图的邻接矩阵。 了解：有向图的可达矩阵。
返回 结束
7.3.1 图的矩阵表示
3
存储原则: 存储结点集和边集的信息.
（1）存储结点集； （2）存储边集： 存储每两个结点 是否有关系。
返回 结束
邻接矩阵
7.3.1 邻接矩阵

无向图的关联矩阵
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 的关联矩阵。
10
返回 结束
7.3.1 邻接矩阵
矩阵的计算：
０１００ ００１１ A １１０１ １０００
11
００１１ １０１０ AT ０１００ ０１１０
２１０１ １２０１ AT A ００１１ １１１２
返回 结束
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
2
12
２１０１ １２１１ A3 A2 A ２２１２ ００１１
１２１１ ２２２３ A4 A3 A ３３２３ ２１０１
表示 i 和 j 之间具有长度为 2 A 的通路数， 3 表示i和j之间具有长度为3 A 的通路数， A4 表示i和j之间具有长度为4 的通路数，
第七章 图论
引言 7.1 图的基本概念 7.2 路与连通 7.3 图的矩阵表示 7.4 最短路径问题 7.5 图的匹配 8.1 Euler图和Hamilton图 8.2 树 8.3 生成树 8.4 平面图
1
返回 结束
7.3 图的矩阵表示

2
图的矩阵表示 图的数学抽象是三元组，其形象直观的表 示即图的图形表示。为便于计算，特别为便 于用计算机处理图，下面介绍图的第三种表 示方法—图的矩阵表示。利用矩阵的运算还 可以了解到它的一些有关性质。
长度=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＝
( n 1) 其中元素 pij (i j)可由 Bn 1 bij


n n
求得：
( n 1) 1 b 0 ij pij 0 否则
返回 结束
7.3.3 有向图的可达性矩阵
根据可达性矩阵， 可知图中任意两个结点 之间是否至少存在一条路以及是否存在回路。 利用有向图的邻接矩阵A， 分以下两步可得 到可达性矩阵。
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 ) 由它的顶点与边的关联关系唯一 确定；
返回 结束
(4) 重边所对应的列完全相同。
7.3.2 关联矩阵

19
有向图的关联矩阵
1、设有向图
D V, E ， V v1, v2 ,, vn ，
E e1 , e2 ,, em ，D 的关联矩阵
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的终点
7.3.1 邻接矩阵
2.有向图的邻接矩阵
1、设有向图 D V , E ， V v1, v2 ,, vn ，
(1) E m ，D 的邻接矩阵 A( D ) aij nn ，
14
其中 a 指 vi 邻接到 v j 的边的条数 (非负整数)。
(1) ij
返回 结束
7.3.1 图的矩阵表示
返回 结束
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
9
返回 结束
7.3.1 邻接矩阵
设图Ｇ＝＜Ｖ，Ｅ＞如下图所示 ０１００ ００１１ A １１０１ １０００ 讨论
（1）图G的邻接矩阵中的元素为0和1，∴又称为布尔矩阵； （2）图G的邻接矩阵中的元素的次序是无关紧要的，进行行和行、 列和列的交换，则得到相同矩阵。 ∴若有二个简单有向图，则可得到二个对应的邻接矩阵，若对某一 矩阵进行行和行、列和列之间的交换后得到和另一矩阵相同的矩阵， 则此二图同构。 （3）当有向图中的有向边表示关系时，邻接矩阵就是关系矩阵； （4）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为0； （5）在图的邻接矩阵中， ①行中1的个数就是行中相应结点的引出次数 ②列中1的个数就是列中相应结点的引入次数
e2
v2v1e3v1e9 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
从图的邻接矩阵的定义容易得出以下性质：
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