当前位置：文档之家 › 离散数学 图的矩阵表示

离散数学 图的矩阵表示

  • 格式：ppt
  • 大小：354.00 KB
  • 文档页数：25

下载文档原格式

  / 25

合集下载

离散数学课程设计.图的矩阵表示及基本运算

离散数学课程设计.图的矩阵表示及基本运算

中国矿业大学软件开发基础实践报告姓名： xxs 学号： bbaa0edf 专业：计算机科学与技术指导教师： sjc 职称： js(仅供徐海计算机参考哈哈哈哈)2012 年 6 月 20 徐州目录第一章实验概述 (3)1.1实验目的 (3)1.2实验内容 (3)1.3实验环境 (3)第二章实验原理和实现过程 (4)2.1实验原理 (4)2.1.1建立图的邻接矩阵，判断图是否连通 (4)2.1.2 计算任意两个结点间的距离 (4)2.1.3对不连通的图输出其各个连通支 (5)2.2实验过程（算法描述） (5)2.2.1 程序整体思路 (5)2.2.2具体算法流程 (5)第三章实验数据及结果分析 (7)3.1建立图的邻接矩阵并判断图是否连通的功能测试及结果分析 (7)3.1.1输入无向图的边 (7)3.1.2建立图的连接矩阵 (8)3.2其他功能的功能测试和结果分析 (9)3.2.1计算节点间的距离 (9)3.2.2判断图的连通性 (9)3.2.3输出图的连通支 (10)3.2.4退出系统 (10)第四章实验收获和心得体会 (11)4.1实验收获 (11)4.2心得体会 (12)第五章实验源程序清单 (13)5.1程序代码 (13)第一章实验概述1.1 实验目的理解图论的基本概念，图的矩阵表示，图的连通性，图的遍历，以及求图的连通支方法。

通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算，培养逻辑思维；通过实验提高学生编写实验报告、总结实验结果的能力，提高理论联系实际的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。

1.2 实验内容以偶对的形式输入一个无向简单图的边，建立该图的邻接矩阵，判断图是否连通（A），并计算任意两个结点间的距离（B），对不连通的图输出其各个连通支（C）。

注意：题目类型分为A，B，C三类，其中A为基本题，完成A类题目可达到设计的基本要求，其他均为加分题，并按字母顺序分数增加越高。

离散数学图论(图、树)常考考点知识点总结

离散数学图论(图、树)常考考点知识点总结

离散数学图论（图、树）常考考点知识点总结图的定义和表示1.图：一个图是一个序偶＜V , E ＞，记为G =< V ，E >，其中：① V ={V1,V2,V3,…, Vn}是有限非空集合，Vi 称为结点，V 称为节点集② E 是有限集合，称为边集，E中的每个元素都有V中的结点对与之对应，称之为边③与边对应的结点对既可以是无序的，也可以是有序的表示方法集合表示法，邻接矩阵法2.邻接矩阵：零图的邻接矩阵全零图中不与任何结点相邻接的结点称为孤立结点，两个端点相同的边称为环或者自回路3.零图：仅有孤立节点组成的图4.平凡图：仅含一个节点的零图无向图和有向图5.无向图：每条边都是无向边的图有向图：每条边都是有向边的图6.多重图：含有平行边的图(无向图中，两结点之间包括结点自身之间的几条边；有向图中同方向的边)7.线图：非多重图8.重数：平行边的条数9..简单图：无环的线图10.子图，真子图，导出子图，生成子图，补图子图：边和结点都是原图的子集，则称该图为原图的子图真子图（该图为原图的子图，但是不跟原图相等）11.生成子图：顶点集跟原图相等，边集是原图的子集12.导出子图：顶点集是原图的子集，边集是由顶点集在原图中构成的所有边构成的图完全图（任何两个节点之间都有边）13.完全图：完全图的邻接矩阵主对角线的元素全为0，其余元素都是114.补图：完全图简单图15.自补图：G与G的补图同构，则称自补图16.正则图：无向图G=<V,E>,如果每个顶点的度数都是k，则图G称作k-正则图17.结点的度数利用邻接矩阵求度数：18.握手定理：图中结点度数的总和等于边数的两倍推论：度数为奇数的结点个数为偶数有向图中，所有结点的入度=出度=边数19.图的度数序列：出度序列+入度序列20.图的同构：通俗来说就是两个图的顶点和边之间有双射关系，并且每条边对应的重数相同（也就是可任意挪动结点的位置，其他皆不变）21.图的连通性及判定条件可达性：对节点vi 和vj 之间存在通路，则称vi 和vj 之间是可达的22.无向图的连通性：图中每两个顶点之间都是互相可达的23..强连通图：有向图G 的任意两个顶点之间是相互可达的判定条件：G 中存在一条经过所有节点至少一次的回路24.单向连通图：有向图G 中任意两个顶点之间至少有一个节点到另一个节点之间是可达的判定条件：有向图G 中存在一条路经过所有节点25.弱连通图：有向图除去方向后的无向图是连通的判定条件：有向图邻接矩阵与转置矩阵的并是全一的矩阵26.点割：设无向图G=<V,E>为联通图，对任意的顶点w  V,若删除w及与w相关联的所有边后，无向图不再联通，则w称为割点；27.点割集：设无向图G=<V,E>为连通图，若存在点集 ，当删除 中所有顶点及与V1顶点相关联的所有边后，图G不再是联通的；而删除了V1的任何真子集 及与V2中顶点先关的所有边后，所得的子图仍是连通图，则称V1是G的一个点割集设无向图G=<V,E>为连通图，任意边e  E,若删除e后无向图不再联通，则称e 为割边，也成为桥28.边割集：欧拉图，哈密顿图，偶图（二分图），平面图29.欧拉通路（回路）：图G 是连通图，并且存在一条经过所有边一次且仅一次的通路（回路）称为拉通路（回路）30.欧拉图：存在欧拉通路和回路的图31.半欧拉图：有通路但没有欧拉回路32.欧拉通路判定：图G 是连通的，并且有且仅有零个或者两个奇度数的节点欧拉回路判定：图G 是连通的，并且所有节点的度数均为偶数有向欧拉图判定：图G 是连通的，并且所有节点的出度等于入度33.哈顿密图：图G 中存在一条回路，经过所有点一次且仅一次34..偶图：图G 中的顶点集被分成两部分子集V1,V2，其中V1nV2= o ,V1UV2= V ，并且图G 中任意一条边的两个端点都是一个在V1中，一个在V2中35.平面图：如果把无向图G 中的点和边画在平面上，不存在任何两条边有不在端点处的交叉点，则称图G 是平面图，否则是非平面图36.图的分类树无向树和有向树无向树：连通而不含回路的无向图称为无向树生成树：图G 的某个生成子图是树有向树：一个有向图，略去所有有向边的方向所得到的无向图是一棵树最小生成树最小生成树：设G -< V . E 是连通赋权图，T 是G 的一个生成树，T 的每个树枝所赋权值之和称为T 的权，记为W ( T . G 中具有最小权的生成树称为G 的最小生成树最优树（哈夫曼树）设有一棵二元树，若对所有的树叶赋以权值w1,w2… wn ，则称之为赋权二元树，若权为wi 的叶的层数为L ( wi )，则称W ( T )= EWixL ( wi ）为该赋权二元树的权，W ）最小的二元树称为最优树。

《离散数学图论》课件

《离散数学图论》课件
最短路径问题
实现方法：使用 队列数据结构， 将起始节点入队， 然后依次处理队 列中的每个节点， 直到找到目标节
点或队列为空
Dijkstra算法和Prim算法
Dijkstra算法：用于 求解单源最短路径问 题，通过不断更新最 短路径来寻找最短路 径。
Prim算法：用于求解 最小生成树问题，通过 不断寻找最小权重的边 来构建最小生成树。
图的矩阵表示
邻接矩阵的定义和性质
定义：邻接矩阵是一个n*n的矩阵，其 中n是图的顶点数，矩阵中的元素表示 图中顶点之间的连接关系。
性质：邻接矩阵中的元素只有0和1， 其中0表示两个顶点之间没有边相连， 1表示两个顶点之间有一条边相连。
应用：邻接矩阵可以用于表示图的连通 性、路径长度等信息，是图论中常用的 表示方法之一。
图像处理：优化图像分割， 提高图像质量
物流配送：优化配送路径， 降低配送成本
社交网络：优化社交网络 结构，提高用户活跃度
感谢您的观看
汇报人：PPT
数学：用于图论、组合数 学、代数拓扑等领域
物理学：用于量子力学、 统计力学等领域
生物学：用于蛋白质结构、 基因调控等领域
社会科学：用于社会网络 分析、经济模型等领域
图的基本概念
图的定义和表示方法
图的定义：由节点和边组成的数学结构，节点表示对象，边表示对象之间的关系
节点表示方法：用点或圆圈表示 边表示方法：用线或弧线表示 图的表示方法：可以用邻接矩阵、邻接表、关联矩阵等方式表示
顶点和边的基本概念
顶点：图中的基本元素，表示一个对象或事件 边：连接两个顶点的线，表示两个对象或事件之间的关系 度：一个顶点的度是指与其相连的边的数量 路径：从一个顶点到另一个顶点的边的序列 连通图：图中任意两个顶点之间都存在路径 强连通图：图中任意两个顶点之间都存在双向路径

离散数学图的矩阵表示

离散数学图的矩阵表示

A4=
23321
01011
11010
22221
V4
v3
问每条：从vv33到到0 v0v1由1长1长0度上度0为可为22看的的路出路有A，n几中中条间元？02肯素11定a01经ij的11过10意1个义中：间结点vk，
A该 即 逐(G路个v)23=,k表遍v示历k,1为0201每=11111：个。a0101iv结每j=31100点k有1000表，v一k 示并个进v从vA1k，(，行Gv)在i3就乘到= 邻对法v接j应运长100矩一算302度阵个，111为中110v获3n110,，k取的v就从k路,1是=v3有1：到；kvv31条,k全=。1部，长vk度,1=为1，2 的路的数目：v3,1v1,1+v3,2其v中21+a3v2=3,33表v示3,1v+3到v3,v42长v4度,1+为v33,的5路v5,有1=3条v。3,ivi,1
由于，邻接矩阵的定义与关系矩阵表示定义相同，所以，可达性
矩阵P即为关系矩阵的MR+，因此P矩阵可用Warshall算法计算。
13
❖可达性矩阵的求解方法
23221 35332 58553 12111 46442
Br的任一元素bij表示的是从vi到vj长度不超过r的路的数目；
若bij 0，
若bij=0，
ij时，表示vi到vj可达， i=j时，表示vi到vi有回路；
ij时，表示vi到vj不可达， i=j时，表示vi到vi无回路；
在许多实际问题中，我们关心的往往是vi和vj之间是否存在路的 问题，而对路的数目不感兴趣，为此，引出可达矩阵。
由7.2.1推论，若从vi到vj存在一条路，则必存在一条边数小于n 的通路，（或边数小于等于n的回路）。即：如果不存在一条小

《离散数学》第6章 图的基本概念

《离散数学》第6章 图的基本概念

E ' E )。
生成子图—— G ' G 且 V ' V 。
导出子图 ——非空 V ' V ，以 V ' 为顶点集， 以两端均在 V ' 中的边的全体为边集的 G 的 子图，称 V ' 的导出子图。 ——非空 E ' E ，以 E ' 为边集，以
E ' 中边关联的顶点的全体为顶点集的 G 的子
0 vi与ek 不关联 无向图关联的次数 1 vi与ek 关联1次 2 v 与e 关联2次(e 为环) i k k
1 vi为ek的始点 有向图关联的次数 0 vi与ek 不关联 1 v 为e 的终点 (无环) i k
点的相邻——两点间有边，称此两点相邻 相邻 边的相邻——两边有公共端点，称此两边相邻
孤立点——无边关联的点。 环——一条边关联的两个顶点重合，称此边 为环 (即两顶点重合的边)。 悬挂点——只有一条边与其关联的点，所
对应的边叫悬挂边。
(3) 平行边——关联于同一对顶点的若干条边 称为平行边。平行边的条数称为重数。 多重图——含有平行边的图。
简单图——不含平行边和环的图。
如例1的(1)中，
第六章 图的基本概念 第一节 无向图及有向图
内容：有向图，无向图的基本概念。
重点：1、有向图，无向图的定义， 2、图中顶点，边，关联与相邻，顶点 度数等基本概念，
3、各顶点度数与边数的关系
d (v ) 2m 及推论，
i 1 i
n
4、简单图，完全图，子图， 补图的概念， 5、图的同构的定义。
一、图的概念。 1、定义。 无序积 A & B (a, b) a A b B 无向图 G V , E E V & V ， E 中元素为无向边，简称边。 有向图 D V , E E V V ， E 中元素为有向边，简称边。

离散数学第8章 图论

离散数学第8章 图论
ij
为d（vi，vj）。
8.2
图的矩阵表示
一、图的邻接矩阵 二、图的连接矩阵
三、图的关联矩阵
二、图的连接矩阵 定义 8-9 设图 G= （ V ， E ），其中 V={v1 ，
v2 ， … ， vn } ， n 阶方阵 C= （ cij ），称为图 G 的连接 矩阵，其中第i行j列的元素
1 c ij 0
利用邻接矩阵，我们可以 （1）判断G中任意两个结点是否相连接；
方法是：对 l=1，2，…，n–1，依次检查Al的（i，j）
项元素
(l （ ) ij）是否为0，若都为0，那么结点v 与v 不 a ij i j
相连接，否则vi与vj有路相连接。 （2）计算结点vi与vj之间的距离。
(1) ( 2) ( n 1) 中至少有一个不为0， 若 aij , aij , , aij 则可断定vi与vj相连接，使 a (l ) 0 的最小的 l 即
若中有相同的结点，设为ur= uk（r<k），则子路ur+1…uk可以从 中删去而形成一条较短的路= viu1…ur uk+1…uh–1 vj，仍连接vi到 vj 。 若中还有相同的结点，那么重复上述过程又可形成一条 更短的路，…。这样，最后必得到一条真路，它连接vi到vj， 并短于前述任一非真路。因此，只有真路才能是短程。
非真 生成
真 生成
真 非生成
非真 非生成
真 非生成
七、路与回路 定义:图G中l条边的序列{v0，v1}{v1，v2}…{vl–1，vl}称为连
接v0到vl的一条长为 l 的路。它常简单地用结点的序列 v0v1v2…vl–1vl来表示。其中v0和vl分别称为这条路的起点和终点。 开路：若v0vl，则称路v0v1v2…vl–1vl为开路； 回路：若v0=vl，则称路v0v1v2…vl–1vl为回路； 真路：若开路v0v1v2…vl–1vl中，所有结点互不相同（此时所有 边也互不相同），则称该路为真路； 环：在回路v0v1v2…vl–1v0中，若v0，v1，v2，…，vl–1 各不相同 （此时所有边也互不相同），则称该回路为环。

离散数学第九章 图的基本概念及其矩阵表示

证明：设 V1 {v v 为奇点} ， V2 {v v 为偶点} ，则 d (v) d (v) d (v) 2m 因为
奇数，因此
vV1
d (v) 是偶数，所以 d (v) 也是偶数，
V1 为偶数。
vV2
而 V1 中每个点 v 的度 d (v) 均为
vV1
vV2
图9.11 1至3阶完全有向图
显然，完全无向图的任意两个不同结点都邻接，完全有向图的任意两个不同结点之间都有 一对方向相反的有向边相连接。
9.1 图的基本概念
定理9.3 n个节点的无向完全图 证明：因为在无向完全图
k n 的边数为 Cn2 。
k n 中，任意两个节点之间都有边相连，所以 n
2 2 个节点中任取两个点的组合数为 Cn ，故无向完全图 的边数为 Cn 。
如果在
k n 中，对每条边任意确定一个方向，就称该图为 n 个节点的
2 有向完全图。显然，有向完全图的边数也是 Cn 。
主要内容
PART 01
PART 02
图的基本概念 子图和图的运算 路径、回路和连通性
图的矩阵表示
PART 03
PART 04
9.2 子图和图的运算
子图和补图
定义9.10 设 G V , E , 和 G ' V '（1）如果 V ' V , E ' E , ' ，则称 G ' 是 G 的子图，记作 G ' G， 并称 G 是 G ' 的母图。 （2）如果 V ' V , E ' E , ' ，则称 G ' 是 G 的真子图，记作
9.1 图的基本概念

离散数学 图论-通路与回路

2、简单通路和初级通路的关系
有向图中的每一条初级通路，也都必定是简单通路。 反之不成立 回路也可分为简单回路和初级回路。
3、通路的表示：
可仅用通路中的边序列表示：e1e2…ek 也可仅用通路中所经过的结点的序列表示：v1v2v3…vk
4、性质： 1）定理 在n阶图D中，若从顶点vi到vj(vi≠vj)存在通路，则从vi到vj存在长度 小于或等于(n—1)的通路 若大于n-1，则存在相同节点（有回路），将回路删去可得 2）在n阶图D中，若从顶点vi到vj存在通路，则vi到vj一定存在长度小于或等于 n—1的初级通路(路径) 3）定理 在一个n阶图D中，若存在vi到自身的回路，则一定存在vi到自身长度 小于或等于n的回路． 4）在一个n阶图D中，若存在vi到自身的简单回路，则一定存在长度小于或等 于n的初级回路．
（3）A(D)中所有元素之和为D中长度为1的（边）通路总条数。 主对角线的元素值为图中结点vi长度为1 的环的条数
利用A(D)确定出D中长度为L的通路数和回路数,就需要用到邻接矩阵的幂次运算 （4）A2中的元素值bij是结点vi到vj长度为2 的通路条数：
说明：由矩阵的乘积定义 bij = ∑k aik * akj 由此可推断，A3矩阵中的Cij元素值，表示了从到长度恰为3的通路条数目 （5）定理14．11 设A为有向图D的邻接矩阵，V＝{v1，v2，…，vn} 为D的
注：三种图的关系：强连通图一定是单向连通图，反之不成立
单向连通图一定是弱连通图．反之不成立
6、有关强连通图与单向连通图的判定 （1）定理： 设有向图D＝<V，E>，V＝{v1，v2，…，vn}．
D是强连通图当且仅当D中存在经过每个顶点至少一次的回路． (2) 定理 设D是n阶有向图

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


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称为通路长度.

图的矩阵表示 北京大学计算机系离散数学讲义


《集合论与图论》第22讲
18
定理4(证明)
证明: (归纳法) (1)r=1: a(1)ij=aij, 结论显然. (2) 设rk时结论成立, 当r=k+1时, a(k)it•a(1)tj=从vi到vj最后经过vt的长度为 k+1的通路总数, a(k+1)ij=nt=1a(k)it•a(1)tj=从vi到vj的长度为 k+1的通路总数. #
0
0
《集合论与图论》第22讲
27
相邻矩阵与通路数
设Ar=Ar-1•A,(r2), Ar=[a(r)ij]nn, Br=A+A2+…+Ar= [b(r)ij]nn
定理5: a(r)ij=从vi到vj长度为r的通路总数 ni=1a(r)ii=长度为r的回路总数. #
推论1: a(2)ii=d(vi). # 推论2: G连通距离d(vi,vj)=min{r|a(r)ij0}.
A(D)=[aij]nn, aij = 从vi到vj的边数
v1
v2
2020/7/2
v4
v1 v2
v1 A(D) v2
0 0
2 0
v3 v4
1 0
1
0
v3
v3 v4
0 0
0 0
0 1
1
1
《集合论与图论》第22讲
16
有向图邻接矩阵(性质)
每行和为出度: nj=1aij=d+(vi) 每列和为入度: ni=1aij=d-(vj) 握手定理: ni=1nj=1aij=ni=1d-(vj)=m 环个数: ni=1aii
《集合论与图论》第22讲
2,3,4 2,3,5 2,3,6 2,4,5 2,4,6 2,5,6 3,4,5 3,4,6 3,5,6 4,5,6
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

(4) 平行边对应的列相同
7
有向图的邻接矩阵
定义 设有向图D=<V,E>, V={v1, v2, …, vn}, E={e1,
( e2, …, em}, 令 aij1) 为顶点vi邻接到顶点vj边的条数，
称(ij1) a(
)mn为D的邻接矩阵, 记作A(D), 简记为A.
8
求下图G的邻接矩阵。
18
有向图的可达矩阵(续)
例 右图所示的有向图D的可达矩阵为
1 1 P 1 1
0 0 0 1 1 1 0 1 1 0 1 1
19
设G=V,E是n阶简单有向图，V={v1,v2,…,vn}， 由可达性矩阵的定义知，当i≠j时，如果vi 到vj 有路， 则pij=1；如果vi 到vj 无通路，则pij=0；又如果vi 到vj 有通路，则必存在长度小于等于n–1的通路。又n 阶图中，任何回路的长度不大于n ，如下计算图G 的可达性矩阵P： B=E+A+A2+…+A n-1 =(b ij ) n×n 其中 E 是单位矩阵。则
0 2 0 0 0
1 0 1 0 0
0 0 0 1 0
0 0 0 0 1
0 2 A3 0 0 0
2 0 0 0 0 2 0 0 2 0 0 0 0 0 0 1 0 0 1 0
2 0 4 A 2 0 0
0 2 0 0 4 0 0 0 0 2 0 0 0 0 1 0 0 0 0 1
1 0 A2 1 0 3 1 A3 2 1
15


所以，由v1到v3长度为1、2、3、4的通路 分别有0、2、2、4条，G中共有长度为4的 通路43条，其中回路11条，长度小于等于4 的通路共有87条，其中回路22条。 注 无向图也有相应的邻接矩阵，一般只考 虑简单图，无向图的邻接矩阵是对称的， 其性质基本与有向图邻接矩阵的性质相同。
16
例如:下图邻接矩阵为：
0 1 A(G ) 0 1
1 0 1 1
0 1 0 1
1 1 1 0
17
有向图的可达矩阵
定义 设D=<V,E>为有向图, V={v1, v2, …, vn}, 令
1, vi可达v j pij 0, 否则
称(pij)nn为D的可达矩阵, 记作P(D), 简记为P. 性质: P(D)主对角线上的元素全为1. D强连通当且仅当P(D)的元素全为1.
(1) ( 2) ( 3) (4)
( aij1 ) d ( vi ), j 1 n ( aij1 ) d ( v j ), i 1 n
i 1, 2,..., n j 1, 2,..., n
( aij1 ) m D中长度为 1 的通路数 i, j ( aii1 ) D中长度为 1 的回路数 i 1 n
6
有向图的关联矩阵(续)
性质
m 0 ( j 1,2,..., m ) ( 2) ( m 1) d ( v ), ( m 1) d ( v ), i 1,2,..., n ( 3) m 0
(1)
n i 1 m ij j 1 ij i m j 1 ij i ij i, j
23
P=
可达性矩阵用来描述有向图的一个结点到另 一个结点是否有路，即是否可达。无向图也 可以用矩阵描述一个结点到另一个结点是否 有路。在无向图中，如果结点之间有路，称 这两个结点连通，不叫可达。所以把描述一 个结点到另一个结点是否有路的矩阵叫连通 矩阵，而不叫可达性矩阵。
24
定义 设G=V,E是简单无向图，V={v1,v2,…,vn}
11
D中的通路及回路数(续)
推论 设Bl=A+A2+…+Al(l1), 则Bl中元素
( bijl ) 为D中长度小于或等于l 的通路数， i i 1
为D中长度小于或等于l 的回路数.
例 有向图D如图所示, 求A, A2, A3, A4, 并回答诸问题： (1) D中长度为1, 2, 3, 4的通路各有多 少条？其中回路分别为多少条？ (2) D中长度小于或等于4的通路为多 少条？其中有多少条回路？
2
例:求下图G的关联矩阵
e1
4 1
e2
2
e3 e4
e5
3

上图G的关联矩阵:
1 2 M (G ) 3 4
e1 e2 e3 e4 e5
2 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1
3
无向图的关联矩阵
性质：
m 2 ( j 1,2,..., m ) ( 2) m d ( v ) ( i 1, 2,..., n) ( 3) m 2m
P(G)=( pij) n×n
vi 与v j 连通 1 其中： pij vi 与v j 不连通 0
i,j=1,…,n 称P(G)为G的连通矩阵。简记为P。 无向图的邻接矩阵是对称阵，无向图的连通矩
阵也是对称阵。求连通矩阵的方法与可达性矩阵类
似。
25
回路
8 11 14 17 50
1 3 1 3 8
13
在下图中v1到v3长度为1、2、3、4的通路分别有 多少条，G中共有长度为4的通路多少条，其中回 路多少条，长度小于等于4的通路共有多少条，其 中回路多少条。
1
4
2
3
14

解:因为
2 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 2 2 2 2 1 0 A4 2 2 1 2 1 0 2 0 0 1 1 0 1 0 0 0 1 1 0 1 0 1 5 6 4 2 2 2 2 1 4 4 3 2 2 2 2 1 2 2 0 0 0 1 2 1 0 0 0 1
12
例(续)
1 2 A 1 1 1 4 A3 3 3 0 0 0 1 0 3 0 0 1 0 A2 2 0 0 0 1 0 1 0 2 0 0 0 0 1 0 5 0 0 1 0 A4 4 0 0 0 1 0 1 0 4 0 0 0 长度 通路 0 1 1 1 0 2 0 1 3 0 0 4 0 1 合计 1 0 0 1
1 4
2
3

解 上图G的邻接矩阵。
1 0 A(G ) 1 0 2 0 0 0 0 1 0 1 0 0 1 0
给出了图G的邻接矩阵，就等于给出了图G的全部
信息。图的性质可以由矩阵 A通过运算而获得。
9
有向图的邻接矩阵
定义 设有向图D=<V,E>, V={v1, v2, …, vn}, E={e1, ( e2, …, em}, 令 aij1) 为顶点vi邻接到顶点vj边的条数， 称(ij1) )mn为D的邻接矩阵, 记作A(D), 简记为A. a( 性质
22
4 3 0＋A＋A2＋A3＋A4 = B= A 3 0 0
3 7 3 0 0
3 3 4 0 0
0 0 0 3 1
0 0 0 1 3
则图G的可达性矩阵
1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1
(1)
n i 1 m ij j 1 ij i ij i, j
( 4) 平行边的列相同
（5） j 1 mij 0, 当且仅当vi为孤立点。
m
4
有向图的关联矩阵
定义 设无环有向图D=<V,E>, V={v1, v2, …, vn}, E={e1, e2, …, em}, 令
1 , vi为e j的始点 mij 0 ， vi与e j 不关联 1 ， v 为e 的终点 i j
10
D中的通路及回路数
定理 设A为n阶有向图D的邻接矩阵, 则Al(l1)中
元素
( aijl ) 为D中vi到vj长度为 l 的通路数，
a
(l ) ii 为vi到自身长度为
n
l 的回路数，
( aijl ) 为D中长度为 l 的通路总数， i 1 j 1 n (l) ii i 1
n
a 为D中长度为 l 的回路总数.
1 bij 0 pij 0 bij 0
20
图9.24邻接矩阵A和A2，A3，A4如下：
0 1 A 0 0 0
1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0
21
1 0 A2 1 0 0
7.3 图的矩阵表示
无向图的关联矩阵 有向图的关联矩阵 有向图的邻接矩阵 有向图的可达矩阵
1
无向图的关联矩阵
定义 设无向图G=<V,E>, V={v1, v2, …, vn}, E={e1,
e2, …, em}, 令mij为vi与ej的关联次数，称(mij)nm为G
的关联矩阵，记为M(G).
则称(mij)nm为D的关联矩阵，记为M(D).
5
例:
求图G的关联矩阵。
e2
2
e3 e1
1
3
e5
e6
5 4
e4
上图G的关联矩阵:
1 2 M (G ) 3 4 5
e1 e2 e3 e4 e5 e6
1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 1 0 0 0 0 0 0