图论
G
其中V(G) 是非空的顶点集, E(G)是不与V(G)相交的边集,
而Ψ 是关联函数,它使G的每条边对应于G 的无序顶点对。 若e是一条边,而u和v是使得 G (e ) uv 的顶点,则称 e 连接 u 和 v ;顶点 u 和 v 称为 e 的端点。
图graph, 顶点vertex,边edge
-23-
图论及其应用第一章
例1
G {V (G ), E (G ), G )
e7
此时,V (G ) {v1 , v2 , v3 , v4 }
E (G ) {e1 , e2 , e3 , e4 , e5 , e6 , e7 }
v2
e1
v1
e2
G 定义为
e3
e4 e5
v3
e6
G (e1 ) v1v2 , G (e2 ) v2v3
-13-
图论及其应用第一章
-14-
图论及其应用第一章
Ramsey理论的哲理意义
-15-
图论及其应用第一章 婚姻匹配
某村里有n 个男士与n 个女士,每个男士恰 好认识 r 个女士,每个女士也恰好认识 r 个男士, 问:在这个村中,能否做到:每个男士与其 认识的女士结婚,每个女士也恰好与其 认识的男士结婚。
端点处相交, 这样画出的平面图形称为图的图形表示。
-25-
图论及其应用第一章
例2
G = (V, E) ,其中 V (G ) {v1 , v2 , v3 , v4 , v5 }
E (G ) {(v1 , v2 ), (v2 , v3 ), (v3 , v4 ), (v3 , v5 ), (v1 , v5 ), (v1 , v5 ), (v5 , v5 )}
-7-
图论及其应用第一章
进入20世纪以来,科学家们对四色猜想的证明基本上是 按照肯普的想法在进行。后来美国数学家富兰克林于1939年 证明了22国以下的地图都可以用四色着色。1950年,有人从 22国推进到35国。1960年,有人又证明了39国以下的地图可 以只用四种颜色着色;随后又推进到了50国。 1976年 6月,美国伊利诺大学哈肯与阿佩尔在两台不同 的电子计算机上,用了1200个小时,作了100亿判断,终于 完成了四色定理的证明,轰动了世界。 然而,真正数学上的严格证明仍然没有得到!数学家仍 为此努力,并由此产生了多个不同的图论分支。
-27-
图论及其应用第一章 一些概念和术语: (1) 点与边的关联(incident) (2) 点与点的相邻(adjacent) (3) 边与边的相邻 (4)(自)环(loop)、连杆(link) (5)重边(parallel edge) (6)简单图(simple graph) (7)有限图(finite graph) (8)平凡图(trivial graph)和非平凡图 (9)空图(empty graph)和零图(null graph) (10)图的顶点数(图的阶order) 、边数(size)
-5-
图论及其应用第一章 四色问题
四色问题是世界近代三大数 学难题之一。 四色问题的内容是:任何一张 地图只用四种颜色就能使具有共 同边界的国家着上不同的颜色。 它的提出来自英国。 1852 年, 毕业于伦敦大学的弗南西斯 · 格思 里发现了一种有趣的现象:“看 来,每幅地图都可以用四种颜色 着色,使得有共同边界的国家都 被着上不同的颜色。”这个现象 能不能从数学上加以严格证明呢?
G (e3 ) v3v1 , G (e4 ) v1v4
v4
G (e5 ) v3v4 , G (e6 ) v3v4 , G (e7 ) v2v2 .
这便定义出一个图。
-24-
图论及其应用第一章 图的图形表示
通常,图的顶点可用平面上的一个点来表示,边
可ቤተ መጻሕፍቲ ባይዱ平面上的线段来表示(直的或曲的),而边仅在
-8-
图论及其应用第一章 Ramsey 问题
几个事实:
1. 任意的6个人中,总有3个人互相认识或有3个人互不认 识。
2.
任意的9个人中,总有3个人互相认识或有4个人互不认 识。
问题: 对任意的自然数 k 和 t ,是否存在一个最小的正整数 r(k,t),使得每个至少有r(k,t)个人的团体,总有k个人 互相认识或有t个人互不认识。
-2-
图论及其应用第一章
七 桥 问 题
C 转化 A D Euler 1736年
包含两个要素:对象(陆 地)及对象间的二元关系 (是否有桥连接) C A B D
B
图论中讨论的图
问题:是否能从A,B,C,D 中的任一个开始走,通过每 座桥恰好一次再回到起点?
转化
是否能从任意一个顶点开 始,通过每条边恰好一次 再回到起点?
[5] 徐俊明,图论及其应用,中国科技大学出版社, 1998。
-20-
图论及其应用第一章
第一章
1.1
1.2 1.3 1.4 1.5 1.6 1.7 子图
图和子图
图和简单图
图的同构 顶点的度 路、圈和连通 关联矩阵和邻接矩阵 应用: 最短路问题
-21-
图论及其应用第一章
1.1 图和简单图
-22-
图论及其应用第一章 图的定义 一个图 G 是指一个有序三元组 (V (G ), E (G ), G ) ,
-16-
图论及其应用第一章
图论相关的交叉研究 代数图论 拓扑图论 化学图论 算法图论 随机图论 极值图论 超图
以往数学家习惯将纯数学应用于其它学科, Gowers将图论和组合数学中的Ramsey理论 应用于泛函分析的研究,获得了1998年的 Fields奖。
-17-
图论及其应用第一章
内容提要
图的基本概念 图的基本概念;二部图及其性质;图的同构;关联矩 阵与邻接矩阵。路、圈与连通图;最短路问题。树及 其基本性质;最小生成树。
有向图;网络与网络流的基本概念;最大流最小割
定理;求最大流的标号算法;网络流理论的应用。
-19-
图论及其应用第一章 主要参考书
[1] J.A. Bondy and U.S. Murty, Graph Theory with
Applications, 1976 (GTM244, 2008)。 [2] B. Bollobas, Modern Graph Theory (现代图论),科学 出版社,2001。 [3] 王树禾,图论,科学出版社,2004。 [4] 蒋长浩,图论与网络流,中国林业出版社,2001。
这便定义出一个图。 注:由于表示顶点的平 面点的位置的任意性, 同一个图可以画出形状
迥异的很多图示。
例2中图的另一个 图示:
-26-
图论及其应用第一章
图的图示直观易懂,因此以后一般说到一个图,
我们总是画出它的一个图示来表示。 阅读书P.2-3页,理解平面图和非平面图,并且 完成课后习题1.1.2。
图的连通性
割点、割边和块;边连通与点连通;连通度; Whitney 定理;可靠通信网络的设计。 匹配问题 匹配与最大匹配;完美匹配;二部图的最大匹配。
-18-
图论及其应用第一章 欧拉图与哈密尔顿图
欧拉图;中国邮递员问题;哈密尔顿图;旅行商问
题。
独立集、覆盖集与团
点独立集、点覆盖集、边覆盖集与团的概念。 图的着色问题 点着色;边着色;平面图;四色猜想。 网络流理论
拉姆瑟(F.P. Ramsey)在1930年证明了这个数 r(k,t) 是存在的,人们称之为 Ramsey 数。确定其精确值是 个公开的难题。
-9-
图论及其应用第一章
Ramsey数R(p,q)
p,q
3
3
6
4
9
5
14
6
18
7
23
8
28
9
36
4 5
6 7 8
18
25 43–49
35–41 58–87
102–165
图论及其应用
Graph Theory with Applications
江苏师范大学数学学院 祝宝宣
图论及其应用第一章
图论发展史
图论在现代科学技术中有着重要的理论价值和广泛的应用 背景,如:线性代数、密码学、物理化学、网络设计、计 算机科学、信息科学、DNA的基因谱的确定和计数、工业生 产和企业管理中的优化方法等都广泛的应用了图论及其算 法。 首先我们通过图的发展过程来了解一下图论所研究的内容。 图论起源于18世纪的一个游戏----俄罗斯的哥尼斯堡七桥 问题。 (1736年 瑞士数学家欧拉——图论之父)
-6-
图论及其应用第一章
1872 年,英国当时最著名的数学家凯利正式向伦敦数学 学会提出了这个问题,于是四色猜想成了世界数学界关注的 问题。 1878 ~ 1880 年两年间,著名的律师兼数学家肯普和泰勒 两人分别提交了证明四色猜想的论文,宣布证明了四色定理, 大家都认为四色猜想从此也就解决了。 1890年,在牛津大学就读的年仅 29岁的赫伍德以自己的 精确计算指出了肯普在证明上的漏洞。不久,泰勒的证明也 被人们否定了。后来,人们开始认识到,这个貌似容易的题 目,其实是一个可与费马猜想相媲美的难题。
Ramsey理论的哲理意义
-12-
图论及其应用第一章
最精美的组合定理
Rota:如果要求在组 合学中仅举出一个 精美的定理,那么 大多数组合学家会 提名Ramsey定理。
• • • • • • •
1984年Wolf奖得主Erdös 1997年Fulkerson奖得主Kim 1998年Fields奖得主Gowers 1999年Wolf奖得主Lovasz 2003年Steele奖得主Graham 2005年Gödel奖得主Alon 2006年Fields奖得主Tao 均对Ramsey理论有杰出贡献