耿素云等清华版离散数学ppt课件第七章图的基本概念_2.ppt

第四部分 图论,,,,,,,,,,,,,,第七章 图的基本概念,,,,,,,,,第一节 无向图及有向图,,,,,图1,,,,,,,,,V={a,b,c,d} E={,,,,,,},,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,第二节 通路、回路、图的连通性,,,,,,,,,,,,,,,,,,,,,,,,,,,,,不是，删除{ v5}后，p(G-{ v5})>p(G),不满足极小性,,,,,,,,,,,,,第三节 图的矩阵表示,,,,,,,,,,,,,,,,,,,,,,,,,,,,,第四节 最短路径与关键路径,,,,,2.最短路径问题：（1）定义18设带权图G=,G中每条边的权都大于等于0，u，v为G中任意两个顶点，从u到v中的所有通路中带权最小的通路称为u到v的最短路径，求给定两顶点之间的最短路径问题称为最短路径问题（2）Dijkstra算法问题的提法： 给定一个带权有向图D与源点v，求从v到D中其它顶点的最短路径限定各边上的权值大于或等于0求解思想：按路径长度的递增次序，逐步产生最短路径的算法。

首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止例：,v0,v1,v2,v3,v4,3.关键路径问题：(1) 定义19 PERT图（计划评审技术图：Program Evaluation and Review Technic）设D=是n阶有向带权图,满足：① D是简单图② D中并无回路③ 有一个顶点入度为0称此节点为发点；有一个顶点出度为0，称 此节点为收点；④ 记边带的权为wij，它常表示时间；称D为PERT图;(2) PERT图的关键路径：从发点到收点的一条最长路径。