上海交通大学离散数学课件第一章图的基本概念.pdf

图论第1章 图的基本概念 本章主要内容 ⚫ 图的定义 ⚫ 图的运算 ⚫ 图的表示 图论的研究对象 ⚫ 世界由事物组成,事物之间有联系. ⚫ 图可以直观地描述事物及其间联系. ⚫ 用结点表示事物 ⚫ 用边表示它们之间的联系 ⚫ 可见,图模型几乎可用于任何领域. ⚫ 图论(graph theory)就是以这种结点和边构成的图为研究 对象. 图论的研究对象 ⚫ 图论的一些研究主题 ⚫ 优化问题 ⚫ 拓扑图论 ⚫ 图的染色 ⚫ 解析图论 ⚫ 代数图论 ⚫ 网络科学 ⚫ 图论的一些经典应用 ⚫ 物理: 电路及芯片设计 ⚫ 化学:化合物结构 ⚫ 科学与经济管理:道路交通网络 ⚫ 社会学:社交网络分析 ⚫ 计算机科学: ⚫ 数据结构的二大类非线性结构：树和图 ⚫ 操作系统进程演变状态图和目录树有哪些信誉好的足球投注网站 ⚫ 人工智能图有哪些信誉好的足球投注网站策略和知识的表示 ⚫ 计算机网络的最短路径路由算法 ⚫ 自动机理论 图的例子 七桥问题 电路 腾讯微博社交网络 图的例子-化学化合物转化关系 ⚫ 化合物结构和转化关系图 图的例子-四色问题 ⚫ 地图只需四种颜色即可保证相邻区域具有不同颜色. ⚫ 1852年De Morgan的学生Guthrie提出的猜想,从而De Morgan成为最早研究此问题的数学家. ⚫ De Morgan也是数理逻辑的大家. ⚫ 1976年由Kenneth Appel和Wolfgang Haken证明,也是用 计算机证明的第一个重要定理. 图的例子- Dijkstra最短路径 ⚫ 路由算法LSR中运用Dijkstra算法计算一个路 由器到网络中所有其它路由器的最短路径。 图的例子- 大数据分析中的应用 ⚫ Google PageRank 图的例子- Ramsey问题 ⚫ Ramsey问题：世界上任意6个人中，总有3个人相互 认识，或互相皆不认识。 ⚫ 证明如下： ⚫ 首先，把这6个人设为A 、B、C、D、E、F六个点。 ⚫ 由A点可以引出AB 、AC 、AD 、AE 、AF五条线段。红色代表 认识，蓝色代表不认识。由抽屉原理可知：这五条线段中至 少有三条是同色的。不妨设AB 、AC 、AD为红色。 ⚫ 若BC或CD为红色，则结论显然成立。 ⚫ 若BC和CD均为蓝色， ⚫ 则若BD为红色，则一定有三个人相互认识； ⚫ 若BD为蓝色，则一定有三个人互相不认识。 图的定义 ⚫ 定义1: 图(graph) G是一个二元组:G=(V(G),E(G)),其中 V(G)是非空结点(vertex)集合,E(G)是边(edge)的集合,每条 边与V(G)中两个结点(可相同)相关联。 ⚫ 定义2 ：图G是一个三元组：G=(V(G),E(G),f ),其中V(G), G E(G)与定义1相同，f 是关联函数，使E(G)中的每条边对 G 应于V(G) 中的两个结点(可相同) 。 ⚫ 例如右图G: 定义1：V(G)={A ,B,C} ，E(G)={AB , AB, BC , AC} or E(G) = { e1, e2, e3,e4 } 定义2 ：V(G)={A ,B,C} ，E(G) = { e1, e2, e3,e4 } f ：f (e1) = AB, f (e2) = AB G G G