离散基础及数学 7

1离散数学第十章特殊图回顾路径，简单路径，基本路径连通，强连通，单向连通，弱连通分支回路，有向回路图的矩阵表示方法邻接矩阵可达矩阵2/170本章内容欧拉图哈密尔顿图二部图及匹配二部图的概念及性质二部图匹配平面图平面图的概念及性质多边形图、对偶图及平面图着色3/170本章内容网络网络的基本概念网络流网络最大流求解开关网络4/170本章内容应用与拓展中国邮递员问题旅行售货员问题排课问题时延容忍网络问题最短路径问题欧拉图在智能物流与路径规划中的应用哈密尔顿图在药物分子设计中的应用二部图模型在推荐系统与计算广告中的应用5/170本章内容思政案例中国杰出运筹学家——管梅谷图论在物流领域的应用网神经网络及其应用6/1707/17010.1欧拉图哥尼斯堡七桥问题：从四块陆地的任何一块出发，怎样通过且仅通过每座桥一次，最终回到出发地点？结点表示陆地区域，边表示桥。于是，哥尼斯堡七桥问题就是要找到左图中包含图的所有边的简单闭路径。

8/170欧拉图对这个问题进行推广，也就是判断在一个多重图里是否存在包含每一条边的简单回路？1736年欧拉发表论文，在论文中提出了一条解决此问题的简单准则，确定七桥问题是不能解的。9/170欧拉路径与欧拉闭路定义：图G中包含其所有边的简单开路径称为图G的欧拉路径，图G中包含其所有边的简单闭路径称为G的欧拉闭路。

例：判断下列三个图中是否有欧拉路径或欧拉闭路。10/170欧拉路径与欧拉闭路例：判断下列三个图中是否有欧拉路径或欧拉闭路。11/170欧拉图定义：每个结点都是偶结点的连通无向图称为欧拉图。每个结点的出度和入度相等的连通有向图称为欧拉有向图。

（规定平凡图是欧拉图）欧拉给出了一个连通无向图是欧拉图的充分必要条件，这就是下面的欧拉定理。

定理：设G是连通无向图，则G是欧拉图，当且仅当G有欧拉闭路。

12/170欧拉定理定理：设G是连通无向图，则G是欧拉图，当且仅当G有欧拉闭路。

证：首先证明充分性。若连通无向图G有欧拉闭路，则从该闭路径中任选一个节点a，按照闭路径的顺序依次遍历节点。在路径上每访问一个节点就给该节点增加了两度。因此，每个节点的度都是偶数，该图是欧拉图。再证必要性。对G的边数采用归纳法。若G没有边，即图G是平凡图，必要性显然成立（这里把0当作偶数）。欧拉定理

13/17014/170欧拉定理哥尼斯堡七桥问题，由于哥尼斯堡七桥问题不是欧拉图，不存在欧拉闭路，所以哥尼斯堡七桥问题无解。15/170构造欧拉回路构造欧拉回路的方法：在图G中任选一个结点，找到一个基本循环a1，从G中删去a1的各边之后得到生成子图G1，G1中的每个结点仍然是偶结点；如果G1是零图，则a1即为G中的欧拉回路，退出；否则，转3；若G1不是零图，由G的连通性可知，G1中必有与a1有公共顶点的基本循环a2。这两个基本循环可以通过这个公共顶点合并成一个简单循环；从G1中去掉a2的各边，得到一个生成子图，依次执行2和3，直到G1变为零图，就得到了一条包含各边的欧拉回路。16/170构造欧拉回路例：构造下图的欧拉回路。17/170构造欧拉回路解：首先找出一个基本圈C1，如v1v2v3

v1，从G中删去C1的各条边后得G1，再找出一个基本圈C2，如v1v4v5v1，把两个基本圈合并，得v1v2v3

v1v4v5v1。再从G1中删去C2的各条边得G2；最后从G2找出一个基本圈C3，即v4v3v5v2v4，继续合并，得v1v2v3

v1v4v3v5v2v4v5v1。若从G2删去C3的各边后得到零图，于是合并后的简单循环即为所求的欧拉回路。18/170基本圈C1与C2合并19/17020/170构造欧拉回路基本圈C1、C2与C3合并，所得的简单循环即为所求的欧拉回路21/170欧拉图

22/170一笔画问题一笔划问题：用铅笔连续移动，不离开纸面并且不重复的画出图形。一张图能由一笔画出来的充要条件是：每个交点处的线条数都是偶数或恰有两个交点处的线条数是奇数。

23/170一笔画问题例：构造欧拉回路，看能否一笔画。（穆罕默德短剪刀）24/170欧拉图定理：设G为弱连通的有向图。G是欧拉有向图，当且仅当G有欧拉闭路。每个结点的出度和入度相等的连通有向图称为欧拉有向图。

25/170欧拉图定理：如果G1和G2是可运算的欧拉图，则G1⊕G2是欧拉图。

26/170欧拉图的应用除了一笔画，利用欧拉路径和欧拉回路可以解决很多实际问题。例如：很多应用要求一条路径或者回路，它要恰好一次的经过一个街区的每条道路、一个高压输电线的每个连接或者一个通信网络里的每个链接。求出适当的图模型里的欧拉路径或者欧拉回路可以解决这个问题。中国邮路问题（中国邮递员问题）：投递员在邮局领取邮件，准备投递。他必须走过他投递范围内的每一条街道之后返回邮局，并且选择一条最短的线路。（中国科学家管梅谷1962年提出）27/17010.2哈密尔顿图问题的产生：1859年，爱尔兰数学家哈密尔顿(W.R.Hamilton)在给他朋友的一封信中，首先提出“环球周游”问题：他用一个正十二面体的20个顶点代表世界上20个大城市，连接两个顶点的边看成是交通线，要求旅游者能否找到沿着正十二面体的棱，从某个顶点(即城市)出发，经过每个顶点(即每座城市)恰好一次，然后回到出发顶点？这便是著名的哈密尔顿问题。28/170哈密尔顿图29/170哈密尔顿图按下图中所给的编号进行旅游，便是哈密尔顿问题的解。如果推广到任何的连通图上，也有类似的问题：是否可以从图中任何一点出发，经过每个结点一次且仅一次？30/170哈密尔顿图定义：图G中包含其所有顶点的简单开路径称为图G的哈密尔顿路径，图G中包含其所有顶点的简单闭路径称为G的哈密尔顿回路。具有哈密顿回路的图称为哈密尔顿图。完全图必是哈密尔顿图。哈密尔顿图尽管在形式上与欧拉图极其相似，但其结论上却有很大不同，至今还没有得到关于哈密尔顿图的简明的充要条件，这是图论尚未解决的主要问题之一。然而，还是有不少重要成果，下面给出几个必要和充分条件的定理。31/170哈密尔顿图

上述本定理给出是哈密尔顿图的一个必要条件，但这个条件又不便于使用，因为它要求对G的结点集合的所有真子集进行验证。尽管如此，利用它还可以证明某些图不是哈密尔顿图。32/170哈密尔顿图例：判断下图是否是哈密尔顿图。33/170若S={v2，v6}，则G-S是3个连通分图，因此ω(G-S)≮|S|，从而G不是哈密尔顿图。删除节点v2和v6哈密尔顿图34/170哈密尔顿图尽管这个定理可以用来判断一个图不是哈密尔顿图，但是，当满足ω(G-S)≤|S|时，该图不一定就是哈密尔顿图。上图不是哈密尔顿图。但对于V的任意真子集S，总有ω(G-S)≤|S|。35/170哈密尔顿图

36/170哈密尔顿图

37/170哈密尔顿图已知的最好的求一个图里的哈密尔顿回路或者判定这样的回路不存在的算法具有指数的最坏情形时间复杂度（向对于图的顶点数来说）。找到具有多项式最坏情形时间复杂性的解决算法是NP复杂的。38/170哈密尔顿图的应用旅行商问题：一位旅行商想要访问n个城市中每个城市恰好一次，最后返回到出发点，并且走的路程最短。怎样设计路线？39/170哈密尔顿图的应用

40/17010.3二部图及匹配二部图

二部图没有自圈。与二部图的一条边关联的两个结点一定分属于两个互补结点子集。一般来说，二部图的互补结点子集的划分不是唯一的。41/170二部图定理：设G是阶大于1的无向图。G是二部图，当且仅当G的所有回路长度均为偶数。

42/170二部图

得证。43/170二部图定义：设V1和V2是简单二部图G的互补结点子集，如果V1中的每个结点与V2中的每个结点相邻，则称G为完全二部图。我们把互补结点子集分别包含m和n个结点的完全二部图记为Km,n。

44/170二部图45/170匹配

最大匹配一定是极大匹配，而极大匹配不一定是最大匹配。在一个无向图中，可以有多个极大匹配和最大匹配46/170匹配例：极大匹配：

最大匹配：匹配数：3{a,c,g}{a,e}{a,f},{b,e},{b,g}{b,f,g},{c,h},{c,p},{d,g},{d,h},

{f,p}{a,c,g},{b,f,g}47/170完美匹配定义：设V1和V2是二部图G的互补结点子集。如果G的匹配数等于|V1|，则称G中的最大匹配为V1到V2的完美匹配。

只有|V1|≤|V2|时可能存在从V1到V2的完美匹配。但这个条件并不是充分条件。

上图不存在V1到V2的完美匹配。48/170完美匹配

当二部图的结点数目比较大时，上述定理用起来不太方便下面给出存在完美匹配的一个充分条件，判断二部图是否存在完美匹配时，可以先用这个充分条件，如果得不出结论，再用上述定理。49/170完美匹配定理：设V1和V2是二部图G的互补结点子集，t是正整数。对于V1中的每个结点，在V2中至少有t个结点与其邻接。对于V2中的每个结点，在V1中至多有t个结点与其邻接。则存在V1到V2的完美匹配。

50/170二部图例：有q个委员会，要从每个委员会的委员中选出该委员会的主任，并限定任何人不得兼任一个以上委员会的主任。问是否可能按照要求选出主任？

思路：把这个问题化为图论的问题。令V1是所有委员会的集合，V2是参加这些委员会的人的集合，若某人m是委员会C的委员，则在m和C之间连一条边这样就构成了以V1和V2为互补结点子集的二部图可能按照要求选出主任，当且仅当存在V1到V2的完美匹配每个委员会至少有t个委员，每个委员至多参加t个委员会，这时主任是可以选出的51/17010.4平面图在生活中，通常有这样一类问题，涉及到图的平面性的研究，比如大家都知道的印刷线路板的布线问题。近些年来，大规模集成电路的发展，进一步促进了图的平面性的研究。52/170平面图定义：在一个平面上，如果能够画出无向图G的图解，其中没有任何边的交叉，则称图G是个平面图；否则，称G是非平面图。例：将下列非平面图转化为平面图。53/170平面图图10.18（例10.9）54/170平面图根据平面图的定义，非循环图显然是平面图。故，研究图的平面性问题，只需要限制有回路的一类图即可。判别方法是：对于有回路的图找出一个长度尽可能大的且边不相交的基本回路。将图中那些相交的边，适当放置在已选定的基本圈内侧或外侧，若能避免除结点之外边的相交，则该图是平面图；否则，便是非平面图。55/170平面图

56/170平面图例：设有一个电路，它含有两个结点子集V1和V2，且有|V1|=|V2|=3。用导线把一个集合中的每一个结点，都与另外一个集合中的每一个结点连通，如下图所示。试问，是否有可能这样来接线，使得导线相互不交叉。对于印刷电路，避免交叉具有实际意义。57/170平面图

58/170库拉托夫斯基图上图跟下图图（a）等价，由于已经证明了上图是非平面图，因此下图（a）也是非平面图。同样方法，知（b）也是非平面图。图（a）和（b）都称为库拉托夫斯基图。59/170库拉托夫斯基图如上图（a）所示，试往图中的一条边上，插上一个新的次数为2的结点，把一条边分解成两条边，则不会改变给定图的平面性。另外，如图(b)所示，把联系于一个次数为2的结点的两条边，合并成一条边，也不会改变给定图的平面性。

（a）（b）60/170库拉托夫斯基图定义：设G1和G2是两个无向图。如果G1和G2是同构的，或者是通过反复插入和(或)删除次数为2的结点，能够把G1和G2转化成同构的图，则称G1和G2在次数为2的结点内是同构的。

61/170库拉托夫斯基图库拉托夫斯基定理：设G是一个无向图。图G中不存在任何与下图的两个图同构的子图，当且仅当图G是个平面图。

62/170库拉托夫斯基图例：判断下图是否是可平面图。63/170多边形

64/170多边形多边形的图是个平面图(或多重边图，因为允许长度为2的循环存在)，它能够把平面划分成数个区域，每一个区域都是由一个多边形定界。65/170多边形定义：由多边形的图定界的每一个区域，都称为图G的面。

定义：包含有多边形的图G的所有面的边界的多边形，称为G的极大基本循环。

多边形给定图G的极大基本循环外侧的无限区域，是另外一个面，一般称为G的无限面。事实上，如果把图G的图解画在球面上，则G的无限面与其它的有限面并没有什么区别。定义：如果图G的两个面共有一条边，则称这样的两个面是邻接的面。66/17067/170多边形

多边形

68/17069/170对偶图

由G求G*的方法：对于G中的任何一个面Fi，给G*指定一个结点fi，对于面Fi和Fj所共有的一条边，给G*指定一条边{fi,fj}。实际上，首先在Fi内指定每个结点fi，并且用连通fi和fj的一条边，去交叉Fi和Fj所共有的边，这样就可求得对偶图G*。

70/170对偶图例：给定下图的对偶图。结论：每一个多边形的图G，其对偶图G*也必定是一个多边形的图G和G*是互为对偶的71/170自对偶图定义：如果多边形的图G的对偶G*同构于G，则称G是自对偶图。

与平面图相关的应用：四色问题。是否可用四种颜色对任何平面图形的区域染色，使得任何两个邻接区域，包括无限区域都不会呈现相同的颜色？

72/170图着色平面图的着色问题，最早起源于地图的着色。在一张地图中，若相邻国家着以不同的颜色，那么最少需要多少种颜色呢？1840年，德国数学家麦比乌斯(A.F.Mǒbius)在他的讲稿中第一次提出了确信用四种颜色可以对地图着色的问题(以下简称四色猜想)。1879年肯普(Kempe)给出了这个猜想的第一个证明，但到1890年希伍德(Hewood)发现肯普证明是有错误的，然而他指出了肯普的方法虽不能证明地图着色用四种颜色就够了，但却可以证明用五种颜色是够的，即五色定理成立。直到1976年，美国数学家阿普尔(K.I.Apple)和黑肯(W.Haken)在考西(J.koch)的帮助下，用计算机作了一百多亿次逻辑判断，花了1200多机时才证明了四色猜想是成立的，从此，四色猜想成为四色定理。73/170图着色

74/170图着色定义：对于平面图G着色时，需要的最少颜色数称为G的着色数，记为χ(G)。四色定理：对于任何平面图G，有χ(G)≤4。75/170图的着色数将图的着色数从平面图推广到所有图中，判断下图的着色数。76/170图的着色数77/170图的着色数78/170图的着色数总结：图G只有孤立结点时，即G是平面图，

(G)=1.图G为n阶完全图时，

(G)=n.若图G是n个结点回路时，则当n为偶数，

(G)=2；当n为奇数，

(G)=3。若图G是二部图时，

(G)=2.79/170求图的着色数

80/170求图的着色数例：求下图G的着色数。注意：已知的最好的求图的着色数的算法（对图的顶点个数来说）具有指数的最坏情形时间复杂度。即使是求图的色数的近似值也是很难的。81/170图着色的应用图着色在与调度和分配有关的问题中有多种应用（注意：由于不知道图着色的有效算法，所以并不能得出调度和分配的有效方法），这里仅给出一个重要的例子：安排期末考试。安排期末考试问题：如何安排一个大学里的期末考试，使得没有学生要同时考两门试。图模型：用顶点表示科目，若有学生要考两门试，则在表示考试科目的两个顶点之间用边连接。用不同颜色来表示期末考试的不同时间段，考试的安排就对应于图的着色问题。82/170图着色的应用例：安排七门考试，假定科目从1到7编号，下列各对科目的考试都有学生要同时参加：1和2，1和3，1和4，1和7，2和3，2和4，2和5，2和7，3和4，3和6，3和7，4和5，4和6，5和6，5和7，6和7。时间段1:科目1，6时间段2:科目2时间段3:科目3，5时间段4:科目4，783/17010.4网络本节以运输网络和开关网络为例，介绍网络的流及有关问题。网络是一类特殊的加权图。84/170网络的基本概念定义：一个网络N=(V,A)是指一个连通无环且满足下列条件的有向图。有一个结点子集X，其每个结点的入度都是0。有一个与X不相交的结点子集Y，其每个结点的出度都为0。每条弧都有一个非负的权值，称为弧的容量。上述网络N可以记作N=(V,X,Y,A,C)，其中，X称为网络的源点集，Y称为网络的汇点集，V和A分别为结点集和弧集，网络中的除源点和汇点之外的结点称为中转点。源点和汇点在实际网络中对应于网络的入口和出口，或者说计算机网络的源结点和目的结点。C为网络的容量函数，容量函数是定义在弧集A上的非负函数。85/170网络的基本概念例：图中所示的网络中，{x1,x2}是源点集，{y1,y2}是汇点集。其他结点是中转结点，弧上的数字表示弧的容量。86/170网络的基本概念在原有非单源单汇网络中添加一个新的源点和一个新的汇点，并且添加从新的源点指向原有源点的弧，再添加从原有汇点指向新的汇点的弧，就能得到一个单源单汇网络。单源单汇网络是一种特殊的网络，它在各种网络问题的求解方面比非单源单汇网络更为简单。任意网络都可以转化为单源单汇网络。87/170网络流定义：可行流：网络N=(V,X,Y,A,C)中的一个可行流是指定义在A上的一个整值函数f，使得：对任意a

A,0≤f(a)

≤

c(a),（容量约束）对任意v

V-(X∪Y),f-(v)=f+(v),

（流量守恒）其中，f-(v)表示点v处入弧上的流量之和，即流入v的流量之和，f+(v)表示点v处出弧上的流量之和，即从v流出的流量之和。可行流满足两个条件：一是容量约束，即可行流在某一弧上的流量小于该弧的容量；二是流量守恒，即流入某一中转点的流量等于流出该点的流量。可行流总是存在的，如果f(a)=0，这个流称为零值流。88/170网络流定义：设

f

是网络N=(V,X,Y,A,C)中的一个可行流，则必有f+(X)=f-(Y)。f+(X)(或f-(Y))称为流

f

的流量，记为Valf。最大流，是指网络N中流量最大的可行流。网络的最大流对于实际应用具有重要意义，例如，公路网络中获得最大的运输量、计算机网络中获得最大的转发增益等等。89/170网络流定义：设N=(V,x,y,A,C)是一个单源单汇网络。假设网络中的某些结点组成集合S,S⊆V,

S=V-S。用(S,S)表示尾在S中而头在

S中的所有弧的集合(即从S中的结点指向S之外结点的所有弧的集合)。如果x

S,

而yS,则称弧集(S,S)为网络N的一个割。一个割(S,S)的容量是指(S,S)中各条弧的容量之和，记为Cap(S,S)。对网络N中的任意流f和任意割(S,S),流f的流量等于流出S的流量与流入S的流量之差，即Valf=f+(X)-f-(Y)。90/170网络流定理：最大流最小割定理的基本内容为：任一网络N=(V,X,Y,A,C)中，最大流的流量等于最小割的容量。网络N可能存在多个割，各个割的容量并不一定相等，其中容量最小的一个割称为网络N的最小割。91/170网络最大流求解定义：设P=uv1…ukv是网络N=(V,x,y,A,C)中一条u-v路，若弧<vi,vi+1>

A，则称此弧为u-v路P的一条正向弧（或称前向弧、顺向弧），若弧<vi+1,vi>

A，则称此弧为u-v路P的一条反向弧（或称后向弧、逆向弧）。将u-v路P所经过的弧（无论正向弧还是反向弧）称为路P上的弧。92/170网络最大流求解在下图中网络N中，x-y路P=xv1v3v4y上，所有弧都是正向弧；而在x-y路Q=xv2v4v3y上，弧<x,v2>和<v3,y>是正向弧，而<v4,v2>和<v3,v4>是反向弧。可以看出，对于同一条弧<v3,v4>，在路P中为正向弧，而在路Q中为反向弧。可见，一条弧是正向弧还是反向弧与路的选择有关。93/170网络最大流求解定义：假设f是网络N=(V,X,Y,A,C)中的一个可行流，u是N中任意一点，P是网络N中的一条x-u路，如果对路P上的任一条弧a，都有若弧a是P的正向弧，则c(a)-f(a)>0；若弧a是P的反向弧，则f(a)>0。则称P是N的一条f可增x-u路。特别的，N中的一条f可增x-y路可简称为N的一条f可增路。94/170网络最大流求解对于N中任意一条f可增路P和P上任意一条弧a，假设沿路P可增加的流量为Δf(P)=min{Δf(a)},这一值称为f可增路P上流的增量（可增量）。95/170网络最大流求解例：下图(a)中，每条弧上括号内的数字为弧的容量，括号外的数字为当前流在弧上的流值。图中的虚线表示x-y路。由于Δf(x,v2)=6-1=5、Δf(v2,v4)=2、Δf(v4,v3)=5、Δf(v3,y

)=4-0=4，可增量为Δf(P)={5,2,5,4}=2。因此，路P是N中的f可增路，其可增量为2。增流后的网络如下图(b)所示。图(a)网络的可增路图(b)增流后的网络96/170标号算法标号算法就是由可增路的概念得到的。其基本原理为：对于一个网络N中的一个可行流f，如果能找到N中的一条f可增x-y路P，则可沿着P修改流的值，得到一个流量更大的可行流f

'。修改后流的流量为Valf

'=Valf+Δf(P)。如果反复找N中的可增路，沿着可增路将流量扩大，直到找不出可增路为止，就可以达到最大流97/170标号算法Ford-Fulkerson标号法，标号过程如下：设网络N=(V,x,y,A,C)中当前可行流为f。从源点x开始，首先给x标上∞，即l(x)=∞（x称为已标未查结点，其它结点称为未标未查结点）。任选一已标未查结点u，检查其所有尚未标号的邻点：对u的尚未标号的出邻点v（即<u,v>

A），若c(u,v)>f(u,v)，则给v标号：

l(v)=min{l(u),c(u,v)–f(u,v)},(v称为已标未查结点)

否则，不给v标号。对u的尚未标号的入邻点v（即<v,u>

A），若f(u,v)>0，则给v标号：

l(v)=min{l(u),f(u,v)},(v称为已标未查结点)

否则，不给v标号。当检查完u的所有邻点之后，u称为已标已查结点。反复进行上述操作，最终结果有两种情况：（1）汇点y获得标号，此时已经得到了f的可增流（2）y点没有获得标号，并且已经没有已标未查结点。此时当前的流f就是最大流。98/170标号算法99/170标号算法在标号算法中，有可能出现每次只能增加一个单位流量的情况，这时，如果弧的容量为m,需要2m次增流才能达到最大流。可见，标号算法的计算量不完全依赖于问题的规模（结点数和弧数），还依赖于弧的容量。我们把计算量虽然是问题规模的多项式，但是还依赖于其它参量的算法称为伪多项式算法。Ford-Fulkerson标号算法就是一种伪多项式算法。标号算法不是一个多项式算法，其复杂度还依赖于弧的容量，因此，我们需要复杂度更低的算法。Dinic算法就是一种改进的算法。100/170Dinic算法定义：对于网络N=(V,x,y,A,C)和N上的一个可行流f，构造一个新的网络N(f)=(V,x,y,A(f),C’)，其中A(f)及容量函数C′

定义如下：（1）若<u,v>

A并且f(u,v)<c(u,v)，则<u,v>

A(f

)，并且c′

(u,v)=c(u,v)-f(u,v)。（2）若<u,v>

A并且f(u,v)>0，则<v,u>

A(f)，并且c′

(u,v)=f(u,v)。这样构造的网络N(f

)称为网络N关于流f的增量网络。简单的说，对应于N中一条非饱和流，N(f

)中有一条正向弧，其容量值为N中弧的容量与流量之差；对应于N中一条非零流弧，N(f

)中有一条反向弧，其容量值为N中弧的流量。101/170Dinic算法下图(a)为原始网络，图(b)为增量网络Dinic算法：增量网络N(

f

)中找x-y有向路的方法来寻找网络N的f可增路。102/170Dinic算法定义：在网络N=(V,x,y,A,C)中，令：Vi={v

V|N中x到v的最短有向路的长度为i}。假设x到y的最短有向路的长度为n，则：（1）x

V，y

Vn。（2）Vi∩Vj=Φ，(j≠i)。Vi中的结点称为网络N的第i层结点。上述有向路的长度是指路上有向边的数目，而两点间最短有向路指两点间有向边最少的有向路。103/170Dinic算法下图为网络分层示例。V0={x},V1={v1,v2},V2={y,v3,v4}图(a)待分层的网络N图(b)网络N的分层网络结点分层后，弧有三种可能性：从第i层结点指向第i+1层结点；从第i层结点指向第i层结点；从第i层结点指向第j层结点(j<i)。根据层的定义，不可能出现第i层结点指向第i+k(k≥2)的情况。104/170Dinic算法定义：对于网络N=(V,x,y,A,C)，假设N(f

)是N的关于流f的增量网络。对N(f

)的结点按照最短有向路进行分层后，删除层数不低于y的结点（即比y层数高的结点和与y同层的结点），再删除从高层指向低层的弧和同层结点之间的弧，得到的N(f

)的子网络称为N的关于流f的辅助网络，记为AN(f

)。此时所剩下的各条弧上的容量与N(f

)相同。105/170Dinic算法下图演示了从网络N到增量网络N(f

)，再对增量网络N(f

)进行分层并得到辅助网络的过程。106/170Dinic算法Dinic算法可以从网络N=(V,x,y,A,C)的任意可行流f开始，执行如下过程：（1）构造增量网络N(f

)（2）对N(f

)分层并构造辅助网络AN(f

)（3）求AN(f

)中的一条x-y有向路P，它就是N中的一条f可增路；（4）在N中沿着P增流得到更大的流，并去掉因增流在AN(f

)中所导致的饱和弧。如果此时AN(f

)中仍然有x-y有向路，则再沿着新的x-y有向路在N中增流，直到N(f

)剩余网络中没有x-y有向路为止；（5）反复执行（1）—（4），直到新流f的增量网络N(f

)不能分层到达y位置。完成上述步骤后，网络N不再有f可增路，因此得到的是最大流。107/170Dinic算法108/170Dinic算法在Dinic算法中，找路循环最多能进行e次，而在分层辅助网络中找一条x-y有向路的计算量为O(v)，因此，算法的总计算复杂度为O((v-1)(e+ev))=O(v2e)。其中，e为弧的数量、v为结点的数量。在每次可增加的量较小时，Dinic算法的复杂度要明显低于标号算法。109/170开关网络

110/170开关网络例：在下图中a.b间的道路有：x1x3x7，x2x4x8，x1x5x8，x2x6x7，x1x3x6x4x8，x2x4x5x3x7，x2x6x3x5x8，x1x5x4x6x7；故：上式中的乘积为逻辑乘，和为逻辑和，故服从逻辑运算规则其中，布尔变量x1，x2，…，x8可以是独立的变量，也可以是相同的。比如若则由布尔量的运算法则，上述开关函数可以简化为

111/170开关网络112/170开关网络例：简单接触网络如下图所示。113/170开关网络114/170开关网络

115/170开关网络

116/170开关网络

117/170开关网络（3）若e0边的两个端点都不在回路L上，如下图所示,a,b间的一条道路与L的前后汇合点分别为l和k。令118/170开关网络例：设fab=x1x2x3x5x7+x1x3x4x6+x1x5x6x8+x2x4+x2x3x5x8+x3x4x6x7x8+x5x6x7。第一步：引进边<a,b>=x0,并从回路矩阵出发，通过一系列初等变换，目的要得出基本回路矩阵，步骤如下：从基本回路矩阵可知，图GN有m=9,余数边数=4,树的边数=5,

n=6119/170开关网络第二步：从基本回路矩阵与基本割集矩阵Sf的关系可得矩阵Sf如下：120/170开关网络

对矩阵Sf进行下列一系列初等变换，便能得到一个每列至多有两个元素1的矩阵。121/170开关网络第三步：对上面所的矩阵增加最后一行，使得每列有两个元素1，于是得关联矩阵。根据基本道路矩阵与关联矩阵，可得开关网络图（去掉x0边）如下图所示。122/17010.6*应用与拓展应用与拓展中国邮递员问题旅行售货员问题排课问题时延容忍网络问题最短路径问题欧拉图在智能物流与路径规划中的应用哈密尔顿图在药物分子设计中的应用二部图模型在推荐系统与计算广告中的应用123/170中国邮递员问题1962年我国的管梅谷首先提出并研究了如下的问题：邮递员从邮局出发经过他投递的每一条街道，然后返回邮局，邮递员希望找出一条行走距离最短的路线。这个问题被外国人称为中国邮递员问题（ChinesePostmanProblem）。中国邮递员问题的核心是在一个连通带权无向图中，寻找一个经过每条边至少一次且总权重最小的回路。具体解法依据图的结构不同有三种情况：欧拉图：如果图是欧拉图，则从任意结点出发的欧拉回路即为最优投递路线。半欧拉图：如果图有两个奇结点，存在一条连接这两个奇结点的欧拉链，加上这两个结点之间的最短路径，即为最优路线。非欧拉图：即图中有偶数个奇结点，通过找到两个奇结点之间的最短路径并将其边变为二重边，逐步减少奇结点，直到所有结点的度数为偶数，形成一个多重欧拉图。最后，找到最短的欧拉回路即为最优解。124/170中国邮递员问题

125/170中国邮递员问题奇偶点图上作业法：非欧拉带权连通图G的最优环游的算法，过程如下：（1）把G中所有奇结点配成对，将每对奇结点之间的一条路上的每边改为二重边，得到一个新图G1，新图G1中没有奇结点，即G1为多重欧拉图。（2）若G1中每一对结点之间有多于2条边连接，则去掉其中的偶数条边，留下1条或2条边连接这两个结点。直到每一对相邻结点至多由2条边连接，得到图G2。（3）检查G2的每一个圈C，若某一个圈C上重复边的加权和超过此圈权和的一半，则将C中的重复边改为不重复，而将单边改为重复边。重复这一过程，直到对G2的所有圈，其重复边的权和不超此圈权和的一半，得到图G3。（4）G3的欧拉回路。126/170中国邮递员问题例：求下图(a)中G的最优环游。解：图G中有6个奇结点v2，v4，v5，v7，v9，v10，把它们配成三对：v2与v5，v4与v7，v9与v10。在图G中，取一条连接v2与v5的路v2v3v4v5，把边(v2，v3)，(v3，v4)，(v4，v5)作为重复边加入图中；再取v4与v7之间一条路v4v5v6v7，把边(v4，v5)，(v5，v6)，(v6，v7)作为重复边加入图中，在v9和v10之间加一条重复边(v9，v10)，如上图(b)所示，这个图没有奇结点，是一个欧拉图。图(a)图(b)127/170中国邮递员问题在上页图(b)中，结点v4与v5之间有3条重边，去掉其中2条，得下图(c)所示的图，该图仍是一个欧拉图。如图(c)中，圈v2v3v4v11v2的总权为24，而圈上重复边的权和为14，大于该圈总权的一半，于是去掉边(v2,v3)和(v3,v4)上的重复边，而在边(v2

,v11)和(v4,v11)上加入重复边，此时重复边的权和为10，小于该圈总权的一半。同理，圈v5v6v7v12v5的总权为25，而重复边权和为15，于是去掉边(v5,

v6)和(v6,v7)上的重复边，在边(v5,v12)和(v7,v12)上加重复边，如下图(d)所示。图(c)图(d)128/170中国邮递员问题上页图(d)中，圈v4v5v12v11v4的总权为15，而重复边的权和为8，从而调整为下图(e)所示。图(e)中，圈v1v2v11v12v7v8v9v10v1的总权为36，而重复边的总权为20，继续调整为下图(f)所示。检查图(f)，可知定理的⑴和⑵均满足，故为最优方案，接着给出图(f)所示图的Euler回路，即为图(a)中G的最优环游。图(e)图(f)129/170旅行售货员问题

130/170旅行售货员问题最邻近方法的步骤如下：（1）由任意选择的结点开始，指出与该结点最靠近（即权最小）的点，形成有一条边的初始路径。（2）设x表示最新加到这条路径上的结点，从不在路径上的所有结点中选一个与x最靠近的结点，把连接x与这个结点的边加到这条路径上。重复这一步，直到图中所有结点包含在路径上。（3）将连接起点与最后加入的结点之间的边加到这条路径上，就得到一个哈密尔顿圈，即得问题的近似解。131/170旅行售货员问题例：用“最邻近方法”找出下图所示加权完全图中具有充分小权的哈密尔顿圈。解：

ADCBEFA的权和为55，BCADEFB的权和为53，CBADEFC的权和为42，DABCFED的权和为42，EADCBFE的权和为51，FCBADEF的权和为42。

由上例可知，所选取的哈密尔顿圈不同，其近似解也不同，而“最邻近插入法”对上述方法可以进行改进，从而产生一个较好的结果。

该方法在每次迭代中都构成一个闭的旅行路线。它是由多个阶段而形成的一个个旅程，逐步建立起来的，每一次比上一次多一个结点，即是说，下一个旅程比上一个旅程多一个结点，求解时，在已建立旅程以外的结点中，寻找最邻近于旅程中某个结点的结点，然后将其插入该旅程中，并使增加的距离尽可能小，当全部结点收入这个旅程后，就找到了我们所求的最短哈密尔顿圈的近似解。132/170旅行售货员问题

133/170旅行售货员问题例：用“最邻近插入法”找出下图所示加权完全图中具有充分小权的哈密尔顿圈。解：

①开始于结点A，组成闭旅程AA。②最邻近A的结点为D，建立闭旅程ADA。③结点B最邻近结点A，建立闭旅程ADBA。④由于C最邻近B，将C插入，分别得到三个闭旅程ACDBA、ADCBA、ADBCA，其长度依次为33、20、23，选取长度最短的旅程ADCBA。⑤距旅程ADCBA中结点最邻近结点为F，将F插入，分别得到四个闭旅程AFDCBA、ADFCBA、ADCFBA、ADCBFA，其长度依次为52、34、37、45，选取长度最短的旅程ADFCBA。⑥把结点E插入旅程ADFCBA中，得到5个闭旅程AEDFCBA、ADEFCBA、ADFECBA、ADFCEBA、ADFCBEA、，其长度依次为54、42、60、61、49。显然，长度最短的旅程ADEFCBA即为我们要求的最短哈密尔顿圈的近似解。134/170排课问题排课是高校教学管理中一项重要而且复杂的基本工作，其实质就是为学校所设置的课程安排一组适当的教学时间与空间，从而使整个教学活动能够有计划有秩序地进行。在排课问题中，其主要任务是将具有多种属性的各种资源，如教室、班级、教师、学生、课程、时间等，以一个周期的方式进行合理的匹配，使其不发生冲突。事实上，在排课问题中，每节课可抽象为教师和学生在时间和空间上的统一。因此，课表是协调教师和上课班级在上课时间、上课教室两个要素的总调度。课表算法本质要求主体即教师和上课班级合理使用时间和教室两种资源。课表的编排包括教师和上课班级在上课时间（节次）和上课地点（教室）上的编排，这其中的组合可能性太多，为此可将模型简化为两个子模型：教师和上课班级在时间（节次）上的编排；教师和上课班级在地点（教室）上的编排，而这两个优化过程都可以转化为图论问题来解决。135/170排课问题排课问题在时间上的安排实际上就是安排每一个教师在具体的时间段到某个具体的班级去上课。这个安排要求满足下面的条件：同一时间每位教师只能到一个班级去上课；一个班级在同一个时间也只能由一位教师来上课。用图论的知识可以来表示这个问题。例如：有n位教师，用x1,x2,…,xn来表示，有m个班，用y1,y2,…,ym来表示，教师xi要给班级yj上课就将xi与yj相连，如果一周内教师xi要给班级yj

上2次课，则连2条线，以此类推。可以先作一个二部图G，使G=(X,Y,E)，其中X={x1,x2,…,xn}代表n

个教师，Y={y1,y2,…,ym}代表m个班级，E代表xi与yj之间连接的边，如下图所示。136/170排课问题有相同结点的边称为相邻边。对每一条边进行着色，一种颜色代表一个时间段，通常在大学中2个课时为1节课，每天4节，一周5天，故而在排课问题中边色数是20，代表的是20个时间段，同种颜色的边代表同一个时间段。因为在同一时间每位教师只能到一个班级去上课，而一个班级也只能由一位教师来上课，相邻的边代表有共同的教师或学生，不可以安排在同一个时间段同时上课，因此相邻的边不能着相同的颜色。时间表的安排就变成了对所有的边进行着色，有相同结点的边着不同的颜色，而所有颜色的种类不能超过20种。课表在地点安排上则是安排某个班级在某个时间段在一个具体的教室上课的问题，它必须要满足的条件是：班级人数小于教室的容量，也就是容量大于班级人数的教室都可用，这样班级与教室之间就形成了一个多对多的关系。而事实上，一个班级在同一时间内只能到一个教室去上课，一个教室在同一时间内也只能有一个班级在上课。这就要将一个多对多的关系转换成为一个一一对应的关系，这实际上是一个匹配问题。同时考虑到，如果班级人数比较少而教室太大的话将会影响上课质量，因此，可对每个可用的教室进行赋权，这就形成了一个加权图的匹配问题。137/170排课问题例：在某一时间段，有5个班级x1,x2,x3,x4,x5需要安排教室上课，同时有5个教室y1,y2,y3,y4,y5可用，班级与教室之间的关系如下图所示。解：针对各个教室的使用情况进行赋值，设置权值如下：138/170排课问题矩阵中的每个元素aij分别代表第i个班级安排在第j个教室上课的合适度的权数，权数越高的教室表示越合适，那么就越优先考虑，最终要使得每个班级都能够安排到相对合适的教室，这就要求找到一个权数最高的分配方案。该问题即抽象为在一个加权二部图中找一个权最大的匹配。这个问题可以利用Kuhn—Munkres算法求出最终结果。将上面两个方面结合起来就是一个完整的排课问题，在边色数为20的情况下进行着色表示在20个可用时间段内进行课程安排，而同种颜色互不相邻表示一个教师不能在同一个时间上两门课，同一个班级不能在同一个时间上两门课。在某个时间段上课教室的安排则可看为是一个一一对应的匹配问题。将这两部分结合起来就可以得到在每个时间段内课程的安排和每门课程具体在哪个教室授课的地点安排，从而得到一张完整的课程表。139/170时延容忍网络问题在计算机网络中，传统的网络如以太网、无线自组织网等都有一个基本假设，那就是存在一条端到端的路径。在这一假设下，可以先寻找一条路由，再按照路由进行转发。但是，在挑战性网络环境下，端到端的路径并不一定存在，此时，需要一定的策略来保证转发成功率，其中有一种策略叫做消息的泛洪机制。泛洪机制的基本原理是，节点为了确保数据能到达目的节点，每当该节点与其它节点相遇，都会将数据转发给对方，这样的方式能提高转发成功的概率，但却会加重网络负担。按概率转发的方式是对泛洪机制的改进，在节点与其它节点相遇时，先判断对方节点是否比自己更容易将数据转发到目的节点，再按概率进行转发，这样可以减小网络负担。泛洪机制或者按概率转发的方式下，节点会将数据发送多次，使得网络中存在该数据的多份拷贝，这一转发方式我们称之为多份拷贝（MultipleCopy）的方式。与之对应的是单份拷贝（SingleCopy）方式，即网络中只存在一个数据包的一份拷贝。140/170时延容忍网络问题对于时延容忍网络（DelayTolerantNetworks，DTN）来说，链路容量可以认为是一个固定的量，不会因为选择单份拷贝或者多份拷贝策略而改变，因此，我们可以采用网络流的方法对网络的流量进行分析，得到一个最适合的转发策略。在DTN性能方面，主要考虑转发成功率和延时。在满足转发成功率和延时要求的前提下，我们应尽量传递更多信息，也就是说，需要使信息流最大。对转发成功率和延时条件的要求我们可以合并为一个条件：在所允许的延时时间内，转发成功率大于给定值。141/170时延容忍网络问题例：如下图所示，网络中有4个节点，节点S和节点D固定，节点A和B以一定的规律运动，他们与节点S和节点D在给定的时间内相遇的概率各为0.5（由于对延时有一定限制，超过这一时间后数据将被丢弃，因此后面再遇到目的节点也无法转发成功），每次相遇只能转发一份数据。由于A和B与S、D是以一定概率相遇的，我们在图中用虚线表示这两个节点。在这样的网络中，如果节点S需要发送一些数据给节点D，应该采用何种策略？是转发一次之后就删除本节点的缓存，还是转发成功后继续尝试？142/170时延容忍网络问题由于转发成功率对一条路的各条弧来说是具有相乘关系，如果对转发成功率取对数，就能得到一个相加的量，这与费用函数的定义是一致的。同时，我们所需的是使成功率最大。如果在取对数之后再加上负号，就能对应为使用费用函数了。即：设p为弧上的转发成功率，费用函数的定义为w=-log2p。在进行这样的转换后，可以变为求最小费用流问题。在相遇概率方面，我们可以将A、B两点分裂，用弧<A,A‘>和<B,B’>来表示相遇概率，在弧<A,A‘>和<B,B’>上，容量为相遇概率和原有容量的乘积。经过上述处理后，可用下图来表示这个网络。143/170时延容忍网络问题转发成功率0.5对应的费用即为-log20.5=1，如果对转发成功率的要求就是0.5，那么直接求这个网络的最大流就可以了。相应地，如果需要更高的转发成功率，则需要更低的费用，很容易看出，在上页网络图中找不到一条这样的路径，此时就需要考虑多份拷贝的方式。在多份拷贝方式下，两份不同拷贝的路的总费用为-log2[1-(1-2-x)(1-2-y)]，按照这样的方式可以求解，只是过程更为复杂。上面的示例选择的是最为简单的情况，没有考虑节点的缓存空间大小，如果考虑缓存空间大小，分析的过程将更为复杂，但基本原理仍然可以采用这样的方式，不同的是需要将节点的缓存转化为容量问题再进行求解。144/170最短路径问题在现实生活和生产实践中，有许多管理、组织与计划中的优化问题，如在企业管理中，如何制定管理计划和设备购置计划，使收益最大或费用最小；在组织生产中，如何使各工序衔接好，才能使生产任务完成的既快又好；在现有交通网络中，如何使调运的物资数量多且费用最小等。这类问题均可借助于图论知识得以解决。本节介绍有关网络图中两点间（一般常指始点和终点）的最短路径问题。145/170最短路径问题例：下图是一个石油流向的管网示意图，v1代表石油开采地，v7代表石油汇集站，箭线旁的数字表示管线的长度，现在要从v1地调运石油到v7地，怎样选择管线可使路径最短？可以用点代表城市，以连接两点的连线表示城市间的道路，这样便可用图形描述城市间的交通网络。如果连线旁标注城市间道路的距离或单位运价，就可进一步研究从一个城市到另一个城市的最短路或运费最省的运输方案。在动态规划中，最短路径问题可由贝尔曼最优化原理及其递推方程求解，在阶段明确情况下，用逆向逐段优化嵌套推进，这是一种反向搜索法；在阶段不明确情况下，可用函数迭代法逐步正向搜索，直到指标函数衰减稳定得解。这些算法都是依据同一个原理建立的。即在网络图中，如果v1…vn是从v1到vn的最短路径，则v1…vn-1也必然是从v1到vn-1的最短路径。146/170最短路径问题Dijkstra算法也称为双标号法。所谓双标号，也就是对图中的点vi赋予两个标号(P(vi),

λi):第一个标号P(vi)表示从起点v1到vi的最短路的长度，第二个标号λi表示在v1到vi的最短路上vi前面一个邻点的下标，即用来表示路径，从而可对终点到始点进行反向追踪，找到v1到vn的最短路径。Dijkstra算法适用于每条边的权数都大于或等于零的情况。147/170最短路径问题

148/170最短路径问题例：以下图给出的石油流向的管网示意图为例，v1代表石油开采地，v7代表石油汇集站，箭线旁的数字表示管线的长度，现在要从v1地调运石油到v7地，怎样选择管线可使路径最短？149/170最短路径问题

150/170最短路径问题

151/170最短路径问题

152/170欧拉图在智能物流与路径规划中的应用

在智能物流与机器人路径规划领域，欧拉图与欧拉路径理论为自动配送与全覆盖作业系统提供了坚实的数学基础。欧拉路径要求在图中经过每一条边且仅经过一次，这一特性与配送机器人需要遍历所有街道、清扫车需要覆盖全部路面、电力或管网巡检机器人需要检查所有线路的作业目标高度一致。当城市道路网络被抽象为图模型时，路口被表示为节点，道路被表示为边，边的权重可用于描述距离、通行时间、能耗或综合运行成本。通过这种建模方式，复杂的城市空间被转化为可计算的离散结构。在理想情况下，若该图存在欧拉回路，则机器人可以从仓库或调度中心出发，在不重复经过任何道路的前提下完成全部覆盖任务并返回起点，从而在理论上实现路径长度、能源消耗和车辆磨损的最小化。153/170欧拉图在智能物流与路径规划中的应用

然而，现实城市道路网络往往难以满足欧拉图的存在条件。根据图论中的基本结论，一个无向图存在欧拉回路必须同时满足图的连通性以及所有顶点度数为偶数的要求，而实际路网中普遍存在大量奇度顶点，例如丁字路口、断头路、支路入口以及临时施工形成的非对称连接。这些结构性特征导致配送或巡检机器人在执行全覆盖任务时不可避免地需要对部分道路进行重复访问。为此，工程实践中通常引入中国邮路问题作为解决方案，其核心思想是在保持原有道路结构的前提下，通过最小代价的方式对部分边进行重复，使扩展后的图满足欧拉图条件。具体而言，该方法通过在所有奇度顶点之间计算最短路径，并寻找最小权的匹配方案，确定需要额外经过的道路集合，从而在总体代价最小的条件下构造出可执行的欧拉遍历路径。这一算法框架由Edmonds和Johnson提出，系统性地结合了最短路径搜索与图匹配理论，至今仍是覆盖型路径规划问题的经典解法。154/170欧拉图在智能物流与路径规划中的应用

该理论已被广泛应用于现代智能物流与自动化系统中。无人配送车、城市清扫车和巡检机器人通常首先将作业区域构建为加权无向图，并结合实时交通信息、道路等级、时间窗口和任务优先级动态调整边权重。随后，系统基于中国邮路问题的求解流程生成全覆盖的最优或近似最优巡检路径。针对大规模城市路网，实际系统往往采用分层与分区相结合的策略：将城市划分为多个子区域，在每个区域内分别求解近似欧拉遍历路径，再通过主干道路或调度节点实现区域之间的衔接。这种多级调度机制不仅降低了计算复杂度，也提高了系统对动态环境变化的适应能力。类似的方法还被应用于无人机巡检、电力线路维护和公共设施检查等场景，充分体现了欧拉图理论在现代智能物流与机器人系统中的通用价值。155/170哈密尔顿图在药物分子设计中的应用

在药物分子设计与蛋白质结构预测领域，哈密尔顿图及其路径问题为一类复杂的组合优化任务提供了重要的理论视角。哈密尔顿路径要求在图中经过每个节点且仅经过一次，这一约束在数学结构上与分子骨架的遍历顺序、蛋白质中氨基酸残基的空间排布问题高度同构。在分子建模中，原子或官能团可被抽象为节点，化学键或潜在相互作用被视为边，合理的构建顺序需要确保每个结构单元被恰当引入且不发生冲突。在蛋白质折叠问题中，氨基酸序列需要在三维空间中形成唯一且稳定的构象，其折叠过程可被视为在复杂能量景观中寻找一条满足生化约束的最优遍历路径，使整体自由能达到最低。。156/170哈密尔顿图在药物分子设计中的应用

这类问题在计算复杂度上极具挑战性。哈密尔顿路径问题是经典的NP完全问题，随着节点规模的增加，精确求解在计算上迅速变得不可行。蛋白质分子通常包含数百甚至上千个氨基酸残基，其可能的构象空间呈指数级增长，传统穷举或确定性算法难以适用。为应对这一困难，现代人工智能方法引入了近似建模思想，通过学习方式在高维空间中搜索近似最优解。以DeepMind提出的AlphaFold为代表，该模型在CASP14中实现了接近实验精度的蛋白质结构预测。其核心思想[1]并非直接求解哈密尔顿路径，而是通过注意力机制学习氨基酸残基之间的空间邻接关系和相互作用强度，从而在隐式构象空间中逐步逼近能量最优的结构排列。这一过程可以理解为在巨大的搜索空间中，通过可微分模型对最优遍历结构进行连续近似。[1]JumperJ,EvansR,PritzelA,etal.HighlyaccurateproteinstructurepredictionwithAlphaFold[J].nature,2021,596(7873):583-589.157/170哈密尔顿图在药物分子设计中的应用在药物发现领域，类似的路径建模思想被广泛应用于分子生成任务。模型通常将分子表示为图结构，通过逐步添加原子和化学键的方式生成新分子结构，这一生成过程要求每个原子位点被合理访问一次，同时满足化学价键、空间构型和稳定性等约束。从组合优化角度看，该过程等价于在分子图上构造满足多重约束的遍历路径。IBM的MolFormer以及MIT提出的GeoDiff等模型，均通过深度学习方法刻画分子图的分布特性，在抗生素发现、新冠病毒相关药物筛选等任务中取得了实际成果。这些应用表明，哈密尔顿路径这一源自图论的抽象概念，能够通过现代AI技术转化为解决生命科学核心问题的有效工具。158/170二部图模型在推荐系统与计算广告中的应用

在现代推荐系统与计算广告领域，二部图（又称二分图）是用户—物品关系建模的核心数学结构。二部图的顶点集可以自然地划分为两个不相交的子集，通常分别对应用户集合与物品集合，且边仅存在于跨集合的节点之间。这一结构与现实中的交互行为高度一致，例如“用户购买商品”“用户观看视频”“用户点击广告”等均可被表示为用户节点与物品节点之间的连接关系。通过这种建模方式，推荐系统能够在保持结构简洁性的同时，完整刻画用户行为数据的离散关联特征，为后续的相似度计算与预测任务提供统一表示。

基于二部图的推荐算法可以从图论角度刻画用户与物品之间的潜在关系。传统方法通常依赖于共同邻居思想，即通过分析用户与物品在图中共享的邻接结构来度量相似性。例如，若两个用户连接到大量相同物品，则可推断其兴趣偏好相近；若某个用户与目标物品之间存在多条短路径，也可视为潜在兴趣信号。在此基础上，AA指数、RA指数、Katz指数等指标被用于衡量节点间的关联强度。进一步地，网络嵌入方法将二部图映射到低维连续向量空间，使用户和物品在嵌入空间中的距离或内积反映其匹配程度，这一思路与矩阵分解模型在本质上是等价的，只是从代数视角转化为图结构视角。159/170二部图模型在推荐系统与计算广告中的应用

随着模型复杂度的提升，更进阶的方法开始直接在二部图上进行深度学习建模。其中，图卷积矩阵补全（GC-MC）[2]是典型代表。该类方法不再仅依赖静态相似度计算，而是通过在二部图结构上反复执行邻域聚合操作，动态学习用户与物品的表示。具体而言，用户节点通过聚合其交互过的物品邻居的信息来更新自身表示，物品节点则通过聚合与其交互的用户邻居信息进行更新。通过多层传播，高阶协同信号逐步显现，例如“与该用户相似的其他用户偏好的物品”。最终得到的节点表示用于预测尚未出现的交互关系。这一过程在数学上等价于对二部邻接结构进行多次线性与非线性变换，与图论中的矩阵表示和谱分析思想保持一致。

二部图模型面临的主要挑战来自数据规模与实时性要求。以短视频与电商平台为例，用户规模可达数亿至十亿级，物品规模往往达到千万级甚至更高，交互边数量呈指数式增长。为应对这一问题，工业系统通常采用邻居采样、层级采样和子图训练等策略，将超大规模二部图拆分为可处理的局部结构，并通过小批量训练实现模型的持续更新。此外，二部图理论在计算广告领域中还被用于解决广告分配与竞价问题，将广告商与用户请求建模为二部节点，通过加权匹配或稳定匹配的方式实现收益最大化与用户体验平衡。这类问题往往需要在极短时间内在线求解，体现了二部图匹配理论在实时决策系统中的重要作用。[2]BergR,KipfTN,WellingM.Graphconvolutionalmatrixcompletion[J].arXivpreprintarXiv:1706.02263,2017.10.7*思政案例思政案例中国杰出运筹学家——管梅谷图论在物流领域的应用网神经网络及其应用160/170161/170中国杰出运筹学专家——管梅谷

管梅谷（Mei-KOKWAN），1934年出生，上海人，教授。1957年毕业于华东师范大学数学系。管梅谷教授一直从事运筹学，组合优化与图论方面的研究工作，是国内外知名度很高的学者。2016年被中国运筹学会授予科学技术奖——终身成就奖。早在1960年在国际上最先提出邮递员问题，被国际图论界命名为“中国邮路问题”，载入经典著作中。管梅谷在图论领域有着重要贡献：

提出中国邮递员问题：1960年，管梅谷提出了著名的中国邮递员问题，该问题可表述为邮递员从邮局出发，遍历辖区内所有街道后再返回邮局，要找到一条行走距离最短的路线。这是一个典型的图论问题，与欧拉图和最短路径问题密切相关，可从图论角度进行表述和求解。

奇偶点图上作业法：为解决中国邮递员问题，管梅