08图论模型.ppt

第八章 图论 图论 Graph Theory Leonhard Euler (1707-1783) 在1736年发表第一篇图论方面的论文，奠基了图论中的一些基本定理 很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联 节点 (Vertex) 物理实体、事物、概念 一般用 vi 表示 边 (Edge) 节点间的连线，表示有关联 一般用 eij 表示 图 (Graph) 节点和边的集合 一般用 G(V,E) 表示 点集 V={v1,v2,…, vn} 边集E={eij } 所有边都没有方向的图称为无向图，如上图 在无向图中 eij=eji，或 (vi, vj)=(vj, vi) 当所有边都有方向时，称为有向图，用G(V,A)表示 在有向图中，有向边又称为弧，用 aij表示，i, j 的顺序是不能颠倒的，图中弧的方向用箭头标识 图中既有边又有弧，称为混合图 图中可以只有点，而没有边；而有边必有点 若节点vi, vj 之间有一条边 eij，则称 vi, vj 是 eij 的端点(end vertex)，而 eij 是节点 vi, vj 的关联边(incident edge) 同一条边的两个端点称为相邻(adjacent)节点，具有共同端点的边称为相邻边 一条边的两个端点相同，称为自环(self-loop)；具有两个共同端点的两条边称为平行边(parallel edges) 目录 最优连线问题 最短通路问题 贮藏问题 最大流问题 循环赛名次问题 排课表问题 8.1.1 问题的背景与提出 8.1.2 模型假设与符号说明 a） 假设要建造一个连接 个城镇的通信网络； b） 第 个城镇与第 个城镇之间直通线路的造价为 。 8.1.3 模型的建立与求解 8.1.4 模型实验 8.1.5 模型的分析与讨论 8.2 最短通路问题 8.2.1 问题的背景与提出 8.2.2 模型假设与符号说明 8.2.3 模型的建立与求解 8.2.4 模型实验 8.2.5 模型的分析与讨论 8.3 贮藏问题 8.3.1 问题的背景与提出 8.3.2 模型假设与符号说明 8.3.3 模型的建立与求解 我们构造一个图 ,其顶点集是 两个顶点 和 相连当且仅当化学制品 和 互不相容。 8.3.4 模型实验 8.3.5 模型的分析与讨论 8.4 最大流问题 8.4.1 问题的背景与提出 8.4.2 模型假设与符号说明 8.4.3 模型的建立与求解 8.4.4 模型实验 8.4.5 模型的分析与讨论 8.5.1 问题的背景与提出 在体育比赛中，特别是分组赛上，经常要进行循环赛，循环赛结束后，根据比赛结果排出名次．也就是参赛队两两交锋，单循环比赛，最后根据比赛结果排出名次．问题是：在循环赛结束后，怎样根据参赛队的结果排列名次呢？这需要我们更加仔细合理． 乒乓球单循环比赛中名次问题？ 乒乓球单循环比赛中：甲胜乙3：1，输丙2：3；乙胜丙3：2，输甲1：3丙胜甲3：2输乙2：3 请判断甲乙丙的名次，为什么？ 单循环的名次按选手胜负的【人数】来排列，如果选手最后胜负的人数一样，就按他们所胜的【场数】（打一个人通常要胜几场、败几场）来排，如果所胜的场数也一样的话就按两人的胜负关系来排。按照这个方法推出甲、乙、丙的名次为： 丙第一、甲第二（因为输给了丙）、乙第三 因三者三角互赢，故应按净胜场次算，甲净胜1场，乙-1场，丙0场，所以甲第一，丙第二，乙第三。 计算三者的胜负比率，（胜局数为分子，负局数作分母），比率大的名次列前。 甲的胜负比率：(3＋2)/(1＋3)＝5/4＝1.25 乙的胜负比率：(3＋1)/(2＋3)＝4/5＝0.8 丙的胜负比率：(3＋2)/(2＋3)＝5/5＝1 1.25＞1＞0.8；所以甲的名次为1、丙的名次为2、乙的名次为3。 如果胜负比率都一样，那就要算他们的胜负分比率。方法是把他们三人各自取得的分数做分子，负的分数做分母。算出来的结果大的，名次列前。 8.5.2 模型假设与符号说明 8.5.3 模型的建立与求解 8.5.4 模型实验 8.5.5 模型的分析与讨论 循环赛名次问题，也是一个排序和评价问题．其排名方法可能很多，如用第四章中的层次分析法排序．也可以逆向思维，考虑各参赛队的失分向量，不妨一试． 8.6