离散数学复件

离散数学复件第一页，共一百八十七页，编辑于2023年，星期日主要内容

7.1

图论的基本概念

7.2

子图和图的运算

7.3

路径、回路和连通图

7.4

欧拉图和哈密顿图

7.6树、有向树和有序树第二页，共一百八十七页，编辑于2023年，星期日什么是图?普通含义:

在坐标系中用点线表示的数据。离散数学中的含义:

一种用于表示关系的特殊离散结构，具有网状表示形式不是这个含义第三页，共一百八十七页，编辑于2023年，星期日图论已有二百多年历史，近四十年来发展十分迅速，成为一个新兴的数学分支。1、计算机科学中许多概念、算法需要图论支持。 （如二叉树）2、为计算机应用建模提供数学工具第四页，共一百八十七页，编辑于2023年，星期日图论的应用网络、调度、流量优化、电路设计、路径规划……计算机游戏、程序编译、面向对象设计……表示各种关系第五页，共一百八十七页，编辑于2023年，星期日7.1图论的基本概念第六页，共一百八十七页，编辑于2023年，星期日图论的基本概念目的：了解图论的基本概念；重点：图论的基本概念；难点：度、图同构。第七页，共一百八十七页，编辑于2023年，星期日无向图、有向图设V和E是有限集合，且V≠如果Ψ：E→｛｛v1，v2｝｜v1∈Ｖ且v2∈V｝，则称

G＝<Ｖ，Ｅ，Ψ>为无向图。如果Ψ:E→V×V，则称G＝<Ｖ，Ｅ，Ψ>为有向图。注意：

E可空 零图

一个E中元素可对应二个相同的V中元素 自圈

多个E中的元素可对应V中相同的二元素平行边无向图和有向图统称为图，其中V的元素称为图G的结点，E的元素称为图G的边，图G的结点数目称为它的阶。第八页，共一百八十七页，编辑于2023年，星期日 无向图 有向图 混合图 *混合图中无向边可用一对方向的有向边代替

本章仅讨论无向图和有向图既有有向边，又有无向边第九页，共一百八十七页，编辑于2023年，星期日 图的最本质内容：结点和边的对应关系。 用几何图形表示图： 小圆圈表示结点 无向图：若Ψ(e)={v1，v2}，就用一条连接结点v1和v2的

无向线段表示边e

有向图：若Ψ(e)＝〈v1，v2〉，就用一条由v1指向v2的 有向线段表示边e第十页，共一百八十七页，编辑于2023年，星期日例123ab无向图<{1,2,3},{a,b},{<a,{1,2}>,<b,{2,3}>}>第十一页，共一百八十七页，编辑于2023年，星期日例123ab有向图<{1,2,3},{a,b},{<a,<2,1>>,<b,<2,3>>}>第十二页，共一百八十七页，编辑于2023年，星期日关联、邻接——结点和边的关系设无向图G＝<Ｖ，Ｅ，Ψ>，e，e1，e2∈E且v1，v2∈V如果Ψ(e)＝｛v1，v2｝，则称e与v1(或v2)互相关联，e连接v1和v2，v1和v2既是e的起点，也是e的终点，也称v1和v2邻接。如果两条不同边e1和e2与同一个结点关联，则称e1和e2邻接。第十三页，共一百八十七页，编辑于2023年，星期日关联、邻接——结点和边的关系设有向图G＝〈Ｖ，Ｅ，Ψ〉，e∈E且v1，v2∈V如果Ψ(e)＝〈v1，v2〉，则称e连接v1和v2，e与v1(或v2)互相关联，分别称v1和v2是e的起点和终点，也称v1和v2邻接。第十四页，共一百八十七页，编辑于2023年，星期日自圈、平行边、简单图设图G＝〈Ｖ，Ｅ，Ψ〉，e1和e2是G的两条不同边。如果与e1关联的两个结点相同，则称e1为自圈；如果Ψ(e1)＝Ψ(e2)，则称e1与e2平行； （对有向图不是平行边）如果图G没有自圈，也没有平行边，则称G为简单图。第十五页，共一百八十七页，编辑于2023年，星期日有些书中：图——简单图；多重图——含平行边； 伪图——图。平行边第十六页，共一百八十七页，编辑于2023年，星期日有多少条边与某一个结点相关联？——结点的度第十七页，共一百八十七页，编辑于2023年，星期日度设v是图G的结点。如果G是无向图，G中与v关联的边和与v关联的自圈的数目之和称为v的度，记为dG(v)。如果G是有向图，G中以v为起点的边的数目称为v的出度，记为；G中以v为终点的边的数目称为v的入度，记为

；v的出度与入度之和称为v的度，记为dG(v)。注意：每增加一条边，都使图中所有结点的度数之和增加2。在计算无向图中结点的度时，自圈要考虑两遍，因为自圈也是边。第十八页，共一百八十七页，编辑于2023年，星期日例123第十九页，共一百八十七页，编辑于2023年，星期日例2314第二十页，共一百八十七页，编辑于2023年，星期日定理7.1.1、定理7.1.2设无向图G＝〈Ｖ，Ｅ，Ψ〉有m条边，则 （握手定理）设有向图G＝〈Ｖ，Ｅ，Ψ〉有m条边，则

，且

。第二十一页，共一百八十七页，编辑于2023年，星期日奇结点、偶结点度为奇数的结点称为奇结点；度为偶数的结点称为偶结点。第二十二页，共一百八十七页，编辑于2023年，星期日任何图都有偶数个奇结点。

定理7.1.3第二十三页，共一百八十七页，编辑于2023年，星期日孤立点、端点度为0的结点称为孤立点；度为1的结点称为端点。第二十四页，共一百八十七页，编辑于2023年，星期日定义以下特殊图：结点都是孤立点的图称为零图。

一阶零图称为平凡图。所有结点的度均为自然数d的无向图称为d度正则图。设n∈I+，如果n阶简单无向图G是n-1度正则图，则称G为完全无向图，记为Kn。设n∈I+，每个结点的出度和入度均为n-1的n阶简单有向图称为完全有向图。零图、平凡图、d度正则图、完全图

第二十五页，共一百八十七页，编辑于2023年，星期日例K1K2K3K4K5K6第二十六页，共一百八十七页，编辑于2023年，星期日图的最本质内容：结点和边的关联关系。第二十七页，共一百八十七页，编辑于2023年，星期日同构设图G＝〈Ｖ，Ｅ，Ψ〉和G′＝〈Ｖ′，Ｅ′，Ψ′〉。如果存在双射f：V→Ｖ′和双射g：E→Ｅ′,使得对于任意e∈Ｅ及v1，v2∈Ｖ都有：

｛f（v1），f（v2）｝ 若Ψ(e)＝｛v1，v2｝Ψ′(g(e))＝ 〈f（v1），f（v2）〉 若Ψ(e)＝〈v1，v2〉则称G与G′同构，记做G

Ｇ′，并称f和g为G与G′之间的同构映射，简称同构。第二十八页，共一百八十七页，编辑于2023年，星期日必要非充分条件两图结点数目和边数目相同；两图中度数为d的结点数目相同；……第二十九页，共一百八十七页，编辑于2023年，星期日例判断下面两个图是否同构？如是，标出对应结点；否则，说明两图的差异abcdefbdaefc第三十页，共一百八十七页，编辑于2023年，星期日例abcde*结点数相同*边数相同*度为2的结点数不同

(1对3)第三十一页，共一百八十七页，编辑于2023年，星期日作业习题7.1 1.a)c) 3. 6. 9. 10. 11.第三十二页，共一百八十七页，编辑于2023年，星期日7.2子图和图的运算第三十三页，共一百八十七页，编辑于2023年，星期日子图和图的运算目的：了解子图和图的基本概念；重点：子图、可运算、图的运算；难点：图的运算、子图。第三十四页，共一百八十七页，编辑于2023年，星期日子图、真子图、生成子图设图G＝〈Ｖ，Ｅ，Ψ〉，G′＝〈Ｖ′，Ｅ′，Ψ′〉。如果V′V，E′E，Ψ′Ψ，则称G′是G的子图，记为G′G，并称G是G′的母图。如果V′V，E′E，Ψ′Ψ，则称G′是G的真子图，记为G′G。如果V′＝V，E′E，Ψ′Ψ，则称G′是G的生成子图。第三十五页，共一百八十七页，编辑于2023年，星期日结点导出的子图设图G＝〈Ｖ，Ｅ，Ψ〉，V′V且V′.以V′为结点集合，以所有起点和终点均在V′中的边为边集合的G的子图称为由V′导出的G的子图，记为G[V′].

若V′V，导出子图G[V－V′]记为G－V′.G－V′是从G中去掉V′中的结点以及与这些结点关联的边而得到的G的子图第三十六页，共一百八十七页，编辑于2023年，星期日例第三十七页，共一百八十七页，编辑于2023年，星期日例求G－a和G－d第三十八页，共一百八十七页，编辑于2023年，星期日边导出的子图设图G＝〈Ｖ，Ｅ，Ψ〉，E′E且E′.V′={v|vV且有eE′使v与e关联}。以V′为结点集合，以E′为边集合的G的子图称为由E′导出的G的子图，记为G[E′].第三十九页，共一百八十七页，编辑于2023年，星期日例第四十页，共一百八十七页，编辑于2023年，星期日从图示来看，图G的子图是G的一部分，G的真子图的边比G的边少，G的生成子图与G有相同的结点，G的导出子图G[V]是G的以V为结点集合的最大子图。第四十一页，共一百八十七页，编辑于2023年，星期日可运算、不相交设图G＝〈Ｖ，Ｅ，Ψ〉和G′＝〈Ｖ′，Ｅ′，Ψ′〉同为无向图或同为有向图。如果对于任意e∈Ｅ∩E′均有Ψ(e)＝Ψ′(e)，则称G和G′是可运算的。如果V∩V′＝E∩E′＝，则称G和G′是不相交的。如果E∩E′＝，则称G和G′是边不相交的。第四十二页，共一百八十七页，编辑于2023年，星期日例abcdefdghi如果E∩E′，则边所连接的结点必须相同下面两个图是否可运算？第四十三页，共一百八十七页，编辑于2023年，星期日交、并、环和设图Ｇ1＝〈Ｖ1，Ｅ1，Ψ1〉和Ｇ2＝〈Ｖ2，Ｅ2，Ψ2〉为可运算的。称以Ｖ1∩Ｖ2为结点集合，以Ｅ1∩Ｅ2为边集合的Ｇ1和Ｇ2的公共子图为Ｇ1和Ｇ2的交，记为Ｇ1∩Ｇ2。称以Ｖ1∪Ｖ2为结点集合，以Ｅ1∪Ｅ2为边集合的Ｇ1和Ｇ2的公共母图为Ｇ1和Ｇ2的并，记为Ｇ1∪Ｇ2。称以Ｖ1∪Ｖ2为结点集合，以Ｅ1

Ｅ2为边集合的Ｇ１∪Ｇ２的子图为Ｇ１和Ｇ２的环和，记为

Ｇ１Ｇ２。第四十四页，共一百八十七页，编辑于2023年，星期日交、并、环和Ｇ1∩Ｇ2=〈V1∩Ｖ2，Ｅ1∩Ｅ2，Ψ1∩Ψ2〉Ｇ1∪Ｇ2=〈V1∪Ｖ2，Ｅ1∪Ｅ2，Ψ1∪Ψ2〉Ｇ1

Ｇ2=〈V1∪Ｖ2，Ｅ1Ｅ2，Ψ1∪Ψ2Ｅ1Ｅ2〉

显然，并不是任何两个图都有交、并和环和，它们必须可运算才行。第四十五页，共一百八十七页，编辑于2023年，星期日例abcdefdgh第四十六页，共一百八十七页，编辑于2023年，星期日定理7.2.1设图Ｇ1＝〈Ｖ1，Ｅ1，Ψ1〉和Ｇ2＝〈Ｖ2，Ｅ2，Ψ2〉为可运算。如果Ｖ1∩Ｖ2，则存在唯一的Ｇ1∩Ｇ2。（若

V１∩Ｖ２＝，则Ｇ１∩Ｇ２不存在）存在唯一的Ｇ1∪Ｇ2和Ｇ1Ｇ2

。第四十七页，共一百八十七页，编辑于2023年，星期日运算G–E设图G＝〈Ｖ，Ｅ，Ψ〉。若E′E，则记〈Ｖ，Ｅ－E′，Ψ(E-E′)〉为G－E′；若eE，则记G－{e}为G－e。G－E′是从G中去掉E′中的边所得到的G的子图。注意：与E′中的边相关联的结点并不去掉。第四十八页，共一百八十七页，编辑于2023年，星期日例求G－{a,e}和G－{c,e}第四十九页，共一百八十七页，编辑于2023年，星期日例求G－{{a,e},{e,d},{e,c},{b,c}}第五十页，共一百八十七页，编辑于2023年，星期日运算G+EΨ设G＝〈Ｖ，Ｅ，Ψ〉和G′＝〈Ｖ′，Ｅ′，Ψ′〉同为无向图或同为有向图，若G和G′边不相交且G′无孤立点，则记G∪G′为

G＋Ｅ′Ψ′G＋Ｅ′Ψ′是由G增加Ｅ′中的边所得到的图其中，Ψ指出E中的边与结点的关联关系。第五十一页，共一百八十七页，编辑于2023年，星期日设n阶无向图G＝〈Ｖ，Ｅ，Ψ〉是n阶完全无向图Kn的生成子图，则称Kn-E为G的补图，记为。*简单无向图都有补图，并且一个简单无向图的所有补图都同构。补图第五十二页，共一百八十七页，编辑于2023年，星期日例第五十三页，共一百八十七页，编辑于2023年，星期日例第五十四页，共一百八十七页，编辑于2023年，星期日定理7.2.2设f和g为图G＝〈Ｖ，Ｅ，Ψ〉和G′＝〈Ｖ′，Ｅ′，Ψ′〉之间的同构映射。i)若vV且v’＝f(v)，则dG(v)＝dG’(v’)；ii)若SV且S’＝f[S]，则G[S]G’[S’]且G－SG’－S’；iii)若KE且K’＝g[K]，则G[K]G’[K’]且G－KG’－K’；iv)G的补图与G’的补图仍同构。第五十五页，共一百八十七页，编辑于2023年，星期日作业习题7.2 2.

3. 4. 5. 6. 7.第五十六页，共一百八十七页，编辑于2023年，星期日7.3路径、回路和连通性第五十七页，共一百八十七页，编辑于2023年，星期日路径、回路和连通性目的：了解与路径、回路、连通性、分支、非循环图相关的基本概念；掌握求加权路径的算法、判一个图是否有回路、有有向回路、有半回路的过程；重点：路径、回路、连通、分支等重要概念；求加权路径的算法；判回路、有向回路、半回路、循环图；难点：几种判定方法及其原理。第五十八页，共一百八十七页，编辑于2023年，星期日应用：无向图的结点和边分别表示城市和连接城市的双轨铁路。从城市v0到城市vn的路径由一个结点和边组成的序列来表示。

v0e1v1e2v2…en-1envn ei(1in)表示连接城市的铁路；

v1，v2，…，vn-1表示途经城市。第五十九页，共一百八十七页，编辑于2023年，星期日路径设n为自然数，v0，v1

，…，vn是图G的结点，e1，e2，…，en是图G的边，并且vi-1和vi分别是ei的起点和终点(i=1，2，…，n)，则称序列v0e1v1e2…vn-1envn为图G中从v0至vn的路径，n称为该路径的长度。如果v0=vn，则称该路径为闭的，否则称为开的。如果e1，e2，…，en互不相同，则称该路径为简单的。如果v0，v1，…，vn互不相同，则称该路径为基本的。 （简单路径基本路径？）

“基本必定简单”第六十页，共一百八十七页，编辑于2023年，星期日例uavfyfvgyhwbvwcxdyhwbvgyxcwhyeuavuavfygubwhyeuuavbwhyeu第六十一页，共一百八十七页，编辑于2023年，星期日任何结点到自身总存在路径。v到v存在路径

v到v存在路径？

(无向图√

有向图╳)长度为0的基本路径第六十二页，共一百八十七页，编辑于2023年，星期日定理7.3.1设图G＝〈Ｖ，Ｅ，Ψ〉，v,v′Ｖ。如果存在从v至v′的路径，则存在从v至v′的基本路径。第六十三页，共一百八十七页，编辑于2023年，星期日定理7.3.2n阶图中的基本路径的长度小于n。（因为基本路径中的结点互不相同，即最多仅含n个结点，所以所经过的边数必定小于n。）第六十四页，共一百八十七页，编辑于2023年，星期日可达设图G＝〈Ｖ，Ｅ，Ψ〉，v,v′Ｖ。若存在从v1至v2的路径，则称在G中从v1可达v2，否则称在G中从v1不可达v2对于图G的结点v，我们用R(v)表示从v可达的全体结点的集合。第六十五页，共一百八十七页，编辑于2023年，星期日可达集（reachableset）的概念用于安全性证明。

无向图：若从v1可达v2，则从v2必可达v1。有向图：从v1可达v2不能保证从v2必可达v1。第六十六页，共一百八十七页，编辑于2023年，星期日定理7.3.3设图G＝〈Ｖ，Ｅ，Ψ〉，v,v′Ｖ。从v1可达v2 iff 存在从v1至v2的基本路径。 （长度最短的路径）第六十七页，共一百八十七页，编辑于2023年，星期日距离设图G＝〈Ｖ，Ｅ，Ψ〉，v,v′Ｖ。i)

若从v1可达v2，从v1至v2的测地线：从v1至v2的路径中长度最短者；从v1至v2的距离：从v1至v2的测地线长度，记作d(v1,v2)。ii)

若从v1不可达v2，d(v1,v2)=∞，并且规定∞+∞=∞；nN，∞>n，n+∞=∞+n=∞。第六十八页，共一百八十七页，编辑于2023年，星期日直径图G＝〈Ｖ，Ｅ，Ψ〉的直径定义为第六十九页，共一百八十七页，编辑于2023年，星期日例v2v1v3v4v5v6e1e2e3e4e5e6第七十页，共一百八十七页，编辑于2023年，星期日加权设图G＝〈Ｖ，Ｅ，Ψ〉且Ｗ：Ｅ→R＋（R＋是正实数集合），i)

则称〈G，W〉为加权图；ii)

e∈Ｅ，称W(e)为边e的加权长度；路径中所有边的加权长度之和称为该路径的加权长度。iii)

从结点v至结点v′的路径中加权长度最小的称为从v至v′的最短路径。iv)

若从v可达v′，则称从v至v′的最短路径的加权长度为从v至v′的加权距离；若从v不可达v′，则称从v至v′的加权距离为∞。第七十一页，共一百八十七页，编辑于2023年，星期日戴克斯特拉（Dijkstra）算法算法：λ(s)←0，且v∈V-｛s｝，λ（v）←∞；T←V；任取u∈｛u′｜若v′∈T，则λ(u′)≤λ(v′)｝；如果u=t，则算法结束。对于以u为起点的每条边e，如果e的终点v∈T并且λ(v)>λ(u)+W(e)，则λ(v)←λ(u)+W(e)；T←T-｛u｝且转向3)。当算法结束时，λ(t)即为从s至t的加权距离。第七十二页，共一百八十七页，编辑于2023年，星期日例子（加权距离）从1到4的加权距离为1.4。

0.5

1

0.5

0.4

1

1

2

3

4

当前点\\结点1234

01/10.53/0.9/1.52///1.44

第七十三页，共一百八十七页，编辑于2023年，星期日无向图的连通如果无向图G的任意两个结点都互相可达，则称G是连通的；否则称G是非连通的。无向图G＝〈Ｖ，Ｅ，Ψ〉是连通的iffv∈V皆有R(v)＝Ｖ第七十四页，共一百八十七页，编辑于2023年，星期日有向图的基础图设有向图G＝<Ｖ，Ｅ，Ψ>，定义Ψ′：E→{{v１，v２}｜v1∈Ｖ∧v2∈Ｖ}如下：对任意e∈E和v1，v2∈V，若Ψ(e)＝〈v１，v２〉，则Ψ′(e)＝｛v1，v2｝这时称无向图G′＝<Ｖ，Ｅ，Ψ′>为有向图G的基础图。 所有有向边改为无向边有向图有向图的基础图第七十五页，共一百八十七页，编辑于2023年，星期日有向图的连通设G是有向图。如果G中任意两结点都互相可达，则称G是强连通的；如果对于G的任意两结点，必有一个结点可达另一结点，则称G是单向连通的；如果G的基础图是连通的，则称G是弱连通的。第七十六页，共一百八十七页，编辑于2023年，星期日例第七十七页，共一百八十七页，编辑于2023年，星期日极大子图设G’是图G的具有某性质的子图，并且对于G的具有该性质的任意子图G’’，只要G’G’’，就有G’＝G’’，则称G’相对于该性质是G的极大子图。第七十八页，共一百八十七页，编辑于2023年，星期日分支无向图G的极大连通子图称为G的分支。第七十九页，共一百八十七页，编辑于2023年，星期日有向图的分支设G是有向图。G的极大强连通子图称为G的强分支。G的极大单向连通子图称为G的单向分支。G的极大弱连通子图称为G的弱分支。第八十页，共一百八十七页，编辑于2023年，星期日回路、半回路、有向回路回路：连通2度正则图；半回路：基础图是回路的有向图；有向回路：每个结点的出度和入度均为1的弱连通有向图；回路(半回路，有向回路)的长度：回路(半回路，有向回路)中边的数目。第八十一页，共一百八十七页，编辑于2023年，星期日有回路、非循环图如果回路(有向回路，半回路)C是图G的子图，则称G有回路(有向回路，半回路)C。没有回路的无向图和没有半回路的有向图称为非循环图。第八十二页，共一百八十七页，编辑于2023年，星期日判断一个图是否有回路、有有向回路、有半回路？判断一个图是否为非循环图？第八十三页，共一百八十七页，编辑于2023年，星期日定理7.3.7如果有向图G有子图G′满足：对于G′的任意结点v，dＧ＋(v)>0，则G有有向回路。第八十四页，共一百八十七页，编辑于2023年，星期日定理7.3.8如果有向图G有子图G′满足：对于G′中的任意结点v，dＧ－(v)>0，则G有有向回路。第八十五页，共一百八十七页，编辑于2023年，星期日W-过程判断一个有向图是否有有向回路的方法：W—过程从G中去掉v和与之关联的边得到有向图G-{v}的过程（其中v是有向图的结点，dＧ－(v)=0或dＧ＋(v)=0）。

G有有向回路 当且仅当 G-{v}有有向回路；若n阶有向图G没有有向回路，则经过n-1次W—过程得到平凡图。第八十六页，共一百八十七页，编辑于2023年，星期日定理7.3.9图G不是非循环图iffG有子图G′满足：对于G′的任意结点v，dＧ′(v)>1。 （证明方法与定理7.3.8类似）类似方法：G0，Ｇ1，…，Ｇm，其中0≤m≤n-1，G0=G，Gi+1=Gi-{vi}（其中dＧi(vi)1）。若Ｇm是平凡图，则G是非循环图，否则不然。第八十七页，共一百八十七页，编辑于2023年，星期日作业习题7.3 3. 10. 11. 12. 15.第八十八页，共一百八十七页，编辑于2023年，星期日

§7.4欧拉图和哈密顿图

第八十九页，共一百八十七页，编辑于2023年，星期日哥尼斯堡桥问题

从四块陆地的任何一块出发，怎样通过每座桥恰巧一次，最终回到出发地点？（即找包含所有边的简单闭路径。）Euler 1736 瑞士数学家 证明不可能第九十页，共一百八十七页，编辑于2023年，星期日欧拉路径、欧拉闭路图G中包含其所有边的简单开路径称为G的欧拉路径。图G中包含其所有边的简单闭路径称为G的欧拉闭路。

第九十一页，共一百八十七页，编辑于2023年，星期日欧拉图、欧拉有向图每个结点都是偶结点的无向图称为欧拉图。每个结点的出度和入度都相等的有向图称为欧拉有向图。

欧拉找到了连通无向图是欧拉图的充分必要条件：欧拉定理。

第九十二页，共一百八十七页，编辑于2023年，星期日欧拉定理设G是连通无向图，G是欧拉图iffG有欧拉闭路。第九十三页，共一百八十七页，编辑于2023年，星期日定理7.4.2设G＝〈Ｖ，Ｅ，Ψ〉为连通无向图且v1，v2∈Ｖ，则G有一条从v1至v2的欧拉路径iffG恰有两个奇结点v1和v2。第九十四页，共一百八十七页，编辑于2023年，星期日根据哥尼斯堡桥问题画出的图不是欧拉图，因此不存在欧拉闭路，即哥尼斯堡桥问题没有解。第九十五页，共一百八十七页，编辑于2023年，星期日一笔画第九十六页，共一百八十七页，编辑于2023年，星期日周游世界的数学游戏Hamilton(哈密顿)十九世纪 爱尔兰数学家 正十二面体， 二十个顶点， 三十条棱 城市 路问：找一条从某城市出发，经过每个城市恰好一次，并且最后回到出发点的路线。等价于：在图中找出一条包含所有结点的闭路，并且，除始点和终点重合外，这条闭路所含结点是互不相同的。根据定理7.3.6，这条闭路的所有结点和边组成了一个回路。第九十七页，共一百八十七页，编辑于2023年，星期日Hamilton回路如果回路(有向回路)C是图G的生成子图，则称C为G的Hamilton回路（Hamilton有向回路）。图G中包含它的所有结点的基本路径称为G的Hamilton路径。有Hamilton回路（Hamilton有向回路）的图称为Hamilton图（Hamilton有向图）。第九十八页，共一百八十七页，编辑于2023年，星期日4图的矩阵表示定义4.1设G=V,E是一个简单图，V=v1,v2,…,vn

A(G)=(aij)

n×n

其中：

i,j=1,…,n称A(G)为G的邻接矩阵。简记为A。

第九十九页，共一百八十七页，编辑于2023年，星期日例如图9.22的邻接矩阵为：

第一百页，共一百八十七页，编辑于2023年，星期日又如图9.23(a)的邻接矩阵为：

第一百零一页，共一百八十七页，编辑于2023年，星期日邻接矩阵具有以下性质：①邻接矩阵的元素全是0或1。这样的矩阵叫布尔矩阵。邻接矩阵是布尔矩阵。②无向图的邻接矩阵是对称阵，有向图的邻接矩阵不一定是对称阵。③邻接矩阵与结点在图中标定次序有关。例如图9.23(a)的邻接矩阵是A(G)，若将图9.23(a)中的接点v1和v2的标定次序调换，得到图9.23(b)，图9.23(b)的邻接矩阵是A′(G)。第一百零二页，共一百八十七页，编辑于2023年，星期日考察A(G)和A′(G)发现，先将A(G)的第一行与第二行对调，再将第一列与第二列对调可得到A′(G)。称A′(G)与A(G)是置换等价的。一般地说，把n阶方阵A的某些行对调，再把相应的列做同样的对调，得到一个新的n阶方阵A′，则称A′与A是置换等价的。可以证明置换等价是n阶布尔方阵集合上的等价关系。虽然，对于同一个图，由于结点的标定次序不同，而得到不同的邻接矩阵，但是这些邻接矩阵是置换等价的。今后略去结点标定次序的任意性，取任意一个邻接矩阵表示该图。④对有向图来说，邻接矩阵A(G)的第i行1的个数是vi的出度，第j列1的个数是vj的入度。⑤零图的邻接矩阵的元素全为零，叫做零矩阵。反过来，如果一个图的邻接矩阵是零矩阵，则此图一定是零图。第一百零三页，共一百八十七页，编辑于2023年，星期日

定理

设A(G)是图G的邻接矩阵，A(G)k=A(G)A(G)k-1，A(G)k的第i行，第j列元素等于从vi到vj长度为k的路的条数。其中为vi到自身长度为k的回路数。

推论设G=V,E是n阶简单有向图，A是有向图G的邻接矩阵，Bk=A＋A2＋…＋Ak，Bk=()n×n，则是G中由vi到vj长度小于等于k的路的条数。是G中长度小于等于k的路的总条数。是G中长度小于等于k的回路数。

【例】设G=V,E为简单有向图，图形如图9.24，写出G的邻接矩阵A，算出A2，A3，A4且确定v1到v2有多少条长度为3的路?v1到v3有多少条长度为2的路?v2到自身长度为3和长度为4的回路各多少条?第一百零四页，共一百八十七页，编辑于2023年，星期日

解：邻接矩阵A和A2，A3，A4如下：

第一百零五页，共一百八十七页，编辑于2023年，星期日

=2，所以v1到v2长度为3的路有2条，它们分别是：v1v2v1v2和v1v2v3v2。

=1，所以v1到v3长度为2的路有1条：v1v2v3。

=0，v2到自身无长度为3的回路。

=4，v2到自身有4条长度为4的回路，它们分别是：v2v1v2v1v2、v2v3v2v3v2、v2v3v2v1v2和v2v1v2v3v2。第一百零六页，共一百八十七页，编辑于2023年，星期日定义9.4.2设G=V,E是简单图，V=v1,v2,…,vn

P(G)=(pij)n×n

其中：pij

=i,j=1,…,n称P(G)为G的可达性矩阵。简记为P。在定义9.3.10中，规定了向图的任何结点自己和自己可达。所以可达性矩阵P(G)的主对角线元素全为1。第一百零七页，共一百八十七页，编辑于2023年，星期日设G=V,E是n阶简单有向图，V=v1,v2,…,vn，由可达性矩阵的定义知，当i≠j时，如果vi到vj有路，则pij=1；如果vi到vj无路，则pij=0；又由定理9.2.1知，如果vi到vj有路，则必存在长度小于等于n–1的路。依据定理9.4.1的推论，如下计算图G的可达性矩阵P：先计算Bn–1=A＋A2＋…＋An–1，设Bn–1=()n×n。若≠0，则令pij=1，若=0，则令pij=0，i,j=1,…,n。再令pii=1，i=1,…,n。就得到了图G的可达性矩阵P。令A0为n阶单位阵，则上述算法也可以改进为：计算Cn–1=A0＋Bn–1=A0＋A＋A2＋…＋An-1，设Cn–1=()n×n。若≠0，则令pij=1，若=0，则令pij=0，i,j=1,…,n。第一百零八页，共一百八十七页，编辑于2023年，星期日使用上述方法，计算例9.4中图G的可达性矩阵，

C4=A0＋A＋A2＋A3＋A4=

P=第一百零九页，共一百八十七页，编辑于2023年，星期日计算简单有向图G的可达性矩阵P，还可以用下述方法：设A是G的邻接矩阵，令A=(aij)n×n，A(k)=()n×n，A0为n阶单位阵。

A(2)=A∘A，其中=(ai1∧a1j)∨(ai2∧a2j)∨…∨(ain∧anj)i,j=1,…,n。

A(3)=A∘A(2)，其中(ai1∧)∨…∨(ain∧)

i,j=1,…,n。

……P=A0∨A∨A(2)∨A(3)∨…∨A(n–1)。其中，运算∨是矩阵对应元素的析取。可达性矩阵用来描述有向图的一个结点到另一个结点是否有路，即是否可达。无向图也可以用矩阵描述一个结点到另一个结点是否有路。在无向图中，如果结点之间有路，称这两个结点连通，不叫可达。所以把描述一个结点到另一个结点是否有路的矩阵叫连通矩阵，而不叫可达性矩阵。

第一百一十页，共一百八十七页，编辑于2023年，星期日定义9.4.3设G=V,E是简单无向图，V=v1,v2,…,vnD(G)=(dij)

n×n

其中：dij为vi到vj

的距离

i,j=1,…,n称D(G)为G的距离矩阵。第一百一十一页，共一百八十七页，编辑于2023年，星期日定义9.4.4设G=V,E是无向图，V=v1,v2,…,vp，E=e1,e2,…,eqM(G)=(mij)

p×q

其中：

i=1,…,p，j=1,…,q称M(G)为无向图G的完全关联矩阵。简记为M。

第一百一十二页，共一百八十七页，编辑于2023年，星期日例如图9.25的完全关联矩阵为：

M(G)=

第一百一十三页，共一百八十七页，编辑于2023年，星期日设G=V,E是无向图，G的完全关联矩阵M(G)有以下的性质：①每列元素之和均为2。这说明每条边关联两个结点。②每行元素之和是对应结点的度数。③所有元素之和是图各结点度数的和，也是边数的2倍。④两列相同，则对应的两个边是平行边。⑤某行元素全为零，则对应结点为孤立点。

定义9.4.5设G=V,E是有向图，V=v1,v2,…,vp，E=e1,e2,…,eq

M(G)=(mij)

p×q

其中：i=1,…,p，j=1,…,q

称M(G)为有向图G的完全关联矩阵。简记为M。

第一百一十四页，共一百八十七页，编辑于2023年，星期日图9.26的完全关联矩阵为：

M(G)=

第一百一十五页，共一百八十七页，编辑于2023年，星期日设G=V,E是有向图，G的完全关联矩阵M(G)有以下的性质：①每列有一个1和一个-1，这说明每条有向边有一个始点和一个终点。②每行1的个数是对应结点的出度，-1的个数是对应结点的入度。③所有元素之和是0，这说明所有结点出度的和等于所有结点入度的和。④两列相同，则对应的两边是平行边。

第一百一十六页，共一百八十七页，编辑于2023年，星期日

§7.6树第一百一十七页，共一百八十七页，编辑于2023年，星期日树非循环的连通无向图称为树。

第一百一十八页，共一百八十七页，编辑于2023年，星期日定理7.6.1设G是n阶无向图。以下可以用六种等价办法定义树。i)

G是连通的，又是非循环的。ii)G没有自圈，并且对于G的任意两结点v和v′，在G中存在唯一的一条从v至v′的基本路径。iii)

G是连通的，如果v和v′是G的两结点，e不是G的边，当令Ψ′＝｛〈e，｛v，v′｝〉｝时，则G＋｛e｝Ψ′有唯一的一条回路。G是连通的，并且对于G的任意边e，G-e非连通。G是连通的，并且有n-1条边。G是非循环的，并且有n-1条边。第一百一十九页，共一百八十七页，编辑于2023年，星期日树是非循环连通无向图，如果去掉对连通性的要求，就得到森林的概念。第一百二十页，共一百八十七页，编辑于2023年，星期日森林每个分支都是树的无向图称为森林。

第一百二十一页，共一百八十七页，编辑于2023年，星期日生成树、生成森林如果树T是无向图G的生成子图，则称T为G的生成树。如果森林F是无向图G的所有分支的生成树的并，则称F为G的生成森林。

第一百二十二页，共一百八十七页，编辑于2023年，星期日找连通图的生成树方法找连通图G的生成树方法： “避圈法” “破圈法”避圈法：添加e１，e２，…，添加中保证ei+1不与{e１，…，ei}的任何子集构成回路。破圈法：在G0=(G)，G1，G2，…中去掉e１，e２，e3，…，ei为Gi-1中某回路的边。第一百二十三页，共一百八十七页，编辑于2023年，星期日最小生成树设〈G，W〉是加权图，G′G，G′中所有边的加权长度之和称为G′的加权长度。设G是连通无向图，〈G，W〉是加权图，G的所有生成树中加权长度最小者称为〈G，W〉的最小生成树。第一百二十四页，共一百八十七页，编辑于2023年，星期日最小生成树求法（避圈法、破圈法）“避圈法”求最小生成树：设G是有m条边的n阶连通无向图，1

把G的m条边排成加权长度递增的序列e1，e2，…，em；2T←；3j←1，i←1；（i记录正在扫描的边的下标；j记录T中边数是否已达n-1）4若j=n则算法结束。5若G的以T∪｛ei｝为边集合的生成子图没有回路，则T←T∪｛ei｝且j←j+1；6i←i+1，转向3

。算法结束时T即为所求的最小生成树的边集合。第一百二十五页，共一百八十七页，编辑于2023年，星期日第一百二十六页，共一百八十七页，编辑于2023年，星期日设G为无向连通图，有n个结点和m条边。T为G的生成树，T有n个结点和n-1条边。所以要得到G的一棵生成树，必须删除G的m-(n-1)=m–n＋1条边。在树上的边枝n-1条不在树上的边弦m–n＋1条秩树换成森林余圈秩圈秩给定树基本回路

第一百二十七页，共一百八十七页，编辑于2023年，星期日有向树一个结点的入度为0，其余结点的入度均为1的弱连通有向图称为有向树。在有向树中，入度为0的结点称为根，出度为0的结点称为叶，出度大于0的结点称为分支结点，从根至任意结点的距离称为该结点的级，所有结点的级的最大值称为有向树的高度。第一百二十八页，共一百八十七页，编辑于2023年，星期日有向树的归纳定义也可用归纳法定义有向树。定义7.6.9有向树归纳定义如下：i) ii) 第一百二十九页，共一百八十七页，编辑于2023年，星期日有向森林每个弱分支都是有向树的有向图称为有向森林。第一百三十页，共一百八十七页，编辑于2023年，星期日m元有向树设m∈N，D为有向树。i)

如果D的所有结点出度的最大值为m，则称D为m元有向树。ii)如果对于m元有向树D的每个结点v皆有dＤ＋（v）＝m或dＤ＋（v）=0，则称D为完全m元有向树。第一百三十一页，共一百八十七页，编辑于2023年，星期日完全二元有向树也称二叉树。用途：字母和符号识别程序 {+，-，*，/} 00011011统计字母出现的频繁程度

第一百三十二页，共一百八十七页，编辑于2023年，星期日叶加权二叉树设V是二叉树D的叶的集合，R＋是全体正实数的集合，W：V→R＋，则称〈D，W〉为叶加权二叉树。对于D的任意叶v，称W(v)为v的权，称为〈D，W〉的叶加权路径长度，其中L(v)为v的级。第一百三十三页，共一百八十七页，编辑于2023年，星期日*我们用叶表示字母或符号，用分支结点表示判断，用权表示字母或符号出现的概率，则叶加权路径长度就表示识别算法的平均执行时间。第一百三十四页，共一百八十七页，编辑于2023年，星期日最优二叉树设〈D，W〉是叶加权二叉树。如果对任一叶加权二叉树〈D′，W′〉，只要对于任意正实数r，D和D′中权等于r的叶的数目相同，就有〈D，W〉的叶加权路径长度不大于〈D′，W′〉的叶加权路径长度，则称〈D，W〉为最优的。第一百三十五页，共一百八十七页，编辑于2023年，星期日最优二叉树求取*我们把求某问题的最佳算法归结为求最优二叉树。最优二叉树求取算法：（举例说明）2

3 9 18 23 29

5

9 18 23 29

14

18 23 29 32 23

29

32

52 84*将求n个叶的最优二叉树归结为求n-1个叶的最优二叉树。第一百三十六页，共一百八十七页，编辑于2023年，星期日有序树、有序森林为每一级上的结点规定了次序的有向树称为有序树。如果有向森林F的每个弱分支都是有序树，并且也为F的每个弱分支规定了次序，则称F为有序森林。第一百三十七页，共一百八十七页，编辑于2023年，星期日我们约定，在画有序树时，总是把根画在上部，并规定同一级上结点的次序是从左至右。在画有序森林时，弱分支的次序也是从左至右。例：用有序树表示算术表达式

((v1*v2)+(-v3))+v4/(v5-v6)第一百三十八页，共一百八十七页，编辑于2023年，星期日定位有序树为每个分支结点的儿子规定了位置的有序树称为定位有序树。第一百三十九页，共一百八十七页，编辑于2023年，星期日定位有序树例：可用定位二元有序树表示二进制编码情况。

T中全体叶的编码表示的集合称为T的前缀编码。

{00，01，101}

计算机存储第一百四十页，共一百八十七页，编辑于2023年，星期日定义9.6.15给定一个0、1序列的集合。若没有一个序列是另一个序列的前缀，则称该集合为前缀码。例如1,00,011,0101,01001,01000是前缀码。而1,00,0101,0100,01001,01000不是前缀码，因为0100是01001的前缀，也是01000的前缀。若使用前缀码中的0、1序列表示英文字母，当接收者收到0、1组成的长串时，就可以惟一的、准确无误地分割成字母对应的0、1序列。定理9.6.7任意一个二叉树，可以产生惟一的前缀码。证明：在二叉树中，每一个分枝点引出的左侧边标记0，右侧边标记1。由根结点到树叶的路经上各边的标记组成的0、1序列作为该片树叶的标记。显然，没有一片树叶的标记是另一片树叶的标记的前缀。所有树叶的标记构成了一个前缀码。第一百四十一页，共一百八十七页，编辑于2023年，星期日

【例9.12】求图9.50(a)所示的二叉树产生的前缀码。解：在图9.50(a)中，每一个分枝点引出的左侧边标记0，右侧边标记1。由根结点到树叶的路经上各边的标记组成的0、1序列作为对应树叶的标记，如图9.50(b)所示。产生的前缀码为：01,11,000,0010,0011

第一百四十二页，共一百八十七页，编辑于2023年，星期日定理9.6.8

任意一个前缀码，都对应一个二叉树。证明：给定了一个前缀码，设h是其中最长序列的长度。画出一个高为h的正则二叉树。按定理9.6.7中描述的办法给各边标记0或1。每一个结点对应一个0、1序列，它是由根结点到该结点的路经上各边的标记组成的。如果某个0、1序列是前缀码的元素，则标记该结点。将已标记结点的所有后代和该结点的射出边全部删除，得到了一个二叉树，再删除未加标记的树叶，就得到要求的二叉树。

【例9.13】设1,01,000是一前缀码，画出对应一个二叉树。解：画出一个高为3的正则二叉树，给各边标记0或1，每一个结点对应一个0、1序列，如果某个0、1序列是前缀码的元素，则标记该结点。如图9.51(a)所示。将已标记结点的所有后代和该结点的射出边全部删除，再删除未加标记的树叶，得到要求的二叉树,如图9.51(b)所示。第一百四十三页，共一百八十七页，编辑于2023年，星期日第一百四十四页，共一百八十七页，编辑于2023年，星期日

9.7二部图及匹配

9.7.1二部图定义9.7.1G=V,E是无向图，V1V，V2V，满足：①V1∪V2=V，V1∩V2=Æ。②G中每一条边的两端点，一个属于V1，另一个属于V2。则称G为二部图或偶图，常记为G=V1,V2,E，V1和V2称为G的互补的结点子集。二部图的每一条边的两个端点位于两个互补的结点子集，所以没有自回路。二部图是无自回路图。定义9.7.2设G=V1,V2,E是二部图，|V1|=r,|V2|=s，若V1的每个结点和V2的所有结点邻接,则称G为完全二部图或完全偶图，常记为Kr,s。在图9.55中，(a)，(b)，(c)都是二部图，其中(b)，(c)是完全二部图K1,3和K3,3。第一百四十五页，共一百八十七页，编辑于2023年，星期日第一百四十六页，共一百八十七页，编辑于2023年，星期日定理9.7.1设G=V,E是无向图，G为二部图的充分必要条件是G的所有回路的长均为偶数。证明：设G是二部图，下证G的所有回路的长均为偶数。设G是二部图，则V可以分成两个互补的结点子集V1和V2，每一个边的两个端点分别在V1和V2中，令

C：v0v1v2…vl-1v0是G中任一长度为l的回路。不失一般性，设v0V1，则v1V2，v2V1，则v3V2，……。由此可知，v2iV1，v2i＋1V2。又因为v0V1，所以vl-1V2，l-1是奇数，l是偶数。设G的所有回路的长均为偶数，下证G是二部图。不妨设G是连通图，否则可对每一个连通分支进行讨论。v0V，定义V的两个子集V1和V2为：

V1=v|vV∧d(v0,v)为偶数

V2=v|vV∧d(v0,v)为奇数因为G是连通图，任何结点与v0之间都有路，d(v0,v)不是偶数就是奇数，所以V1∪V2=V，V1∩V2=Æ。第一百四十七页，共一百八十七页，编辑于2023年，星期日下面证明V1中任意两个结点不邻接，V2中任意两个结点也不邻接。若存在viV1，vjV1，vi

和vj邻接，由于d(v0,vi)为偶数，v0到vi有一条长为偶数的路。同样的道理，v0到vj也有一条长为偶数的路。这两条路和边(vi,vj)构成一条回路，其长度为奇数。与条件矛盾。所以V1中任意两个结点不邻接。类似的可证，V2中任意两个结点也不邻接。于是G为二部图。根据此定理，图9.56中的(a)和(b)两个图是二部图。这比用定义判断要方便得多。画二部图时，习惯将互补的结点子集V1和V2分开画，画成图9.55的形式。图9.56中的(a)，(b)两个二部图，一定可以改画为图9.55的形式。第一百四十八页，共一百八十七页，编辑于2023年，星期日第一百四十九页，共一百八十七页，编辑于2023年，星期日

9.7.2匹配定义9.7.3设G=V1,V2,E是二部图，M是G中一些边组成的集合，如果M中任意两条边都没有公共端点，则称M为G的一个匹配或对集。设v是G的结点，如果v是M中某条边的端点，则称v为M的饱和点。否则，称v为M的非饱和点。在图9.57中，边集M=(a1,b2),(a2,b3),(a4,b1)是一个匹配，a1,a2,a4和b1,b2,b3为M的饱和点。结点a3为M的非饱和点。在图9.57中，如果用a1,a2,a3,a4表示4位教师，b1,b2,b3表示三门待开的课程。当某位教师能开某门课程时，则把它们的对应结点用边连接起来。如果规定一个教师只能担任一门课程，那么匹配M就表示了一种排课方案。为了使排课方案能最大限度地作到“各尽其能”，下面将引进最大匹配的概念。第一百五十页，共一百八十七页，编辑于2023年，星期日第一百五十一页，共一百八十七页，编辑于2023年，星期日定义9.7.4

设G=V1,V2,E是二部图，M是G的一个匹配，如果对G的任意匹配M′，都有|M′|≤|M|，则称M为G的最大匹配或最大对集。

第一百五十二页，共一百八十七页，编辑于2023年，星期日

【例9.15】图9.60是二部图，求其最大匹配。第一百五十三页，共一百八十七页，编辑于2023年，星期日第一百五十四页，共一百八十七页，编辑于2023年，星期日

【例9.16】图9.62是二部图，求其最大匹配。第一百五十五页，共一百八十七页，编辑于2023年，星期日第一百五十六页，共一百八十七页，编辑于2023年，星期日定义9.7.6设G=V1,V2,E是二部图，M是G的最大匹配，若|M|=min|V1|,|V2|，则称M为G中的一个完备匹配，此时若|V1|≤|V2|，则称M为V1到V2的一个完备匹配。定理9.7.3

设G=V1,V2,E是二部图，|V1|≤|V2|，G中存在V1到V2的完备匹配的充分必要条件是V1中每k个结点(k=1,2,…,|V1|)至少和V2中k个结点相邻接(该条件称为相异性条件)。

第一百五十七页，共一百八十七页，编辑于2023年，星期日定理9.7.4

设G=V1,V2,E是二部图，如果存在某一整数t＞0，使得V1中的每个结点至少关联t条边，而V2中的每个结点至多关联t条边。则G中存在V1到V2的完备匹配。证明：由定理的条件知，V1中任意k个结点(k=1,2,…,|V1|)至少关联kt条边。因为V2中的每个结点至多关联t条边，所以这kt条边至少关联于V2中的k个结点。于是二部图G满足相异性条件。由定理9.7.3可知，G有V1到V2的完备匹配。图9.64中的二部图满足定理9.7.4的条件。其中t=3。因此在图9.64中存在V1到V2的完备匹配。第一百五十八页，共一百八十七页，编辑于2023年，星期日第一百五十九页，共一百八十七页，编辑于2023年，星期日下列例题给出了完备匹配的一个应用。

【例9.17】在某大学本科毕业生分配的供需洽谈会上，有n个毕业生可从m(m≥n)个单位选择自己职业。已知每个毕业生至少愿意去r(1≤r≤m)个单位去工作，而每个用人单位至多看中了r–1个毕业生，愿意从中选择一名。问最多有多少个单位可以选择到满意的毕业生？写出判断过程。解：设V1=v|v为毕业生，V2=u|u为用人单位，

E=(v,u)|v