图论笔记

图论概述

研究对象

图论是研究点与连接两点间的线组成的 “图形” 问题的一门科学. 属于应用数学 (运筹学与控制论) 分支. 现实世界的许多问题都可以用图来描述, 如互联网, 交通网, 社团网, 大规模集成电路, 分子结构等.

发展历史

图论起源于1736年, 标志事件是“哥尼斯堡七桥”问题的解决.

数学家欧拉被称为“图论之父”.

应用状况

图论的应用领域已经非常广泛(几乎在所有的科学和技术分支), 这也是图论受到广泛关注和研究的重要原因(是我们开图论课程的一个原因).

图论令人着迷的部分原因是有许多有趣且重要的问题(不限于图论学科)可能用简单和基本的图论方法解决, 让人们感受到一些真正成功的前景.

图论模型

为了抽象和简化现实世界, 常建立数学模型, 图是常用的数学模型.

(1) 化学中的图论模型

19世纪, 数学家Cayley用图论研究简单烃—即碳氢化合物. 通过这样的建模, 能很好研究简单烃的同分异构现象. 用点抽象分子式中的碳原子和氢原子, 用边抽象原子间的化学键.

(2) 商业中的图论模型

经济学中经常用图来对工人和工作进行建模.

例如: 令 $V=w_1,w_2,w_3,r_1,r_2,r_3,r_4,r_5$ 代表 3 名工人和 5 种工作. $E=w_1{r}_1,w_1{r}_2,w_2{r}_2,w_2{r}_3,w_2{r}_4,w_3{r}_3,w_3{r}_5$ 代表每个工人能胜任的工作之间的关系.

(3) 考试时间安排问题

一个教授需要对期末考试时间进行安排, 使得学生们不会有相互冲突的考试. 如何解决？

该问题可以建立一个图论模型来解决: 待考的课程可抽象为图的顶点, 连接两个顶点的边表示至少有一个学生同时选择了这两门课程.

问题归结于在模型图中求所谓的“顶点着色方案”问题, 该问题将在第七章讨论.

通过上面几个例子, “点集合” 表示事物或研究对象的集合, “连线集合” 表示事物之间的某种关系. 直观地, “图论” 是研究事物之间相互之间关系的的数学分支.

研究生阶段性学习的特点

(1) 研究生不能读成“大五”;

(2) 研究生阶段考试成绩已经不重要了(可能只决定你的奖学金的多少). 那什么重要呢？能力最重要！所以研究生学习是主动的学习、有意识地学习, 思考地学习. 不仅是简单的 “yes or no” 的问题, 而且有 How 和 Why 的问题.

华罗庚在《要学会自学》一文中说: “一个青年即使他没有大学毕业或中学毕业, 但如果他有了自学的习惯, 他将来在工作上的成就就不会比大学毕业的人差. 与此相反, 如果一个青年即使读到了大学毕业, 甚至出过洋, 拜过名师, 得过博士, 如果他没有学会自己学习, 自己钻研, 则一定还是在老师所划定的圈子里团团转, 知识领域不能扩大, 更不要说科学研究上有所创造发明了.”