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