离散数学图论图矩阵表示PPT学习教案

1、会计学1 离散数学图论图矩阵表示离散数学图论图矩阵表示 内容：内容：关联矩阵，邻接矩阵，可达矩阵。 重点：重点：1、有向图，无向图的关联矩阵， 2、有向图的邻接矩阵。 了解：了解：有向图的可达矩阵。 第1页/共22页 邻接矩阵邻接矩阵 存储原则存储原则: 存储结点集和边集的信息存储结点集和边集的信息. （1 1）存储结点集；）存储结点集； （2 2）存储边集：）存储边集： 存储每两个结点存储每两个结点 是否有关系。是否有关系。 第2页/共22页 ij a i v 12 , p Vv vv 定义 1.6.2设 的顶点集为 ，用 表示 中顶点 与 之间的边数。称矩阵 为 的 邻接矩阵。 ( , )

2、GV E Gj v( )() ijp p M Ga G 从图的邻接矩阵的定义容易得出以下性质： (1) 是一个对称矩阵； (2)若 为无环图。则 中第 行(列)的元素之和等于顶点 的度 数； (3) 两个图 与 同构的充要条件是存在一个置换矩阵 ，使得 。 ( )M G ( )M G( )M G i i v GHP ( )() T M GP M H P 对应的邻接矩 阵 12345 1 2 3 4 5 01011 10211 () 02000 11011 11010 vvvvv v v MG v v v 例2下图所示 的邻接矩阵为： G A( G) A( G) A( G) A( G) A( G

3、) A( G) 相当于将单位 矩阵中相应的 行与行，或者 列与列互换的 矩阵 第3页/共22页 v1 v2 v3 v4 图G1 va vb vc vd 图G2 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 A1 1 2 3 4 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 A2 a b c d v1va v2vb v3vc v4vd 第4页/共22页 所以 n k=1 v k viv j 长度长度 =1 长度长度=l 第5页/共22页 第6页/共22页 2 34 0100010100 1010002000 0100010100 0000100001 0001

4、000010 0200020200 2020004000 0200020200 0000100010 0001000001 AA AA 第7页/共22页 第8页/共22页 设图，如下图所示 讨论 （1）图G的邻接矩阵中的元素为0和1，又称为布尔矩阵； （2）图G的邻接矩阵中的元素的次序是无关紧要的，进行行和行 、列和列的交换，则得到相同矩阵。 若有二个简单有向图，则可得到二个对应的邻接矩阵，若对某 一矩阵进行行和行、列和列之间的交换后得到和另一矩阵相同的 矩阵，则此二图同构。 （3）当有向图中的有向边表示关系时，邻接矩阵就是关系矩阵； （4）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为0；

5、 （5）在图的邻接矩阵中， 行中1的个数就是行中相应结点的引出次数 列中1的个数就是列中相应结点的引入次数 A 第9页/共22页 A T A T AA AAT 主对角线上的数表 示结点i（或j）的 引出次数。 主对角线上的数表示 结点i（或j）的引入次 数。 第10页/共22页 AAA2 AAA 23 AAA 34 表示i和j之间具有长度为 2的通路数， 表示i和j之间具有长度为 3的通路数， 表示i和j之间具有长度为 4的通路数， 2 A 3 A 4 A 第11页/共22页 bij表示从结点vi到vj有长度分别为1，2，3 ，4的不同通路总数。 此时， bij0，表示从vi到vj是可达的。

6、4321 4 AAAAB 第12页/共22页 1、设有向图,DV E 12 , n Vv vv， EmD的邻接矩阵 (1) () ij n n A Da ， 其中指邻接到的边的条数 (非负整数)。 (1) ij a i v j v 第13页/共22页 第14页/共22页 有向图(下图所示)，求D()A D。 解：解： 1210 0010 () 0001 0010 A D 第15页/共22页 一个图 由它的顶点与边的关联关系唯一 确定； ( , )GV E ( )() ijp q B Gb j e i vij b 12 , p Vv vv 定义定义 1.6.1 设 的顶点集和边集分别为 ， 。用

7、 表示顶点 与边 关联的次数(0， 1或2)，称矩阵 为 的关联矩阵。 ( , )GV E 12 , q Ee ee G 第16页/共22页 G 下图所示 的关联矩阵为： 对应的关联矩 阵 123456789 1 2 3 4 5 000010011 111000101 ( ) 110000000 001211000 000001110 eeeeeeeee v v B G v v v 从图的关联矩阵的定义容易得出以下性质： (1) 的每一列元素之和均为2； (2) 的每一行元素之和等于对应顶点的度数。 (3)若某行元素全为0，则对应的顶点为孤立点。 (4)重边所对应的列完全相同。 ( )B G

8、( )B G 2 1 0 jij jij ji exe exe ex 关联于 ， 是自环 关联于 ， 不是自环 不关联与 = ij b 第17页/共22页 1、设有向图有向图,DV E 12 , n Vv vv， 12 , m Ee ee，的关联矩阵 D ()() ijn m M Dm ， 1 0 1 ij ijij ij ve mve ve 为 的始点 与 不关联 为 的终点 其中 2 1 1 0 ji jij jij ji ex Dexe Dexe ex 是自环，且关联与 在 中 以 为起点， 不是自环 在 中 以 为终点， 不是自环 与 不关联 第18页/共22页 有向图(下图所示)，求D()M D。 11000 10111 () 00001 01110 M D 解：解： A(D) A(D) 第19页/共22页 设为有向图，,DV E 12 , n Vv vv 令1 ii p ，1