2014图论(1) 上传

• （1）V = {v1, v2, …, vn}是有限非空集合，vi称为 结点(Nodal Point)，简称点(Point)，V称为结点 集(Nodal Set)。
• （2）E是有限集合，称为边集(Frontier Set)。E 中的每个元素都有V中的结点对与之对应，称之 为边(Edge)。
图的表示
Euler
卡尔· 弗里德里希· 高斯
• • • • • • • • • • 高斯能完整地背出圆周率——是倒着背。 高斯口渴时会用塔斯基悖论弄出更多橙汁。 高斯不能理解随机过程，因为他能预测随机数 高斯小时候，老师让他算从1到100的和。他计算了这个无穷级数的和，然后一个一个地减去从100 开始的所用自然数。而且，是心算。 一位数学家、一位物理学家、一位工程师走进酒吧，酒吧招待说：“您好，高斯教授。” 询问高斯一个命题是真的还是假的，构成了一个严格的证明。 有一次高斯证明了一条公理，但他不喜欢它，所以他又证明了它是假命题。 高斯通过在证明结束时省去“QED”来保护热带雨林。 有一次高斯在森林里迷路了，于是他加了几条边把它变成了一棵树。 高斯用奥卡姆剃刀剃胡子。
B
C
E
F
基本思想
• 用图形表示一组对象，其中有些对象对 是有联系的。 对于这种图形，我们感兴趣的只是有多 少个点和哪些结点之间有线连接，至于连 线的长短曲直和结点的位置却无关紧要， 只要求每一条线都起始于一个点，而终止 于另一个点。
•
图的定义
• 一个图(Graph)是一个序偶<V, E>，记为G = <V, E>，其中：
1 2
七桥问题
欧拉
游戏博弈问题 树 四色猜想 高速数字计算机
3
4 5
七桥问题
• 如何不重复的走完七座桥？
七桥问题
• 抽象
Байду номын сангаас络通讯
完全对偶图
旅行社
航空公司
连接
9
游戏博弈问题
数据结构中的树
四色问题
• 可否用四种颜色标示所有的地图？
高速计算
第一章 图
1 2 图的基本概念 图的表示、分类 图的性质 通路与回路 图的连通性
图 论
第一节 课程概述
参考书
• 参考书
– 《图论引导》，Douglas B. West，机器工业出版社
教学周历
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 图的基本概念 树、生成树、最优树、有序二元树、追捕问题 平面图、Euler公式、灌木生长算法 匹配理论、图的因式分解 着色问题、四色证明、Ramsey数 Euler图、Hamilton图、邮递员问题 有向图、强弱连通、循环赛 最大流、2F算法、Dinic分层算法、网络流 连通度、边数最少的k连通图 图的线性空间与矩阵 图论中的NPC问题及算法分析 习题课与考试
考核方法
• 书面作业及报告
– 20%
• 课外编程项目
– 10%
• 期末闭卷考试
– 70%
课程特点
• • • • 图论是研究点与线的学问 图论是组合数学的一个分支 图论交叉运用了拓扑学、群论和数论 图论中的定理证明有的显而易见、有的令 人费解 • 图论是一项强大而灵活的科学分析工具 • 图论是形式语言、数据结构、分布式系统、 操作系统理论的数学基础
图论 第一节课 图的表示
有序 与 无序
• 定义中的结点对即可以是无序的，也可以 是有序的。
– 若边e与无序结点对(u,v)相对应，则称e为无向 边(Undirected Edge)，记为e = (u, v) = (v, u)， A e的两个端点 D (End point)。 这时称u、v是边
B E
• 形式化：对于一个图G，如果将其记为
– G = <V, E>，并写出V和E的集合表示 – 称为图的集合表示。
• 图形化：用小圆圈表示V中的结点，
– 用由u指向v的有向线段表示有向边<u, v> – 无向线段表示无向边(u, v)， – 称为图的图形表示。
图论的艰苦
• 从许多实例中，我们发现图论最吸引人的特色是 它蕴含着大量强有力的思想、漂亮的图形和巧妙 的论证，即使是非常困难的尚未解决的问题也易 于表达。 • 问题外表的简单朴素和本质上的难以解决，使每 个搞图论的人在图论面前必须谨慎严肃地思考问 题。常常是貌似简单的问题，即使幸运地得出证 明，证明中包含的细节也十分之繁琐，并且往往 运用了极艰苦的计算。
• 在一群人数不少于三的人群中， 若任意两人都刚好只有一个共 同认识的人，这群人中总有一 人是所有人都认识的。
• 对于所有的N顶图，包含k个顶 的团或q个顶的独立集。具有这 样性质的最小自然数N就称为一 个拉姆齐数，记作R(k,q)
莱昂哈德· 欧拉(Leonhard Euler) 瑞士的数学家和物理学家。他被称为历史上最伟大 的两位数学家之一（另一位是卡尔· 弗里德里克· 高斯）。 欧拉出生于瑞士，在那里受教育。他是一位数学神童。作 为数学教授，他先后任教于圣彼得堡(1727-1741)和柏林 ，尔后再返圣彼得堡(1766)。 欧拉的离世也很特别：据说当时正是下午茶时间，正 在逗孙儿玩的时候，被一块蛋糕卡在喉头窒息而死。 欧拉是第一个使用“函数”一词来描述包含各种参数 的表达式的人，例如：y = F(x) (函数的定义由莱布尼兹在 1694年给出)。他是把微积分应用于物理学的先驱者之一 。欧拉是有史以来最多产的数学家，他的全集共计75卷。 欧拉实际上支配了18世纪的数学，对于当时新发明的微积 分，他推导出了很多结果。在他生命的最后7年中，欧拉 的双目完全失明，尽管如此，他还是以惊人的速度产出了 生平一半的著作。 小行星欧拉2002是为了纪念欧拉而命名的。
解
• G的图形如下图所示。
v3 e6
e4 v2 e2 e1 v5 v4
e5
e3 v1
• G中的e1、e3、e4、e6是无向边，e2、e5是 有向边。
例题
• 设图G = <V, E>的图形如下图所示，试写 1 出G的集合表示。
2
4 3 5
• 解 图G的集合表示为G = <V, E> = <{1, 2, 3, 4, 5}，{<1, 1>，<1, 2>，(1, 4)，(1, 5)，(2, 3)，<3, 5>，<4, 3>，<4, 5>}>。
– V = {v1, v2, v3, v4, v5}， – E = {e1, e2, e3, e4, e5, e6}，
– 其中e1 = (v1, v2)，e2 = <v1, v3>，e3 = (v1, v4)， e4 = (v2, v3)，e5 = <v3, v2>，e6 = (v3, v3)。 – 试画出图G的图形，并指出哪些是有向边，哪些 是无向边？
– 若边e与有序结点对 <u, v>相对应，则称 e为有向 C F 边(Directed Point)(或弧)，记为e = <u, v>，这时 称u为e的始点(Initial Point)(或弧尾)，v为e的终 点(terminal Point)(或弧头)，统称为e的端点。
例题
• 设图G = <V, E>，这里
3
4 5
6
图的应用
第一章学习要求
重点掌握 一般掌握 了解
1
1. 2. 3. 4. 5. 图的概念 特殊图 图论的基本定理 通路与回路 图的连通性
2
3
1. 图的同构 2. 图的构成与证明
图论的典型应用
图的基本概念
• 图的定义
• 考虑一张航线地图，图中用点表示城市， 当两个城市间有直达航班时，就用一条线 将相应的点连接起来。这种航线地图的一 部分如下图所示；
钻石与足球烯
• 足球烯应用在超导、太阳能电池、护肤品 • 数学领先其他科学100年
妖怪（snark）
妖怪图每个点都关联着3条边，用4种颜 色可以把每条边涂上颜色，使得有公共端点 的边异色，而用3种颜色办不到，切断任意3 条边不会使它断裂成2个有边的图。
单星妖怪
双星妖怪
更多妖怪
Hamilton旅行游戏
两种描述方法的优缺点
• 用集合描述图的优点是精确，但抽象不易 理解； • 用图形表示图的优点是形象直观，但当图 中的结点和边的数目较大时，使用这种方 法是很不方便的，甚至是不可能的。
北京 长春
成都
上海 武汉
图的基本概念
• 假设有4台计算机，分别标记为A、B、C 和D，在计算机A和B、C和D以及B和C之间 有信息流。这种情形可用下图表示，通常 称这种图为通信网络；
A B
C
D
图的基本概念
• 假设有一群人和一组工作，这群人中的 某些人能够做这组工作中的某些工作。例 如，有3个人A、B和C，3件工作D、E和F， 假设A只能做工作D, B能做工作E和F, C能 做工作D和E。则这种情形可用下图表示， 其中，在人和这个人能够做的工作之间画 A D 有线。
• 货郎担问题
– TSP（Traveling Salesman Problem）
– 假设有一个旅行商人要拜访n个城市，他必须 选择所要走的路径，路经的限制是每个城市只 能拜访一次，而且最后要回到原来出发的城市。 路径的选择目标是要求得的路径路程为所有路 径之中的最小值。
– NPC问题
Ramsey定理