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

1,第四部分 图论,,,,,2,,,,,,3,,,,,4,第七章 图的基本概念,,,,,5,,,,,6,第一节 无向图及有向图,,,,,7,图1,,,,,8,,,,,V={a,b,c,d} E={,,,,,,},9,,,,,10,,,,,11,,,,,12,,,,,13,,,,,14,,,,,15,,,,,16,,,,,17,,,,,18,,,,,19,,,,,20,,,,,21,,,,,22,,,,,,23,,,,,24,,,,,25,,,,,26,第二节 通路、回路、图的连通性,,,,,27,,,,,28,,,,,29,,,,,30,,,,,31,,,,,32,,,,,不是，删除{ v5}后，p(G-{ v5})>p(G),不满足极小性,33,,,,,34,,,,,35,,,,,36,第三节 图的矩阵表示,,,,,37,,,,,38,,,,,39,,,,,40,,,,,41,,,,,42,,,,,43,第四节 最短路径与关键路径,,,,,44,2.最短路径问题：（1）定义18设带权图G=,G中每条边的权都大于等于0，u，v为G中任意两个顶点，从u到v中的所有通路中带权最小的通路称为u到v的最短路径，求给定两顶点之间的最短路径问题称为最短路径问题（2）Dijkstra算法问题的提法： 给定一个带权有向图D与源点v，求从v到D中其它顶点的最短路径。

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