离散数学图基本概论.pptVIP

图的基本概念;计算机科学广泛应用于运筹学，信息论，控制论，网络理论，化学生物学，物理学。原因在于这些学科的许多实际问题和理论问题可以概括为图论。第八、九章介绍与计算机科学关系密切的图论内容及其在实际中的应用。;8.1 无向图及有向图;无向图：无向图G是一个二元组 V,E ，其中;v4;有向图：有向图D是一个二元组 V,E ，其中;有限图：V，E均为有穷集合;顶与顶相邻：如果ek = (vi,vj) ?E，称vi与vj相邻；;孤立点：无边关联的顶点。;度：(1) 在无向图G = V, E 中，与顶点v(v?V)关联的边的数目(每个环计算两次)，记作：d(v)。;(2) 在有向图D = V,E 中，以顶点v(v?V)作为始点的边的数目，称为该顶点的出度，记作： d+(v)；;;;例8.1 (3,3,2,3)，(5,2,3,1,4)能成为图的度数序列吗？为什么？;例8.2 已知图G中有10条边，4个3度顶点，其余顶点的度数均小于等于2，问G中至少有多少个顶点？为什么？;;(2) 设D = V,E 是n阶的有向简单图，如果D中任意顶点u，v?V(u?v)，即有有向边 u,v ，又有有向边 v,u ，则称D为n阶有向完全图。;四、子图与母图：;(3) 设V1?V，且V1??，以V1为顶点集，以2端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图。;例8.3 列举下图的一些子图、真子图、生成子图、导出子图。;;;;例8.4 画出4个顶点3条边的所有可能非同构的无向简单图。;例8.5 画出3个顶点2条边的所有可能非同构的有向简单图。; 8.2 通路、回路、图的连通性;简单通路： ? = v0 e1 v1 e2… ek vk为通路且边e1 e2… ek 互不相同，又称之为迹，可简用v0 v1 … vk 来表示。;例8.6 就下面两图列举长度为5的通路，简单通路，回路，简单回路，再列举长度为3的基本通路和回路。;v1;(2)中 v1e2v2e5v3e7v4 v1到v4的长度为 了的基本通路；;二、通路与回路的性质：;(2) 在n阶图中，如果从vi到vj (vi?vj)存在通路，则必存在从vi到vj 的长度小于等于 n–1的基本通路。;两顶点连通：u,v为无向图G的两个顶点，u到v存在一条通路。;连通性的性质：无向图中顶点之间的连通关系是顶点集V上的等价关系。;连通分支：无向图G中每个划分块称为G的一个连通分支，p(G)表示连通分支的个数。p(G) = 1为连通图。;点割集：无向图G = V,E 为连通图，如果V?V，且在G中删除V中所有顶点(包括与该顶点关联的边)后所得子图是不连通的或是平凡图，而删除V中任何真子集中的顶点时，所得子图仍连通，则V是G的点割集。 ;点连通度：G为无向连通图，记k(G) = min{|V| V是G的点割集}，称k(G)为G的点连通度。 ;边割集：设无向图G = V,E 连通，边集E?E，在G中删除E中所有边后所得子图不连通，而删除E中的任何子集中的边后，所得子图仍连通，则E为G的边割集。;;五、有向图的连通性：;有向连通图的性质：;(2) 有向图D强连通，当且仅当D中存在一条回路，它至少经过每个顶点一次。;因为vi可达vi+1, i=1,2,…，n–1，让这些通路首尾相连，;8.3 图的矩阵表示;邻接矩阵的特性：在无向图中：;在有向图中：; 邻接矩阵可推广到多重图或带权图，这时令aij为vi到vj的边的重数或边上的权值W(vi, vj)。;关联矩阵：;(2) 设D = V,E 是有向图且无环，令：;无向图的关联矩阵的性质：;有向图的关联矩阵的性质：;通路数与回路数的矩阵算法：;(2) 设A是有向图D的邻接矩阵，B1 = A，B2 = A+A2,……，Br = A+A2+…+Ar，则Br中元素bij(r) 为D中vi到vj长度小于等于 r 的通路数，;可达矩阵：;例. 求下图的可达矩阵，判断它是否为强连通图？;2. 计算 A2, A3, A4, A5.;3. 计算 B = A +A2 + A3 + A4 + A5 , 并求出;可达矩阵的求法：由邻接矩阵A计算A2,A+A2,…… A+A2+…+A(n–1) = B = (bij(n–1))n?n ;8.4 最短路径问题;G = V,E,W 为带权图，且G中各边带的权均大于等于0，从顶点u到顶点v的所有通路中求带权最小的通路问题，称为最短路径问题。;标号法：(1) 符号说明;(2) 算法：;修改通过集和未通过集：Pr = Pr–1∪{vi}， Tr = Tr–1∪{vi}，;step2. 修改Tr中各顶点的t标号;例8.7 求下图中顶点v0与v5之间的最短路径;解