离散件基本图类及算法

离散件基本图类及算法第一页，共一百三十二页，编辑于2023年，星期日度为1的结点称为树的叶，度大于1的结点称为树的枝点。只含一个结点的树称为平凡树。v1v2v3v4v6v5董事会总经理生产科销售科维修科第二页，共一百三十二页，编辑于2023年，星期日如上面的组织机构图所示，在树中有一类称为根树的有向树。在数据结构、数据库原理、编译技术等课程中都要谈到根树，特别是2叉树。下面是根树的两个例子。外向3叉树内向2叉树第三页，共一百三十二页，编辑于2023年，星期日2。树的等价定义：设T是n个结点m条边的非平凡图，则以下6条等价：①连通无回路。②无回路，m=n-1。③连通，m=n-1。④无回路，任增加一条新边后只增加一条回路。⑤连通，但任删一条边后不再连通。⑥任何两结点间只有一条道路。证明要点：采用循环证法。第四页，共一百三十二页，编辑于2023年，星期日①②

(连通无回路无回路，m=n-1)对图的阶数n归纳。无回路必有1度结点v，则T-v满足归纳假设，即m-1=(n-1)-1,也就是m=n-1。第五页，共一百三十二页，编辑于2023年，星期日②③

(无回路，m=n-1连通，m=n-1。)设图有k支，每支是树应满足关系式，从而全部支合起来为m=n-k，对照已知条件必然k=1，即证得连通。第六页，共一百三十二页，编辑于2023年，星期日③④

(连通，m=n-1无回路，任增加一条新边后只增加一条回路。)对图的阶数n归纳。由m=n-1图中必有1度结点v，则T-v满足归纳假设无回路，从而T也无回路，任增加一条新边后只增加一条回路。第七页，共一百三十二页，编辑于2023年，星期日④⑤(无回路，任增加一条新边后只增加一条回路。连通，但任删一条边后不再连通。)如果不连通，则在两支间增加一条边不会增加任何回路；反之，如果连通且删去一边后仍然连通，T必有回路，产生矛盾。第八页，共一百三十二页，编辑于2023年，星期日⑤⑥(连通，但任删一条边后不再连通。任何两结点间只有一条道路。)如果结点u和v之间有两条不同的道路，则构成回路，删去回路中任一边后仍然连通，产生矛盾。第九页，共一百三十二页，编辑于2023年，星期日⑥①(任何两结点间只有一条道路连通无回路)连通显然，由于任何两结点间只有一条道路，所以无回路。第十页，共一百三十二页，编辑于2023年，星期日2。树的等价定义：设T是n个结点m条边的非平凡图，则以下6条等价：①连通无回路。②无回路，m=n-1。③连通，m=n-1。④无回路，任增加一条新边后只增加一条回路。⑤连通，但任删一条边后不再连通。⑥任何两结点间只有一条道路。第十一页，共一百三十二页，编辑于2023年，星期日从上述6条可知，树中任何一边都是割边，任何枝点都是割点。

推论非平凡树至少有2个叶。

证明要点：设T有n个结点t个叶，由图论基本定理及m=n-1可得

t+2(n-t)2(n-1)，也就是t2。

第十二页，共一百三十二页，编辑于2023年，星期日二、连通图的生成树1。如果连通图G的生成子图T是树，则称T是G的生成树。2。任何连通图都至少有一个生成树。通过反复去掉图中每条回路的一边，即可得到生成树。

n阶连通图至少有n-1条边。第十三页，共一百三十二页，编辑于2023年，星期日例：连通图及其一个生成树的产生过程。v1v6v4v5v3v2图G第十四页，共一百三十二页，编辑于2023年，星期日例：连通图及其一个生成树的产生过程。v1v6v4v5v3v2图G第十五页，共一百三十二页，编辑于2023年，星期日例：连通图及其一个生成树的产生过程。v1v6v4v5v3v2图G第十六页，共一百三十二页，编辑于2023年，星期日例：连通图及其一个生成树的产生过程。v1v6v4v5v3v2图G第十七页，共一百三十二页，编辑于2023年，星期日例：连通图及其一个生成树的产生过程。v1v6v4v5v3v2图G第十八页，共一百三十二页，编辑于2023年，星期日例：连通图及其一个生成树的产生过程。v1v6v4v5v3v2图G第十九页，共一百三十二页，编辑于2023年，星期日例：连通图及其一个生成树的产生过程。v1v6v4v5v3v2图G第二十页，共一百三十二页，编辑于2023年，星期日例：连通图及其一个生成树的产生过程。v1v6v4v5v3v2图G第二十一页，共一百三十二页，编辑于2023年，星期日例：连通图及其一个生成树的产生过程。v1v6v4v5v3v2图G第二十二页，共一百三十二页，编辑于2023年，星期日例：连通图及其一个生成树的产生过程。v1v6v4v5v3v2图G第二十三页，共一百三十二页，编辑于2023年，星期日例：连通图及其一个生成树的产生过程。v1v6v4v5v3v2图G第二十四页，共一百三十二页，编辑于2023年，星期日例：连通图及其一个生成树的产生过程。v1v6v4v5v3v2图G第二十五页，共一百三十二页，编辑于2023年，星期日3。设T是连通图G的一个生成树，e是G的一条边。如果e在T中，则称之为树边，否则称之为树补边。

(n,m)连通图有n-1个树边,m-n+1个树补边。v1v6v4v5v3v2图G第二十六页，共一百三十二页，编辑于2023年，星期日4。定理：设T是连通图G的一个生成树，则G的任何边割集必至少含一条树边；G的任何回路必至少含一条树补边。证明要点：如果一个边割集F不含任何树边。则G-F仍有生成树。如果一个回路C不含任何树补边，则T中含有回路C。v1v6v4v5v3v2图G第二十七页，共一百三十二页，编辑于2023年，星期日

三、最小生成树

1。问题：在带边权的连通图G中，找一个生成树，使得在G的全部生成树中其边权之和W(T)为最小。adcgefhb2123332214233第二十八页，共一百三十二页，编辑于2023年，星期日2。求最小生成树的Kruskal算法要点：输入：n阶连通权图G输出：最小生成树T步骤要点：①把G的边按权不减方式排成序列。②按从左到右顺序依次扫描序列，如果当前扫描边e与已选出的树边不构成回路，则将e加入树边中，否则扫描下一边。③如果已经选出n-1条边，算法结束。第二十九页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：fhb2123332214233第三十页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，

fhb2123332214233第三十一页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，

fhb2123332214233第三十二页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，

fhb2123332214233第三十三页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，egfhb2123332214233第三十四页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第三十五页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第三十六页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第三十七页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第三十八页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第三十九页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第四十页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第四十一页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第四十二页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第四十三页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第四十四页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第四十五页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第四十六页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第四十七页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第四十八页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第四十九页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第五十页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第五十一页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：fhb2123332214233第五十二页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：{ab，fh，ac，ch，fe，bd，hg}

fhb2123332214233第五十三页，共一百三十二页，编辑于2023年，星期日adcge例：下面权图产生的一个最小生成树。边按序排列：ab，fh，ac，bc，ch，cf，fe，ae，bd，cd，ed，hg，eg按算法构造的生成树边集为：{ab，fh，ac，ch，fe，bd，hg}生成树T的权W(T)=14。fhb2123332214233第五十四页，共一百三十二页，编辑于2023年，星期日从算法可知，无回路且含n-1条边，因此一定得到生成树，且由选边的顺序决定它是最小的。一个连通权图的最小生成树可以不唯一。

第五十五页，共一百三十二页，编辑于2023年，星期日作业：习题10.11、2、4、8（吴子华）Or

习题11.11、2习题11.21、2（冯伟森）附加题：

1。我们把无回路图称为林，林的阶数和边数应满足什么关系式？

2。如果n阶连通简单图G恰有n条边，那么，G最少有多少个生成树？最多有多少个生成树？第五十六页，共一百三十二页，编辑于2023年，星期日

一、平面图的概念

1。定义如果图G存在一种图形表示，使其各边不在结点之外交叉，则称G是一个平面图。

例：下面的图是平面图。第12章平面图及其应用第五十七页，共一百三十二页，编辑于2023年，星期日

v1v6v4v5v2v3v7注意：图中边v4v5画在外面，则不与v2v6交叉。第五十八页，共一百三十二页，编辑于2023年，星期日例：阶数小于5的完全图都是平面图K1K2K3K4第五十九页，共一百三十二页，编辑于2023年，星期日

例：完全二部图K2，3是平面图。第六十页，共一百三十二页，编辑于2023年，星期日例：完全图K5是典型的非平面图。第六十一页，共一百三十二页，编辑于2023年，星期日

例：完全二部图K3，3是典型的非平面图。第六十二页，共一百三十二页，编辑于2023年，星期日2。图的面：由边围成的封闭区域、且其内部不再包含边数更少的封闭区域的区域。

例：下图中共有F1、F2、F3、F4四个面。F4F1F3F2第六十三页，共一百三十二页，编辑于2023年，星期日

每个平面图中有且仅有1个无限区域的面，称为外部面。其它的面称为内部面。围住面的边构成面的边界。①面的度：设F是图的面，令d(F)=围成F的边数，但割边算2，称之为面F的面度。F4F1F3F2第六十四页，共一百三十二页，编辑于2023年，星期日

例：下面的平面图中4个面的度分别是：

d(F1)=4，d(F2)=3，

d(F3)=3，d(F4)=6。F4F1F3F2第六十五页，共一百三十二页，编辑于2023年，星期日②定理任何平面图必满足d(F)=2m，其中m是图的边数。

证明要点：平面图中每条边要么是两个面的公共边，要么只是一个面的边（即为图的割边），即每条边都贡献面度2。F4F1F3F2第六十六页，共一百三十二页，编辑于2023年，星期日二、平面图的欧拉公式

1。定理设G是n个结点、m条边、f个面的连通平面图，则

n-m+f=2。证明要点：设T是G的一个生成树，T是平面图且含n个结点、n-1条边和一个外部面，满足

n-（n-1）+1=2根据树的性质：“无回路，任增加一条新边后只增加一条回路”，依次把m-n+1条树补边加入T中，增加了m-n+1个面，即共有m-n+2个面。第六十七页，共一百三十二页，编辑于2023年，星期日一个图是平面图当且仅当它的每个支都是平面图。注意，平行边和环都不影响图的平面性，只需考虑简单图的平面性就行了。2。推论1：设G是n个结点、m条边、f个面的简单连通平面图，则m3(n-2)。

证明要点:因为G是简单图，其每个面的度至少是3，因此

3f2m，代入欧拉公式后整理即得结论。3。推论2：在简单连通平面图中至少有1个度不大于5的结点。证明要点：阶小于6时明显成立。一般情况下，若5成立，将导致2m6n，产生矛盾。第六十八页，共一百三十二页，编辑于2023年，星期日4。图的围长：图中最短圈的长度称为该图的围长，并记为g（当图中无圈时，规定g）推论3：设G是一个g2的（n,m）连通平面图，则m证明要点：由d(F)g,2m=

d(F)gf,代入n-m+1=2可得。g(n-2)g-2第六十九页，共一百三十二页，编辑于2023年，星期日

三、证明K5和K3，3不是平面图1、对于K5，它是（5，10）图，其回路长度至少为3，不满足m3(n-2)，因此K5不是平面图。

2、对于K3，3，它是（6，9）图，g=4，不满足推论3，因此K3，3不是平面图。

第七十页，共一百三十二页，编辑于2023年，星期日四、判别平面图的Kuratowski定理

1。图的细分：在图的边上设置若干2度点后得到图称为原图的细分图。第七十一页，共一百三十二页，编辑于2023年，星期日例：下面是图G及其一个细分图G1图G图G1细分第七十二页，共一百三十二页，编辑于2023年，星期日2。图的细分不改变图的平面特性。即它们同为平面图或同为非平面图。3。Kuratowski定理：图G是平面图当且仅当G没有任何与K5或K3，3的细分图同构的子图。

证明略。可参考教材末页文献[3]、[12]。第七十三页，共一百三十二页，编辑于2023年，星期日例:用库氏定理判定下图不是平面图第七十四页，共一百三十二页，编辑于2023年，星期日例:用库氏定理判定下图不是平面图第七十五页，共一百三十二页，编辑于2023年，星期日例:用库氏定理判定下图不是平面图第七十六页，共一百三十二页，编辑于2023年，星期日例:用库氏定理判定下图不是平面图第七十七页，共一百三十二页，编辑于2023年，星期日五、对偶图

1。设G=(V,E)是含有面集V*={F1，F2，...，Ft}的平面图，定义图G*=(V*，E*）使对任何eE且e是面Fi和Fj的边界，都有e*=FiFjE*与之一一对应，则称G*为G的对偶图。

第七十八页，共一百三十二页，编辑于2023年，星期日例：下面是图G及其对偶图G*的示例。其中黑点代表对偶图的结点，红边是对偶图的边。第七十九页，共一百三十二页，编辑于2023年，星期日2。对偶图的性质①对偶图G*是连通图。②图G和对偶图G*同是平面图。③如果图G是连通图，则(G*)*G.④G的边割集对应G*的圈，G*的边割集对应G的圈。第八十页，共一百三十二页，编辑于2023年，星期日3。如果G*G，则称G是自对偶图。 例如：第八十一页，共一百三十二页，编辑于2023年，星期日对偶图的应用:地图着色问题简介第八十二页，共一百三十二页，编辑于2023年，星期日

作业：习题10。42、3、5、8（吴子华）or习题12.21、2、5；习题12.41（冯伟森）思考题：1.欧拉公式及其推论是否适用于非连通平面图？如果不能，如何稍加改进使其适用于非连通平面图？2.用库氏定理证明Peterson图不是平面图。第八十三页，共一百三十二页，编辑于2023年，星期日第13章欧拉图问题的提出：Gonigberg7桥问题第八十四页，共一百三十二页，编辑于2023年，星期日一、基本概念

1。如果图G=(V,E)存在一条包含全部边的简单回路,则称G是欧拉图。这条回路称为欧拉回路。

2。如果存在一条包含图G=(V,E)全部边的简单道路,则称之为欧拉道路。上面定义中加上“有向”二字，就可用于有向图。第八十五页，共一百三十二页，编辑于2023年，星期日二、判定无向欧拉图定理

1。定理

G是欧拉图当且仅当G连通且其点度都是偶数。证明要点：(“”)当G是欧拉图时，存在欧拉回路，因而连通。每个结点在回路中出现一次，就用去两条边，所以每个结点的度是偶数。(“”)反过来，当G连通且其点度都是偶数时，设C是一条包含边数最多的简单回路，如果C不是欧拉回路，则必有边不在C中，由此可以构造包含边数更多的简单回路，引起矛盾。（示意图演示）第八十六页，共一百三十二页，编辑于2023年，星期日2。定理连通图G存在欧拉道路当且仅当G最多有2个奇数度结点。

证明要点：

(“”)当连通图G存在欧拉道路时，最多有道路的起点和终点是奇数度点；(“”)反之，如果u、v是两个奇数度结点，在G中增加新边uv使之变成欧拉图，再由导出的欧拉回路中去掉边uv就得到欧拉道路。第八十七页，共一百三十二页，编辑于2023年，星期日由上面2个定理可知，Gonigberg7桥问题不仅无解，甚至连欧拉道路都不存在。第八十八页，共一百三十二页，编辑于2023年，星期日三、判定有向欧拉图定理

1。定理

G是有向欧拉图当且仅当G连通且其每个点的出度等于入度。证明过程类似于无向图情形，只要注意有向欧拉回路每次进入一个结点再离开它，要用去一条入边和一条出边就行了。第八十九页，共一百三十二页，编辑于2023年，星期日2。定理连通图G存在有向欧拉道路当且仅当G最多有2个结点的入度不等于出度，且其中一个结点的出度比入度多1，另一个结点的出度比入度少1。证明过程与无向图情形类似，只要注意有向欧拉道路的起点的出度比入度多1

，终点的出度比入度少1就行了。第九十页，共一百三十二页，编辑于2023年，星期日四、由欧拉图构造欧拉回路算法记号：G–C表示从图G中删去图C中的边后得到的图。

输入：欧拉图G

输出：欧拉回路C

步骤：1。初始化C=。任选G中结点u为当前结点t，即t=u。2。如果G–C是零图，输出C，算法结束。3。如果G–C中与t关联的边e=tv不是G–C的割边，则C=C+e，t=v，转2；4。如果G–C中与t关联的边e=tv都是G–C的割边，则C=C+e，t=v，转2。第九十一页，共一百三十二页，编辑于2023年，星期日v1v2v7v5v6C=例：下面给出构造欧拉回路的算法过程演示。v3v8v4第九十二页，共一百三十二页，编辑于2023年，星期日v1v2v7v5v6C=v1v5例：下面给出构造欧拉回路的算法过程演示。v3v8v4第九十三页，共一百三十二页，编辑于2023年，星期日v1v2v7v5v6C=v1v5v7例：下面给出构造欧拉回路的算法过程演示。v3v8v4第九十四页，共一百三十二页，编辑于2023年，星期日v1v2v7v5v6C=v1v5v7v4例：下面给出构造欧拉回路的算法过程演示。v3v8v4第九十五页，共一百三十二页，编辑于2023年，星期日v1v2v7v5v6C=v1v5v7v4v3例：下面给出构造欧拉回路的算法过程演示。v3v8v4第九十六页，共一百三十二页，编辑于2023年，星期日v1v2v7v5v6C=v1v5v7v4v3v2例：下面给出构造欧拉回路的算法过程演示。v3v8v4第九十七页，共一百三十二页，编辑于2023年，星期日v1v2v7v5v6C=v1v5v7v4v3v2v4例：下面给出构造欧拉回路的算法过程演示。v3v8v4第九十八页，共一百三十二页，编辑于2023年，星期日v1v2v7v5v6C=v1v5v7v4v3v2v4v8例：下面给出构造欧拉回路的算法过程演示。v3v8v4第九十九页，共一百三十二页，编辑于2023年，星期日v1v2v7v5v6C=v1v5v7v4v3v2v4v8v7例：下面给出构造欧拉回路的算法过程演示。v3v8v4第一百页，共一百三十二页，编辑于2023年，星期日v1v2v7v5v6C=v1v5v7v4v3v2v4v8v7v6例：下面给出构造欧拉回路的算法过程演示。v3v8v4第一百零一页，共一百三十二页，编辑于2023年，星期日v1v2v7v5v6C=v1v5v7v4v3v2v4v8v7v6v5例：下面给出构造欧拉回路的算法过程演示。v3v8v4第一百零二页，共一百三十二页，编辑于2023年，星期日v1v2v7v5v6C=v1v5v7v4v3v2v4v8v7v6v5v2例：下面给出构造欧拉回路的算法过程演示。v3v8v4第一百零三页，共一百三十二页，编辑于2023年，星期日v1v2v7v5v6C=v1v5v7v4v3v2v4v8v7v6v5v2v1例：下面给出构造欧拉回路的算法过程演示。v3v8v4第一百零四页，共一百三十二页，编辑于2023年，星期日应用：模数转换—磁鼓设计问题简介abdc0000000011111111第一百零五页，共一百三十二页，编辑于2023年，星期日思考题：如果图中只存在欧拉道路，如何利用欧拉回路算法去找它？即考虑一般的“一笔画”问题的解法。第一百零六页，共一百三十二页，编辑于2023年，星期日adcgefhb4213241311323五、中国邮递员问题1、问题的提出在一个带边权的简单连通图中，构造一条包括全部边的回路（边可能重复），并使回路的权和最小。

11第一百零七页，共一百三十二页，编辑于2023年，星期日2、无向图中中国邮递员问题的解法如果G中无奇度结点，则欧拉回路就是解。如果G中有奇度结点，为v1,v2,…,v2k，计算每对结点间最短道路（距离）。在这些道路中选出k条道路P1,P2,…,Pk，使满足:彼此无共同的起点或终点;P1+P2+…+Pk最短.在G中复制P1,P2,…,Pk的边；在新图中构造欧拉回路。五、中国邮递员问题第一百零八页，共一百三十二页，编辑于2023年，星期日例：在下图中有4个奇数度点(红点),两两之间最短道路长度为: Pa-c=3(abc),Pa-e=3(abe) Pa-h=5(abcfh),Pc-e=2(cbe), Pe-h=3(egh),Pc-h=2(cfh),可见,Pa-e和Pc-h满足最小性要求.复制abe和cfh中的边,得到一个欧拉图,再由欧拉回路算法,即得到问题的解.adcgefhb421324131132311第一百零九页，共一百三十二页，编辑于2023年，星期日作业：习题10.52、5、6（吴子华）or习题13.12、5、6（冯伟森）证明：连通图G是平面欧拉图当且仅当其对偶图是平面二部图。第一百一十页，共一百三十二页，编辑于2023年，星期日第13.2节哈密顿图问题的提出：在一个正12面体上沿棱找一条通过每个顶点的圈。第一百一十一页，共一百三十二页，编辑于2023年，星期日第六节哈密顿图问题的提出：在一个正12面体上沿棱找一条通过每个顶点的圈。第一百一十二页，共一百三十二页，编辑于2023年，星期日一、基本概念

1。如果图G=(V,E)存在一条包含全部结点的基本回路（或圈）,则称G是哈密顿图。这条回路称为哈密顿圈。

2。如果存在一条包含图G=(V,E)全部结点的基本道路,则称之为哈密顿道路。由定义，只需考虑简单图的哈密顿性。第一百一十三页，共一百三十二页，编辑于2023年，星期日二、判别哈密顿图的必要条件

定理如果图G=(V,E)是哈密顿图，则对任何非空SV，(G–S)S。

证明要点：因为G=(V,E)是哈密顿图，必存在哈密顿圈C，对于这个C，(C–S)S自然成立，从而(G–S)S。第一百一十四页，共一百三十二页，编辑于2023年，星期日

注意：这只是一个必要条件而非充分条件。例：可以用必要条件判断下图不是哈密顿图。只要令S={a，b，c，d，e}就行了。abcde第一百一十五页，共一百三十二页，编辑于2023年，星期日三、判别哈密顿图的充分条件定理如果n阶简单图G=(V,E)的任何两个结点u和v，都使d(u)+d(v)n-1成立，则G存在哈密顿道路。证明要点：必须证明如下几点：从给定条件看，G必定连通；设L=v1v2…vk是G中一条最长的基本道路。如果kn，则能由L构造一个长度为k的圈C；由圈C可构造比L更长的基本道路，引起矛盾。第一百一十六页，共一百三十二页，编辑于2023年，星期日由最长的基本道路L=v1v2…vk构造长度为k的圈：如果v1vkE，圈就存在了。如果v1vkE，由于kn，且v1和vk的邻接结点都在这条道路上，因此这条道路上必有vi和vi+1

使得v1vi+1E，vivk

E，也得到圈。v1v2v3v4vivi+1vk-1vk第一百一十七页，共一百三十二页，编辑于2023年，星期日由圈C可构造比L更长的基本道路：由于kn，必有结点u与圈上结点邻接，从而构造更长的基本道路。v1v2v3v4vivi+1vk-1vku第一百一十八页，共一百三十二页，编辑于2023年，星期日定理如果n(>2)阶简单图G=(V,E)的任何两个结点u和v，都使d(u)+d(v)n成立，则G是哈密顿图。证明要点：由给定条件，G含有哈密顿道路，再进一步证明由这条哈密顿道路可以扩充成哈密顿圈。注意：定理中的条件是充分的而不是必要的，例如下图是哈密顿图但不满足定理中的条件。第一百一十九页，共一百三十二页，编辑于2023年，星期日下面举一个应用定理的例子。

题目:设n(>2)阶简单图G的边数m2+(n-1)