图论-福州第一中学.ppt

图论及其应用 现实世界中许多问题的数学抽象形式可以用图来描述。如互联网、交通网、通讯网、大规模集成电路、分子结构等都可以用图来描述。对图的研究形成了一个专门的数学分支：图论（Graph Theory)。 图的直观定义：点与边 图的抽象定义：一个集合上的二元关系 两个长度为5的圈通过5条边相连，也可如 下构造：5个元素集合的所有2-子集作为点， 两点有边相连当且仅当对应的2-子集不交。 ◆ 没有长度小于5的圈 ◆ 没有长度为10的圈(哈密顿圈) ◆ 边传递、点传递 ◆ 不是平面图 离散数学 图论是离散数学的一个主要分支 广泛应用背景的基础研究 与计算机科学密切相关 离散数学 以蒸汽机的出现为标志的工业革命促进了 以微积分为基础的连续数学的发展。 以计算机的出现为标志的信息革命将促 进离散数学的发展。 波长分配问题转化为图论问题 每条信道看作图的一个点。两点间有边 相连当且仅当它们对应的信道有公共部 分。波长问题等价于所构造图的点着色 问题： 给图的每个点着色，有边相连的点 须着不同的颜色。所用颜色尽可能少。 图的例子 交通网 ?互联网 ?计算机处理器连接方式 ?集成电路板 ?分子结构图 ?分子间相互作用及信息传递 具体应用 大型高速计算机：处理器的连接方式 互联网：信息传输及控制管理 大规模集成电路：布局、布线 数据库技术：数据的存储、检索 理论计算机科学： 子图理论对计算机算法研究的应用 旅行推销员问题 简单情形: 任意六个人中, 必有3个互相 认识, 或三个互相不认识。 ? 数学抽象: 点代表人, 两点相连当且仅 当对应的两人认识。该图要么有三角形, 要么有三个点两两不连。 证明：令G是6个点的图，x为G中一个点。与x 相邻的点集记为N,与x不相邻的点集记为R. 情形I.|N|2.若N中有两点相连，则这两点连 同x构成一个三角形；若N中任意两点均不相 连，则N含三个两两不连的点。 情形II.|N|2.那么|R|2.若R中有两点不相 连，则这两点连同x是三个两两不连的点；若 R中任意两点均相连，则R含一个三角形。 整数流问题 给图的每条边一个定向及一个整数值, 使得在图的每个点, 进入该点的所有边的整数值之和等于离开该点的所有边的整数值之和。 整数流的抽象定义 给定图G 和k 阶可换群A。若对G 的某个定向, 存在一个函数f : 从G 的边集到A的非零元素, 使得在图的每个一点, 进入该点的边的函数值之和等于离开该点的边函数值之和, 则称f 为G 的一个 k-流。 整数流与平面图着色 Tutte定理(1954年): 平面图可k着色当且仅当该图存在k-流。 ◆ 四色问题等价于平面图的4-流存在性 孤独的跑步者 n 个人绕跑道以各自固有的速度跑步。他们在同一时间、同一起点起跑。是否存在某一时刻，某个跑步者 “远离” 其余跑步者？ 数学定量描述 设跑道一圈的长度为 1 个单位。是否存在某个时刻、某跑步者与所有其余跑步者的距离至少是 1/n 单位。 等价描述 n-1 个人绕单位长度跑道以各自固有的速度从同一起点起跑。是否存在某个时刻，所有跑步者与起点的距离至少是 1 / n ？ 数学描述 n-1 个跑步者的速度分别为a1, a2, …, an-1 。 1 圈跑道相当于数轴上的一个单位， 2 圈2 个单位， … , k 圈k 个单位… 。这样，每个正整数均相当于跑道起点。是否存在时间t , 对每个 i, tai 与最近整数的距离至少是1/ n ? 数论难题（丢番图逼近） 给定 n-1 个正整数 a1, a2, … , an-1, 是否存在实数 t , 使得对每个 i, tai与最近整数的距离至少为 1/n ? 对 n﹥5, 未解决世界难题。 大规模集成电路（VLSI） Very Large Scale Integration 用半导体工艺技术将电子电路的电子元器件（电阻、电容、电感、晶体管、二极管、传感器等）在一块半导体材料（硅、砷化镓）芯片上“一气呵成”，互连成有独立功能的电路和系统。亦称为“芯片”（Chip）。 1961年早期芯片 4 个 晶 体 管 和 若 干 电 阻 1990年Intel奔腾处理器芯片 1.5cm2 310万 晶体管 奔Ⅳ芯片结构图 2000年，0.18 μm工艺，4千2百万个晶体管 头发对最小特征尺寸为0.18μm的比较 Metal Layers in a Chip 研究大规模集