图论课件课件.ppt

* 用点表示城市，两点连线当且仅当两城市有航线。为了 求出两城市间最短航线，需要在线的旁边注明距离值。 例如：令V={a, b, c, d, e}代表5个城市} E={a b, ad, b c , be, de}代表城市间的直达航线 则航线图的图形为： a b c d e 500 320 140 430 370 请求出从d到c的最短路 (3) 最短航线问题 * (4) 任务分配问题 有一个旅行团要组织一批人去旅游，其中一些人是朋友 他们要乘坐公共汽车去，而车上的位子是成对的。因此 为了让大家旅途更愉快，旅行团负责人需要将成对的朋 友安排在一起。给出一种安排方案。 该问题可以建立一个图论模型来解决：旅行团的人抽象 为图的顶点，两个顶点连线，当且仅当两个顶点代表的 人是朋友。 问题归结于在模型图中求所谓的“匹配”，关于图的匹配 将在第五章介绍。 * (5) 考试时间安排问题 一个教授需要对期末考试时间进行安排，使得学生们 不会有相互冲突的考试。如何解决？ 该问题可以建立一个图论模型来解决：待考的课程可 抽象为图的顶点，连接两个顶点的边表示至少有一个学生 同时选择了这两门课程。 问题归结于在模型图中求所谓的“顶点着色方案”问题， 该问题将在第六章讨论。 例如：有a, b, c ,d, e, f 六门课程。按照上面方法建立 的模型图如下： * 一种可行的安排方案为：第一时间：a, d, e;第二时间： b, f ；最后：c. a b c e f d 另一种可行的安排方案为：第一时间：a, e;第二时间： c, d ；最后：b, f . (6) 旅行售货员问题 一电脑代理商要从她所在城市出发，乘飞机去六个城市， 然后回到出发点，如果要求每个城市只经历一次，能否办 到？给出行走方案。 * 问题归结为在模型图中寻求所谓的“哈密尔顿圈”问题。 将在第四章介绍。 例如：如果模型图如下： 该问题可以建立一个图论模型来解决：城市抽象为 图的顶点，边代表城市间的直达航线。 a b c d e f 可行方案: (1) h, d, e, c, b, a, h (2) h, d, e, c, a, b, h 数学预备知识 集合论 数理逻辑 归纳法原理 组合分析与计数 鸽巢原理（鸽舍原理、抽屉原理） 等价关系与同余 集合论 自然数集、整数集、有理数集、实数集 并集，交集，差集，补集，对称差集 集合的计数：card A=n 自然数集的计数： 实数集的计数： 数理逻辑 （1） 全称量词 存在量词 否定 合取 析取 条件命题 双条件命题 数理逻辑 （2） 条件命题 逆命题 逆否命题： 数理逻辑 （3） 双条件命题 引理、定理、推论 引理（lemma) : 希腊语意为前提 定理 (theorem):希腊语意为待证的论题 推论 (corollary): 拉丁语，意为赠品，是从定理或命题出发无需太多额外工作即可得出的论断 归纳法原理一 对每个自然数，设P(n)是一个数学命题。如果下面的性质a和b成立，则P(n)对每个自然数n均为真 a) P(1)为真； b) 对于 ，如果P(k)为真，则 P(k+1)为真； 归纳法原理二 对每个自然数，设P(n)是一个数学命题。如果下面的性质a和b成立，则P(n)对每个自然数n均为真 a) P(1)为真； b) 对于 ，如果对所有 P(t)为真，则 P(k+1)为真； 组合分析与计数 映射 双射 幂集、子集的个数计数 鸽巢原理（鸽舍原理、抽屉原理） 平均值总是介于最大值和最小值之间 如果对象多于kn的一个集合被划分为n个类，则必有一个包含的对象多于k个 等价关系与同余 （1） 集合S上的一个等价关系是S上的一个关系R,它对不同元素 满足 a) 自反性 b) 对称性 c) 传递性 等价关系与同余 （2） 对于“模n同余”是等价关系，其等价类成为模n的余数类或者同余类，所有的同余类构成的集合 * 图论及其应用Graph Theory and Its Applications 主要内容 图论前言 数学预备知识 前言 课程目标 学时和学分 教学大纲 教材和主要参考资料 课程考核 图论学科简介 （1） 图论是研究点与线组成的“图形”问题的一门科学。图论是组合数学的一个分支，它交叉运用了拓扑学、群论、数论等学科，有时将其归为离散数学的一个分支 属于应用数学分支 哥尼斯堡七桥问题 欧拉（1707~1782）：根据几何位置的解题方法，这是图论领域的第一篇