范更华-图论及其应用

图论及其应用范更华福州大学离散数学研究中心离散数学及其应用教育部重点实验室

现实世界中许多问题的数学抽象形式可以用图来描述。如互联网、交通网、通讯网、大规模集成电路、分子结构等都可以用图来描述。对图的研究形成了一个专门的数学分支：图论（GraphTheory)。图论(GraphTheory)图的直观定义：点与边图的抽象定义：一个集合上的二元关系图的定义两个长度为5的圈通过5条边相连，也可如下构造：5个元素集合的所有2-子集作为点，两点有边相连当且仅当对应的2-子集不交。◆没有长度小于5的圈◆没有长度为10的圈(哈密顿圈)◆边传递、点传递◆不是平面图Petersen图图论结构图论随机图论代数图论拓扑图论图论分支离散数学

图论是离散数学的一个主要分支广泛应用背景的基础研究与计算机科学密切相关离散数学

以蒸汽机的出现为标志的工业革命促进了以微积分为基础的连续数学的发展。

以计算机的出现为标志的信息革命将促进离散数学的发展。计算机光纤网波长分配问题

在一个计算机光纤网络中，给传输信道分配波长，两信道若有公共部分，必须得到不同的波长。要求使用尽可能少的波长。波长分配问题转化为图论问题每条信道看作图的一个点。两点间有边相连当且仅当它们对应的信道有公共部分。波长问题等价于所构造图的点着色问题：

给图的每个点着色，有边相连的点须着不同的颜色。所用颜色尽可能少。图的例子

交通网

互联网

计算机处理器连接方式

集成电路板

分子结构图

分子间相互作用及信息传递具体应用

大型高速计算机：处理器的连接方式互联网：信息传输及控制管理大规模集成电路：布局、布线数据库技术：数据的存储、检索理论计算机科学：

子图理论对计算机算法研究的应用

DNA序列分析：图的欧拉回路问题机器智能与模式识别：图的同构通讯网络：连通性，可靠性印刷电路板检测:12万5千次降为4次(《美国科学》ScientificAmerican,9(1997),92-94)具体应用

旅行推销员问题问题提出:一个推销员从公司出发,访问若干指定城市,最后返回公司,要求设计最优旅行路线。(费用最小)

数学抽象:城市作为点,两点间有边相连,如果对应的城市间有直飞航班。机票价作为每条边的权。求解:在图中求一个圈过每点恰好一次,且边的权之和最小。(最优哈密顿问题；比较：最优欧拉回路问题—中国邮递员问题)难度:NP--完全问题应用:投币电话、自动取钞机、机器人行走路线设计旅行推销员问题简单情形:任意六个人中,必有3个互相认识,或三个互相不认识。

数学抽象:点代表人,两点相连当且仅当对应的两人认识。该图要么有三角形,要么有三个点两两不连。Ramsey数问题证明：令G是6个点的图，x为G中一个点。与x相邻的点集记为N,与x不相邻的点集记为R.情形I.|N|>2.若N中有两点相连，则这两点连同x构成一个三角形；若N中任意两点均不相连，则N含三个两两不连的点。情形II.|N|<2.那么|R|>2.若R中有两点不相连，则这两点连同x是三个两两不连的点；若R中任意两点均相连，则R含一个三角形。Ramsey数问题一般化:定义R(s,t)为最小整数使得任意R(s,t)个人中,要么有s个人两两认识,要么有t个人两两不认识。

R(3,3)=6R(4,4)=18R(5,5)=?Ramsey问题

应用广、影响大。微软研究中心的Kim因求解R(3,t)的工作而获1997年Fulkerson奖。Ramsey数问题一般叙述:

图的边数大于某个数时,该图具有某种性质,此数的最小值称为该性质的极值.Mantel

定理(1907年):n点图的边数大于n2/4时,该图含三角形,且n2/4是具有该性质的最小数.上述定理是Turan定理(1941年)的特殊情形.极值图论Mantel定理的证明:

设G是不含三角形的n点图,其最大点度数为t.不难证明G的边数至多是f(t)=t(n-t).该二次函数在t=n/2处取得极大值:f(n/2)=n2/4.当n为偶数时,n个点的平衡完全二部图不含三角形,且边数恰为n2/4.因此,n2/4是具有该性质的最小数.极值图论1852年,Morgan教授的一位学生问他:能否给出一个理由,为什么只需4

种颜色，就可给任意地图的每个国家着色，使得有共同边界的国家着不同的颜色。教授无语,该问题成为数学史上最著名问题之一,对它的研究推动了图论,拓扑,代数的发展.历史上许多著名数学家研究过四色问题并给出错误证明.四色问题当年,这位学生告诉Morgan教授:下面的例子说明3种颜色不够,至少需4种颜色.四色问题转化为图论问题:点代表国家,两点相连当且仅当对应的两个国家有共同边界。由此得到的图是平面图.四色问题:

每个平面图可用4种颜色对其点着色,使得任何两个有边相连的点得到不同颜色.1976年,两位计算机专家借助计算机验证,解决了四色问题.未被数学界普遍接受.四色问题子图覆盖问题定义：若一个图的某些子图共同包含了该图的所有边，则称该图被这些子图覆盖。

子图覆盖问题：用具有某种特性的子图来覆盖一个图。子图覆盖四色问题的一个等价形式:每个2-边连通平面图可被两个偶图覆盖（偶图：每个点与偶数条边关联;圈是连通极小偶图）

哥德巴赫猜想:每个大于2的偶数是两个素数之和。子图覆盖图论:每个2-边连通图可被3个偶图覆盖。数论:每个充分大的奇数是3个素数之和。陈景润定理:每个充分大的偶数是一个素数与不超过两个素数的乘积之和。Seymour定理:每个2-边连通图可被一个偶图及不超过两个偶图的并所覆盖。子图覆盖哥尼斯堡七桥问题哥尼斯堡七桥问题1735年,欧拉(Euler)证明哥尼斯堡七桥问题无解,由此开创了数学的一个新分支---图论.欧拉将哥尼斯堡七桥问题转化为图论问题:求图中一条迹(walk),过每条边一次且仅一次.后人将具有这种性质的迹称为欧拉迹,闭的欧拉迹也称为欧拉回路.欧拉定理:

连通图存在欧拉迹当且仅当图中奇度数的点的个数至多为2(若为0,则存在欧拉回路,这种图称为欧拉图,也称为偶图)哥尼斯堡七桥问题欧拉定理

(图论最古老的定理,1735年)：无奇度数点的连通图(欧拉图)存在欧拉回路（一笔划）,且可被边不交的圈覆盖。次此定理未能回答需要多少个圈。二百多年来，人们一直试图回答这个问题。

子图覆盖Hajos

猜想：n个点的欧拉图可被[n/2]个边不交的圈覆盖。Erdos-Goodman-Posa

猜想(1966):存在常数c,n个点的欧拉图可被cn

个边不交的圈覆盖。定理

(范更华，2003年)：n个点的欧拉图可被[n/2]个圈覆盖，且每条边恰好被覆盖奇数次。子图覆盖圈k-覆盖:给定一个图，对哪些正整数k，存在一组圈，使得图中的每条边恰好在k个圈上?这样一组圈称为该图的一个圈k-覆盖。 当k为奇数时，这个问题已解决；

然而当k为偶数时，至今仍未完全解决。60年代中，Edmonds（JohnvonNeumann奖得主）的匹配多面体理论为人们提供了有力工具，得以证明圈k-覆盖对某个偶数k存在，但无法确定这个偶数的值。子图覆盖定理(BJJ1983)：当k是4的倍数，圈k-覆盖存在。定理(Fan1992)：当k是6的倍数，圈k-覆盖存在。推论：当k是大于2的偶数时，圈k-覆盖存在。

唯独k=2未能解决。圈2-覆盖也被称为圈双覆盖，至今仍是图论界的一个著名难题。它是曲面拓扑中的强嵌入猜想的一个弱形式。子图覆盖圈双覆盖猜想（CycleDoubleCoverConjecture）每个2-边连通图存在圈2-覆盖。

强嵌入猜想（StrongEmbeddingConjecture）每个2-连通图可嵌入到某个曲面上，使得每个面的周界是一个圈（2-cell-embedding:eachfaceishomeomorphictoanopendisk）。子图覆盖

若我们不要求每条边恰好在k个圈上，而只要求每条边至少在一个圈上，这样一组圈称为该图的一个圈覆盖。所有这些圈的边数之和称为该圈覆盖的长度。短圈覆盖问题：寻找长度最短的圈覆盖。Itai-Rodeh猜想（1978）：若图的边数为m，点数为n，则一定有长度不超过m+n-1的圈覆盖。子图覆盖l

1985年，Alon（2002年世界数学家大会作１小时报告）证明存在长度不超过m+7(n-1)/3的圈覆盖。l

1994年，Thomassen（丹麦科学院院士）证实了计算机算法专家Papadimitriou的猜测：短圈覆盖问题是NP-完全。l

1998年，范更华彻底解决了Itai-Rodeh猜想，证明存在长度不超过m+n-1的圈覆盖。子图覆盖未解决问题

(Itai-Rodeh，1978)：是否存在长度不超过7m/5

的圈覆盖？若答案是肯定的，则推出圈2-覆盖猜想成立。已知最好结果(BJJ，1983；Alon-Tarsi，1985)：存在长度不超过5m/3的圈覆盖。子图覆盖整数流问题 给图的每条边一个定向及一个整数值,使得在图的每个点,进入该点的所有边的整数值之和等于离开该点的所有边的整数值之和。整数流的一个例子

整数流的抽象定义

给定图G和k阶可换群A。若对G的某个定向,存在一个函数f

:从G的边集到A的非零元素,使得在图的每个一点,进入该点的边的函数值之和等于离开该点的边函数值之和,则称f为G的一个k-流。

Tutte定理(1954年):平面图可k着色当且仅当该图存在k-流。

◆四色问题等价于平面图的4-流存在性整数流与平面图着色

5-流猜想：每个2-边连通图有5-流。4-流猜想：每个不含广义Petersen子图的2-边连通图有4-流。3-流猜想：每个4-边连通图有3-流。整数流三大猜想

弱3-流猜想：存在常数t，使得每个t-边连通图有3-流。此猜想与有限域向量空间堆垒基（AdditiveBasis）猜想有关联，吸引了众多国际一流学者。定理(Thomassen，2012):每个8-边连通图有3-流。(随后被改进到：6-边连通图有3-流。)弱3-流猜想

整数流与数学其他领域的一些著名问题有关联:

组合学:LonelyRunner

数论:DiophantineApproximation

几何学:ViewObstruction有限域线性空间:AdditiveBasis

整数流理论孤独的跑步者

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,

未解决世界难题。观察者问题(ViewObstruction)大规模集成电路（VLSI）VeryLargeScaleIntegration

用半导体工艺技术将电子电路的电子元器件（电阻、电容、电感、晶体管、二极管、传感器等）在一块半导体材料（硅、砷化镓）芯片上“一气呵成”，互连成有独立功能的电路和系统。亦称为“芯片”（Chip）。

集成电路产业包括设计、芯片制造、封装检测三大部分。可形象地比喻为写书、印刷、装订。显然，设计最具原创性。“863”、“973”，及国家重大专项都把集成电路设计列入其中。集成电路设计所依赖的关键软件EDA(ElectronicDesignAutomation),基本上全是进口。

(EDA软件的研制涉及大量的图论和组合优化问题.)集成电路产业

《国家中长期科学和技术发展规划纲要》确定了16个重大专项作为我国科技发展的重中之重（总投资超过1万亿）。其中与集成电路有关的占了两项:◆核心电子器件、高端通用芯片及基础软件◆极大规模集成电路制造技术及成套工艺我国集成电路产业发展前景硅园片上的芯片硅衬底drain硅衬底顶部保护层金属层绝缘层凹进导电层导电层1961年早期芯片

4个晶体管和若干电阻

1990年Intel奔腾处理器芯片1.5cm2310万晶体管奔Ⅳ芯片结构图

2000年，0.18μm工艺，4千2百万个晶体管头发对最小特征尺寸为0.18μm的比较ContactholeLinewidth

Space~90mmMinimumICfeaturesize=0.18mm90mm0.18mm=500Crosssectionofhumanhair芯片中金属层（介质腐蚀后呈立交桥状）MetalLayersinaChip973项目：数学与其它领域交叉的若干专题（2006.6-2010.12)课题

：大规模集成电路设计中的图论与代数方法负责人：范更华承担单位：福州大学参加单位：北京大学、南开大学、山东大学

国家重点基础研究发展计划新一轮973项目：信息及相关领域若干重大需求的应用数学研究（2011.1-2015.12)课题

：大规模集成电路物理设计中关键应用数学理论和方法负责人：范更华承担单位：福州大学参加单位：北大、南开、山东大学、四川大学

国家重点基础研究发展计划

研究大规模集成电路设计中的电路划分、布图、布线等问题。以图论、组合优化、算法设计为主，为研制具有自主知识产权的大规模集成电路设计应用软件提供理论支持，提高我国在EDA（ElectronicDesignAutomation）工具研制这一领域的基础理论研究水平。973课题概述电路划分布局布线原理图输入芯片制造版图验证数据导出芯片版图设计三个主要部分：电路划分、布图、布线涉及大量图论问题芯片版图设计大规模集成电路设计的关键一步，其结果会影响后续的布局、布线等过程。由于需要布局的电路太大，且输入输出引脚数目受到芯片封装工艺的限制，需要将整个电路划分成若干模块，要考虑模块的大小、模块间的连线等。电路划分

是一个多约束、多目标的优化问题。它的理论抽象是图论中的点集划分（VertexPartition）问题:

给定一个图G及边集E(G)上的一个权函数w.对正整数k≤t，求点集V(G)的一个划分(A1,A2,...,Am)使得k≤|Ai|≤t，1≤i≤m，且∑i<jw(Ai,Aj)尽可能小。电路划分

最简单情形：二部划分且对每部分的点数不加限制，则等价于在给定赋权图（允许负权）中找最大生成二部子图。就一般图而言，这是NP-困难。平面图有多项式算法。其主要思想是：将所有奇圈（长度为奇数的圈）破坏，剩下的图就是一个二部子图。电路划分求平面图G的最大二部子图求G中最小权和的边集E使得G\E不含奇圈在对偶图G*中求奇度点间的一组权和最小的路P使得G*\P不含奇度点在以奇度点为点集的赋权完全图中求最小完美匹配（Edmonds多项式算法）电路划分

若对每部分的点数加以限制，则有下述至今未解决的难题：平面图二部划分问题：对任何n顶点平面图，是否存在一个顶点集的二部划分(X,Y)使得：||X|-|Y||≤1且X与Y之间的边的数目至多为n.电路划分在完成电路划分之后，通过布局规划（floorplanning）把模块安置在芯片的适当位置上，并满足一定的要求，如面积最小、模块间的连线最短且容易布通等。由于模块间连线要占用芯片面积，布局时要为后一步的布线留下必要的布线通道。布局

若只考虑模块间的互连关系，则问题成为典型的“二次分配”问题（QuadraticAssignmentProblem）：给定两个n阶矩阵A=(aij)n×n，B=(bij)n×n，求映射π:{1,2,…,n}→{1,2,…,n}使得

aij

bπ(i)π(j)

尽可能小。布局

目标是完成模块间的互连，且满足一定的要求，如减小连线总长度，减轻走线拥挤度，减少层间通孔数等。布线分为总体布线和详细布线。总体布线是在布局完成后，将线网分配到合适的布线区域，确保布通率而不考虑走线的具体位置。详细布线则最终确定走线的具体位置。

布线最小斯坦纳树(MinimumSteinerTree)问题：

给定一个赋权图G及点集V(G)的一个子集S，求G中一个连结S的所有点的最小权树。

S中的点对应模块，通过添加斯坦纳点构造斯坦纳树，减小连线总长度。总体布线中的数学问题总体布线中的数学问题总体布线中的数学问题详细布线中的数学问题通道布线(两层模型)

i:表示线网Ｎi的引脚，1≤i≤5；0:空线网。目标：用最少的线槽(Track)完成线网引脚的连接。所需线槽数称为通道宽度(ChannelWidth)。１５２０２１１０３４０３０１25340023tracktrunkbranchviadogleg详细布线中的数学问题对应每个通道布线可构造两个图。水平约束图（horizontalconstraintgraph）：

顶点集

V={vi

＝I(Ni)：线网Ni最左端与最右端引脚所包含的闭区间}

边集

E={vivj

:I(Ni)与I(Nj)相交}这是个无向的区间图（intervalgraph）1

5

2

021103405301253400231234HCG详细布线中的数学问题详细布线中的数学问题

设e=vivj

是水平约束图（HCG)中的一条边,那么线网Ni与Nj不能使用同一个线槽，至少需要两个线槽来完成Ni和Nj

的引脚的连接。

HCG的团数(CliqueNumber)给出通道宽度（线槽数）的下界。详细布线中的数学问题垂直约束图(verticalconstraintgraph)顶点集

V={vi＝Ni}有向边集E

={(vi,vj):Ni与Nj有引脚在通道的同一列，且Ni引脚在Nj引脚之上}1

5

2

021103403012534002323415VCG详细布线中的数学问题详细布线中的数学问题

在无dogleg的双层模型，垂直约束图(VCG)中有向路上任意两点所代表的线网不能使用同一个线槽。如果存在有向圈则不可布。

VCG中最长有向路的长度给出通道宽度（线槽数）的下界。详细布线中的数学问题

对HCG中所有不相邻的点对x和y，若它们在VCG中被有向路相连，则添加无向边xy。记所得到的无向图为MG。

MG的团数(CliqueNumber)给出通道宽度（线槽数）的下界。详细布线中的数学问题

因HCG是区间图，有多项式算法求它的团数(CliqueNumber)，但一般而言，求MG的团数是NP-完全，除非MG是弦图(chordalgraph)。Algorithm(Paletal.,

2007):求MG的弦子图(chordal

subgraph)的团数，给出通道宽度下界。详细布线中的数学问题定理(FanandLiu,2011):令K是MG中的一个团(Clique)。设Kp=K﹨HCG，则(1)Kp中任意两条边要么相邻，要么通过另一条边相连;(2)Kp中的任意导出圈的长度至多是4。推论：令P是MG﹨HCG的非空连通分支，则(1)若P是树，则ω(HCG+P)≤ω(HCG)+2;(2)若P仅含一个圈，则ω(HCG+P)≤ω(HCG)+3详细布线中的数学问题定理(FanandLiu,2011):设D是MG上的一个无圈定向。若D包含VCG的定向，则定向D中最长有向路的长度给出通道宽度（线槽数）的上界；且存在这样一个定向D*，使得D*中最长有向路的长度给出通道宽度的精确值。比较：MG的团数只能给出通道宽度的下届，无法给出精确值。详细布线中的数学问题定理(Szeszler,2003):n个线网的通道布线问题，若可解，则通道宽度（线槽数）至多为7n/4，且可多项式时间完成布线。定理(FanandGeng,2011):n个线网的通道布线问题，若可解，则通道宽度（线槽数）至多为3n/2，且可多项式时间完成布线。路覆盖(PathCovering)问题：

给定图G及G中一组路P

={P1,P2,…，Pk}，对每条边e∈E(G)，定义P(e)为通过e的路的个数，即P(e)=|{Pi

:

e∈Pi,1≤i≤k}|

如果e代表一个通道，则P(e)为通道宽度，也即所需线槽数。详细布线中的数学问题P

的覆盖数：θ(P)=max