1. 概论

图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。

2. 图与网络的基本概念

2.1 无向图

一个无向图(undirected graph) G是由一个非空有限集合V(G)V(G)V(G)（称为图G的顶点集(vertex set)或节点集(node set)，其中的每个元素称为顶点或节点）和V(G)V(G)V(G)中某些元素的无序对集合E(G)E(G)E(G)（称为图G的边集，其中的每个元素为V(G)中的无序对组合）构成的二元组，记为G=(V(G),E(G))G = (V (G),E(G))G=(V(G),E(G))。

当边ek=vivje_k=v_iv_jek=vivj时，称vj,vjv_j,v_jvj,vj为边eke_kek的端点，并称viv_ivi与vjv_jvj相邻（adjacent）；边eke_kek称为与顶点vi,vjv_i,v_jvi,vj关联（incident）。如果某两条边至少有一个公共端点，则称这两条边在图G 中相邻。

边上赋权的无向图称为赋权无向图或无向网络（undirected network）。

一个图称为有限图，如果它的顶点集和边集都有限。图G的顶点数用符号|V | 或 ν (G) 表示，边数用| E |或ε (G)表示。

端点重合为一点的边称为环(loop)。

一个图称为简单图(simple graph)，如果它既没有环也没有两条边连接同一对顶点。

2.2 有向图

一个有向图（directed graph或digraph）G是由一个非空有限集合V 和V 中某些元素的有序对集合 A 构成的二元组，记为G = (V, A)。V 中的每一个元素称为该图的一个顶点或节点；A称为图G 的弧集（arc set），A 中的每一个元素(即V 中某两个元素的有序对) 被称为该图的一条弧（arc）。

当弧ak=vivja_k=v_iv_jak=vivj时，称viv_ivi为aka_kak的尾（tail），vjv_jvj为aka_kak的头（head），并称弧aka_kak为viv_ivi的出弧（outgoing arc），为vjv_jvj的入弧（incoming arc）。

一个有向图G对应的无向图称为图G的基础图，一个无向图G‘对应的任一有向图称为G’的定向图。

未指明“有向图”三字，“图”字皆指无向图。

2.3 完全图、二分图

每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。n 个顶点的完全图记为 Kn。

若图G的顶点集V可分为两个非空集合X，Y的并集，且这两集和交集为空，X中无相邻顶点对时，Y中亦然，则称G为二分图(bipartite graph)。特别地，若∀x ∈ X,∀y ∈Y，则xy∈E(G)，则称G 为完全二分图，记成K∣X∣,∣Y∣K_{|X |,|Y |}K∣X∣,∣Y∣。

举一个最简单的例子，下图是一个完全二分图：

2.4 子图

如果V(H)⊂V(G)V (H ) ⊂V (G)V(H)⊂V(G)， E(H)⊂E(G)E(H) ⊂ E(G)E(H)⊂E(G)，则H叫做图G的子图（subgraph），记作H⊂GH ⊂GH⊂G，H是G的子图，则G 称为 H 的母图。

G 的支撑子图（spanning subgraph，又称生成子图）是指满足V(H) =V(G) 的子图H。

2.5 顶点的度

设v∈V(G)v ∈V (G)v∈V(G) ，G 中与v 关联的边数（每个环算作两条边）称为v的度(degree)，记作d(v)。若d(v)是奇数，称v 是奇顶点(odd point)；d(v)是偶数，称v 是偶顶点(even point)。关于顶点的度，我们有如下结果：

∑v∈Vd(v)=2ϵ\\sum\\limits_{v\\in V}d(v)=2\\epsilonv∈V∑d(v)=2ϵ
任意一个图的奇顶点的个数是偶数。

2.6 图与网络的数据结构

为了在计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图与网络。在下面数据结构的讨论中，我们首先假设G = (V, A)是一个简单有向图，|V |= n,| A |= m ，并假设V 中的顶点用自然数1,2,…,n表示或编号， A 中的弧用自然数1,2,…,m 表示或编号。

2.6.1 邻接矩阵表示法

邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。图G = (V, A)的邻接矩阵是如下定义的：C 是一个n × n 的0 −1矩阵，即
C=(cij)n×n∈{0,1}n×n{1,i,j∈A0,i,j∉AC=(c_{ij})_{n\\times n}\\in\\{0,1\\}^{n\\times n}\\\\\\begin{cases}1,{i,j}\\in A\\\\0,{i,j}\\notin A\\\\\\end{cases}C=(cij)n×n∈{0,1}n×n{1,i,j∈A0,i,j∈/A

也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为 1；否则为 0。可以看出，这种表示法非常简单、直接。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络中查找弧的时间。

2.6.2 关联矩阵表示法

G = (V, A)的关联矩阵 B 是如下定义的： B 是一个n × m 的矩阵，即
B=(bik)n×m∈{1,0,−1}n×mbik={1,∃j∈V,k=(i,j)∈A−1,∃j∈V,k=(j,i)∈A0,otherwiseB=(b_{ik})_{n\\times m}\\in\\{1,0,-1\\}^{n\\times m}\\\\b_{ik}=\\begin{cases}1,\\exist j\\in V,k=(i,j)\\in A\\\\-1,\\exist j\\in V,k=(j,i)\\in A\\\\0,otherwise\\end{cases}B=(bik)n×m∈{1,0,−1}n×mbik=⎩⎪⎨⎪⎧1,∃j∈V,k=(i,j)∈A−1,∃j∈V,k=(j,i)∈A0,otherwise

也就是说，在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。如果一个节点是一条弧的起点，则关联矩阵中对应的元素为 1；如果一个节点是一条弧的终点，则关联矩阵中对应的元素为 −1；如果一个节点与一条弧不关联，则关联矩阵中对应的元素为 0。

2.6.3 弧表表示法

图的弧表，也就是图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点，共需2m 个存储单元，因此当网络比较稀疏时比较方便。此外，对于网络图中每条弧上的权，也要对应地用额外的存储单元表示。

2.6.4 邻接表表示法

图的邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的所有出弧。邻接表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所有弧，链表中每个单元对应于一条出弧。为了记录弧上的权，链表中每个单元除列出弧的另一个端点外，还可以包含弧上的权等作为数据域。

2.6.5 星形表示法

星形（star）表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点，它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表示。也就是说，在该数组中首先存放从节点 1 出发的所有弧，然后接着存放从节点2出发的所有孤，依此类推，最后存放从节点n 出发的所有孤。对每条弧，要依次存放其起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号，只是从同一节点出发的弧的顺序可以任意排列。

2.7 轨与连通

道路W的数学定义：W=v0e1v1e2⋅⋅⋅ekvkW=v_0e_1v_1e_2\\cdot\\cdot\\cdot e_kv_kW=v0e1v1e2⋅⋅⋅ekvk，其中k为路长，顶点v0和vk称为道路的起点和终点，而其他顶点称为内部顶点。

若道路W 的边互不相同，则W 称为迹(trail)。若道路W 的顶点互不相同，则W 称为轨(path)。如果有正的长且起点和终点相同，称一条道路是闭的。起点和终点重合的轨叫做圈(cycle)。若图G 的两个顶点u, v 间存在道路，则称u和v连通(connected)。u, v 间的最短轨的长叫做u, v 间的距离。记作d(u,v) 。若图G 的任二顶点均连通，则称G 是连通图。

显然有以下结论：

图 P 是一条轨的充要条件是 P 是连通的，且有两个一度的顶点，其余顶点的度为 2；
图C 是一个圈的充要条件是C 是各顶点的度均为 2 的连通图。

3. 应用——最短路径问题

求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距u0u_0u0从近到远为顺序，依次求得u0 到G 的各顶点的最短路和距离，直至v0v_0v0（或直至G的所有顶点），算法结束。

具体算法步骤如下：

起点sb到终点db通用的Dijkstra标号算法matlab程序如下：

function [mydistance,mypath]=mydijkstra(a,sb,db);% 输入：a—邻接矩阵(aij)是指i到j之间的距离，可以是有向的% sb—起点的标号, db—终点的标号% 输出：mydistance—最短路的距离, mypath—最短路的路径n=size(a,1); visited(1:n) = 0;distance(1:n) = inf; % 保存起点到各顶点的最短距离distance(sb) = 0; parent(1:n) = 0;for i = 1: n-1temp=distance;id1=find(visited==1); %查找已经标号的点temp(id1)=inf; %已标号点的距离换成无穷[t, u] = min(temp); %找标号值最小的顶点visited(u) = 1; %标记已经标号的顶点id2=find(visited==0); %查找未标号的顶点for v = id2if a(u, v) + distance(u) < distance(v)distance(v) = distance(u) + a(u, v); %修改标号值parent(v) = u;endendendmypath = [];if parent(db) ~= 0 %如果存在路!t = db; mypath = [db];while t ~= sbp = parent(t);mypath = [p mypath];t = p;endendmydistance = distance(db);return

对于如下问题，求A到D的最短路径：

编写Lingo程序如下：

model:sets:cities/A,B1,B2,C1,C2,C3,D/;roads(cities,cities)/A B1,A B2,B1 C1,B1 C2,B1 C3,B2 C1,B2 C2,B2 C3,C1 D,C2 D,C3 D/:w,x;endsetsdata:w=2 4 3 3 1 2 3 1 1 3 4;enddatan=@size(cities); !城市的个数;min=@sum(roads:w*x);@for(cities(i)|i #ne#1 #and# i #ne#n:@sum(roads(i,j):x(i,j))=@sum(roads(j,i):x(j,i)));@sum(roads(i,j)|i #eq#1:x(i,j))=1;@sum(roads(i,j)|j #eq#n:x(i,j))=1;end

计算赋权图中各对顶点之间最短路径，显然可以调用 Dijkstra 算法。方法是：每次以不同的顶点作为起点，用 Dijkstra 算法求出从该起点到其余顶点的最短路径，反复执行 n −1次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。另一种解决这一问题的方法是 Floyd 算法。

Floyd 算法的基本思想是：递推产生一个矩阵序列Ak(i,j)A_k (i, j)Ak(i,j)，表示两点的路径上所经过的顶点序号不大于 k 的最短路径长度。

Floyd算法的Matlab通用程序如下：

function [dist,mypath]=myfloyd(a,sb,db);% 输入：a—邻接矩阵(aij)是指 i 到 j 之间的距离，可以是有向的% sb—起点的标号；db—终点的标号% 输出：dist—最短路的距离；% mypath—最短路的路径n=size(a,1); path=zeros(n);for i=1:nfor j=1:nif a(i,j)~=infpath(i,j)=j; %j 是 i 的后续点endendendfor k=1:nfor i=1:nfor j=1:nif a(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=path(i,k);endendendenddist=a(sb,db);mypath=sb; t=sb;while t~=dbtemp=path(t,db);mypath=[mypath,temp];t=temp;endreturn

4. 树

4.1 基本概念

连通的无圈图叫做树，记之为T 。若图G 满足V (G) =V (T ) ， E(T ) ⊂ E(G) ，则称T 是G 的生成树。图G 连通的充分必要条件为G 有生成树。一个连通图的生成树的个数很多，用τ (G) 表示G 的生成树的个数，则有公式
(caylay)τ(Kn)=Nn−2τ(G)=τ(G−e)+τ(G⋅e)(caylay)\\tau(K_n)=N^{n-2}\\\\\\tau(G)=\\tau(G-e)+\\tau(G\\cdot e)(caylay)τ(Kn)=Nn−2τ(G)=τ(G−e)+τ(G⋅e)
其中G − e 表示从G 上删除边e ，G ⋅ e 表示把e 的长度收缩为零（即把e的两端点重合为一点）得到的图。

树有下面常用的五个充要条件：

G 是树当且仅当G 中任二顶点之间有且仅有一条轨道。
G 是树当且仅当G 无圈，且ε =ν −1。
G 是树当且仅当G 连通，且ε =ν −1。
G 是树当且仅当G 连通，且∀e∈ E(G) ，G − e 不连通。
G 是树当且仅当G 无圈，∀e∉ E(G) ，G + e 恰有一个圈。

4.2 应用—连线问题

连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生成树叫做最小生成树。下面介绍构造最小生成树的两种常用算法。

4.2.1 prim算法构建最小生成树

设置两个集合P和Q ,其中P用于存放G的最小生成树中的顶点，集合Q 存放G的最小生成树中的边。令集合 P 的初值为P={v1}P=\\{v_1\\}P={v1}（假设构造最小生成树时，从顶v1v_1v1出发），集合Q 的初值为Q = Φ 。prim 算法的思想是，从所有 p ∈ P ，v ∈V − P 的边中，选取具有最小权值的边 pv ，将顶点 v 加入集合 P 中，将边 pv 加入集Q 中，如此不断重复，直到 P =V 时，最小生成树构造完毕，这时集合Q 中包含了最小生成树的所有边。

4.2.2 Kruskal 算法构造最小生成树

5. 匹配问题

若M⊂E(G)，∀ei,ej∈M，ei与ejM ⊂ E(G) ，∀ei ,e j ∈ M ，e_i与 e_jM⊂E(G)，∀ei,ej∈M，ei与ej无公共端点（i ≠ j ），则称 M 为图G 中的一个对集；M 中的一条边的两个端点叫做在对集 M 中相配；M 中的端点称为被 M 许配；G 中每个顶点皆被 M 许配时，M 称为完美对集；G 中已无使| M \’|>| M |的对集 M ，则 M 称为最大对集；若G 中有一轨，其边交替地在对集 M 内外出现，则称此轨为M 的交错轨，交错轨的起止顶点都未被许配时，此交错轨称为可增广轨。

最大对集的充要条件：
定理：M 是图G 中的最大对集当且仅当G 中无 M可增广轨。

许配定理：
G 为二分图， X 与Y 是顶点集的划分，G 中存在把 X 中顶点皆许配的对集的充要条件是，∀S ⊂ X ，则| N(S) |≥| S |，其中 N(S) 是 S 中顶点的邻集。

推论 1：若G是k次（k>0) 正则2分图，则G有完美对集。所谓k 次正则图，即每顶点皆k 度的图。

婚配定理：
每个姑娘都结识k(k ≥ 1) 位小伙子，每个小伙子都结识k位姑娘，则每位姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。

人员分派问题：工作人员X去做n件工作Y ，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？

这个问题的数学模型是：G是二分图，顶点集划分为V(G) =XUY，当且仅当xix_ixi适合做工作yjy_jyj时，xiyj∈E(G)x_iy_j ∈E(G)xiyj∈E(G) ，求G 中的最大对集。

在人员分派问题中，工作人员适合做的各项工作当中，效益未必一致，我们需要制定一个分派方案，使公司总效益最大。这个问题的数学模型是：在人员分派问题的模型中，图 G 的每边加了权w(xiyj)≥0w(x_i y_ j) ≥ 0w(xiyj)≥0 ，表示工作的效益，求加权图G 上的权最大的完美对集。

为此，我们要引入可行顶点标号与相等子图的概念。

6. Euler 图和 Hamilton 图

6.1 基本概念

经过G 的每条边的迹叫做G 的 Euler 迹；闭的 Euler 迹叫做 Euler 回路或 E回路；含 Euler 回路的图叫做 Euler 图。

定理：

G 是 Euler 图的充分必要条件是G 连通且每顶点皆偶次。
G 是 Euler 图的充分必要条件是 G 连通且G=⋃i=1dCiG=\\bigcup\\limits_{i=1}^dC_iG=i=1⋃dCi，CiC_iCi是圈，E(Ci)E(Cj)=Φ(i≠j)E(C_i ) E(C_j )= Φ(i≠j)E(Ci)E(Cj)=Φ(i=j)。
G 中有 Euler 迹的充要条件是G 连通且至多有两个奇次点。

包含G 的每个顶点的轨叫做 Hamilton(哈密顿)轨；闭的 Hamilton 轨叫做Hamilton 圈或 H 圈；含 Hamilton 圈的图叫做 Hamilton 图。

6.2 Euler回路的Fleury算法

6.3 应用

6.3.1 邮递员问题

一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投递的每条街道至少一次，为他设计一条投递路线，使得他行程最短。上述中国邮递员问题的数学模型是：在一个赋权连通图上求一个含所有边的回路，且使此回路的权最小。

显然，若此连通赋权图是 Euler 图，则可用 Fleury 算法求 Euler 回路，此回路即为所求。对于非 Euler 图，有下面的解法：

6.3.2 旅行商（TSP）问题

一名推销员准备前往若干城市市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这个问题称为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的Hamilton 圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。

6.3.3 旅行商问题的数学表达式

7. 最大流问题

7.1 最大流问题的数学描述

7.1.1 网络中的流

由于我们只讨论V, A 为有限集合的情况，所以对于弧上的权函数 L,U 和顶点上的权函数 D ，可以直接用所有孤上对应的权和顶点上的权组成的有限维向量表示，因此L,U, D 有时直接称为权向量，或简称权。由于给定有向图G = (V, A) 后，我们总是可以在它的弧集合和顶点集合上定义各种权函数，所以流网络一般也直接简称为网络。

可见，当di > 0时，表示有di 个单位的流量从网络外部流入该顶点，因此顶点i 称为供应点（supply node）或源（source），有时也形象地称为起始点或发点等；当di < 0
时，表示有|di| 个单位的流量从该顶点流失到网络外部（或说被该顶点吸收），因此顶点i 称为需求点（demand node）或汇（sink），有时也形象地称为终止点或收点等；当di = 0时，顶点i 称为转运点（transshipment node）或平衡点、中间点等。此外，可知，对于可行网络，必有∑i∈vdi=0\\sum\\limits_{i\\in v}d_i=0i∈v∑di=0