图论(网络)模型与案例分析.ppt

图论（网络）模型与案例分析 第1讲 图的基本概念、画法及计算机存取 子图 图的其它术语 C. 图的计算机存取 邻接矩阵 邻接矩阵 加权邻接矩阵 邻接表(仅供计算机编程参考，略讲或不讲) 邻接表 邻接表 邻接表 邻接表的实现 邻接表的实现 十字接表 十字接表 邻接多重表 邻接多重表 第2讲 图的连通性、图的遍历、图的最小生成树 2.1.3 无向连通图的生成树 (1) 深度优先有哪些信誉好的足球投注网站 深度优先有哪些信誉好的足球投注网站举例 深度优先有哪些信誉好的足球投注网站的实现 （2）广度优先有哪些信誉好的足球投注网站 广度优先有哪些信誉好的足球投注网站举例① Prim算法程序设计 2.2.2 有向图的强连通分支及求法 2.2.2 有向图的强连通分支及求法 有向图的强连通分量的求法 第3讲 最短路径问题、匹配问题、一笔画问题 3.1 最短路问题 Dijstra算法的改进（双标法号） 在施行过程中，对于每个顶点Vj都要赋予一个标号，这分为固定标号（P标号）和临时标号（T标号）两类，含义如下： P标号：从起点到当前顶点的最短路长 。 T标号：从起点到当前顶点的最短路线长度的上界。 注：每个顶点的标号只能够是P和T二者之一。如果为T标号，则有待修改，而一旦成为P标号，则固定不变了。标号过程正是将T标号顶点逐步修改为P标号顶点的过程。 具体标号过程 开始先给起点V1标上P标号0，给其余顶点标上T标号∞，然后检查与V1相邻的一切顶点Vj,选取到起点距离最小者，将其顶点T标号修改为P标号； 以后每次检查刚得到P标号的顶点，检查与它相邻的一切顶点,同样从中选取到起点距离最小者，将其顶点T标号修改为P标号； 由于每次都将一个T标号修改为P标号，总共n个顶点，故最多需要 n-1次就可以将终点改为P标号。 求最短路例（双标法号） 具体问题描述： 有n个女士和n个男士参加舞会，每位女士与其中若干位男士相识，每位男士与其中若干位女士相识，问如何安排，使得尽量多配对的男女舞伴相识。 下图就是一种分配方法： 匹配问题是运筹学的重要问题之一，也是图论的重要内容，它在所谓“人员分配问题”和“最优分配问题”中有重要作用。 假定有一个男生有穷集合，其中每个男生认识一些女生，在什么条件下每个男生都可以和他认识的女生配对？ 类似的工作分配问题：现有n个人，m份工作，每个人有其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作？如何分配？ 定义：若图G=(V,E)的顶点可以分成X，Y两个子集，每个子集里的顶点互不相邻，这样的图称为二分图。 定义：若M是图G=(V,E)的边子集，且M中的任意两条边在G中不相邻，则称M为G中的一个匹配。 定义：若图G中每个顶点均被M许配时，称M为G中的一个完美匹配。 定义：图G中边数最多的匹配M，称为G中的一个最大匹配。 定义：若匹配M的某边和顶点v关联，称v是M-饱和的，否则就是M-不饱和的。 定义：若M是图G的一个匹配，若从G中一个顶点到另一个顶点存在一条道路，此路径由属于M和不属于M的边交替出现组成的，则称此路径为M-交错路。 定义：若交错路的两个端点为关于M的不饱和顶点，称此交错路为一条可增广路。 定理 (Berge 1957)：M为最大匹配的充要条件是：图G中不存在可增广路。 Hall定理(1935)：二分图G存在一匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X任一子集A，恒有：|N(A)|≥|A|，其中N(A)表示A的邻接点集。 1965年，匈牙利著名数学家Edmonds设计了一种求最大匹配的算法，称为匈牙利(Hungarian)算法。 匈牙利(Hungarian)算法： （1）任给一个初始匹配； （2）若X已经饱和，结束；否则转（3）； （3）在X中找一个非饱和点x0，V1={x0}，V2=空集； （4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2； （5）若y已饱和， M中必有(y,z) ；作V1 =V1 ∪{z} ， V2 =V2∪ {y}，转（4）；否则，求一条从x0到y的 可增广道路P，对之进行增广，转（2）。 用匈牙利算法求下图的最大匹配： （1）任给一个初始匹配； （2）若X已经饱和，结束；否则转（3）； （3）在X中找一个非饱和点x2，V1={x0}，V2=空集； （4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2 （5）若y已饱和，M中必有(y,z) ；作【 V1 =V1 ∪{z} ， V2 =V2∪ {y}； 转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】 （4）若N(V1)=V2则停止，否则任选一点y∈N(V1)-V2； （5）若y已饱和， M中必有(y,z) ；作【 V1 =V1 ∪{z} ， V2 =V2∪ {y}； 转（4）】，否则【求