离散数学 课件 第6、7章 代数系统、图.ppt

证明设G中的两个奇结点是v1和v2(1)若G是连通图，则v1和v2之间必有路径；(2)若G是非连通图，则G至少有两个以上的分支因为，在任何一个图中必有偶数个奇结点所以：v1和v2必处于同一个分支中，即：V1和v2之间必有路径。第4节 图的矩阵表示一、邻接矩阵二、可达性矩阵三、完全关联矩阵一、邻接矩阵1、简单无向图的邻接矩阵2、简单有向图的邻接矩阵3、矩阵AAT4、矩阵ATA5、矩阵Am1、简单无向图的邻接矩阵G:简单无向图n阶方阵A=(aij)n×nV={v1,v2,…,vn}邻接矩阵:aij=(vi,vj)?E10否则邻接矩阵举例写出简单无向图G对应的邻接矩阵A。A=abcdeabcde1111111111111100000000000简单无向图邻接矩阵的特点(1)主对角线均为0的对称阵；(2)每一行（列）中“1”的个数是该行所对应的结点的度；(3)所有元素均为“0”的邻接矩阵对应的是零图;(4)除主对角线外所有元素均为“1”的邻接矩阵对应的是完全图。2、简单有向图的邻接矩阵G:简单有向图n阶方阵A=(aij)n×nV={v1,v2,…,vn}邻接矩阵:aij=vi,vj?E10否则邻接矩阵举例写出简单有向图G对应的邻接矩阵A。A=v1v2v3v4v1v2v3v40101111010100000简单有向图邻接矩阵的特点(1)不一定是对称阵；(2)每一行中“1”的个数是该行所对应的结点的出度；(3)每一列中“1”的个数是该列所对应的结点的入度；(4)第i行中“1”的个数与第i列中“1”的个数之和，恰为记点vi的度。二、可达性矩阵1、可达性矩阵P2、求可达性矩阵P的方法1、可达性矩阵PG:简单有向图V={v1,v2,…,vn}n阶方阵P=(pij)n×nG的可达性矩阵pij=10从vi到vj至少存在一条路径否则2、求可达性矩阵P的方法(1)回忆两个定理(2)求可达性矩阵P的方法(1)回忆两个定理若存在从vi到vj的路径，则存在从vi到vj的基本路径；n阶图的基本路径长度小于n;(2)求可达性矩阵P的方法A：aij表示从vi到vj长度为1的路径的数目；A2:aij(2)表示从vi到vj长度为2的路径的数目；……An:aij(n)表示从vi到vj长度为n的路径的数目；令：Bn=A+A2+…+An其中：Bn中第i行第j列的记入值bij表明：从vi到vj长度小于或等于n的路径的数目若bij≠0，则表明从vi到vj可达。求可达性矩阵P的方法（续）A:简单有向图G的邻接矩阵（1）A2=A∧AA3=A2∧A,…,An=An-1∧A（2）P=A∨A2∨…∨An1、路径(1)路径(2)回路(3)简单路径、基本路径(1)路径路径是结点和边的交替序列图G=V,Ev0,v1…vn?Ve1,e2…en?Eei:关联vi-1和vi序列v0e1v1e2…envn:从v0到vn的路路径路径的起点路径的终点路径的长度:路径中边的数目(2)回路起点和终点为同一个结点的路径(3)简单路径、基本路径简单路径:简单回路:基本路径:基本回路:边不重复的路径边不重复的回路点不重复的路径点不重复的回路路径举例(1)AaAcBgChF:(2)AbDdEeBfChF:(3)AbDdEeBcA:从A到F的路径长度为4简单路径不是基本路径从A到F的路径长度为5简单路径基本路径从A到A的回路长度为4简单回路基本回路路径举例v1e2v2e3v3e4v4v4e1v1e2v2e3v3e4v4e1v1简单路径基本路径不是基本路径不是简单路径定理寻找基本路径的方法：v和v’是图G中的结点存在从v到v’的路径存在从v到v’的基本路径从路径中去掉所有的回路证明从v到v′存在路径Pvv′:v0e1v1e2…elvlvv′若Pvv′不是基本路径结点vi在该路径中不止一次出现v0e1v1e2…eiviei+1…ejvjej+1…elvlvi=vj在该路径中去掉从vi到vj的边v0e1v1e2…eiviej+1…elvl从v0到vl的路径如此反复去掉所有的回路从v0到vl的基本路径定理应用举例(1)ae2be10de9ae2be4c:(2)ae1ae2be4c:求从a到c的基本路径是从a到c的一条路径,是从