离散数学-图课件.ppt

,2023年3月14日,裘国永,离散数学第十章 图,本章内容及教学要点,10.1 图的基本概念教学内容：结点（顶点），边，无向边，有向边（弧），环（自回路），孤立结点，有向图，无向图，度数，出（入）度，欧拉握手定理,10.2 路、回路与连通性教学内容：路（通路），回路（圈），简单（回）路，基本（回）路，连通图，连通分支，点（边）割集，割（边），强（单向，弱）连通图，强（单向，弱）分图,10.4 欧拉图与哈密顿图 教学内容：欧拉（回）路，欧拉图，哈密顿（回）路，哈密顿图,10.6 平面图教学内容：平面图，面，边界，欧拉公式,10.7 树及其应用教学内容：树，树叶，分支点，生成树，最小生成树，Kruskal算法，Prim算法，根树，有序树，二叉树，树的遍历，最优二叉树，Haffman算法,10.9 最短路径教学内容：最短路径，Dijkstra算法,图论是以图为研究对象的一个数学分支。图论中的图指的是一些点以及连接这些点的线的总体。通常用点代表事物，用连接两点的线代表事物间的关系。图论则是研究事物对象在上述表示法中具有的特征与性质的学科。,在自然界和人类社会中，用图形来描述和表示某些事物之间的关系既方便又直观。例如，国家用点表示，有外交关系的国家用线连接代表这两个国家的点，于是世界各国之间的外交关系就被一个图形描述出来了。,另外我们常用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系（芯片设计）等等。,任何一个包含某种二元关系的系统都可以用图形来表示。由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要。由此经数学抽象产生了图的概念。研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。图是计算机中数据表示、存储和运算的基础。,图论的产生和发展经历了二百多年的历史，大体上可分为三个阶段：第一阶段是从1736年到19世纪中叶。当时的图论问题是盛行的迷宫问题和游戏问题。最有代表性的工作是著名数学家欧拉于1736年解决的哥尼斯堡七桥问题。,东普鲁士的哥尼斯堡城（今俄罗斯的加里宁格勒）位于普雷格尔（Pregel）河的两岸，河中有一个岛，于是城市被这条河、它的分支和岛分成了四个部分，各部分通过7座桥彼此相通。该城的居民喜欢在周日绕城散步。于是就产生了这样一个问题：能不能设计一条散步的路线，使得一个人从家里（或从四部分陆地任一块）出发，经过每座桥恰好一次再回到家里？这就是有名的哥尼斯堡七桥问题。,哥尼斯堡七桥问题看起来并不复杂，因此立刻吸引许多人的注意，但是实际上很难解决。瑞士数学家欧拉注意到了这个问题，并在1736年写的有关“哥尼斯堡七桥问题”的论文中解决了这个问题。这篇论文被公认为是图论历史上的第一篇论文，欧拉也因此被誉为图论之父。,欧拉是这样解决这个问题的：将四块陆地表示成四个点，桥看成是对应结点之间的连线。则哥尼斯堡七桥问题就变成了：从A，B，C，D任一点出发，通过每边一次且仅一次返回原出发点的路线（回路）是否存在？欧拉证明这样的回路是不存在的。,第二阶段是从19世纪中叶到1936年。一开始，图论的理论价值似乎不大，因为图论主要研究一些娱乐性的游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。但是随着一些图论中的著名问题如四色问题（1852年）和哈密顿环游世界问题（1856年）的出现，出现了以图为工具去解决其它领域中一些问题的成果。,1847年德国的克希霍夫将树的概念和理论应用于电网络研究。1857年英国的凯莱也独立地提出了树的概念，并应用于有机化合物分子结构即CnH2n+2的同分异构物数目的研究中。1936年匈牙利的数学家哥尼格写出了第一本图论专著有限图与无限图的理论，标志着图论成为一门独立学科。,第三阶段是1936年以后。由于生产管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现，大大促进了图论的发展。特别是计算机的大量应用，使大规模问题的求解成为可能。,电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及到的图形都是很复杂的，需要计算机的帮助才有可能进行分析和解决。目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域都有应用。,10.1 图的基本概念,这一节的主要内容：无（有）向边、环、孤立结点、无（有）向图、混合图、基图、简单图、多重图、平凡图、零图、完全图、加权图、度数、出度、入度、欧拉握手定理。,定义10.1.1 一个图G定义为一个有序对，记为G=。其中V为非空有限集，其元素称为结点或顶点（Vertex,Node），E也是有限集，其元素称为边（Edge）。对E中的每条边都有V中的两个结点与之对应，其结点对可以有序也可无序。,若边e与无序结点对u,v对应，称e为无向边（Undirected edge），简称边，记为e=u,v，u、v称为边e的端点，也称u和v为邻接点，边e关联u与v。关联同一结点的两条边称为邻接边。连接一结点与它自身的边称为环或自回路（Loop）。两条端点对应相同的边称为平行边。,若边e与有序结点对对应，称e为有向边或弧（Directed edge），记为e=，u和v分别称为弧e的始点（Initial vertex）和终点（Terminal vertex），也称u邻接到v，v邻接于u。若e和e有相同始点，称e和e相邻。始点和终点都对应相同的弧称为平行弧。,在图中不是任何边的端点的结点称为孤立结点（Isolated vertex）。每条边都是无向边的图称为无向图（Graph）。每条边都是有向边的图称为有向图（Digraph）。既有有向边又有无向边的图称为混合图。将有向图各有向边去掉方向后得到的无向图称为原图的基图（Underlying graph）。,例10.1.1 图10-1的两个图分别为无向图和有向图。在（a）中，e7是环，e1、e2与e3是邻接边。在（b）中，v2v1与v2v3是邻接边，但v2v3和v3v2不是邻接边，v5为孤立结点。,定义10.1.2（1）含有平行边（或弧）的图称为多重图（Multigraph）。不含平行边（或弧）和环的图称为简单图（Simple Graph）。（2）具有n个结点和m条边的图称为(n,m)图，也称n阶图。一个(n,0)图称为零图，(1,0)图称为平凡图。,（3）任两结点之间都有边（或弧）的简单图称为完全图（Complete graph）。n个结点的无向完全图记为Kn。,例10.1.2 在图10-2中，（a）是简单图且为完全图，但（b）是多重图，因为e4和e5是平行弧。,定理10.1.1 完全图Kn的边数为C(n,2)。,证明：因为在完全图Kn中任意两结点之间都有边相连，且n个结点中任取两点的组合数为C(n,2)，故完全图Kn的边数为C(n,2)。,定义10.1.3 给每条边（或弧）都赋予权的图G=称为带权图或加权图（Weighted graph），记为G=，W为各边（或弧）权的集合。,定义10.1.4 设G=、G=是两个图。（1）若VV且EE，则称G为G的子图（Subgraph），G为G的母图（Supergraph）。,（2）若G是G的子图，且VV或EE，则称G为G的真子图（Proper subgraph）。（3）若V=V且EE，则称G为G的生成子图或支撑子图（Spanning graph）。,定义10.1.5 G=，V1V且V1，以V1为结点集，以两端点均在V1中的全体边为边集的G的子图，称为V1的诱导子图；E1E且E1，以E1为边集，以E1中边关联的结点的全体为结点集的G的子图，称为E1的诱导子图。,定义10.1.6 若G=是一个n阶无向简单图，从Kn中删去G的所有边而得到的图称为G的补图或G的相对于完全图的补图，记为。,例10.1.3 在图10-3中，（b）、（c）、（d）都是（a）的子图，也是真子图。（b）和（c）是（a）的生成子图。（d）既是结点集v2,v3,v4的诱导子图，也是边集v2,v3，v2,v4，v3,v4的诱导子图。（b）和（c）互为补图。,定义10.1.7 在有向图G=中，对于结点vV，以v为始点的弧的条数称为v的出度（Outdegree），记为d+(v)；以v为终点的弧的条数称为v的入度（Indegree），记为d-(v)；v的出度和入度之和称为v的度数（Degree），记为d(v)。,在无向图G=中，结点v的度数等于它关联的边数，记为d(v)。若v有环，规定该结点度数因环而增加2。,例10.1.4 在图10-1（a）中，d(v1)=3，d(v2)=5，在图10-1（b）中，d+(v2)=2，d-(v2)=1。,定理10.1.2（握手定理）在图G=中，结点度数的总和等于边数的两倍，即 2|E|=。,证明：因为图G中的每条边（包括环）都有两个端点，所以加上一条边就使各结点度数总和增加2，因此图G中结点度数的总和等于边数的两倍，即=2|E|。,推论 图中度数为奇数的结点必为偶数个。,定理10.1.3 在任何有向图中，所有结点的入度之和等于所有结点的出度之和。,证明：因为每一条有向边必对应一个入度和一个出度，若某个结点具有一个入度或出度，则必关联一条有向边，所以有向图中各结点入度之和等于边数，各结点出度之和等于边数，故结论成立。,定义10.1.8 无向图中度数为1的结点称为悬挂结点，它对应的边称为悬挂边。各结点度数均相同的图称为正则图。各结点度数均为k的图称为k度正则图。,定理10.1.4 设G为任意n阶无向简单图，则每个结点的度数都不超过n-1。,证明：因G无平行边也无环，所以G中任意结点v至多与其余n-1个结点相邻，于是d(v)n-1。,定义10.1.9 对无向图（或有向图）G1=和G2=，若有双射f：V1V2，使得对任意u、vV1，有u,vE1 f(u),f(v)E2(或E1 E2)，且其重数相同，则称G1同构于G2，记为G1G2。若G与其补图同构，称G为自补图。,例10.1.5 在图10-5中，(a)和(b)是同构的。因为可作映射g，使得g(1)=v3，g(2)=v1，g(3)=v4，g(4)=v2。在映射g下，边，和分别映射到，和。,若两个图同构，则它们的结点数相同，边数相同，度数相同的结点数相同等等。但这并不是图同构的充分条件，如在图106中，(a)和(b)虽然满足以上3条件但不同构。(a)中的x应与(b)中的y对应，因为度数都是3。但(a)中的x与两个度数为1的结点u、v邻接，而(b)中的y仅与一个度数为1的结点w邻接。,例10.1.6（1）画出4阶3条边的所有非同构无向简单图；（2）画出3阶2条边的所有非同构有向简单图。,解：（1）由握手定理可知，所画的无向简单图各结点度数之和为23=6，最大度数小于或等于3。于是所求无向简单图的度数列应满足的条件是：将6分成4个非负整数，每个整数均大于或等于0且小于或等于3，并且奇数个数为偶数。将这样的整数列排列出来只有下列三种情况：,3，1，1，1 2，2，1，1 2，2，2，0,所要求的全部非同构的图，如图10-7所示。,（2）由握手定理可知，所画的有向简单图各结点度数之和为4，且最大出度和最大入度均小于或等于2。故度数列与入度列、出度列分别为：度数列：1，2，1：入度列为0，1，1；0，2，0或1，0，1；出度列为1，1，0；1，0，1或0，2，0。,度数列：2，2，0 入度列为1、1、0；出度列为1、1、0；四个所求有向简单图如图10-8所示。,10.2 路、回路和连通性,这一节的主要内容：路、回路、简单路、基本路、简单回路、基本回路、结点之间的可达性、连通图、连通分支、点割集、割点、边割集、割边、强连通、单向连通、弱连通。,定义10.2.1 给定图G=，设v0，vmV，边（或弧）e1，e2，emE，其中vi-1、vi是ei的端点（始点和终点），交替序列v0e1v1e2emvm称为连接v0到vm的路或通路（Path），通常简记为v0v1vm。路上边的数目称为该路的长度。当v0=vm时，称其为回路（Cycle，Circuit）。,定义10.2.2 在一条路中，若出现的所有边（或弧）互不相同，称其为简单路或迹；若出现的结点互不相同，称其为基本路或初级通路（Simple path）。,定义10.2.3 在一条回路中，若出现的每条边（或弧）恰好一次，称其为简单回路；若出现的每个结点恰好一次，称其为基本回路或初级回路或圈（Simple cycle）。,定理10.2.1 在一个图中，若从结点u到v存在一条路，则必有一条从u到v的基本路。,证明：（构造性证明方法）若u到v的路已是基本路，结论成立。否则，在u到v的路中至少有一个结点比如w重复出现，于是经过w有一个回路C，删去回路C上的所有边（或弧）。若得到的u到v的路上仍有结点重复出现，则续行此法，直到u到v的路上没有重复的结点为止，此时所得即是基本路。,例10.2.1 在图10-9中，v1v2v3v2v4是一条简单路但不是基本路，v1v2v3v4是一条基本路；v1v2v3v2v4v1是一简单回路但不是基本回路，v1v2v3v4v1是一基本回路。,定理10.2.2 在n阶图中，任何基本路的长度均不大于n-1，任何基本回路的长度均不大于n。,证明：在n阶图中，因为任何基本路和基本回路中都最多有n个结点，所以任何基本路的长度均不大于n-1，任何基本回路的长度均不大于n。,定义10.2.4 在一个图中，若从u到v存在路，或u=v，则称从u到v是可达（Accessible）。,定义10.2.5 若无向图G中任意两个结点之间都是可达的，则称G为连通图（Connected graph），否则称G为非连通图（Disconnected graph）。一个图G的连通分支数记为(G)。连通分支就是图中具有连通性的最大子图。,定理10.2.3 若G是n阶m条边的连通无向图，则mn-1。该定理的逆否命题可用来判定一个图不连通。,例10.2.2 在图10-10中，（a）是连通的，而（b）是不连通的，其连通分支数为3。,定义10.2.6 设G=是无向连通图，若SV，使G删除S（将S中结点及其关联的边都一起删除）后所得子图G-S不连通，但删去S的任一个真子集所得子图仍是连通的，则称S是G的一个点割集。若G的点割集S=v，称v是G的割点（Cut vertex）。,若TE，使G删除T（将T中的边从G中全删除）后所得子图G-T不连通，但删去T的任一个真子集所得子图仍是连通的，则称T是G的一个边割集。若G的边割集T=e，称e是G的割边或桥（Cut edge，Bridge）。,例10.2.3 在图10-11中，v3是割点；v1,v3,v2,v3是边割集，但没有割边。,定理10.2.4 一个连通无向图G中的结点v是割点 存在结点u和w，使得连接u和w的每条路都经过v。,证明：充分性。若连通图G存在结点u和w，使得连接u和w的每条路都经过v，则在子图G-v中u和w必不可达，故v是G的割点。,必要性。若v是G的割点，则G-v至少有两个连通分支G1=和G2=。现取uV1，wV2。因为G连通，故在G中必有连接u和w的路。对任一条连接u和w的路，由于u、w在G-v中不可达，因此必通过v。故u和w之间的任意路必经过v。,定理10.2.5 一个连通无向图G中的边e是割边 存在结点u和w，使得连接u和w的每条路都经过e。,定理10.2.6 无向图G的边e是割边 e不包含在图的任何基本回路中。,证明：e=x,y是连通图G的割边当且仅当x、y在G-e的不同连通分支中，而后者等价于在G-e中不存在x到y的路，从而等价于e不包含在图的任何基本回路中。于是定理得证。,定义10.2.7 在简单有向图G中，若任何两个结点之间是相互可达的，则称G是强连通的（Strongly connected）；若任何两个结点之间，至少从一个结点到另一个结点是可达的，则称G是单向连通的或单侧连通的（Unilaterally connected）；若有向图G的基图是连通的，则称G是弱连通的（Weakly connected）。,由定义可知，强连通图一定是单向连通的，单向连通图一定是弱连通的，但反之不然。,例10.2.4 在图10-12中，（a）是强连通的，（b）是单向连通非强连通的，（c）是弱连通非单向连通的。,定理10.2.7 有向图G是强连通的 G中有一回路，它至少通过每个结点一次。,证明：充分性。如G中有一回路，它至少通过每个结点一次，则G中任意两个结点相互可达，故G是强连通的。必要性。如有向图G是强连通的，则任意两个结点相互可达。设V=v1,v2,vn，i为vi到vi+1的路，n为vn到v1的路，则1、2、n-1、n所围成的回路至少通过每个结点一次。,定义10.2.8 在图G中，结点u到结点v的最短路的长度称为u到v的距离，记作d。如u到v没有路，则d=+。它具有下列性质：d0（非负性）d=0 d+dd（三角不等式）注 u与v相互可达，d未必等于d。,10.4 欧拉图和哈密顿图,这一节的主要内容：欧拉回路、欧拉路、欧拉图、哈密顿回路、哈密顿路、哈密顿图。,定义10.4.1 通过G的每条边恰好一次的路称为欧拉路（Euler path）。通过图G的每条边恰好一次的回路称为欧拉回路（Euler cycle）。具有欧拉回路的图称为欧拉图（Euler graph）。约定平凡图为欧拉图。,例10.4.1 在图10-18中，（a）有欧拉路但无欧拉回路，（b）有欧拉回路，（c）既无欧拉路也无欧拉回路。,定理10.4.1 连通无向图G有欧拉回路 G中每个结点都是偶数度结点。,证明：必要性。若连通无向图G有欧拉回路，设C是G的一条欧拉回路，则C通过G的任一结点时必通过关联该点的两条边，而G中每条边仅出现一次，所以C所通过的每个结点必为偶数度结点。,充分性。若G中每个结点都是偶数度结点，因G连通，所以G中至少含有一个基本回路C1，从G中删除C1上的各边得到子图G1。若G1中仍然有边，由G1每个结点仍为偶数度结点，则可得基本回路C2，且C1与C2有一个公共结点。续行此法，直到删去G中的所有边。于是得到一系列基本回路C1，C2，Cm，且 Ck与Cj有一个公共结点，则可由C1，C2，Cm构成一个欧拉回路。,定理10.4.1不仅给出了欧拉图的判定方法，而且也给出了构造欧拉回路的方法。,例10.4.2 图G=如图10-19所示，构造其欧拉回路。,解：在G中取基本回路C1：v1v2v3v4v5v1，对于图G-C1，又可取基本回路C2：v1v3v5v2v4v1，C1与C2的公共结点为v1，因为图G-C1-C2已没有边，所以得到的欧拉回路为：v1v2v3v4v5v1v3v5v2v4v1。,定理10.4.2 连通无向图G=，u、vV且uv，u与v之间存在欧拉路 G中仅有u和v为奇数度结点。,证明：对G加上一条边u,v得到新图G1，G中u和v之间存在欧拉路 G1中有欧拉回路 G1中每个结点为偶数度结点 G除u、v外其余结点均为偶数度结点 G仅有u和v为奇数度结点。,定理10.4.3 强连通有向图G有欧拉回路 G中的每个结点的入度等于出度。,定理10.4.4 单向连通有向图G=，u、vV且uv，u与v存在欧拉路 G中唯有u和v的入度不等于出度，且u的出度比其入度大1，v的出度比其入度小1。,与欧拉回路类似的是哈密顿回路问题。它是1859年哈密顿首先提出的一个关于12面体的数字游戏：能否在12面体中找出一条回路，使它通过图中所有结点一次且仅一次？将12面体画作与其同构的平面图，如图10-20所示。,定义10.4.2 经过图中每个结点恰好一次的路称为哈密顿路（Hamiltonian path）。经过图中每个结点恰好一次的回路称为哈密顿回路（Hamiltonian cycle）。具有哈密顿回路的图称为哈密顿图（Hamiltonian graph）。,例10.4.3 在图10-21中，（a）有哈密顿路但无哈密顿回路，（b）既有哈密顿路又有哈密顿回路，（c）既无哈密顿路也无哈密顿回路。,定理10.4.5 若连通图G=是哈密顿图，S是V的任意真子集，则(G-S)|S|。,证明：若连通图G=是哈密顿图，设C是G的哈密顿回路，则C-S是G-S的生成子图，所以(G-S)(C-S)。易知当S中的结点互不邻接时，C-S的连通分支数达到最大值|S|，所以有(C-S)|S|。故(G-S)|S|。,推论 若连通图G=存在哈密顿路，S是V的任意真子集，则(G-S)|S|+1。定理10.4.5给出了图是哈密顿图的必要条件，因此该定理的逆否命题可用来判断一个图不是哈密顿图，这是它的价值所在。,例10.4.4 说明图10-22所示的图不是哈密顿图。,解：取S=v2,v6，则G-S有3个连通分图，(G-S)|S|，由定理10.4.5知，图10-22所示的图不是哈密顿图。,定理10.4.6 G=是n阶简单图，n3，则：（1）如任两不相邻结点u、vV，均有d(u)+d(v)n-1，则在G中存在一条哈密顿路。（2）如任两不相邻结点u、vV，均有d(u)+d(v)n，则G是哈密顿图。,定理10.4.6只是一个充分条件，但反过来未必成立。例如，六边形的图是哈密顿图，但不满足定理的条件。,例10.4.5 某地有5个风景点，若每个风景点均有两条道路与其他景点相通，问是否可经过每个风景点恰好一次而游玩这5处？,解：将风景点作为结点，连接风景点的路作为边，则得到一个无向图G。由题意可知，对G中每个结点均有d(v)=2。于是对任意u、vG，有d(u)+d(v)=2+2=4=5-1，所以该图有一哈密顿路，故本题有解。,10.6 平面图,这一节的主要内容：平面图、面、边界、欧拉公式。,定义10.6.1 如把无向图G画在平面上，任意两条边除端点外均不相交，称G为平面图（Planar graph）。,例10.6.1 K2、K3、K4都是平面图，完全二部图K1,n（n1）、K2,n（n2）也是平面图。在研究平面图理论中有两个十分重要的图，就是被称为库拉图斯基图的完全二部图K3,3和完全图K5，它们都不是平面图。其中，K3,3是边数最少的非平面图，K5是结点数最少的非平面图。,由定义我们不难得出：平面图的任何子图都是平面图；非平面图的任何母图都是非平面图；图中的平行边和环并不影响图的平面性。因为当且仅当一个图的每个连通分支都是平面图时，这个图才是平面图。所以，在研究平面图的性质时，只讨论连通平面图。,定义10.6.2 设G为连通平面图，G的边将G所在的平面划分成若干区域，每个区域称为G的一个面（Face），记为f。包围这个区域的各条边构成的回路称为面f的边界（Boundary），其回路的长度称为面f的次数或度数（Degree），记为d(f)。区域有限的面称为有限面，区域无限的面称为无限面。,显然，任何连通平面图只有一个无限面。,例10.6.2 在图10-27中，共有3个面f1、f2、f3。其中，面f1由回路v1v2v3v4v5v6v5v4v1所围，面f2由回路v1v4v7v1所围，面f3由回路v1v2v3v4v7v1所围，所以d(f1)=8，d(f2)=3，d(f3)=5。,定理10.6.1 设G=是连通平面图，F是G的面的集合，则=2|E|。,证明：因为G中每条边无论作为两个面的公共边界，还是作为一个面的边界，在计算总的次数时都计算2次，所以结论成立。,定理10.6.2 设G是n（n3）阶简单连通平面图，则G的每个面的次数大于等于3。,证明：因为G的任意一个面上至少有3个结点，所以G的每个面的次数都大于等于3。,定理10.6.3（欧拉公式）若G为连通平面图，则n-m+r=2，其中，n、m、r分别为G的结点数、边数和面数。欧拉公式是平面图的基本而重要的公式，它反映了平面图的结点数、边数和面数之间的关系。,证明：对G的边数m作归纳。当m=0时，由于G是连通图，所以G为平凡图，此时n=1，r=1，结论自然成立。假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。,设e是G的一条边，从G中删去e后得到的图记为G，并设其结点数、边数和面数分别为n、m和r。对e分下列情况来讨论：,若e为割边，则G有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1+n2=n=n，m1+m2=m=m-1，r1+r2=r+1=r+1。由归纳假设有n1-m1+r1=2，n2-m2+r2=2，从而(n1+n2)-(m1+m2)+(r1+r2)=4，n-(m-1)+(r+1)=4，即n-m+r=2。,若e不为割边，则n=n，m=m-1，r=r-1，由归纳假设有n-m+r=2，从而n-(m-1)+r-1=2，即n-m+r=2。由数学归纳法知，结论成立。,定理10.6.4 若G是连通的平面图，且G的每个面的次数至少为l（l3），则G的边数m与结点数n有如下关系：。,证明：设G有r个面，则2m=lr。由欧拉公式得，n-m+r=2。于是，。,定理10.6.5 设G是n（n3）阶m条边的简单连通平面图，则m3n-6。,证明：因为G是一个简单连通平面图，所以G任意面的次数d(f)3。由定理10.6.4可得m3n-6。,上述定理是判别平面图的必要条件，而不是充分条件。也就是说，即使一个图满足上述不等式，也未必是平面图，但使用上述定理的逆否命题可以判别一个图不是平面图。,例10.6.3 证明K5不是平面图。,证明：若K5是一个平面图，由于K5有5个结点10条边，则35-6=910，与定理10.6.5矛盾。所以，K5不是平面图。,例10.6.4 证明K3,3不是平面图。,证明：若K3,3是平面图，因为在K3,3中任取三个结点，其中必有两个结点不相邻，故每个面的次数大于等于4，于是4/(4-2)(6-2)=89，与定理10.6.4矛盾。所以，K3,3不是平面图。,判断一个图是否为平面图是一件困难的事。通常我们可以采用直观的方法，即：在图中找出一个长度尽可能大的且边不相交的基本回路；然后将图中那些相交于非结点的边，适当放置在已选定的基本回路内侧或外侧，若能避免除结点之外边的相交，则该图为平面图，否则便是非平面图。例如，K5不是平面图，因为无论如何画都不能使其所有边不相交。另外，也可以采用下面的方法来判断。,定义10.6.3 若G2可由在G1中的一些边上适当插入或涂抹度为2的有限个结点后而得到，则称G1与G2同胚或在2度结点内同构（Homeomporphism）。,例10.6.5 图10-29所示的两个图形是同胚的。,定理10.6.6（库拉图斯基图定理）一个图G是平面图 G中不含同胚于K3,3或K5的子图。,10.7 树及其应用,这一节的主要内容：树、生成树、弦、生成树的权、最小生成树、Kruskal算法、Prim算法、根树、有序树、二叉树、Huffman算法、前缀码。,定义10.7.1 连通无回路的无向图称为无向树（Tree），简称树，常用T表示。注 这里的回路指的是简单回路。,在树中，悬挂结点称为树叶，度数大于1的结点称为分支点或内结点（Branching vertex），悬挂边称为叶边。连通分支数大于1，且每个连通分支都是树的无向图称为森林。,例10.7.1 在图10-31中，（a）和（b）是树，（c）是森林。,由定义不难得出，树一定是连通的简单平面图。,定理10.7.1 设T=是n阶m条边的无向图，则下面命题等价：（1）T是树。（2）T无回路且m=n-1。（3）T连通且m=n-1。（4）T连通且T的每条边都是割边。（5）T无回路，但任意增加一条边产生惟一一条回路。（6）T中每对结点间恰有一条基本路。,证明：（1）（2）。只需证m=n-1。因为T是树，所以T是连通平面图，且T只有一个无限面，由欧拉公式得n-m+1=2，即m=n-1。,（2）（3）。只需证T连通。对n用数学归纳法证明。若n=2，则命题显然成立。假设当n=k时命题成立。则当n=k+1时，由于G无回路且m=n-1，所以一定存在度为1的结点（否则G中除了孤立结点之外，其他结点的度数都至少是2。从而G一定存在基本回路，得出矛盾）。,不妨设v是G的度为1的结点，删去v及以v为端点的边得到图G1。图G1有k个结点且k-1条边，从而由归纳假设可知，图G1连通。从而G也连通。,（3）（4）。只需证T的每条边都是割边。任取T的边e，则T-e的边数为m-1，结点数为n，于是m-1=n-2n-1，所以T-e是不连通的，因而e是割边。故T的每条边都是割边。,（4）（5）。由于T的每条边都是割边，因而T中无回路。在T中添加新边u,v，由T是连通的，则存在u到v的一条路，于是+u,v构成一回路。若得到的回路不惟一，不妨记为1和2，则1-u,v与2-u,v构成一回路，其经过的边都不是割边，矛盾。故在T中任意增加一条边产生惟一一条回路。,（5）（6）。若T中存在两个结点u和v，它们之间不存在路，则添加边u,v不产生回路，矛盾。所以T中任意两个结点之间存在基本路。若u和v之间存在两条不同的基本路1和2，则由1和2可以得到一条基本回路，矛盾。所以T中每对结点间恰有一条基本路。,（6）（1）。因为T中每对结点间恰有一条基本路，所以T是连通的。若T有回路，则回路经过的任意两个结点之间存在两条路，矛盾，所以T没有回路。因此，T是树。,由于树少一边就不连通，多一边就有回路，所以树是以“最经济”的方式把各结点连接起来的图。因此，它可以用作典型的数据结构，各类网络的主干网也通常都是树结构。,定理10.7.2 若T=是树，且|V|2，则T中至少存在两片树叶。,证明：由T是树得，|E|=|V|-1。设T有k片树叶，应用握手定理可得2|E|=2(|V|-1)=k+2(|V|-k)，于是k2。,定义10.7.2 若T是连通无向图G的生成子图且是树，则称T是G的生成树（支撑树，Spanning tree）。G在T中的边称为T的树枝，G不在T中的边称为T的弦。,例10.7.2 在图10-32中，（b）是（a）的生成树，而（c）不是。,定理10.7.3 无向图G=有生成树当且仅当G是连通的。,证明：必要性。设T=是G的生成树，则有VT=V。由于T是连通的，所以G是连通的。,充分性。若G中无回路，则G本身就是一棵生成树。若G中有回路，删去回路上的一条边得到图G1，G1仍是连通的且与G有相同的结点集。若G1还有回路，就再删去此回路上的一条边得到图G2，G2是连通的且与G有相同的结点集。续行此法，直到得到连通图T，它无回路且与G有相同的结点集，T就是G的生成树。,定理10.7.4 若T是连通图G的任意生成树，则G的每个边割集和T至少有一条公共边。,证明：若G的边割集与T没有公共边，那么删去这个边割集后所得子图必包含该生成树，这意味着删去边割集后G仍然是连通的，与边割集的定义矛盾。,定义10.7.3 设连通无向带权图G=，T是G的一棵生成树，T的各边带权之和称为T的权（Weight），记为(T)。G的所有生成树中带权最小的生成树称为最小生成树（Minimal spanning tree）。,下面介绍求最小生成树的两种算法：Kruskal算法和Prim算法。设G=是n阶m条边的连通无向带权图。,Kruskal算法（克鲁斯克尔算法）描述如下：（1）在G中选取最小权边e1，并置边数i=1；（2）当i=n-1时结束，否则转向（3）；（3）设已选择的边为e1，e2，ei，在G中选取不同于e1，e2，ei的边ei+1，使得ei+1是满足与e1，e2，ei不构成回路且权值最小的边。（4）置i为i+1，转向（2）。,由于Kruskal算法在求最小生成树时，初始状态为n个结点，然后逐步加边，这个过程中一直要避免回路的产生，所以又称其为“避圈法”。,Prim算法（普里姆算法）描述如下：（1）在G中任意选取一结点v1，并置U=v1，置最小生成树的边集TE=；（2）在所有uU，vV-U的边u,vE中，选取权值最小的边u,v，将u,v并入TE，同时将v并入U；（3）重复（2）直到U=V为止。,例10.7.3 分别用克鲁斯克尔算法和普里姆算法求下列赋权图的最小生成树。,解：用克鲁斯克尔算法求最小生成树的过程如下：,得到最小生成树为：,解：用普里姆算法求最小生成树：,得到最小生成树为：,若有向图D的基图是一棵树，则称D为有向树。在所有的有向树中，根树最重要，所以我们只讨论根树。,定义10.7.4 给定一棵有向树，若只有一结点的入度为0，其余结点的入度都为1，称其为根树（Rooted tree）。入度为0的结点称为树根，入度为1出度为0的结点称为树叶；入度为1出度大于0的结点称为内结点。内结点和树根通称为分支点。从树根到其某个结点的路径长度，称该结点的级或层次（Level），其最大者称为有向树的树高。,一棵根树可看成一棵家族树，若a邻接到b，称b为a的儿子，a为b的父亲。若b、c同为a的儿子，称b、c为兄弟。若ab，而a可达b，称a为b的祖先，b为a的子孙。若根树的一个子图也是树，则称其为根树的子树。,在根树中，由于各有向边的方向是一致的，所以画根树时可以省去各边的方向，并将树根画在最上方，将分支点和树叶依次画在下方。因此，根树具有很好的层次结构。,例10.7.4 在图10-35中，v0是树根，v1、v2、v6是内结点，v3、v4、v5、v7、v8是树叶，v5、v6是v2的儿子，v2是v5、v6的父亲，v5和v6是兄弟。,定义10.7.5 将根树每一级上的结点规定次序，这样的根树称为有序树（Ordered rooted tree）。,定义10.7.6 T为一棵根树，若T的每一分支结点至多有m个儿子，称T为m叉树（m-ary tree）。若T的每一分支结点恰有m个儿子，称T为完全m叉树。若所有叶结点级相同，称T为正则m叉树。,定理10.7.5 设有完全m叉树，其叶子数为t，分支点数为i，则(m-1)i=t-1。,证明：由已知可知，该树共有t+i个结点，共有mi条边，于是mi=t+i-1，即(m-1)i=t-1。,例10.7.5 假设有一台计算机，它有一条加法指令，可同时计算三个数的和。如果要计算九个数的和，至少需要执行几次加法指令？,解：若用每个树叶表示一个数，内结点表示3个数的和，则上述问题可抽象为一个完全3叉树。由定理10.7.5有(3-1)i=9-1，i=4，即至少需要执行4次加法指令。,应用最广泛的是二叉树。,对于二叉树，一个十分重要的问题是访问所有树的结点，这就是二叉树的遍历问题（Traversal）。下面介绍二叉树遍历的3种方法：（1）先序遍历法：访问树根、先序遍历左子树、先序遍历右子树；（2）中序遍历法：中序遍历左子树、访问树根、中序遍历右子树；（3）后序遍历法：后序遍历左子树、后序遍历右子树、访问树根。,例10.7.6 对图10-37所示二叉树的遍历结果如下：（1）先序遍历法：a(b(cde)f)(igh)。（2）中序遍历法：(dce)bf)a(gih)。（3）后序遍历法：(dec)fb)(ghi)a。,定理10.7.6 具有n个结点的完全二叉树T的树叶数为t=(n+1)/2。,证明：设T的树叶数为t，则其分支点为n-t，故其边数为2(n-t)，于是2(n-t)=n-1，即t=(n+1)/2。,定义10.7.7 设二叉树T有t片树叶，分别带权1，2，t，称(T)=为T的权，其中L(i)为从根结点到带权i的树叶的通路长度。在所有带权1，2，t的二叉树中，带权最小的二叉树称为最优二叉树。,定理10.7.7 设T为带权12t的最优二叉树，则（1）带权1，2的树叶v1，v2是兄弟；（2）以树叶v1，v2为儿子的分支点，其通路长度最长。,定理10.7.8 设T为带权12t的最优树，若将以带权1和2的树叶为儿子的分支点改为带权1+2的树叶，得到一棵新树T，则T也是最优树。,证明：根据题设，(T)=(T)+1+2。若T不是最优树，则必有另一棵带权1+2，3，t的最优树T使得(T)(T)。,对T中带权1+2的树叶生成两个儿子，得到新树T*，则(T*)=(T)+1+2。因为(T)(T)，则(T*)=(T)+1+2(T)+1+2=(T)，与T