离散-图论1.ppt

雄关漫道真如铁，而今迈步从头越！ 26--* 在图G1中， 例8.20 由{v2}，{v6}和{v1,v3,v4,v5,v7}导出的子图都是强连通分支； 由{v1,v2,v3,v4,v5,v7}和{v1,v3,v4,v5,v6,v7}导出的子图都是单向连通分支； G1本身为弱连通分支。 在图G2中， 由{v1}，{v2}，{v3}，{v4}和{v5,v6,v7}导出的子图都是强连通分支； 由{v1,v2,v4}，{v1,v3,v4}和{v5,v6,v7}导出的子图都是单向连通分支； 由{v1,v2,v3,v4}和{v5,v6,v7}导出的子图都是弱连通分支。 雄关漫道真如铁，而今迈步从头越！ 26--* 一个等价关系 若在有向图G＝V,E的结点集V上定义二元关 系R为：vi,vj∈R当且仅当vi和vj在同一强（弱）连通分支中，?vi,vj∈V。 　　因为每一个结点vi和自身总在在同一强（弱）连通分支中，所以R是自反的； 　若结点vi和vj在同一强（弱）连通分支中，显然vj和vi也在同一强（弱）连通分支中，所以R是对称的； 又若结点vi和vj在同一强（弱）连通分支中，结点vj和vk在同一强（弱）连通分支中，则vi和vj相互可达，vj和vk相互可达，因而vi和vk相互可达，故vi和vk在同一强（弱）连通分支中，所以R是传递的。 　显然，R是一个等价关系。 雄关漫道真如铁，而今迈步从头越！ 26--* 定理8.8　在有向图G＝V，E，它的每一个结点位于且仅位于一个强（弱）分图中； 定理8.9　在有向图G＝V，E，它的每一个结点至少位于一个单向分图中； 定理8.10　 在有向图G＝V,E中，它的每一条边至多在一个强连通分支中；至少在一个单向连通分支中；在且仅在一个弱连通分支中。 定理 雄关漫道真如铁，而今迈步从头越！ 26--* 在图(a)中，结点v1，v2，v3，v4-仅位于强分图{ v1，v2，v3，v4} 例 中，结点v5-仅位于强分图{ v5} 中，但边v4，v5、v3，v5都不位于强分图中； 结点v1，v2，v3，v4，v5-仅位于单向分图{ v1，v2，v3，v4，v5}，所有的边也都仅位于单向分图中； 结点v1，v2，v3，v4，v5-仅位于弱分图{ v1，v2，v3，v4，v5}；所有的边也都仅位于弱分图中。 在图(b)中，结点v2，v3-和边v2，v3同时位于两个单向分图{ v1，v2，v3}和{v2，v3，v4}中。 雄关漫道真如铁，而今迈步从头越！ 26--* 第200——202页 15 20 21 23 25 习　题 雄关漫道真如铁，而今迈步从头越！ 26--* 8.5　图的矩阵表示 8.5.1　邻接矩阵 定义8.23设G＝V,E是一个线图，V＝{v1, v2,…,vn}，E＝{e1,e2,…,en}，则n阶方阵A＝(aij)n?n称为G的邻接矩阵。其中： 邻接矩阵是一个布尔矩阵 无向线图的邻接矩阵是对称的 而有向线图的邻接矩阵不一定对称 雄关漫道真如铁，而今迈步从头越！ 26--* 例8.21 邻接矩阵： v2,v3,v1,v4： 雄关漫道真如铁，而今迈步从头越！ 26--* 邻接矩阵的性质1 设G＝V，E是一个线图，则有： 当有向线图代表关系时，其邻接矩阵就是前面讲过的关系矩阵。 零图的邻接矩阵的元素全为零，并称它为零矩阵。 图的每一结点都有自回路而再无其他边时，则该图的邻接矩阵是单位矩阵。 简单图的邻接矩阵主对角元全为零。 若设简单图G的邻接矩阵A＝(aij)n×n，则它的补图　的邻接矩阵　　　　　为 雄关漫道真如铁，而今迈步从头越！ 26--* 邻接矩阵的性质2 设无向图G＝V,E，V＝{v1,v2,…,vn}的邻接矩阵A＝(aij)n×n，则 设有向图G＝V,E，V＝{v1,v2,…,vn}的邻接矩阵A＝(aij)n×n，则 雄关漫道真如铁，而今迈步从头越！ 26--* 邻接矩阵的性质3 设图G＝V,E，V＝{v1,v2,…,vn}的邻接矩阵A＝(aij)n×n，则aij表示从结点vi到结点vj长度为1的通路数目，而A中所有元素之和为A中长度为1的通路（包括回路）数目（若G是有向图，它也是边的数目；若G是无向图，它是边的数目的二倍减去G中自回路的数目，因为当vivj时，一条边(vi,vj)即是一条从vi到vj的长度为1的通路，也是一条从vj到vi的长度为1的通路，而(vi,vi)只是一条长度为1的通路，而不能再看作两条）。 雄关漫道真如铁，而今迈步从头越！ 26--* 邻接矩阵的性质4 令B＝(bij)＝A2＝A×A＝(aij(2))n?n，则有： 此时，bij表示从vi到vj长度为2的通路数目，如bij＝0，则无长度为2的通路，而bii表示经过vi 的长