图论中的概念及重要算法

图论中的概念及重要算法

常州一中林厚从

ch1、图论中的基本概念

一、图的概念

简单讲，一个图是由一些点和这些点之间的连线组成的。严格意义讲，图是一种数据结构，定义为：graph=（V，E），V是点（称为“顶点”）的非空有限集合，E是线（称为“边”）的集合，边一般用（v x，v y）表示，其中v x，v y属于V。

图（A）共有4个顶点、5条边，表示为：V={v1，v2，v3，v4}，E={（v1，v2），（v1，v3），（v1，v4），（v2，v3），（v2，v4）}

二、无向图和有向图

如果边是没有方向的，称此图为“无向图”，如图（A）和图（C），用一对圆括号表示无向边，如图（A）中的边（v1，v2），显然（v x，v y）和（v y，v x）是两条等价的边，所以在上面E的集合中没有再出现边（v2，v1）。

如果边是有方向（带箭头）的，则称此图为“有向图”，如图（B），用一对尖括号表示有向边，如图（B）中的边。把边中V x称为起点，V y称为终点。显然此时边与边是不同的两条边。有向图中的边又称为弧，起点称为弧头，终点称为弧尾。

图（B）表示为：V={v1，v2，v3}，E={，，，}

如果两个顶点U、V之间有一条边相连，则称U、V这两个顶点是关联的。

三、带权图

一个图中的两顶点间不仅是关联的，而且在边上还标明了数量关系，如图（C），这种数量关系可能是距离、费用、时间、电阻等等，这些数值称为相应边的权。边上带有权的图称为带权图，也称为网（络）。

四、阶

图中顶点的个数称为图的阶。图（A）、图（B）、图（C）的阶分别为4、3、5。

五、度

图中与某个顶点相关联的边的数目，称为该顶点的度。度为奇数的顶点称为奇点，度为偶数的顶点称为偶点。图（A）中顶点v1，v2是奇点，v3，v4是偶点。

在有向图中，把以顶点V为终点的边的数目称为顶点V的入度，把以顶点U为起点的边的数目称为顶点U的出度，出度为0的顶点称为终端顶点。如图（B）中顶点v1的入度是0、

出度是2，v2的入度是2、出度是1，v3的入度是2、出度是1，没有终端顶点。

定理1：无向图中所有顶点的度之和等于边数的2倍，有向图中的所有顶点的入度之和等于所有顶点的出度之和。

定理2：任意一个无向图一定有偶数个(或0个)奇点。

六、完全图

若无向图中的任意两个顶点之间都存在着一条边，有向图中的任意两个顶点之间都存在着方向相反的两条边，则称此图为完全图。n阶完全有向图含有n*(n-1)条边，n阶完全无向图含有 n*(n-1)/2条边，当一个图接近完全图时，称为稠密图；相反，当一个图的边很少时，称为稀疏图。

七、子图

设有两个图G =（V，E）和G’=（V’，E’），若V’是V的子集，E’是E的子集，则称G’为G的子图。

八、路（径）

在一个G =（V，E）的图中，从顶点v到顶点v’的一条路径是一个顶点序列v i0，v i1，v i2，……, v im，其中 v i0 = v， v im = v’，若此图是无向图，则(v ij-1，v ij)∈E，1≤j≤m；若此图是有向图，则∈E，1≤j≤m。路径长度是指路径上的边或弧的数目。序列中顶点不重复出现的路径称为简单路径，顶点v和顶点v’相同的路径称为回路（或环）。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路（或简单环）。

九、连通图

在无向图G中，如果从顶点U到顶点V有路径，则称U和V是连通的。如果对于图G中的任意两个顶点U和V都是连通的，则称图G是连通图，否则称为非连通图。

在有向图G中，如果对于任意两个顶点U和V，从U到V和从V到U都存在路径，则称图G是强连通图。

Ch2、图的存储结构

一、邻接矩阵表示法

邻接矩阵是表示顶点之间相邻关系的矩阵，设G={V，E}是一个度为n的图（顶点序号分别用1，2，……，n表示），则G的邻接矩阵是一个n阶方阵，G[i,j]的值定义如下：

1或权值当v i与v j之间有边或弧时，取值为1或权值G[ i，j ]=

0或∝当v i与v j之间无边或弧时，取值为0或∝（无穷大）上面3个图对应的邻接矩阵分别如下：

0 1 1 1 0 1 1 ∞ 5 8 ∞ 3

G（A）= 1 0 1 1 G（B）= 0 0 1 G（C）= 5 ∞ 2 ∞6

1 1 0 0 0 1 0 8

2 ∞10 4

1 1 0 0 ∞∞10 ∞11

3 6

4 11 ∞

采用邻接矩阵表示图，直观方便，很容易查找图中任两个顶点i和j之间有无边（或弧），以及边上的权值，只要看A[i,j]的值即可，因为可以根据i,j的值随机查找存取，所以时间

复杂性为O（1）。也很容易计算一个顶点的度（或入度、出度）和邻接点，其时间复杂性均为O（n）。但是，邻接矩阵表示法的空间复杂性为O（n*n），如果用来表示稀疏图，则会造成很大的空间浪费。

二、边集数组表示法

边集数组是利用一维数组存储图中所有边的一种图的表示方法。每个数组元素存储一条边的起点、终点和权值（如果有的话）。在边集数组中查找一条边或一个顶点的度都需要扫描整个数组，所以其时间复杂性为O（e），e为边数。这种表示方法适合那些对边依次进行处理的运算，而不适合对顶点的运算和对任意一条边的运算。从空间复杂性上讲，边集数组适合于存储稀疏图。

三、邻接表表示法（链式存储法）

邻接表表示法是指对图中的每个顶点v i（1≤i≤n）建立一个邻接关系的单链表，并把它们的表头指针用一维向量数组存储起来的一种图的表示方法。为每个顶点v i（1≤i≤n）建立的单链表，是表示以该顶点为起点的所有边的信息（包括一个终点（邻接点）序号、一个权值和一个链接域）。一维向量数组除了存储每个顶点的表头指针外，还要存储该顶点的编号i。图（C）的邻接表表示为：

图的邻接表表示法便于查找任一顶点的关联边及邻接点，只要从表头向量中取出对应的表头指针，然后进行查找即可。由于无向图的每个顶点的单链表平均长度为2e/n，所以查找运算的时间复杂性为O(e/n)。对于有向图来说，想要查找一个顶点的后继顶点和以该顶点为起点的边、包括求该顶点的出度都很容易；但要查找一个顶点的前驱顶点和以此顶点为终点的边、以及该顶点的入度就不方便了，需要扫描整个表，时间复杂度为O（n+e）。所以，对于经常查找顶点入度或以该顶点为终点的关联边的运算时，可以建立一个逆邻接表，该表中每个顶点的单链表存储的是所有以该点为终点的关联边信息。甚至还可以把邻接表和逆邻接表结合起来，构造出“十字邻接表”，此时，每个边结点的数据信息包含五个域：起点、终点、权、以该顶点为终点的关联边的链接、以该顶点为起点的关联边的链接。表头向量的结点也包括三个域：顶点编号、以该点为终点的表头指针域、以该点为起点的表头指针域。

Ch3、图的遍历

一、概念

从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组visited[i]，未访问时值为false，访问一次后就改为true。

图的遍历分为深度优先遍历和广度（宽度）优先遍历两种方法。后面的函授将专门讲解。这儿我们先作个介绍。

二、深度优先遍历

从图中某个顶点V i出发，访问此顶点并作已访问标记，然后从V i的一个未被访问过的邻接点V j出发再进行深度优先遍历，当V i的所有邻接点都被访问过时，则退回到上一个顶点V k，再从V k的另一个未被访问过的邻接点出发进行深度优先遍历，直至图中所有顶点都被访问到为止。如下面的左图从顶点a出发，进行深度优先遍历的结果为：a，b，c，d，e，g，f；右图从V1出发进行深度优先遍历的结果为：V1，V2，V4，V8，V5，V3，V6，V7。

三、广度（宽度）优先遍历

从图中某个顶点V0出发，访问此顶点，然后依次访问与V0邻接的、未被访问过的所有顶点，然后再分别从这些顶点出发进行广度优先遍历，直到图中所有被访问过的顶点的相邻顶点都被访问到。若此时图中还有顶点尚未被访问，则另选图中一个未被访问过的顶点作为起点，重复上述过程，直到图中所有顶点都被访问到为止。如上面的左图从顶点a出发，进行广度优先遍历的结果为：a，b，d，e，f，c，g；右图从顶点V1出发，进行广度优先遍历的结果为：V1，V2，V3，V4，V5，V6，V7，V8。

两种遍历方法相比，深度优先遍历实际上是尽可能地走“顶点表”；而广度优先遍历是尽可能沿顶点的“边表”进行访问，然后再沿边表对应顶点的边表进行访问，因此，有关边表的顶点需要保存(用队列，先进先出)，以便进一步进行广度优先遍历。

ch4、图的重要算法

一、求图的最小生成树算法

如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V， E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。同一个图可以有不同的生成树，但可以证明：n个顶点的连通图的生成树必定含有n-1条边。对于加权连通图（连通网），生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。

求图的最小生成树具有很高的实际应用价值，比如要在若干个城市之间建一个交通网，要求各个城市都能到达且造价最低，这就是一个典型的最小生成树问题。那么如何求（最小）生成树呢？求（最小）生成树可以从某个顶点采用深度优先遍历的方法，也可采用广度优先遍历的方法，分别称为深度优先生成树和广度优先生成树。

上图中的图（B）和图（C）所示两棵生成树，是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树。也可以综合应用深度优先遍历和广度优先遍历的特定算法，如：Prim算法和Kruskal算法，下面我们将分别介绍。

1、用Prim算法求最小生成树的思想如下：（设图G的度为n，G=（V，E））

①设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集；

②选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S；

③重复下列操作，直到选取了n-1条边：

选取一条权值最小的边（X，Y），其中X∈S，not (Y∈S)；

将顶点Y加入集合S，边（X，Y）加入集合TE；

④得到最小生成树T =（S，TE）

下面给出Prim算法构造图的最小生成树的具体算法框架。

①从文件中读入图的邻接矩阵g；

②边集数组elist初始化；

For i:=1 To n-1 Do

Begin

elist[i].fromv:=1；elist[i].endv:=i+1；elist[i].weight:=g[1,i+1]；

End；

③求出最小生成树的n-1条边；

For k:=1 To n-1 Do

Begin

min:=maxint；m:=k；

For j:=k To n-1 Do {查找权值最小的一条边}

If elist[j].weightk Then Begin t:=elist[k]；elist[k]:=elist[m]；elist[m]:=t；End；

{把权值最小的边调到第k个单元} j:=elist[k].endv； {j为新加入的顶点}

For i:=k+1 To n-1 Do {修改未加入的边集}

Begin s:=elist[i].endv； w:=g[j,s]；

If w

Then Begin elist[i].weight:=w；elist[i].fromv:=j；End；

End；

End；

④输出；

2、用Kruskal算法求最小生成树的思想如下：（设图G的度为n，G=（V，E））

设最小生成树为T=（V，TE），设置边的集合TE的初始状态为空集。将图G中的边按权值从小到大排好序，然后从小的开始依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边；若选取的边使生成树形成回路，则将其舍弃；如此进行下去，直到TE中包含n-1条边为止。最后的T即为最小生成树。

Kruskal算法在实现过程中的关键和难点在于：如何判断欲加入的一条边是否与生成树中已保留的边形成回路？我们可以将顶点划分到不同的集合中，每个集合中的顶点表示一个无回路的连通分量，很明显算法开始时，把所有n个顶点划分到n个集合中，每个集合只有一个顶点，表明顶点之间互不相通。当选取一条边时，若它的两个顶点分属于不同的集合，则表明此边连通了两个不同的连通分量，因每个连通分量无回路，所以连通后得到的连通分量仍不会产生回路，因此这条边应该保留，且把它们作为一个连通分量，即把它的两个顶点所在集合合并成一个集合。如果选取的一条边的两个顶点属于同一个集合，则此边应该舍弃，因为同一个集合中的顶点是连通无回路的，若再加入一条边则必然产生回路。

下面给出利用Kruskal算法构造图的最小生成树的具体算法框架。

①将图的存储结构转换成边集数组表示的形式elist，并按照权值从小到大排好序；

②设数组C[1..n-1]用来存储最小生成树的所有边，C[i]是第i次选取的可行边在排好

序的elist中的下标；

③设一个数组S[1..n]，S[i]都是集合，初始时S[i]= [ i ]。

③i:=1；{获取的第i条最小生成树的边}

j:=1；{边集数组的下标}

While i<=n-1 Do

Begin

For k:=1 To n Do Begin {取出第j条边，记下两个顶点分属的集合序号} If elist[j].fromv in s[k] Then m1:=k；

If elist[j].endv in s[k] Then m2:=k；

End；

If m1<>m2 Then Begin {找到的elist第j条边满足条件，作为第i条边保留} C[i]:=j；

i:=i+1；

s[m1]:=s[m1]+s[m2]；{合并两个集合}

s[m2]:=[ ]； {另一集合置空}

End；

j:=j+1； {取下条边，继续判断}

End；

④输出最小生成树的各边：elist[C[i]]

二、求图的最短路径算法

在带权图G=（V，E）中，若顶点 Vi,Vj是图G的两个顶点，从顶点Vi到Vj的路径长度定义为路径上各条边的权值之和。从顶点Vi到Vj可能有多条路径，其中路径长度最小的

一条路径称为顶点Vi到Vj的最短路径。求最短路径具有很高的实用价值，在各种竞赛中经常遇到。一般有两类最短路径问题：一类是求从某个顶点（源点）到其它顶点（终点）的最短路径；另一类是求图中每一对顶点间的最短路径。

对于不带权的图，只要人为的把每条边加上权值1，即可当作带权图一样处理了。

1、从一个顶点到其余各顶点的最短路径

看上图，假设C1,C2,C3,C4,C5,C6是六座城市，他们之间的连线表示两城市间有道路相通，连线旁的数字表示路程。请编写一程序，找出C1到C i的最短路径(2≤i≤6)，输出路径序列及最短路径的路程长度。

对于一个含有n个顶点和e条边的图来说，从某一个顶点Vi到其余任一顶点Vj的最短路径，可能是它们之间的边（Vi，Vj），也可能是经过k个中间顶点和k+1条边所形成的路径(1≤k≤n-2)。下面给出解决这个问题的Dijkstra算法思想

。

设图G用邻接矩阵的方式存储在GA中，GA[i,j]=maxint表示Vi，Vj是不关联的，否则为权值（大于0的实数）。设集合S用来保存已求得最短路径的终点序号，初始时S=[Vi]表示只有源点，以后每求出一个终点Vj，就把它加入到集合中并作为新考虑的中间顶点。设数组dist[1..n]用来存储当前求得的最短路径，初始时Vi，Vj如果是关联的，则dist[j]等于权值，否则等于maxint，以后随着新考虑的中间顶点越来越多，dist[j]可能越来越小。再设一个与dist对应的数组path[1..n]用来存放当前最短路径的边，初始时为Vi到Vj的边，如果不存在边则为空。

执行时，先从S以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，找出其值最小的元素（假设为dist[m]），该元素值就是从源点Vi到终点Vm的最短路径长度，

对应的path[m]中的顶点或边的序列即为最短路径。接着把Vm并入集合S中，然后以Vm作为新考虑的中间顶点，对S以外的每个顶点Vj，比较dist[m]+GA[m,j]的dist[j]的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替dist[j]，同时把Vj或边（Vm，Vj）并入到path[j]中。重复以上过程n-2次，即可在dist数组中得到从源点到其余各终点的最段路径长度，对应的path数组中保存着相应的最段路径。

对于上图，采用Dijkstra算法找出C1到C i之间的最短路径(2≤i≤6)的过程如下：

初始时：

第一次：选择m=2，则S=[C1,C2]，计算比较dist[2]+GA[2,j]与dist[j]的大小（3≤j≤6）

第二次：选择m=3，则S=[C1,C2,C3]，计算比较dist[3]+GA[3,j]与dist[j]的大小（4≤j≤6）

第三次：选择m=4，S=[C1,C2,C3,C4]，计算比较dist[4]+GA[4,j]与dist[j]的大小（5≤j≤6）

第四次：选择m=5，则S=[C1,C2,C3,C4,C5]，计算比较dist[5]+GA[5,j]与dist[j]的大小（j=6）

因为该图的度n=6，所以执行n-2=4次后结束，此时通过dist和path数组可以看出：C1到C2的最短路径为：C1——C2，长度为：4；

C1到C3的最短路径为：C1——C2——C3，长度为：7；

C1到C4的最短路径为：C1——C2——C4，长度为：8；

C1到C5的最短路径为：C1——C2——C3——C5，长度为：9；

C1到C6的最短路径为：C1——C2——C3——C5——C6，长度为：13；

下面给出具体的Dijkstra算法框架（注：为了实现上的方便，我们用一个一维数组s[1..n]代替集合S，用来保存已求得最短路径的终点集合，即如果s[j]=0表示顶点Vj不在集合中，反之，s[j]=1表示顶点Vj已在集合中）。

Procedure Dijkstra(GA,dist,path,i)； {表示求Vi到图G中其余顶点的最短路径，GA为图G的邻接矩阵，dist和path为变量型参数，其中path的基类型为集合} Begin

For j:=1 To n Do Begin {初始化}

If j<>i Then s[j]:=0

Else s[j]:=1；

dist[j]:=GA[i,j]；

If dist[j]

Else path[j]:=[ ]；

End；

For k:=1 To n-2 Do

Begin

w:=maxint；m:=i；

For j:=1 To n Do {求出第k个终点Vm}

If (s[j]=0) and (dist[j]

If m<>i Then s[m]:=1 else exit；{若条件成立，则把Vm加入到S中，否则退出循环，因为剩余的终点，其最短路径长度均为maxint，无需再计算下去} For j:=1 To n Do {对s[j]=0的更优元素作必要修改}

If (s[j]=0) and (dist[m]+GA[m,j]

Then Begin

Dist[j]:=dist[m]+GA[m,j]；

path[j]:=path[m]+[j]；

End；

End；

End；

2、任意一对顶点之间的最短路径

这个问题的解法有两种：一是分别以图中的每个顶点为源点共调用n次Dijkstra算法，这种算法的时间复杂度为O（n3）；另外还有一种算法：Floyed算法，它的思路简单，但时间复杂度仍然为O（n3），下面介绍Floyed算法。

设具有n个顶点的一个带权图G的邻接矩阵用GA表示，再设一个与GA同类型的表示每对顶点之间最短路径长度的二维数组A，A的初值等于GA。Floyed算法需要在A上进行n次运算，每次以V k（1≤k≤n）作为新考虑的中间点，求出每对顶点之间的当前最短路径长度，最后依次运算后，A中的每个元素A[i，j]就是图G中从顶点V i到顶点V j的最短路径长度。再设一个二维数组P[1..n,1..n]，记录最短路径，其元素类型为集合类型set of 1..n。

Floyed算法的具体描述如下：

Procedure Floyed(GA，A，P)；

Begin

For i:=1 To n Do {最短路径长度数组和最短路径数组初始化}

For j:=1 To n Do

Begin

A[i,j]:=GA[i,j]；

If A[i,j]

Else p[i,j]:=[ ]；

End；

For k:=1 To n Do {n次运算}

For i:=1 To n Do

For j:=1 To n Do

Begin

If (i=k)or(j=k)or(i=j) Then Continue；

{无需计算，直接进入下一轮循环}

If A[i,k]+A[k,j]

A[i,j]：= A[i,k]+A[k,j]；

P[i,j]：= P[i,k]+P[k,j]；

End；

End；

End；

对于上图，大家可以运用Floyed算法，手工或编程找出任意一对顶点之间的最短路径及其长度。

三、拓扑排序算法

在日常生活中，一项大的工程可以看作是由若干个子工程（这些子工程称为“活动”）组成的集合，这些子工程（活动）之间必定存在一些先后关系，即某些子工程（活动）必须在其它一些子工程（活动）完成之后才能开始，我们可以用有向图来形象地表示这些子工程（活动）之间的先后关系，子工程（活动）为顶点，子工程（活动）之间的先后关系为有向边，这种有向图称为“顶点活动网络”，又称“AOV网”。在AOV网中，有向边代表子工程（活动）的先后关系，即有向边的起点活动是终点活动的前驱活动，只有当起点活动完成之后终点活动才能进行。如果有一条从顶点Vi到Vj的路径，则说Vi是Vj的前驱，Vj是Vi的后继。如果有弧，则称Vi是Vj的直接前驱，Vj是Vi的直接后继。

一个AOV网应该是一个有向无环图，即不应该带有回路，否则必定会有一些活动互相牵制，造成环中的活动都无法进行。

把不带回路的AOV网中的所有活动排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，这个过程称为“拓扑排序”，所得到的活动序列称为“拓扑序列”。需要注意的是AOV网的拓扑序列是不唯一的，如对下图进行拓扑排序至少可以得到如下几种拓扑序列：02143567、01243657、02143657、01243567。

在上图所示的AOV网中，工程1和过程2显然可以同时进行，先后无所谓；但工程4却要等工程1和工程2都完成以后才可进行；工程3要等到工程1和工程4完成以后才可进

行；工程5又要等到工程3、工程4完成以后才可进行；工程6则要等到工程4完成后才能进行；工程7要等到工程3、工程5、过程6都完成后才能进行。可见由AOV网构造拓扑序列具有很高的实际应用价值。

其实，构造拓扑序列的拓扑排序算法思想很简单：只要选择一个入度为0的顶点并输出，然后从AOV网中删除此顶点及以此顶点为起点的所有关联边；重复上述两步，直到不存在入度为0的顶点为止，若输出的顶点数小于AOV网中的顶点数，则输出“有回路信息”，否则输出的顶点序列就是一种拓扑序列。

对上图进行拓扑排序的过程如下：

1、选择顶点0（唯一），输出0，删除边<0，1>，<0，2>；

2、选择顶点1（不唯一，可选顶点2），输出1，删除边<1，3>，<1，4>；

3、选择顶点2（唯一），输出2，删除边<2，4>；

4、选择顶点4（唯一），输出4，删除边<4，3>，<4，5>，<4,6>；

5、选择顶点3（不唯一，可选顶点6），输出3，删除边<3，5>，<3，7>；

6、选择顶点5（不唯一，可选顶点6），输出5，删除边<5，7>；

7、选择顶点6（唯一），输出6，删除边<6，7>；

8、选择顶点7（唯一），输出7，结束。

输出的顶点数m=8，与AOV网中的顶点数n=8相等，所以输出一种拓扑序列：01243567。

为了算法实现上的方便，我们采用邻接表存储AOV网，不过稍做修改，在顶点表中增加一个记录顶点入度的域id，具体的拓扑排序算法描述如下：

Procedure TopSort(dig:graphlist)；{用邻接表dig存储图G}

Var n,top,i,j,k,m: Integer；

P:graphlist；

Begin

n:=dig.adjv； {取顶点总个数}

top:=0； {堆栈、初始化}

For i:=1 To n Do {对入度为0的所有顶点进行访问，序号压栈}

If dig.adj[i].id = 0 Then Begin

dig.adj[i].id:=top；

top:=i；

End；

m:=0； {记录输出的顶点个数}

While top<>0 Do {栈不空}

Begin

j:=top； {取一个入度为0的顶点序号}

top:=dig.adj[top].id； {出栈、删除当前处理的顶点、指向下个入度为0的顶点} Write(dig.adj[top].v)； {输出顶点序号}

m:=m+1；

p:=dig.adj[j].link； {指向V j邻接表的第一个邻接点}

While p<>nil Do {删除所有与V j相关边}

Begin

k:=p^.adjv； {下一个邻接点}

dig.adj[k].id:= dig.adj[k].id - 1； {修正相应点的入度}

If dig.adj[k].id = 0 Then Begin {入度为0的顶点入栈}

dig.adj[k].id:=top；

top:=k；

End；

p:=p^.next； {沿边表找下一个邻接点}

End；

End；

If m

End；

四、关键路径算法

利用AOV网络，对其进行拓扑排序能对工程中活动的先后顺序作出安排。但一个活动的完成总需要一定的时间，为了能估算出某个活动的开始时间，找出那些影响工程完成时间的最主要的活动，我们可以利用带权的有向网，图中的边表示活动，边上的权表示完成该活动所需要的时间，一条边的两个顶点分别表示活动的开始事件和结束事件，这种用边表示活动的网络，称为“AOE网”。其中，有两个特殊的顶点（事件），分别称为源点和汇点，源点表示整个工程的开始，通常令第一个事件（事件1）作为源点，它只有出边没有入边；汇点表示整个工程的结束，通常令最后一个事件（事件n）作为汇点，它只有入边没有出边；其余事件的编号为2到n-1。在实际应用中，AOE网应该是没有回路的，并且存在唯一的入度为0的源点和唯一的出度为0的汇点。

下图表示一个具有12个活动的AOE网。图中有8个顶点，分别表示事件0到7，其中，0表示开始事件，7表示结束事件，边上的权表示完成该活动所需要的时间。

AOE网络要研究的问题是完成整个工程至少需要多少时间？哪些活动是影响工程进度的关键？

下面先讨论一个事件的最早发生时间和一个活动的最早开始时间。如上图，事件V j必须

在它的所有入边活动e ik（1≤k≤n）都完成后才能发生。活动e ik（1≤k≤n）的最早开始时间是与它对应的起点事件V ik的最早发生时间。所有以事件V j为起点事件的出边活动e jk（1≤k≤m）的最早开始时间都等于事件V j的最早发生时间。所以，我们可以从源点出发按照上述方法，求出所有事件的最早发生时间。

设数组earliest[1..n]表示所有事件的最早发生时间，则我们可以按照拓扑顺序依次计算出earliest[k]：

earliest[1]=0

earliest[k]=max{earliest[j]+dut[j,k]}

(其中，事件j是事件k的直接前驱事件，dut[j,k]表示边上的权) 对于图5_10，用上述方法求earliest[0..7]的过程如下：

earliest[0]=0

earliest[1]=earliest[0]+dut[0,1]=0+6=6

earliest[2]=earliest[0]+dut[0,2]=0+7=7

earliest[4]=max{earliest[1]+dut[1,4]，earliest[2]+dut[2,4]}

=max{6+5,7+4}

=11

earliest[3]=max{earliest[1]+dut[1,3]，earliest[4]+dut[4,3]}

=max{6+3,11+3}

=14

earliest[5]=max{earliest[3]+dut[3,5]，earliest[4]+dut[4,5]}

=max{14+2,11+4}

=16

earliest[6]=earliest[4]+dut[4,6]=11+3=14

earliest[7]=max{earliest[3]+dut[3,7]，earliest[5]+dut[5,7], earliest[6]+dut[6,7]} =max{14+5,16+2,14+4}

=19

最后得到的earliest[7]就是汇点的最早发生时间，从而可知整个工程至少需要19天完成。但是，在不影响整个工程按时完成的前提下，一些事件可以不在最早发生时间发生，而向后推迟一段时间，我们把事件最晚必须发生的时间称为该事件的最迟发生时间。同样，有些活动也可以推迟一段时间完成而不影响整个工程的完成，我们把活动最晚必须开始的时间称为该活动的最迟开始时间。一个事件在最迟发生时间内仍没发生，或一个活动在最迟开始时间内仍没开始，则必然会影响整个工程的按时完成。如上图，事件V j的最迟发生时间应该为：它的所有直接后继事件V jk（1≤k≤m）的最迟发生时间减去相应边上的权（活动e jk需要时间），取其中的最小值。且汇点的最迟发生时间就是它的最早发生时间，再按照逆拓扑顺序依次计算出所有事件的最迟发生时间，设用数组lastest[1..n]表示，即：lastest[n]=earliest[n]

lastest[j]=min{lastest[k]-dut[j,k]}

(其中，事件k是事件j的直接后继事件，dut[j,k]表示边上的权) 对于图5_10，用上述方法求lastest [0..7]的过程如下：

lastest[7]=earliest[7]=19

lastest[6]=lastest[7]-dut[6,7]=19-4=15

lastest[5]=lastest[7]-dut[5,7]=19-2=17

lastest[3]=min{lastest[5]-dut[3,5]，lastest[7]-dut[3,7]}

=min{17-2,19-5}

=14

lastest[4]=min{lastest[3]-dut[4,3]，lastest[5]-dut[4,5], lastest[6]-dut[4,6]}

=min{14-3,17-4,15-3}

=11

lastest[2]=lastest[4]-dut[2,4]=11-4=7

lastest[1]=min{lastest[3]-dut[1,3]，lastest[4]-dut[1,4]}

=min{14-3,11-5}

=6

lastest[0]=min{lastest[1]-dut[0,1]，lastest[2]-dut[0,2]}

=min{6-6,7-7}

=0

计算好每个事件的最早和最迟发生时间后，我们可以很容易地算出每个活动的最早和最迟开始时间，假设分别用actearliest和actlastest数组表示，设活动i的两端事件分别为事件j和事件k,如下所示：

活动i

事件j ————————> 事件k

则：actearliest[i]=earliest[j]

actlastest[i]=lastest[k]-dut[j,k]

对于上面的例子，用上述方法求得所有活动的最早和最迟开始时间如下表：

上表中的余量（称为开始时间余量）是该活动的最迟开始时间减去最早开始时间，余量不等于0的活动表示该活动不一定要在最早开始时间时就进行，可以拖延一定的余量时间再进行，也不会影响整个工程的完成。而余量等于0的活动必须在最早开始时间时进行，而且在规定的工期内完成，否则将影响整个工程的完成。我们把开始时间余量为0的活动称为“关键活动”，由关键活动所形成的从源点到汇点的每一条路径称为“关键路径”。

其实关键路径就是从源点到汇点具有最大路径长度的那些路径。这很容易理解，因为整个工程的工期就是按照最长路径计算出来的。很显然，要想缩短整个工程的工期，就应该想法设法去缩短关键活动的持续时间。读者可以根据上面的思想编程求出AOE网的关键路径。

Ch6、作业：

1、最短路径问题（short.pas，short.exe）

[问题描述] 平面上有n个点（n<=100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。

[输入格式]

输入文件为short.in，共n+m+3行，其中:

第一行为整数n。

第2行到第n+1行（共n行），每行两个整数x和y，描述了一个点的坐标。

第n+2行为一个整数m，表示图中连线的个数。

此后的m行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间有连线。

最后一行：两个整数s和t，分别表示源点和目标点。

[输出格式]

输出文件为short.out，仅一行，一个实数（保留两位小数），表示从s到t的最短路径长度。

[样例输入]

5

0 0

2 0

2 2

0 2

3 1

5

1 2

1 3

1 4

2 5

3 5

1 5

[样例输出]

3.41

2、最优布线问题（wire.pas，wire.exe）

[问题描述] 学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们时间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。

当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。

现在由你负责连接这些计算机，你的任务是使任意两台计算机都连通（不管是直接的或间接的）。

[输入格式]

输入文件wire.in，第一行为整数n（2<=n<=100），表示计算机的数目。此后的n行，每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。

[输出格式] 输出文件wire.out，一个整数，表示最小的连接费用。

[样例输入]

3

0 1 2

1 0 1

2 1 0

[样例输出]

2（注：表示连接1和2，2和3，费用为2）

3、奇怪的数列（num.pas,num.exe）

[问题描述] 编程输入3个整数n，p，q，寻找一个由整数组成的数列（a1，a2，……，a n），要求：其中任意连续p项之和为正数，任意连续q项之和为负数。0

[输入格式]

输入文件名为num.in，仅一行分别表示n，p，q，之间用一个空格隔开。

[输出格式]

输出文件名为num.out，只有一行，有解即输出这个数列，每个数之间用一个空格隔开。否则输出NO。

[输入输出样例]

num.in

6 5 3

num.out

-3 5 –3 -3 5 -3

num.in

3 2 1

num.out

NO

图论算法及其MATLAB程序代码

图论算法及其MATLAB 程序代码 求赋权图G =(V ,E ,F )中任意两点间的最短路的Warshall-Floyd 算法： 设A =(a ij )n ×n 为赋权图G =(V ,E ,F )的矩阵,当v i v j ∈E 时a ij =F (v i v j ),否则取a ii =0,a ij =+∞(i ≠j ),d ij 表示从v i 到v j 点的距离,r ij 表示从v i 到v j 点的最短路中一个点的编号. ①赋初值.对所有i ,j ,d ij =a ij ,r ij =j .k =1.转向② ②更新d ij ,r ij .对所有i ,j ,若d ik +d k j ＜d ij ,则令d ij =d ik +d k j ,r ij =k ,转向③. ③终止判断.若d ii ＜0,则存在一条含有顶点v i 的负回路,终止;或者k =n 终止;否则令k =k +1,转向②. 最短路线可由r ij 得到. 例1求图6-4中任意两点间的最短路. 解：用Warshall-Floyd 算法,MATLAB 程序代码如下： n=8;A=[0281Inf Inf Inf Inf 206Inf 1Inf Inf Inf 8607512Inf 1Inf 70Inf Inf 9Inf Inf 15Inf 03Inf 8 Inf Inf 1Inf 3046 Inf Inf 29Inf 403 Inf Inf Inf Inf 8630];%MATLAB 中,Inf 表示∞ D=A;%赋初值 for (i=1:n)for (j=1:n)R(i,j)=j;end ;end %赋路径初值 for (k=1:n)for (i=1:n)for (j=1:n)if (D(i,k)+D(k,j)

一笔画问题是图论中一个著名的问题

一笔画问题是图论中一个著名的问题。一笔画问题起源于柯尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题，也提出了一笔画定理，顺带解决了一笔画问题[1]。一般认为，欧拉的研究是图论的开端。 与一笔画问题相对应的一个图论问题是哈密顿问题。 目录[隐藏] 1 问题的提出 2 一笔画定理 2.1 定理一 2.2 定理二 3 例子 3.1 七桥问题 3.2 一个可以一笔画的例子 4 一笔画问题与哈密顿问题 5 参见 6 参考来源 [编辑] 问题的提出 一笔画问题是柯尼斯堡问题经抽象化后的推广，是图遍历问题的一种。在柯尼斯堡问题中，如果将桥所连接的地区视为点，将每座桥视为一条边，那么问题将变成：对于一个有着四个顶点和七条边的连通图G(S,E)，能否找到一个恰好包含了所有的边，并且没有重复的路径。欧拉将这个问题推广为：对于一个给定的连通图，怎样判断是否存在着一个恰好包含了所有的边，并且没有重复的路径？这就是一笔画问题。用图论的术语来说，就是判断这个图是否是一个能够遍历完所有的边而没有重复。这样的图现称为欧拉图。这时遍历的路径称作欧拉路径（一个圈或者一条链），如果路径闭合（一个圈），则称为欧拉回路[1]。 一笔画问题的推广是多笔画问题，即对于不能一笔画的图，探讨最少能用多少笔来画成。 [编辑] 一笔画定理 对于一笔画问题，有两个判断的准则，它们都由欧拉提出并证明[1]。 [编辑] 定理一 有限图G是链或圈的充要条件是：G为连通图，且其中奇顶点的数目等于0或者2。有限连通图G是圈当且仅当它没有奇顶点[2]。 证明[2][3]： 必要性：如果一个图能一笔画成，那么对每一个顶点，要么路径中“进入”这个点的边数等于“离开”这个点的边数：这时点的度为偶数。要么两者相差一：这时这个点必然是起点或终点之一。注意到有起点就必然有终点，因此奇顶点的数目要么是0，要么是2。 充分性： 如果图中没有奇顶点，那么随便选一个点出发，连一个圈C1。如果这个圈就是原图，那么

建立数学模型的方法步骤特点及分类

§16.3 建立数学模型的方法、步骤、特点及分类 [学习目标] 1.能表述建立数学模型的方法、步骤； 2.能表述建立数学模型的逼真性、可行性、渐进性、强健性、可转移性、非预制性、条理 性、技艺性和局限性等特点；； 3.能表述数学建模的分类； 4.会采用灵活的表述方法建立数学模型； 5.培养建模的想象力和洞察力。 一、建立数学模型的方法和步骤 —般说来建立数学模型的方法大体上可分为两大类、一类是机理分析方法，一类是测试分析方法．机理分析是根据对现实对象特性的认识、分析其因果关系，找出反映内部机理的规律,建立的模型常有明确的物理或现实意义.§16.2节的示例都属于机理分析方法。测试分折将研究对象视为一个“黑箱”系统，内部机理无法直接寻求，可以测量系统的输人输出数据、并以此为基础运用统计分析方法，按照事先确定的准则在某一类模型中选出一个与数据拟合得最好的模型。这种方法称为系统辨识(System Identification)．将这两种方法结合起来也是常用的建模方法。即用机理分析建立模型的结构，用系统辨识确定模型的参数． 可以看出，用上面的哪一类方法建模主要是根据我们对研究对象的了解程度和建模目的决定的．如果掌握了机理方面的一定知识，模型也要求具有反映内部特性的物理意义。那么应该以机理分析方法为主．当然,若需要模型参数的具体数值，还可以用系统辨识或其他统计方法得到．如果对象的内部机理基本上没掌握，模型也不用于分析内部特性,譬如仅用来做输出预报，则可以系统辩识方法为主．系统辨识是一门专门学科，需要一定的控制理论和随机过程方面的知识．以下所谓建模方法只指机理分析。 建模要经过哪些步骤并没有一定的模式，通常与实际问题的性质、建模的目的等有关，从§16.2节的几个例子也可以看出这点．下面给出建模的—般步骤，如图16-5所示． 图16-5 建模步骤示意图 模型准备首先要了解问题的实际背景，明确建模的目的搜集建模必需的各种信息如现象、数据等，尽量弄清对象的特征,由此初步确定用哪一类模型，总之是做好建模的准备工作．情况明才能方法对，这一步一定不能忽视，碰到问题要虚心向从事实际工作的同志请教，尽量掌握第一手资料. 模型假设根据对象的特征和建模的目的，对问题进行必要的、合理的简化，用精确的语言做出假设，可以说是建模的关键一步．一般地说，一个实际问题不经过简化假设就很难翻译成数学问题，即使可能，也很难求解．不同的简化假设会得到不同的模型．假设作得不合理或过份

经典图论问题

5经典图论问题 5.1 一笔画问题 一笔画算法即是从起点a开始选择关联边（第一这条边不是往回倒，第二这条边在前面延伸路上没有出现过）向前延伸，如果到达终点b，得到a—b迹，判断路上的的边数是否为图的总边数，是就终止，否则选择迹上某个关联边没有用完的顶点v，用同样方式再搜索v—v的闭迹，添加到a—b迹上，即得到a—v---v—b迹，如果这个迹的边数还没有达到总边数，则再选择迹上某个关联边没有用完的顶点。。。。。。逐步扩展即可。

二、弗罗莱（Fleury ）算法 任取v 0∈V(G)，令P 0=v 0； 设P i =v 0e 1v 1e 2…e i v i 已经行遍，按下面方法从中选取e i+1： （a ）e i+1与v i 相关联； （b ）除非无别的边可供行遍，否则e i+1不应该为G i =G-{e 1,e 2, …, e i }中的桥（所谓桥是一条删除后使连通图不再连通的边）； （c ）当（b ）不能再进行时，算法停止。 5.2 中国邮递员问题（CPP ） 规划模型： 设ij x 为经过边j i v v 的次数，则得如下模型。 ∑∈= E v v ij ij j i x z ?min ∑ ∑ E ∈E ∈∈=j i i k v v i v v ki ij V v x x , E ∈∈≤j i ij v v N x ,1 ..t s

5.3旅行推销员问题（TSP，货郎担问题）（NPC问题） 定义：包含图G的所有定点的路（圈）称为哈密顿路（圈），含有哈密顿圈得图称为哈密顿图。 分析：从一个哈密顿圈出发， 算法一：（哈密顿圈的充要条件：一包含所有顶点的连通子图，二每个顶点度数为2） 象求最小生成树一样，从最小权边加边，顶点度数大于3以及形成小回路的边去掉。 算法二： 算法三：

图论算法及matlab程序的三个案例

图论实验三个案例 单源最短路径问题 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到j v 的权ij w =∞。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在 1 i v +，使 1()min{()} i l v l v +=，v S ∈； ⑤ 1{} i S S v +=， 1{} i S S v +=-，1i i =+，转②； 实际上，Dijkstra 算法也是最优化原理的应用：如果12 1n n v v v v -是从1v 到 n v 的最短路径，则 12 1 n v v v -也必然是从1v 到 1 n v -的最优路径。 在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元 素表示顶点i v 到j v 的权ij w ，若i v 到j v 无边，则realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数+308)。 function re=Dijkstra(ma)

图论问题

图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图论与数学的关系 图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。 图论的起源 图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来 问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。然而无数次的尝试都没有成功。欧拉在1736年解决了这个问题，他用抽像分析法将这个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个“图”（如下图）。 欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这就是后

来的欧拉路径和欧拉回路。这项工作使欧拉成为图论〔及拓扑学〕的创始人。 汉密尔顿的游戏与图论 1859年，英国数学家汉密尔顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即“绕行世界”。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个生成圈后来被称为汉密尔顿回路。这个问题后来就叫做汉密尔顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为汉密尔顿问题，从而引起广泛的注意和研究。 四色猜想 在图论的历史中，还有一个最著名的问题－－四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。这一问题最早于1852年由Francis Guthrie提出，最早的文字记载则现于德摩根于同一年写给哈密顿的信上。包括凯莱、肯普等在内的许多人都曾给出过错误的证明。泰特(Tait)、希伍德(Heawood)、拉姆齐和哈德维格(Hadwiger)对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究。一百多年后，四色问题仍未解决。1969年，Heinrich Heesch发表了一

maab图论程序算法大全

图论算法m a t l a b实现求最小费用最大流算法的 MATLAB 程序代码如下： n=5;C=[0 15 16 0 0 0 0 0 13 14 0 11 0 17 0 0 0 0 0 8 0 0 0 0 0]; %弧容量 b=[0 4 1 0 0 0 0 0 6 1 0 2 0 3 0 0 0 0 0 2 0 0 0 0 0]; %弧上单位流量的费用 wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示预定的流量值 for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流 while(1)

for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图 for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j); elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j); elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值 for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路 for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end;e nd if(pd)break;end;end %求最短路的Ford 算法结束 if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有 向赋权图中不会含负权回路, 所以不会出现k=n dvt=Inf;t=n; %进入调整过程, dvt 表示调整量 while(1) %计算调整量 if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量 elseif(a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量

图论基础知识

图论基本知识 对于网络的研究，最早是从数学家开始的，其基本的理论就是图 论，它也是目前组合数学领域最活跃的分支。我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的……这些都可以用图论的语言和符号精确简洁地描述。图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。考虑到物理学家对于图论这一领域比较陌生，我在此专辟一章介绍图论的基本知识，同时将在后面的章节中不加说明地使用本章定义过的符号。进一步研究所需要的更深入的图论知识，请参考相关文献[1-5]。 本章只给出非平凡的定理的证明，过于简单直观的定理的证明将 留给读者。个别定理涉及到非常深入的数学知识和繁复的证明，我们将列出相关参考文献并略去证明过程。对于图论知识比较熟悉的读者可以直接跳过此章，不影响整体阅读。 图的基本概念 图G 是指两个集合(V ，E)，其中集合E 是集合V×V 的一个子集。 集合V 称为图的顶点集，往往被用来代表实际系统中的个体，集合E 被称为图的边集，多用于表示实际系统中个体之间的关系或相互作用。若{,}x y E ，就称图G 中有一条从x 到y 的弧（有向边），记为x→

y ，其中顶点x 叫做弧的起点，顶点y 叫做弧的终点。根据定义，从任意顶点x 到y 至多只有一条弧，这是因为如果两个顶点有多种需要区分的关系或相互作用，我们总是乐意在多个图中分别表示，从而不至于因为这种复杂的关系而给解析分析带来困难。如果再假设图G 中不含自己到自己的弧，我们就称图G 为简单图，或者更精确地叫做有向简单图。以后如果没有特殊的说明，所有出现的图都是简单图。记G 中顶点数为()||G V ν=，边数为()||G E ε=，分别叫做图G 的阶和规模，显然有()()(()1)G G G ενν≤-。图2.1a 给出了一个计算机分级网络的示意图，及其表示为顶点集和边集的形式。 图2.1：网络拓扑结构示意图。图a 是10阶有向图，顶点集为 {1,2,3,4,5,6,7,8,9,10}，边集为{1→2,1→3,1→4,2→5,2→6,2→7,3→6,4→7,4→8,6→9,7→9,8→10}；图b 是6阶无向图，顶点集为{1,2,3,4,5,6}，边集为{13,14,15,23,24,26,36,56}。 从定义中可以看到，从任意顶点x 到y 不能连接两条或以上 边，本文所讨论的图，均符合上述要求，既均为不含多重边的图。如

图论及其算法

《图论及其算法》 --最短路问题 学院：通信学院 姓名：周旋 学号： S110131133 指导老师：陈六新

摘要 图论是数学的一个分支，它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这些图形通常用来描述某些事物之间的特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有的关系。通过对《图论及其应用》中最短路问题的深入学习，本文利用Dijkstra算法来解决日常生活中寻找最短路的问题。同时也是对本学期学习知识的巩固。 关键词：最短路径 Dijkstra算法迭代

Abstract Graph theory is a branch of mathematics, it studies the object of picture. Graph theory graph is given by the number of points and lines connecting the two points of the graphic form. These graphics are often used to describe a specific relationship between certain things. And with the point on behalf of things, with the line connecting the two points that have a corresponding relationship between two things. Through the "Graph Theory and Its Applications," in-depth study of the shortest path problem. In this paper, we use The Dijkstra's algorithm not only to solve everyday life to find the shortest path problem, but also for the consolidation of the semester to learn the knowledge. Keyword: shortest path Dijkstra's algorithm Iteration

图论模型的建立与转化

图论模型的建立与转化 关键字：图论模型、建立、转化 摘要 本文主要写图论模型的建立与转化，共分四部分： 第一部分引言说明了图论建模在整个信息学竞赛中的地位，以及图论模型与其它数学模型的异同，并指出很有研究总结图论建模的思想、方法及技巧的必要。 第二部分提出了图论模型建立中的两个要点：对原型中的要素进行适当的取舍和选择合适的理论体系，并分别举例加以详细分析，然后从中总结出了图论建模的总的原则：准确、清晰、简明。 第三部分主要讨论了在图论模型的转化中，应用得较为广泛的两种方法：拆分转化和补集转化，并着重分析了前者。文中把前者分为三类：点→边、点→点、边→边，其中详细分析了第二类。 第四部分总结了全文，并指出了进一步研究图论模型的必要性 目录 一．引言 (2) 二．图论模型的建立 (2) I.要素的取舍 (2) II.选择合适的理论体系 (4) 三．图论模型的转化 (7) I.拆分转化 (7) II.补集转化 (10) 四．结语 (11)

正文 一.引言 信息学竞赛以解题为主，整个解题过程中一个重要的步骤就是数学建模，本文要讨论的就是数学建模的一个分支——图论建模。 图论建模是指对一些客观事物进行抽象、化简，并用图1来描述事物特征及内在联系的过程。 建立图论模型的目的和建立其它的数学模型一样，都是为了简化问题，突出要点，以便更深入地研究问题的本质；它的求解目标可以是最优化问题，也可以是存在性或是构造性问题；并且，和几何模型、运筹学模型一样，在建立图论模型的过程中，也需要用到集合、映射、函数等基本的数学概念和工具； 但图论模型和其它模型在它们的研究方法上又有着很大的不同，例如我们可以运用典型的图论算法来对图论模型进行求解，或是根据图论的基本理论来分析图论模型的性质，这些特殊的算法和理论都是其它模型所不具备的，而且在其它模型中，能用类似于图这种直观的结构来描述的也很少。 我们学习图论，一般都是通过书籍，但书上介绍的往往只限于图论模型的基本要素、一些图论的相关理论和经典算法等，至于如何建立图论模型、如何运用这些理论和算法、如何研究图论问题，都只有靠自己来理解、来领会，并通过实践来验证这些理解，通过摸索总结来提高自己的能力。 在建立图论模型的过程中，我们常常会遇到一些困难，例如难以建立点、边、权关系，或是原型中的一些重要因素无法纳入现有模型，或是现有模型虽能表示原型，却无法求解等等。为了克服这些困难，就需要用到某些独特的思想、方法和技巧，本文要写的正是我在学习、实践中得出的这方面的一点认识。 二.图论模型的建立 在建立模型之前，我们首先要对研究对象进行全面的调查，将原型理想化、简单化（对于竞赛题而言，这一步大部分已经由出题人完成了）；然后对原型进行初步的分析，分清其中的各个要素及求解目标，理出它们之间的联系；下一步就是用恰当的模型来描述这些要素及联系。 I.要素的取舍 在用图论模型描述研究对象时，为了更突出与求解目标息息相关的要素，降低思考的复杂度，就不可避免地要舍去部分要素。下面我们就通过例1来分析一下。 【例1】导线排布Line[7]： 题目（文档附件：导线排布.doc）中蓝色的一段是问题描述的重点，其中涉及的要素有圆圈、N根导线、2N个端点、编号规则、导线的交叉等，求解目标是构造一种符合所给的导线交叉情况的导线排布方案。 起先，我们对题目描述的导线排布并不熟悉，或许我们能够画出几个无解或是多解的1在本文中，“图”专指由若干不同顶点与连接其中某些顶点的边所组成的图形[6]，不包括一般的示意图。

图论经典问题

常见问题： 1、图论的历史 图论以图为研究对象的数学分支。图论中的图指的是一些点以及连接这些点的线的总体。通常用点代表事物，用连接两点的线代表事物间的关系。图论则是研究事物对象在上述表示法中具有的特征与性质的学科。 在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观。例如，国家用点表示，有外交关系的国家用线连接代表这两个国家的点，于是世界各国之间的外交关系就被一个图形描述出来了。另外我们常用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系等等。 事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟。由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要。由此经数学抽象产生了图的概念。研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。 图论的产生和发展经历了二百多年的历史，大体上可分为三个阶段： 第一阶段是从1736年到19世纪中叶。当时的图论问题是盛行的迷宫问题和游戏问题。最有代表性的工作是著名数学家L.Euler于1736年解决的哥尼斯堡七桥问题(Konigsberg Seven Bridges Problem)。 东普鲁士的哥尼斯堡城(现今是俄罗斯的加里宁格勒，在波罗的海南岸）位于普雷格尔(Pregel)河的两岸，河中有一个岛，于是城市被河的分支和岛分成了四个部分，各部分通过7座桥彼此相通。如同德国其他城市的居民一样，该城的居民喜欢在星期日绕城散步。于是产生了这样一个问题：从四部分陆地任一块出发，按什么样的路线能做到每座桥经过一次且仅一次返回出发点。这就是有名的哥尼斯堡七桥问题。 哥尼斯堡七桥问题看起来不复杂，因此立刻吸引所有人的注意，但是实际上很难解决。 瑞士数学家(Leonhard Euler)在1736年发表的“哥尼斯堡七桥问题”的文章中解决了这个问题。这篇论文被公认为是图论历史上的第一篇论文，Euler也因此被誉为图论之父。 欧拉把七桥问题抽象成数学问题---一笔画问题，并给出一笔画问题的判别准则，从而判定七桥问题不存在解。Euler是这样解决这个问题的：将四块陆地表示成四个点，桥看成是对应结点之间的连线，则哥尼斯堡七桥问题就变成了：从A，B，C，D任一点出发，通过每边一次且仅一次返回原出发点的路线(回路)是否存在？Euler证明这样的回路是不存在的。 第二阶段是从19世纪中叶到1936年。图论主要研究一些游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。一些图论中的著名问题如四色问题(1852年)和Hamilton环游世界问题(1856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。1847年德国的克希霍夫(G.R.Kirchoff)将树

数学竞赛中的图论问题

数学竞赛中的图论问题

分类号密级 U D C 编号 本科毕业论文(设计) 题目数学竞赛中的图论问题 所在院系数学与数量经济学院 专业名称数学与应用数学 年级 08级 学生姓名李曼 学号 0850410013 指导教师孙静

二 0一二年三月 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在孙静老师的指导下独立进行研究所取得的研究成果. 除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品.本人完全意识到本声明的法律后果由本人承担. 作者：

日期：2012年3月29日 文献综述 一综述 在18世纪30年代，一个非常有趣的问题引起了欧洲数学家的浓厚兴趣，这个问题就是著名的哥尼斯堡七桥问题，即要求遍历哥尼斯堡七桥中的每一座桥恰好一次后回到出发点. 欧拉证明这是不可能完成的. 此后，欧拉发表了著名的论文《依据集合位置的阶梯方法》，这是图论领域的第一篇论文，标志着图论的诞生. 图论的真正发展始于20世纪五六十年代之间，是一门既古老又年轻的学科. 图论极有趣味性，严格来讲，它是组合数学的一个重要分支. 虽然图论只是研究点和线的学科,但是它的应用领域十分广泛，不仅局限于数学和计算机学科，还涵盖了社会学、交通管理等. 总的来说，图论这门科学具有以下特点：（1）图论蕴含了丰富的思想、漂亮的图形和巧妙的证明； （2）涉及的问题多且广泛，问题表明上简单朴素，本质上却十分深刻复杂； （3）解决问题的方法千变万化，非常灵活，常常是一种问题一种解法. 由以上三个特点可以看出，图论与其他的数学分支不同，它不像群论、拓扑等学科那样有一套完整的体系和解决问题的系统. 而且图论所研究的内容非常广泛，如图的连通性、遍历性、图的着色、图的可平面性等等. 二内容 由于图论具有蕴含了丰富的思想、漂亮的图形和巧妙的证明，涉及的问题多且广泛，问题表面上简单朴素，本质上却十分深刻复杂，解决问题的方法千变万化，非常灵活，常常是一种问题一种解法的特点. 随着数学竞赛越来越规范化，并且越来越考察考生的灵活运用知识的能力. 因此近年来，图论问题频繁的出现在数学竞赛中，如典型的一笔画问题、中国邮递员问题、旅游推销员问题、排课表问题等.

离散数学图论部分经典精彩试题及问题详解

离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝，则下列结论成立的是 ( )． A ．deg(V )=2∣E ∣ B ．deg(V )=∣E ∣ C ．E v V v 2)deg(=∑∈ D ．E v V v =∑∈)deg( 4．图G 如图一所示，以下说法正确的是 ( ) ． A ．{(a , d )}是割边 B ．{(a , d )}是边割集 C ．{(d , e )}是边割集 D ．{(a, d ) ,(a, c )}是边割集 5．如图二所示，以下说法正确的是 ( )． A ．e 是割点 B ．{a, e }是点割集 C ．{b , e }是点割集 D ．{d }是点割集 6．如图三所示，以下说法正确的是 ( ) ． A ．{(a, e )}是割边 B ．{(a, e )}是边割集 C ．{(a, e ) ,(b, c )}是边割集 D ．{(d , e )}是边割集 ο ο ο ο ο c a b e d ο f 图一 图二

图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( )． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ο ο ο ο c a b f

图论的发展及其在现实生活中的几个应用

图论的发展及其在生活中的应用 数学与应用数学张佳丽 指导教师刘秀丽 摘要主要介绍了图论的起源与发展及其生活中的若干应用，如：渡河问题、旅游推销员问题、最小生成树问题、四色问题、安排问题、中国邮递员问题。同时也涉及到了几种在图论中应用比较广泛的方法，如：最邻近法、求最小生成树的方法、求最优路线的方法等。 关键词图论生活问题应用 Graph Theory Development and the Application in Life Mathematics and applied mathematics Zhang Jiali Tutor Liu Xiuli Abstract This paper mainly introduces the origin and development of graph theory and its several applications in our life, such as: crossing river problem, traveling salesman problem, minimum spanning tree problem, four color problem，arrangement problem，Chinese postman problem．It also researches several methods that are more widely applied in graph theory, for example: the method of most neighboring, the method of solving the minimum spanning tree，the method of the best route，and so on． Key words graph theory life problem application 引言 图论是一门古老的学科，是数学中有广泛应用的一个分支，与其他的数学分支，如群论、矩阵论、概率论、拓扑学、数分析等有着密切的联系．图论中以图为研究对象，图形中我们用点表示对象，两点之间的连线表示对象之间的某种特定的关系．事实上，任何一个包含了二元关系的系统都可以用图论来模拟．而且,图论能把纷杂的信息变的有序、直观、清晰．由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点间连接与否尤为重要，而图形的位置、大小、形状及连接线的曲直长短则无关紧要．图论在自然科学、社会科学等各个领域都有广泛的应用．随着科学的发展，以及生产管理、军事、交通运输等方面提出了大量实际的需要，图论的理论及其应用研究得到飞速发展。从20世纪50年代以后，由于计算机的迅速发展，有力地推动了图论的发展，加速了图论向各个学科的渗透，尤其是网络理论的建立，图论与线性规划、动态规划等优化理论和方法互相渗透。同时，计算机的发展使图论成为数学领域中发展最快的分支

建立数学模型方法步骤 特点及分类

建立数学模型的方法、步骤、特点及分类 [学习目标] 1.能表述建立数学模型的方法、步骤； 2.能表述建立数学模型的逼真性、可行性、渐进性、强健性、可转移性、非 预制性、条理性、技艺性和局限性等特点；； 3.能表述数学建模的分类； 4.会采用灵活的表述方法建立数学模型； 5.培养建模的想象力和洞察力。 一、建立数学模型的方法和步骤 —般说来建立数学模型的方法大体上可分为两大类、一类是机理分析方法，一类是测试分析方法．机理分析是根据对现实对象特性的认识、分析其因果关系，找出反映内部机理的规律,建立的模型常有明确的物理或现实意义.测试分折将研究对象视为一个“黑箱”系统，内部机理无法直接寻求，可以测量系统的输人输出数据、并以此为基础运用统计分析方法，按照事先确定的准则在某一类模型中选出一个与数据拟合得最好的模型。这种方法称为系统辨识(System Identification)．将这两种方法结合起来也是常用的建模方法。即用机理分析建立模型的结构，用系统辨识确定模型的参数． 可以看出，用上面的哪一类方法建模主要是根据我们对研究对象的了解程度和建模目的决定的．如果掌握了机理方面的一定知识，模型也要求具有反映内部特性的物理意义。那么应该以机理分析方法为主．当然,若需要模型参数的具体数值，还可以用系统辨识或其他统计方法得到．如果对象的内部机理基本上没掌握，模型也不用于分析内部特性,譬如仅用来做输出预报，则可以系统辩识方法

为主．系统辨识是一门专门学科，需要一定的控制理论和随机过程方面的知识．以下所谓建模方法只指机理分析。 建模要经过哪些步骤并没有一定的模式，通常与实际问题的性质、建模的目的等有关，从 §16.2节的几个例子也可以看出这点．下面给出建模的—般步骤，如图16-5所示． 图16-5 建模步骤示意图 模型准备首先要了解问题的实际背景，明确建模的目的搜集建模必需的各种信息如现象、数据等，尽量弄清对象的特征,由此初步确定用哪一类模型，总之是做好建模的准备工作．情况明才能方法对，这一步一定不能忽视，碰到问题要虚心向从事实际工作的同志请教，尽量掌握第一手资料. 模型假设根据对象的特征和建模的目的，对问题进行必要的、合理的简化，用精确的语言做出假设，可以说是建模的关键一步．一般地说，一个实际问题不经过简化假设就很难翻译成数学问题，即使可能，也很难求解．不同的简化假设会得到不同的模型．假设作得不合理或过份简单，会导致模型失败或部分失败，于是应该修改和补充假设；假设作得过分详细，试图把复杂对象的各方面因素都考虑进去，可能使你很难甚至无法继续下一步的工作．通常，作假设的依据，一是出于对问题内在规律的认识，二是来自对数据或现象的分析，也可以是二者的综合．作假设时既要运用与问题相关的物理、化学、生物、经济等方面的知识，又要充分发挥想象力、洞察力和判断力，善于辨别问题的主次，果断地抓住主要因素，舍弃次要因素，尽量将问题线性化、均匀化．经验在这里也常起重要作用．写出假设时，语言要精确，就象做习题时写出已知条件那样．

(完整word版)图论算法及matlab程序的三个案例

图论实验三个案例 单源最短路径问题 1.1 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到j v 的权ij w =∞。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在 1 i v +，使 1()min{()} i l v l v +=，v S ∈； ⑤ 1{} i S S v +=U ， 1{} i S S v +=-，1i i =+，转②； 实际上，Dijkstra 算法也是最优化原理的应用：如果121n n v v v v -L 是从1v 到 n v 的最短路径，则 121 n v v v -L 也必然是从1v 到 1 n v -的最优路径。 在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元 素表示顶点i v 到j v 的权ij w ，若i v 到j v 无边，则realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数(1.7977e+308)。 function re=Dijkstra(ma)

图论模型建立与转化

图论模型的建立与转化 安徽徐静 关键字：图论模型、建立、转化 摘要 本文主要写图论模型的建立与转化，共分四部分： 第一部分引言说明了图论建模在整个信息学竞赛中的地位，以及图论模型与其它数学模型的异同，并指出很有研究总结图论建模的思想、方法及技巧的必要。 第二部分提出了图论模型建立中的两个要点：对原型中的要素进行适当的取舍和选择合适的理论体系，并分别举例加以详细分析，然后从中总结出了图论建模的总的原则：准确、清晰、简明。 第三部分主要讨论了在图论模型的转化中，应用得较为广泛的两种方法：拆分转化和补集转化，并着重分析了前者。文中把前者分为三类：点→边、点→点、边→边，其中详细分析了第二类。 第四部分总结了全文，并指出了进一步研究图论模型的必要性。 目录 一．引言 (2) 二．图论模型的建立 (2) I.要素的取舍 (2) II.选择合适的理论体系 (4) 三．图论模型的转化 (7) I.拆分转化 (7) II.补集转化 (10) 四．结语 (11)

正文 一.引言 信息学竞赛以解题为主，整个解题过程中一个重要的步骤就是数学建模，本文要讨论的就是数学建模的一个分支——图论建模。 图论建模是指对一些客观事物进行抽象、化简，并用图[1]来描述事物特征及内在联系的过程。 建立图论模型的目的和建立其它的数学模型一样，都是为了简化问题，突出要点，以便更深入地研究问题的本质；它的求解目标可以是最优化问题，也可以是存在性或是构造性问题；并且，和几何模型、运筹学模型一样，在建立图论模型的过程中，也需要用到集合、映射、函数等基本的数学概念和工具； 但图论模型和其它模型在它们的研究方法上又有着很大的不同，例如我们可以运用典型的图论算法来对图论模型进行求解，或是根据图论的基本理论来分析图论模型的性质，这些特殊的算法和理论都是其它模型所不具备的，而且在其它模型中，能用类似于图这种直观的结构来描述的也很少。 我们学习图论，一般都是通过书籍，但书上介绍的往往只限于图论模型的基本要素、一些图论的相关理论和经典算法等，至于如何建立图论模型、如何运用这些理论和算法、如何研究图论问题，都只有靠自己来理解、来领会，并通过实践来验证这些理解，通过摸索总结来提高自己的能力。 在建立图论模型的过程中，我们常常会遇到一些困难，例如难以建立点、边、权关系，或是原型中的一些重要因素无法纳入现有模型，或是现有模型虽能表示原型，却无法求解等等。为了克服这些困难，就需要用到某些独特的思想、方法和技巧，本文要写的正是我在学习、实践中得出的这方面的一点认识。 二.图论模型的建立 在建立模型之前，我们首先要对研究对象进行全面的调查，将原型理想化、简单化（对于竞赛题而言，这一步大部分已经由出题人完成了）；然后对原型进行初步的分析，分清其中的各个要素及求解目标，理出它们之间的联系；下一步就是用恰当的模型来描述这些要素及联系。 I.要素的取舍 在用图论模型描述研究对象时，为了更突出与求解目标息息相关的要素，降低思考的复杂度，就不可避免地要舍去部分要素。下面我们就通过例1来分析一下。 【例1】导线排布Line[7]： 题目（文档附件：导线排布.doc）中蓝色的一段是问题描述的重点，其中涉及的要素有圆圈、N根导线、2N个端点、编号规则、导线的交叉等，求解目标是构造一种符合所给的导线交叉情况的导线排布方案。 起先，我们对题目描述的导线排布并不熟悉，或许我们能够画出几个无解或是多解的例子，但竞赛时我们不可能花更多的时间在熟悉题目上了，这时只有尽快地把我们不熟悉的、难于思考的原型转化成我们熟知的、便于思考的模型。 先来分析求解目标：所谓的构造导线排布方案，也就是找出每根导线两个端点的编号；而编号要满足的条件就是导线交叉的情况。 那么下一步我们就来分析一下编号与导线交叉之间的关系。记第i根导线两端点的标号为Ai和Bi（AiB1，A2>B2，A1>A2（根据编号规则），不同的是(a)满足A2>B1，B1>B2，