《图论及其应用》主要知识点讲义讲解

连通度问题 连通度 B∈E(G)为图G的k边割≌B=k。 图G的边连通度( edge connectivity) x(G)-mn1E为G的边割料 当G为非平凡图 0 当G为平凡图 =使G变成不连通或平凡图所需去掉的最少边数。) 易见,当G为非平凡连通图时,K'=G的最小键的边数 K=K=2 K=1K=2 K=1K=2 K′=3 K=K=0 例。K'=0G平凡或不连通 K’=1心G连通且含割边 K'(Kn=n 当G为简单图时, 1G≡Ky 称图G为k-边连通的(k- edge connected) 至少去掉k条边才能使G变成不连通或平凡图 例如,所有非平凡连通图都是1-边连通的 称顶点子集V为G的顶点割 vertex cut)eG-V不连通 称顶点子集V为G的k(顶)点割 vertex cut)分V为G的顶点割,且|V|=k。 显然,当G为无环连通图时 为G的1-点割sv为G的割点 完全图无点割。 G的连通度 (connectivity) KG-mYoG的点料)26有二不相邻接顶点时 其它 (=使G变成不连通或平凡图所需去掉的最少的顶点数。) 例。当v≥3时,K=1G连通且有1-点割 K(Kv) G的基础简单图为完全图 称图G为k-连通的(k- connected) 至少去掉k个顶点才能使G变成不连通或平凡图。 例如,所有非平凡连通图都是1-连通的。 定理3.1K≤K'≤δ

16 连通度问题 连通度 B  E(G)为图 G 的 k-边割  B = k 。 图 G 的边连通度（edge connectivity)  '( ) min{ ' ' } G E E G G G =    为 的边割 当 为非平凡图 0 当 为平凡图 ( = 使 G 变成不连通或平凡图所需去掉的最少边数。） 易见，当 G 为非平凡连通图时，  = G 的最小键的边数。 例。 = 0  G 平凡或不连通。  = 1  G 连通且含割边。 (Kn)= n-1 ( n > 0 )。 当 G 为简单图时，  =  -1  G  K 。 称 图 G 为 k-边连通的（k-edge connected）  (G)  k  至少去掉 k 条边才能使 G 变成不连通或平凡图。 例如，所有非平凡连通图都是 1-边连通的。 称 顶点子集 V’为 G 的顶点割(vertex cut)  G - V’ 不连通。 称 顶点子集 V’为 G 的 k-(顶)点割(vertex cut)  V’为 G 的顶点割，且  V’  = k 。 显然，当 G 为无环连通图时， v 为 G 的 1-点割  v 为 G 的 割点。 完全图无点割。 G 的连通度(connectivity)     ( ) min G =      V' V' G G - 1 为 的点割 当 有二不相邻接顶点时 其它 （ = 使 G 变成不连通或平凡图所需去掉的最少的顶点数。） 例。当   3 时，  = 1  G 连通且有 1-点割。 (K) = -1 。 (G) =  -1  G 的基础简单图为完全图。 称 图 G 为 k-连通的（k-connected）  (G)  k  至少去掉 k 个顶点才能使 G 变成不连通或平凡图。 例如，所有非平凡连通图都是 1-连通的。 定理 3.1      。 ==2 =1,=2 =1,=2 ==0 =2,=3 ==0

证明:先证K'≤δ:当G为平凡图时,κ'=0≤δ,结论成立:当G为非平凡图时,选取v使d(v 则E=|{v,{引是6的一个边割,因此 K'≤|E≤δ 结论成立。再来证K≤k’: 不妨设G为简单、连通、非完全图,于是K'≤v-2。任取一K'-边割B,及B中任一边e=xy ,在B-e的每边上各取一个端点使之不等于x及y。令这些端点的集合为S。易见 s|≤K-1 记 H G-S (i)若H不连通,则S为G的点割,从而K≤|s|≤'-1 (i)若H连通,则e=xy为H的割边。但,v(H)=v(G)-|S|≥v-(k-1)≥3,因此, x与y必有一个为H的割点,设为x。于是 s∪【x} 为G的点割,故 习题 3.1.1(a)证明:若G是k-边连通的,且k>0,又E为G的任k条边的集合,则 (G-E) (b)对k>0,找出一个k-连通图G以及G的k个顶点的集合S,使o(G-S)>2。3.1.2 证明:若G是k-边连通的,则E≥kv/2 3.1.3(a)证明:若G是简单图且δ≥V-2,则K=δ (b)找出一个简单图G,使得δ=-3且K<δ 3.1.4(a)证明:若G是简单图且δ≥v2,则K=δ (b)找出一个简单图G,使得δ=[(v/2)-1]且’<δ 31.5证明:若G是简单图且δ≥(+k-2)/2(k<v),则G是k连通的。 3.1.6证明:若G是正则简单图,则K=k’。 3.1.7证明:若1,m和n是适合041≤m≤n的整数,则存在一个简单图G,使得K=l,K'= 和δ=n 块 块( b lock) 无割点连通图 显然,当v≥3时, G为块G为无环、2-连通图 例。≥3的块中无割边 定理3.2( Whitney,1932)当v≥3时, G为2-连通图G中任二顶点间则至少被两条内部不相交( interna l ly dis joint)的路连接 (两条路P与Q内部不相交分P与Q无公共内部顶点) 证明:<:显然,G连通,且无1-点割,因此G为2-连通 →:对G中二顶点间的距离d(,)进行归纳。当d(u,V)=1时(即u为G的边),因G为2- 连通,边u是G的非割边(∵κ≥k≥2)。因此,由定理2.3,边u在G的某一圈内,成立。 假设定理对d(,)<k的任二顶点成立,而d(u,v)=k(≥2)。令W为长为k的一(u,v)-路中v 的前一个顶点。显然, d(u w=k- 因此,由归纳假设,存在二内部不相交的 (u,w)-路P及Q。 因G为2-连通,Gw中一定存在一(u,v)- 路P。令x为P在P∪Q中的最后一个顶点。不 失一般性。不妨设x在P上。这时G中有二内部不 17

17 证明：先证   ：当 G 为平凡图时， =0   ，结论成立；当 G 为非平凡图时，选取 v 使 d(v) =  , 则 E’ =     v , v 是 G 的一个边割，因此      结论成立。 再来证    ： 不妨设 G 为简单、连通、非完全图，于是    -2。 任取一 -边割 B，及 B 中任一边 e = xy 。 今，在 B-e 的每边上各取一个端点使之不等于 x 及 y 。令这些端点的集合为 S。易见，  S   -1 。 记 H = G-S 。 (i) 若 H 不连通，则 S 为 G 的点割，从而    S   -1 。 (ii) 若 H 连通，则 e = xy 为 H 的割边。但，(H) = (G)-  S    - ( -1) 3 ，因此， x 与 y 必有一个为 H 的割点，设为 x 。于是 S  {x} 为 G 的点割，故    S  + 1   。  习题 3.1.1 (a) 证明：若 G 是 k-边连通的，且 k > 0 ，又 E’为 G 的任 k 条边的集合，则 （G-E’)  2。 (b) 对 k >0，找出一个 k-连通图 G 以及 G 的 k 个顶点的集合 S，使(G-S)> 2 。 3.1.2 证明：若 G 是 k-边连通的，则   k/2 。 3.1.3 (a) 证明：若 G 是简单图且    -2，则  =  。 (b) 找出一个简单图 G，使得 =-3 且  < 。 3.1.4 (a) 证明：若 G 是简单图且   /2，则  =  。 (b) 找出一个简单图 G，使得  = [（/2）-1] 且  <  。 3.1.5 证明：若 G 是简单图且  ( +k-2)/2 ( k <  )，则 G 是 k 连通的 。 3.1.6 证明：若 G 是正则简单图，则  =  。 3.1.7 证明：若 l，m 和 n 是适合 0<l  m  n 的整数，则存在一个简单图 G，使得  = l， =m 和  =n。 块 块（block）  无割点连通图。 显然，当 v  3 时， G 为块  G 为无环、2-连通图。 例。 v  3 的块中无割边。 定理 3.2 (Whiteney,1932) 当 v  3 时， G 为 2-连通图  G 中任二顶点间则至少被两条内部不相交（internally disjoint）的路连接。 （两条路 P 与 Q 内部不相交  P 与 Q 无公共内部顶点） 证明： ：显然，G 连通，且无 1-点割，因此 G 为 2-连通。  ：对 G 中二顶点间的距离 d(,)进行归纳。 当 d(u,v) = 1 时（即 uv 为 G 的边)， 因 G 为 2- 连通，边 uv 是 G 的非割边( ∵     2)。因此，由定理 2.3 ，边 uv 在 G 的某一 圈内，成立。 假设定理对 d(,)<k 的任二顶点成立，而 d（u，v）= k （ 2）。令 w 为长为 k 的一(u,v)-路中 v 的前一个顶点。显然， d(u,w)= k-1 。 因此，由归纳假设，存在二内部不相交的 （u,w)-路 P 及 Q。 因G为2-连通，G-w 中一定存在一 (u,v)- 路 P’ 。令 x 为 P’在 P  Q 中的最后一个顶点。不 失一般性。不妨设 x 在 P 上。这时 G 中有二内部不 P Q P’ u v w x

相交的(u,v)-路 (P的(u,x)-节)(P的(x,v)-节) # 推论3.2.1当v≥3时, 图G为2-连通的G的任二顶点共圈 证明:由定理3.2,显然 称边e被剖分用连接e的两端点的长2为的新路去替换e 容易验证,当ν≥3时,块的一些边被剖分后仍然保持是块 推论3.2.2G为块G的任二边共圈 证明:→:当ν≤2时,显然成立。当v≥3时,将G的任二边e1和e2分别用新顶点v和v2加 以剖分,得新图G’。它是块,因此为2-连通的。由推论3.2.1知,v1与v共圈。从而e1与e2共圈。 :由条件知,G无环。只要再证G也不会有割点即可:假设u为G的割点。由割点定义知,存 在E(G)的一个2-划分(E1,E2)使边导出子图G[E1]与G[E2]恰只有一公共顶点u。由边导出子图定义知, E;和E2各含一边e和e2,它们有一公共端点u。从而,易见,e和e2不能共圈,矛盾 附录 Menger定理若v≥k+1,则 G为k-连通的G中任二不同顶点至少被k-条内部不相交的路所连接 G为k-边连通的G中任二不同顶点至少被k-条边不重的路所连接 当一个图G有割点时,我们可沿G的割点将G逐步划分为一些不含割点的极大连通子图,它们每个 称为G的块。例如 性质 划分 图G G的块 )G的两个块之间至多有一公共顶点,它一定是G的割点 (2)G的任一割点至少是G的两个块的公共顶点。 3)G是它的块的边不重并 (4)含割点的连通图G中,至少有两个G的块每个恰含G的一个割点 (5)任一图G中,易证,两边之间的共圈关系是一等价关系。它将E(G)划分为一些等价类 (E1,E2,,E。),而每个G[E;]就是G每个的块。 习题 3.2.1证明:一图是边连通的当且仅当任二顶点至少被两条边不重的路所连接。 2.2举例说明:若P为2-连通图G中一给定的u,V)-路,则G不一定有一条与P内部不相交的 (u,v)-路。 32.3证明:若G没有偶圈及孤立点,则G的每个块为K2或奇圈。 4证明:不是块的连通图G中,至少有两个G的块每个恰含G的一个割点 325证明:的块的数目=a+∑(b(v)-1),其中b()是G中含顶点v的块的个数 3.2.6设G为2-连通,而X和Y是V的不相交子集,它们各至少包含二顶点。证明:G包含二不 相交的路P和Q使得 (i)P和Q的起点在X中; (ii)P和Q的终点在Y中 (i)P和Q的内部顶点都不在X∪Y中 2.7叙述求图的块的好算法

18 相交的(u,v)-路： ( P 的(u,x)-节)( P’的(x,v)-节) Quv。  推论 3.2.1 当  3 时， 图 G 为 2-连通的  G 的任二顶点共圈。 证明：由定理 3.2 ，显然。  称边 e 被剖分  用连接 e 的两端点的长 2 为的新路去替换 e。 容易验证，当  3 时，块的一些边被剖分后仍然保持是块。 推论 3.2.2 G 为块  G 的任二边共圈。 证明： ：当  2 时，显然成立。当  3 时，将 G 的任二边 e1 和 e2 分别用新顶点 v1 和 v2 加 以剖分，得新图 G’ 。它是块，因此为 2-连通的。由推论 3.2.1 知，v1 与 v2 共圈。从而 e1 与 e2 共圈。  ：由条件知，G 无环。只要再证 G 也不会有割点即可：假设 u 为 G 的割点。由割点定义知，存 在 E(G)的一个 2-划分（E1 ,E2 )使边导出子图 G[E1]与 G[E2]恰只有一公共顶点 u。由边导出子图定义知， E1 和 E2 各含一边 e1 和 e2 ，它们有一公共端点 u。从而，易见， e1 和 e2 不能共圈，矛盾。  附录 Menger 定理 若  k+1，则 G 为 k-连通的  G 中任二不同顶点至少被 k-条内部不相交的路所连接。 G 为 k-边连通的  G 中任二不同顶点至少被 k-条边不重的路所连接。 当一个图 G 有割点时，我们可沿 G 的割点将 G 逐步划分为一些不含割点的极大连通子图，它们每个 称为 G 的块。例如 性质 (1) G 的两个块之间至多有一公共顶点，它一定是 G 的割点。 (2) G 的任一割点至少是 G 的两个块的公共顶点。 (3) G 是它的块的边不重并。 (4) 含割点的连通图 G 中，至少有两个 G 的块每个恰含 G 的一个割点。 (5)* 任一图 G 中，易证，两边之间的共圈关系是一等价关系。它将 E(G)划分为一些等价类 (E1 ,E2 ,...,Ep )，而每个 G[Ei ]就是 G 每个的块。 习题 3.2.1 证明：一图是边连通的当且仅当任二顶点至少被两条边不重的路所连接。 3.2.2 举例说明：若 P 为 2-连通图 G 中一给定的(u,v)-路，则 G 不一定有一条与 P 内部不相交的 （u,v)-路。 3.2.3 证明：若 G 没有偶圈及孤立点，则 G 的每个块为 K2 或奇圈。 3.2.4 证明：不是块的连通图 G 中，至少有两个 G 的块每个恰含 G 的一个割点。 3.2.5 证明：G 的块的数目 =  + −  (b(v) ) v V 1 ，其中 b(v)是 G 中含顶点 v 的块的个数。 3.2.6 设 G 为 2-连通，而 X 和 Y 是 V 的不相交子集，它们各至少包含二顶点。证明：G 包含二不 相交的路 P 和 Q 使得 (i) P 和 Q 的起点在 X 中； (ii) P 和 Q 的终点在 Y 中； (iii) P 和 Q 的内部顶点都不在 X  Y 中。 3.2.7 叙述求图的块的好算法。  划分 图G G的块

可靠通信网的建设 κ及κ′越大越可靠(造价越贵:δ≥K'≥K) 问题已给赋权图G及正整数k,求G的最小权k-连通(k-边连通)生成子图。 解当k=1, optimal tree( connector prob.) 当k>1, NP-hard prob 当每边权=1且G为任意图时,问题变成求边数最少的k-连通生成子图。(仍然是 NP-hard prob. 当G≡Kv且每边权为1时, Harary(1962)作出边数最少的G的k连通(k-边连通)生成子 图Hky(边数={kv2})(∴有好算法。) Hamilton圈与 Euler环游 Euler环游 环游(tour)通过图中每边至少一次的闭途径 uler环游分通过图中每边恰一次的闭途径 Euler迹通过图中每边的迹 通过图中每边恰一次的途径。(可“一笔画成”。) uler图包含 Euler环游的图 包含 Euler闭迹的图 本身为闭迹的图 定理4.1设G为非空连通图,则 G为 Euler图分G中无度为奇数的顶点 证明:→:令C=we1u1e2ul2.eu(u=u)为G的一 Euler环游,起点为u。则对 任一顶点v≠u,当v每次作为内部顶点出现于c时,c上有二边与v相关联。由于c上包含了G的 所有边且不重复,因此d(v)=偶数。类似地,d(u)=偶数。 c:反证,假设存在非空连通图,它的每个顶点的度都是偶数,但却不是 Euler图。在这种图中 选取G使其边数最少。由于δ(G)≥2,G包含圈。令C为G中的最长闭迹。由假设,C不会是 Euler 环游。因此 G-E(C) 中一定有一分支G’使ε(G)>0。由于C本身为 Euler图,(由定理的必要条件知)C中每个顶点的 度都是偶数,因此G中无度为奇数的顶点。但 E(G)<(G) 由G的选择知,G中含一 Euler环游C。又,由于G连通,c与C至少有一公共顶点,设为v, 且不妨设它同时为它们的起点。于是 是G的一闭迹,其长大于C的长,矛盾 附录定理4.1←:之新证法(J.G.T.Fal1986) ε进行归纳。当v=2时,显然成立。只 要再考虑v≥3情形。假设对ε<q成立,而ε(G)=q。选取顶点,使v有二不同顶点u及w与 它相邻。考虑图

19 可靠通信网的建设  及越大越可靠（造价越贵：     ） 问题 已给赋权图 G 及正整数 k，求 G 的最小权 k-连通（k-边连通）生成子图。 解 当 k = 1 , optimal tree (connector prob.) 当 k > 1 , NP-hard prob. 当每边权 1 且 G 为任意图时，问题变成求边数最少的 k-连通生成子图。( 仍然是 NP-hard prob.) 当 G  K 且每边权为 1 时，Harary (1962)作出边数最少的 G 的 k-连通（k-边连通）生成子 图 Hk,（边数={k/2}) （∴有好算法。） Hamilton 圈与 Euler 环游 Euler 环游 环游（tour） 通过图中每边至少一次的闭途径。 Euler 环游  通过图中每边恰一次的闭途径。 Euler 迹  通过图中每边的迹 。  通过图中每边恰一次的途径。 （可“一笔画成”。） Euler 图  包含 Euler 环游的图  包含 Euler 闭迹的图。  本身为闭迹的图。 定理 4.1 设 G 为非空连通图，则 G 为 Euler 图  G 中无度为奇数的顶点。 证明： ：令 C = u0 e1 u1 e2 u2 ...e u (u = u0 )为 G 的一 Euler 环游 ，起点为 u0 。则对 任一顶点 v  u0 ，当 v 每次作为内部顶点出现于 C 时，C 上有二边与 v 相关联。由于 C 上包含了 G 的 所有边且不重复，因此 d(v)=偶数。类似地，d(u0)=偶数。  ：反证，假设存在非空连通图，它的每个顶点的度都是偶数，但却不是 Euler 图 。在这种图中 选取 G 使其边数最少。 由于 (G)  2，G 包含圈。令 C 为 G 中的最长闭迹。由假设，C 不会是 Euler 环游。因此 G - E(C) 中一定有一分支 G’ 使(G’)>0。由于 C 本身为 Euler 图，（由定理的必要条件知）C 中每个顶点的 度都是偶数，因此 G’中无度为奇数的顶点。但 (G’) < (G) 由 G 的选择知，G’中含一 Euler 环游 C’。 又，由于 G 连通，C 与 C’至少有一公共顶点，设为 v， 且不妨设它同时为它们的起点。于是， CC’ 是 G 的一闭迹，其长大于 C 的长，矛盾。  附录 定理 4.1 :之新证法（J.G.T.Fall 1986)： 对 进行归纳。当 =2 时，显然成立。只 要再考虑  3 情形。 假设对  < q 成立，而 (G)=q 。 选取顶点 v ，使 v 有二不同顶点 u 及 w 与 它相邻 。考虑图

H=(G-uv, vw])+uw (uw为一新加边一一不管G中是否有以u,w 为两端点的边)显然, 0(H)≤2 d(x)=偶数 (i)当o(H)=1时,由归纳假设,H中有 Euler环游C’。把c中 边ww代之以路uw,即得G的 Euler环游 (i)当o(H)=2时,由归纳假设,H的二分支各有其 Euler环游C C 及C2。不妨设w在Q2中。将C2中的边ww代之以迹 uvC,vw,即得G 的 Euler环游 推论4.1若G连通,则 G有一 Euler迹分G中至多有二度为奇数顶点。 证明:→:类似定理4.1中→:的证明。 ←:若G中无度为奇数顶点,则由定理4.1,G中有 Euler迹。否则,G中恰有二度 为奇数顶点,设为u,v。考虑图 G+ 其中e为连接u与ⅴ的新边。显然,G+e中无度为奇数顶点,从而包含一 Euler环游 C= Vo e, v, e2 v2..ee+lve+ 其中,v+1=vo=u,v;=v。易见 e2V2,,,eg+1VE+1 就是G的 Euler迹。 习题 4.1.1若可能,画出一个ν为偶数,而ε为奇数的 Euler图。否则说明理由。 4.1.2证明:若G无奇点,则G的每个块也是Euer图 4.1.3若G无奇点,则存在边不重的圈C1,C2,,C使得 E(G)=E(C1)∪E(C) E(C) 4.1.4若连通图G有2k>0个奇点,则G中存在k条边不重的迹Q,Q2,,Q使得 EG=E(Q E(Q 4.1.5设G为非平凡 Euler图,且v∈V。证明:G中任一条以v为起点的迹都能延伸成一 Euler 环游当且仅当Gv为林。(0.0re) 中国邮递员问题 问题在一赋权图G中,求一最小权环游(即最优环游)。 当G为 Euler图时,其任一 Euler环游都是最优环游,此时有求最优环游的好算法,如 Fleury算法(“过河拆桥,尽量不走独木桥“) 任取一顶点v,令 若迹W=vev1e;vi已取定,选e;∈E\e,,e]使 (i)e与v相关联 (i)除非无奈,选e;使它不是 G:= G-e 的割边 3.若2.不能再进行下去,停止。 定理4.7若G为εuler图,则由 Fleury算法求得的G中的迹,是G的一 Euler环游。 证明:令W,=ve1v1 en Vn Fleury算法求得的G中的迹,显然 dGn(v,)=0

20 H = (G - {uv,vw})+uw （uw 为一新加边——不管 G 中是否有以 u，w 为两端点的边） 显然， (H)  2 , (H) = q-1 , dH(x) = 偶数  x  V 。 (i) 当(H)=1 时，由归纳假设，H 中有 Euler 环游 C’。把 C’ 中 一边 uw 代之以路 uvw，即得 G 的 Euler 环游 。 (ii) 当(H)=2 时，由归纳假设，H 的二分支各有其 Euler 环游 C1 及 C2 。不妨设 uw 在 C2 中。将 C2 中的边 uw 代之以迹 uvC1vw，即得 G 的 Euler 环游 。  推论 4.1 若 G 连通，则 G 有一 Euler 迹  G 中至多有二度为奇数顶点。 证明： ： 类似定理 4.1 中 ：的证明。  ： 若 G 中无度为奇数顶点，则由定理 4.1 ，G 中有 Euler 迹。否则，G 中恰有二度 为奇数顶点，设为 u，v 。 考虑图 G + e ， 其中 e 为连接 u 与 v 的新边。显然，G+e 中 无度为奇数顶点，从而包含一 Euler 环游 C = v0 e1 v1 e2 v2 ...e+v+ ， 其中，v+ = v0 =u ，v1 =v 。易见 v1 e2 v2 ...e+v+ 就是 G 的 Euler 迹。  习题 4.1.1 若可能，画出一个 为偶数，而 为奇数的 Euler 图。否则说明理由。 4.1.2 证明：若 G 无奇点，则 G 的每个块也是 Euler 图 。 4.1.3 若 G 无奇点，则存在边不重的圈 C1 ,C2 ,...,Cm 使得 E(G) = E(C1)  E(C2) ... E(Cm)。 4.1.4 若连通图 G 有 2k >0 个奇点，则 G 中存在 k 条边不重的迹 Q1 ,Q2 ,...,Qk 使得 E(G) = E(Q1)  E(Q2) ... E(Qk)。 4.1.5 设 G 为非平凡 Euler 图 ，且 v  V。证明：G 中任一条 以 v 为起点的迹 都能延伸成一 Euler 环游 当且仅当 G-v 为林。 （O.Ore） 中国邮递员问题 问题 在一赋权图 G 中，求一最小权环游 （即最优环游）。 当 G 为 Euler 图时，其任一 Euler 环游 都是最优环游，此时有求最优环游的好算法，如 Fleury 算法 （“过河拆桥，尽量不走独木桥“） 任取一顶点 v0 ，令 w0 = v0 。 若迹 Wi =v0 e1 v1 ...ei v i 已取定，选 ei+1  E\{e1 ,..., ei}使 (i) ei+1 与 v i 相关联； (ii) 除非无奈，选 ei+1 使它不是 Gi = G-{e1 ,..., ei} 的割边。 3. 若 2. 不能再进行下去，停止。 定理 4.7 若 G 为 Euler 图 ，则由 Fleury 算法求得的 G 中的迹，是 G 的一 Euler 环游 。 证明：令 Wn =v0 e1 v1 ...en vn Fleury 算法求得的 G 中的迹， 显然 dGn (vn ) = 0 ,  vn = v0 。 u w v C' v u w C1 C2