1、福州大学离散数学研究中心福州大学离散数学研究中心图论及其应用图论及其应用 图是由给定的点及连接两点的线所构成的图形。现实世界中许多问题的数学抽象形式可以用图来描述。如互联网、交通网、通讯网、社团网、大规模集成电路、分子结构等都可以用图来描述。对图的研究形成了一个专门的数学分支图论图论。图论图论(Graph Theory)图的直观定义图的直观定义：点与边图的抽象定义图的抽象定义：一个集合上的二元关系图的定义图的定义Petersen 图图点集点集：5个元素a,b,c,d,e的所有2-子集作为点边集边集：两点有边相连当且仅当对应的2-子集不交 abcdeabcdeaccebebdad离散数学离散数学
2、 图论图论是离散数学离散数学的一个主要分支广泛应用背景的基础研究与计算机科学密切相关离散数学离散数学 以蒸汽机的出现为标志的工业革命促进了以微积分为基础的连续数学的发展。以计算机的出现为标志的信息革命将促进离散数学的发展。图图 论论结构图论结构图论随机图论随机图论代数图论代数图论拓扑图论拓扑图论图论分支图论分支极值图论极值图论图论的起源图论的起源哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题1735年,欧拉(Euler)证明哥尼斯堡七桥问题无解,由此开创了数学的一个新分支-图论。欧拉将哥尼斯堡七桥问题转化为图论问题:求图中一条迹(walk),过每条边一次且仅一次.后人将具有这
3、种性质的迹称为欧拉迹。哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题欧拉定理欧拉定理:连通图存在欧拉迹当且仅当图中奇度数的点的个数至多为2。1852年,Morgan教授的一位学生问他:能否给出一个理由,为什么只需 4 4 种颜色，就可给任意地图的每个国家着色，使得有共同边界的国家着不同的颜色。该问题成为数学史上最著名问题之一。将地图看作一个平面图：国界为边，相交处为点，国家区域称为面，则该问题可表述为：图论的发展图论的发展四色问题四色问题四色问题四色问题:对每个平面图，能否只用4种颜色对其面着色,使得任何两个有公共边的面得到不同颜色.1976年,两位计算机专家借助计算机验证,
4、解决了四色问题，但未被数学界普遍接受。数学家们仍在努力寻找纯数学的推理证明。四色问题四色问题当年,那位学生告诉Morgan教授:下面的例子说明3种颜色不够,至少需4种颜色.四色问题四色问题一百多年来，貌似容易的四色问题让许多一流数学家栽了跟头。后人评说德国大数学家Minkowski（曾是爱因斯坦的老师）时认为，最让Minkowski尴尬的不是他曾骂爱因斯坦“懒虫”，而是他被四色问题挂了黑板。1880年前后，Kempe 和Tait分别发表了证明四色问题的论文，大家都认为四色问题从此也就解决了。十年后，人们发现这两人的证明都是错误的。四色问题四色问题 Tait的错误在于他认为3-正则，3-连通的平
5、面图有一个圈包含所有点（哈密顿圈）。可是他没能证明这一点。半个多世纪后(1946年)，Tutte给出了第一个不含哈密顿圈的3-正则，3-连通平面图，从而宣告了Tait证明的错误是无法修补的。四色问题四色问题 图论的经典图论的经典哈密顿圈哈密顿圈问题问题Tait 对四色问题的错误证明在于假定3-正则，3-连通平面图有哈密顿圈（含所有点的圈）。哈密尔顿圈哈密尔顿圈问题问题:哪些图有哈密顿圈？带权哈密尔顿圈带权哈密尔顿圈 哈密顿圈可看成过每个点恰好一次的回路；若每条边有一个权(weight),求最优哈密顿圈（总权和最小的哈密顿圈），就是找一条回路：过每个点恰好一次且行程最短旅行推销员问题旅行推销员问
6、题。旅行推销员旅行推销员问题问题问题提出问题提出:一个推销员从公司出发,访问 若干指定城市,最后返回公司,要求设计最优旅行路线(行程最短或费用最小)数学抽象数学抽象:城市作为点,两点间有边相连,如果对应的城市间有直飞航班。里程或机票价作为每条边的权。问题问题:在带权图中找一条回路：过每个点恰好一次,且边的权之和最小(带权最优哈密顿圈）难度难度:NP-完全问题应用应用:投币电话、自动取钞机等旅行推销员旅行推销员问题问题中国邮递员问题中国邮递员问题:在带权图中找一条回路：过每条边至少一次,且边的权之和最小(带权最优欧拉回路问题)难度难度:有多项式算法(Edmonds,1985 von Neuman
7、n Prize)应用应用:起源于中国邮递（管梅谷，1962）中国邮递员问题中国邮递员问题简单情形简单情形:任意六个人中,必有3个互相认识,或三个互相不认识。数学抽象数学抽象:点代表人,两点相连当且仅当对应的两人认识。该图要么有三角形,要么有三个点两两不连。图论的经典图论的经典Ramsey数数问题问题一般化一般化:定义R(s,t)为最小整数使得任意R(s,t)个人中,要么有 s 个人两两认识,要么有 t 个人两两不认识。R(3,3)=6 R(4,4)=18 R(5,5)=?RamseyRamsey问题问题 应用广、影响大。微软研究中心的 Kim 因求解R(3,t)的工作而获1997年 Fulke
8、rson 奖。Ramsey数数问题问题一般叙述一般叙述:图的边数大于某个数时,该图具有某种性质,此数的最小值称为该性质的极值.Mantel 定理定理(1907年年):n点图的边数大于n2/4时,该图含三角形,且n2/4是具有该性质的最小数.上述定理是TuranTuran定理(1941年)的特殊情形.主要工具主要工具：正则引理；标号代数(flag algebra)图论的热点图论的热点极值问题极值问题图论的前沿图论的前沿整数流问题整数流问题 给定图G 和k 阶可换群A。若对G 的某个定向,存在一个函数f f:从G 的边集到A的非零元素,使得在图的每个一点,进入该点的边的函数值之和等于离开该点的边函
9、数值之和,则称f f 为G 的一个 k k-流流。整数流问题整数流问题整数流问题整数流问题：对哪些整数k k，存在k-k-流流k k-流的等价定义流的等价定义：给图的每条边一个定向及一个绝对值小于k的非零整数,使得在图的每个点,进入该点的所有边的整数值之和等于离开该点的所有边的整数值之和。整数流的一个例子整数流的一个例子 TutteTutte定理定理(1954年):平面图可 k 着色当且仅当该图存在 k-流。四色问题四色问题等价于平面图的 4-4-流流存在性。整数流理论整数流理论 整数流与数学其他领域的一些著名问题有关联:组合学:Lonely Runner 数论:Diophantine App
10、roximation 几何学:View Obstruction 有限域线性空间:Additive Basis 整数流理论整数流理论5-5-流猜想流猜想:每个2-边连通图有 5-流。4-4-流猜想流猜想:每个不含Petersen广义子图的2-边连通图有 4-流。3-3-流猜想流猜想:每个4-边连通图有 3-流。Tutte整数流三大猜想整数流三大猜想 W.T.Tutte(1917-2002)W.T.Tutte(1917-2002)英国皇家学会会员 创建滑铁卢大学组合与优化系 图论与拟阵论两大领域奠基性工作 二次世界大战伟大无名英雄(Great unsung hero of World War II
11、)W.T.Tutte(1917-2002)Tutte的战友Jerry Roberts(破译小组最后一名成员)2014年3月25日去世，英国每日邮报报道的标题是英国传奇译码专家去世 曾助二战提前两年结束，文中写道：由于Tutte成功破解了“金枪鱼”系统的逻辑原理，他的团队得以破译德军最高级别的密码“金枪鱼”。Paul Erdos(1913-1996)Paul Erdos(1913-1996)美国、英国等8个国家科学院院士 沃尔夫奖(Wolf Prizes,1983/4)颁奖词:,and for personally stimulating mathematicians the world ove
12、r.将荣誉博士学位退还滑铁卢大学 Paul Erdos(1913-1996)图论图论(Graph Theory)图论的起源：图论的起源：哥尼斯堡七桥问题图论的发展：图论的发展：四色问题图论的经典：图论的经典：哈密顿圈，Ramsey数问题图论的热点：图论的热点：极值问题图论的前沿：图论的前沿：整数流问题图论的应用：图论的应用：大规模集成电路设计问题大规模集成电路（大规模集成电路（VLSIVLSI）Very Large Scale Integration 用半导体工艺技术将电子电路的电子元器件（电阻、电容、电感、晶体管、二极管、传感器等）在一块半导体材料（硅、砷化镓）芯片上，互连成有独立功能的电路
13、和系统。亦称为“芯片”（ChipChip）。集成电路产业包括设计、芯片制造、封装检测三大部分。可形象地比喻为写书、印刷、装订。显然，设计设计最具原创性。“863”、“973”，及国家重大专项都把集成电路设计列入其中。集成电路设计所依赖的关键软件EDA(Electronic Design Automation),基本上全是进口。(EDA软件的研制涉及大量的图论和组合优化问题.)集成电路产业集成电路产业硅园片上的芯片硅园片上的芯片硅衬底drain硅衬底顶部保护层金属层绝缘层凹进导电层导电层19611961年早期芯片年早期芯片 4个晶体管和若干电阻 1990年年Intel奔腾处理器芯片奔腾处理器芯片
14、1.5cm2310万晶体管奔奔芯片结构图芯片结构图 20002000年，年，0.18 m0.18 m工艺，工艺，4 4千千2 2百万个晶体管百万个晶体管头发对最小特征尺寸为头发对最小特征尺寸为0.18m0.18m的比较的比较Contact holeLine width Space90 mmMinimum IC feature size=0.18 m(180nm)90 mm0.18 mm=500Cross section of human hair芯片中金属层（介质腐蚀后呈立交桥状）芯片中金属层（介质腐蚀后呈立交桥状）Metal Layers in a Chip电路划分布局布线原理图输入芯片制造
15、版图验证数据导出芯片版图设计芯片版图设计三个主要部分：电路划分、布图、布线涉及大量图论问题芯片版图设计芯片版图设计 是大规模集成电路设计的关键一步，其结果会影响后续的布局、布线等过程。由于需要布局的电路太大，需要将整个电路划分成若干模块，要考虑模块的大小、模块间的连线等。电路划分电路划分 是一个多约束、多目标的优化问题。它的理论抽象是图论中的点集划分（Vertex Partition）问题:给定一个图G 及边集E(G)上的一个权函数w.对正整数 k t，求点集V(G)的一个划分(A1,A2,.,Am)使得 k|Ai|t，1 i m，且ij w(Ai,Aj)尽可能小。电路划分电路划分 在完成电路
16、划分之后，通过布局规划布局规划（floorplanning）把模块安置在芯片的适当位置上，并满足一定的要求，如面积最小、模块间的连线最短且容易布通等。由于模块间连线要占用芯片面积，布局时要为后一步的布线留下必要的布线通道。布布 局局 模块间的互连，且满足一定的要求，如减小连线总长度，减轻走线拥挤度，减少层间通孔数等。布线分为总体布线和详细布线。布布 线线最小斯坦纳树最小斯坦纳树(Minimum Steiner Tree)问题问题：给定一个赋权图G 及点集 V(G)的一个子集S，求G 中一个连结S 的所有点的最小权树。S 中的点对应模块，通过添加斯坦纳点构造斯坦纳树，减小连线总长度。总体布线中的
17、数学问题总体布线中的数学问题总体布线中的数学问题总体布线中的数学问题总体布线中的数学问题总体布线中的数学问题详细详细布线中的数学问题布线中的数学问题 在完成总体布线后，进行详细布线。可转化为在图中找一组路连接指定点集且满足若干条件，如要求每条边不能被太多路共同使用。图的边对应于布线通道，也即要求该通道不能太拥挤。详细布线的一个主要问题就是用图的某些参数给出通道宽度（线槽数）的估计。973973项目项目：数学与其它领域交叉的若干专题 （2006.6-2010.12)课题课题：大规模集成电路设计中的图论与代数方法负责人负责人：范 更 华承担单位承担单位：福州大学参加单位参加单位：北京大学、南开大学
18、、山东大学国家重点基础研究发展计划国家重点基础研究发展计划新一轮新一轮973973项目项目：信息及相关领域若干重大需求的应用数学研究（2011.1-2015.12)课题课题：大规模集成电路物理设计中 关键应用数学理论和方法负责人负责人：范 更 华承担单位承担单位：福州大学参加单位参加单位：北大、南开、山东大学、四川大学 国家重点基础研究发展计划国家重点基础研究发展计划 研究大规模集成电路设计中的电路划分、布图、布线等问题。以图论、组合优化、算法设计为主，为研制具有自主知识产权的大规模集成电路设计应用软件提供理论支持，提高我国在 EDA（Electronic Design Automation）
19、工具研制这一一领域的基础理论研究水平。973973课题概述课题概述德国波恩德国波恩(Bonn)(Bonn)大学离散数学研究所大学离散数学研究所Research Institute for Discrete Mathematicsn 自主开发了一套EDA工具BonnTools（最小特征尺寸为90nm）n 1987年开始与IBM合作，已有上千款IBM 芯片的设计用了BonnToolsn 2005年开始与Magma合作，现今 BonnTools已成为Magma产品的一部分主要研究方向主要研究方向l l 图论与组合数学l 大规模集成电路设计中的数学方法l 优化理论与算法研究平台研究平台离散数学及其应用教育部重点实验室离散数学及其应用教育部重点实验室福州大学离散数学研究中心福州大学离散数学研究中心福州大学离散数学研究中心福州大学离散数学研究中心中心网页中心网页：http:/
