图论(引言)课件1

引言
More Applications
Hypertexts
网页包含到其他网页的超链接。整个 是一个图. 网页包含到其他网页的超链接。整个Web是一个图 搜 是一个图 索引擎需要图处理算法。 索引擎需要图处理算法。
Matching
职位招聘，如何有效将职位与应聘者匹配？ 职位招聘，如何有效将职位与应聘者匹配？
ψ G (e1 ) = x1 x5 ,ψ G (e2 ) = x1 x2 ,ψ G (e3 ) = x2 x5 , ψ G (e4 ) = x3 x4 ,ψ G (e5 ) = x1 x4
e5 x4 e4 x3 注：这里 e 与 e 5 3
x5
e1
e2 e3 x2
1
的交叉点不是我们研究的 顶点。
返回 结束
n
返回 结束
7.1 图的基本概念
2.图的顶点度数 (简称度)
v 无向图 G = V , E ， i 的度数记 d (vi ) ，指与 vi
相关联的边的条数。
v 有向图 G = V , E ， i 的度数
d (vi ) = d + (vi ) + d − (vi )
最大度 ∆ (G ) = max {d (v) v ∈ V } 最小度 δ (G ) = min {d (v) v ∈ V }
返回 结束
引言
2.四色猜想 四色猜想
在任何平面或球面上的地图，只用四种颜色涂色，就 可使得相邻区域涂上不同颜色。
1976年，Appel, Haken 和 Koch 利用计算机辅 助证明了四色猜想，但其数学证明仍不理想。
返回 结束
引言
3. Hamilton周遊世界问題
正十二面体有二十个顶点表示 世界上20个城市各经每个城市！
反映到图论上就是判断一个给 定的图是否存在一条含所有顶 点的回路。 点的回路。
返回 结束
引言
4.最短路径问題 (Shortest Path Problem) 最短路径问題
最快的routing 最快的 最快航線
B 2 1 E
3 A C 1 2 F 3
1 3 D 3 G
3
返回 结束
引言
最短路径算法 Dijkstra算法 算法
可以求出從某一点到图上其他任一点的最短路径
返回 结束
引言
5.走迷宫与深度优先搜索 走迷宫与深度优先搜索(Depth-First Search) 深度优先搜索
一直往前走 碰壁就回头 碰壁就回头換条路找 沿途要记录下走过的路线 沿途要记录下走过的路线 记录下走过的
返回 结束
引言
图论的产生和发展
1.哥尼斯堡七桥问題(Bridges of Koenigsberg)
[问题] 能否从某一块陆地出发，走遍每一座桥，且 问题] 每一座桥只能走一次，最后回到出发点。
返回 结束
引言
欧拉路径：解決哥尼斯保七桥问題
包含两个要素：对象（ 包含两个要素：对象（陆 地）及对象间的二元关系 是否有桥连接） （是否有桥连接）
返回 结束
引言
图论相关的交叉研究
代数图论 拓扑图论 化学图论 算法图论 随机图论 极值图论 网络图论 模糊图论 超图论
以往数学家习惯将纯数学应用于其它学科， 以往数学家习惯将纯数学应用于其它学科， Gowers将图论和组合数学中的 将图论和组合数学中的Ramsey理论应用 理论应用 将图论和组合数学中的 于泛函分析的研究，获得了1998年的 年的Fields奖。 于泛函分析的研究，获得了 年的 奖
老鼠走迷宮 深度优先搜索
两点之间有无道路可通？有 多少条道路可通？哪条路最 短？
返回 结束
引言
图论的重要地位
图论在计算机科学领域中有着重要地位 操作系统进程演变状态图和目录树搜索。 人工智能图搜索策略和知识的表示 数据结构的二大类非线性结构：树和图 数据库系统的实体-联系模型和文件组织 自动机理论
Schedules
工程项目的任务安排，如何满足限制条件， 工程项目的任务安排，如何满足限制条件，并在最短 时间内完成？ 时间内完成？
Program structure
大型软件系统，函数（模块）之间调用关系。 大型软件系统，函数（模块）之间调用关系。编译器 分析调用关系图确定如何最好分配资源才能使程序更 有效率。 有效率。
6
e2
v2 e3
e4
e5
v4
v3 例1、(2) 有向图 D = V , E ，V = {v1 , v 2 , v3 , v 4 , v5 }
E = { v1 , v 2 , v3 , v 2 , v3 , v 2 , v3 , v 4 , v 2 , v 4 , v 4 , v5 , v5 , v 4 , v5 , v5
返回 结束
目的
(1) 掌握图论的基本问题、理论与方法
(2) 初步掌握运用图论的理论和方法解决实际问题 的能 力
(3) 了解图论在信息学科中的应用以及在数学竞赛、 数 学建模中的应用
返回 结束
引言
为什么要学习图论？ 图论——计算机问题求解的描述工具。
实际问题
抽象
数学模型
求解
求解算法（算法） 求解算法（算法）
转化 Euler 1736年
图论中讨论的图
原來是一笔画问题啊！ 问题：是否能从四块陆地中 的任一块开始，通过每座桥 恰好一次再回到起点？
转化
是否能从任意一个顶点开 始，通过每条边恰好一次 再回到起点？
数学家欧拉(Euler, 1707-1783) 于1736年严格的证明了上述哥 尼斯堡七桥问题无解，并且由此开创了图论的典型思维方式及 论证方式
图G的顶点个数称为图G的阶 阶
返回 结束
7.1 图的基本概念
例1、(1) 无向图
G = V , E ，V = {v1 , v 2 , v 3 , v 4 , v 5 }
E = {( v1 , v 2 ), ( v 2 , v 2 ), ( v 2 , v 3 ), ( v1 , v 3 ), ( v1 , v 3 ), ( v1 , v 4 ) } v1 v5 图形表示如右： e1 e
返回 结束
引言
应用背景
The Internet
net, ca, us com, org, mil, gov, edu jp, cn, tw, au de, uk, it, pl, fr br, kr, nl
The Internet as mapped by The Opte Project
返回 结束
用大量数据验证
测试
编程实现
可以采用图论的成果和方法； 最重要的是： 可以培养我们思考问题和解决问题的能力。
返回 结束
引言
应用背景
图论在现代科学技术中有着广泛的应用，如：网络设计、计算机科学、信 息科学、密码学、DNA的基因谱的确定和计数、工业生产和企业管理中的优化 方法等都广泛的应用了图论及其算法。
计算机网络
某学校网络架构图
返回 结束
引言
应用背景
计算机网络
电路模拟
例：Pspice、Cadence 、ADS….. 、
Cadence Pspice
返回 结束
引言
应用背景
计算机网络
电路模拟 交通网络
航空网络! 航空网络
捷運路線图！ 捷運路線图！
返回 结束
引言
应用背景
有向图
行程表！ 行程表！
有单行道的街道！ 行道的街道！
返回 结束
引言
应用背景
Social Network
High School Dating
corporate e-mail
Reference: Bearman, Moody and Stovel, 2004 image by Mark Newman
Reference: Adamic and Adar, 2004
例1 五位代表 x1, x2 , x3 , x4 , x5 , 其中 x1与x2，x1与x5，x2与x5，x3与x4，x4与x1 是朋友。 点集合——人 x
边集合——朋友关系
V (G) = {x1 , x2 , x3 , x4 , x5 }, E (G) = {e1 , e2 , e3 , e4 , e5 }
返回 结束
7.1 图的基本概念
1. 图的定义
定义7.1.1：所谓图(graph)G是一个三元组，记作G＝<V(G),E(G), Ψ(G)>，其中 ： 定义 图 （1）图G的结点 组成的结点集 结点集(vertex set)记作V(G)＝{v1,v2,…,vn}, 结点 结点集 v1 , v 2 , ⋯ , v n (V(G)≠ Ф) （2）图G的边 边集(edge set)记作E (G ) = {e1 , e2 , ⋯ , em } ，且ei为 边 边集 e1 , e 2 , ⋯ , e m 组成的边集 (vj,vt )或 <vj,vt >。若ei＝(vj,vt )，称ei为以vj和vt为端点 端点(end vertices)的无向边 端点 无向边 (undirected edge)；若ei＝<vj,vt>，称ei为以vj为起点 起点(origin)，vt为终点 终点(terminus) 起点 终点 的有向边 有向边(directed edge)。 有向边 （3） Ψ(G)：E→V×V称为关联函数 关联函数(incidence function）。 关联函数
第7章 图论 章
胡 敏
合肥工业大学计算机与信息学院 计算机应用研究所
第七章 图论
引言 7.1 图的基本概念 7.2 路与连通 7.3 图的矩阵表示 7.4 最短路径问题 7.5 图的匹配 8.1 Euler图和Hamilton图 Euler图和 图和Hamilton图 8.2 树 8.3 生成树 8.4 平面图