大学计算机数学基础-何春江-大学教学资料课件PPT
收藏
资源目录
压缩包内文档预览：
编号：21836117
类型：共享资源
大小：19.74MB
格式：ZIP
上传时间：2019-09-06
上传人：QQ24****1780
认证信息
个人认证
王**（实名认证）
浙江
IP属地：浙江
25
积分
- 关 键 词：
-
大学计算机
数学
基础
何春江
大学
教学
资料
课件
ppt
- 资源描述：
-
大学计算机数学基础-何春江-大学教学资料课件PPT,大学计算机,数学,基础,何春江,大学,教学,资料,课件,ppt
- 内容简介：
-
第13章 图论初步本章学习目标 我们在前面曾介绍过二元关系的图形表示，即关系图。在关系图中，我们主要关心研究对象之间是否有连线（图论中称为边），这样的图正是图论的主要研究对象。图论中还根据实际需要，将这类图进行了推广，并且把它当作一个抽象的数学系统来进行研究。通过本章学习，读者应该掌握以下内容：本章学习目标 无向图、有向图的定义，图的基本术语的含义子图、生成子图的概念无向连通图及有向连通图的有关概念通路、回路的概念图的矩阵表示赋权图的概念及应用欧拉通路、欧拉回路、欧拉图和半欧拉图的概念哈密尔顿通路、哈密尔顿回路、哈密尔顿和半哈密尔顿的概念树的定义最小生成树的求法最优树的求法主要内容 13.1 图的基本概念 13.2 图的矩阵表示13.3 路与回路13.4 树及其应用 13.1 图的基本概念13.1.1 图的定义 定义13.1.1 图G是一个三元组，G=，其中V(G)是一个非空的顶点集合，E（G）是边的集合，G是从边集合E到顶点无序偶或有序偶集合上的函数。 由定义可知，图G中的每条边都与图中顶点的无序偶或有序偶相联系，若边eE与顶点无序偶vi，vj相联系，则G（e）=vi，vj，此时边e称为无向边，有时简称边；若边eE与顶点有序偶相联系，则G（e）=，此时边e称为有向边或弧。vi称为弧的始点，vj称为弧的终点，有向边的箭头方向自始点指向终点。 13.1 图的基本概念13.1.1 图的定义 例13.1.1 画出下面二图的图形（1）无向图，其中 13.1 图的基本概念13.1.1 图的定义 例13.1.1 画出下面二图的图形（）有向图，其中 13.1 图的基本概念13.1.1 图的定义 例13.1.1 画出下面二图的图形 解：(1)的图形为13.1-3（a）所示，（2）的图形为13.1-3（b）所示。 13.1 图的基本概念 定义 设无向图 （1）如果在顶点和顶点之间存在一条边，即若存在且=(u,v)，则称顶点u和顶点v是彼此相邻的，简称相邻的，并称顶点u和顶点v是边e的端点，e与u（或e与v）是彼此关联的。（2）若ek,el至少有一个公共端点，则称边ek,el是彼此相邻的，简称相邻的。13.1 图的基本概念13.1.2 顶点的度数 定义13.1.2 设无向图G，v是图G中的顶点，所有与v关联的边的数目，称为顶点v的度数，记作deg(v)。 度数为零的点称为孤立点，度数为1的点称为悬挂点，与悬挂点关联的边称为悬挂边。 定理13.1.1 设图G是具有n个点，m条边的无向图，其中顶点集合为V=v1，v2，vn，则推论 度数为奇数的顶点个数为偶数。13.1 图的基本概念定义13.1.3 设有向图G，v是图G中的顶点，以v为始点的有向边的数目，称为v的出度，记个deg+(v)，以v为终点的有向边的数目，称为v的入度，记作deg-(v)。 定理13.1.2 设有向图G具有n个顶点，m条边，其中顶点集合V=v1，v2，vn，则有证明 因为每一条有向边为始点提供1个出度，为终点提供1个入度，而所有各顶点的出度之和及入度之和均由m条有向边提供，所以定理得证。 13.1 图的基本概念13.1.3 多重图、简单图与完全图 定义13.1.4 如果两个顶点之间存在多条边（对于有向图，则有多条同方向的边），则称这些边为平行边，两相顶点a，b间平行边的条数称为边的重数。含有平行边的图称为多重图，不含平行边和自回路的图称为简单图。当图中顶点的数目为有限个数时，称为有限图，否则称为无限图。本章仅讨论有限图。 定义13.1.5 在n阶无向（无向）图中，如果任意两个不同的顶点之间都有一条边关联，则称此图为n阶无向（无向）完全图，记作Kn。13.1 图的基本概念13.1.2多重图、简单图与完全图 如在图13.1-5中（a）和（b）均为4阶完全图。 13.1 图的基本概念13.1.2多重图、简单图与完全图 定理13.1.3 n阶无向完全图Kn的边数为证明 在Kn中，因为任意两个顶点间都有边联结，所以Kn的边数为n个顶点中取两个顶点的组合数：即，Kn的边数为。 定理13.1.3 n阶无向完全图Kn的边数为。 13.1 图的基本概念13.1.4 子图定义13.1.6 设G=和G=是两个图，（1）若VV且EE，则称G是G的子图；（2）若G是G的子图，但VV或EE，则称G是G的真子图；（3）若G是G的子图，且V=V，则称G是G的生成子图或支撑子图。从上面的定义可以看出，对图G=，G本身和零图G=都是它的生成子图，它们称为G的平凡生成子图。 13.1 图的基本概念13.1.4 子图如图13.1-6，（a）是（b）的子图且是真子图。 13.1 图的基本概念13.1.4 子图如在图7.1-6中，（a）是（b）的一个生成子图。 13.2 图的矩阵表示 13.2.1 图的邻接矩阵表示定义13.2.1 设图G的顶点集合为V，边集为E，且 V=v1，v2，vn，令aij=则称矩阵Aaij为图G的邻接矩阵。13.2 图的矩阵表示13.2.1 图的邻接矩阵表示图13.2.1 有向图G例如，图13.2.1的邻接矩阵为：图13.2.113.2 图的矩阵表示13.2.1 图的邻接矩阵表示从图G的邻接矩阵中，还可以得到图的很多重要的性质：（1）令B=A2，则有 bij= ，bij表示从vi到vj长度为2的通路数目。如果bij=0，则表示不存在长度为2的通路。而bii表示经过vi的长度为2的回路数目。（2）令C=Ar，则此时cij表示从vi到vj长度为r的通路数目。如果cij=0，则表示不存在长度为r的通路。而cii表示经过vi的长度为2的回路数目。13.2 图的矩阵表示13.2.2 图的关联矩阵表示 定义13.2.2 设无环无向图G=，V=v1，v2，vn，E=e1，e2，em，则矩阵M（G）=（mij）nm，其中 mij=称M（G）为完全关联矩阵。图13.2.3 例如，图13.2.3所示的无向图G的关联矩阵为：M（G）= e1 e2 e3 e4 e5 e613.2 图的矩阵表示关联矩阵与图是相互唯一确定的，因而M（G）也描述了G的一切特征，从关联矩阵可以看出图形的一些性质：（1）M（G）中的每一列只有两个1，说明图中每一条边关联两个顶点。（2）M（G）中每一行元素的和数对应顶点的度数。一行中元素全为0，其对应的顶点为孤立顶点。（3）M（G）中，若两列相同，则它们对应的边为平行边。 13.2.2 图的关联矩阵表示 13.2 图的矩阵表示13.2.2 图的关联矩阵表示 定义13.2.3 设简单有向图G=，V=v1，v2，vn，E=e1，e2，em，则矩阵M（G）=（mij）nm，其中称M（G）为G的完全关联矩阵。mij = 13.2 图的矩阵表示有向图的完全关联矩阵也有类似于无向图的一些性质。如：（1）关联矩阵中每列的元素之和为0，说明有向图中每条边关联两个顶点，一个始点，一个终点。（2）第i行元素的绝对值之和为对应顶点的度数，其中1的个数为出度，-1的个数为入度。（3）关联矩阵中，1的个数与-1的个数相同，都等于边的数目，这说明有向图中各顶点入度之和等于出度之和，都等于边数，于是各顶点度数之和等于边数的2倍。（4）若关联矩阵中有两列相同，说明图中这两列对应的边有相同的始点和终点，因而它们是平行边。13.2.2 图的关联矩阵表示 13.2.3 图的可达矩阵表示 定义13.2.4 设n阶简单有向图G=，V=v1，v2，vn，令pij=则称矩阵Ppij为图G的可达矩阵。记作P（G），简记为P。可达性矩阵表明图中任意两个顶点间是否至少存在一条路以及在任何顶点上是否存在回路。可通过图G的邻接矩阵A得到G的可达性矩阵P，令Rn=（rij）nn，Rn=A+A2+A3+An将Rn中不为0的元素改为1，为0的元素不变，这个改变后的矩阵即为可达性矩阵P。例13.2.2 求图G=的可达性矩阵，其中V=v1，v2，v3，v4，E=，。解 图G的邻接矩阵为A=A2= A3=A4=故 R4= P=13.2.3 图的可达矩阵表示13.3 路与回路 13.3.1 通路与回路定义13.3.1 在无向图（或有向图）G=中，设v0，v1，vnV，e0，e1，enE，其中ei是关联于顶点vi-1，vi的边，交替序列v0e0v1e1en-1 vn称为联结v0到vn的通路或路。v0和vn分别称为通路的起点和终点，通路中所含边的条数称为该通路的长度。如果通路中的始点与终点相同，则称这条路为回路。 下面介绍两种常用的特殊通路与回路。简单通（回）路：如果一条（回）路中的各边都是不相同的，则称这样的（回）路为简单通（回）路。基本通（回）路：如果一条（回）路中的各个顶点都是不相同的，则称这样的（回）路为基本通（回）路。13.3 路与回路定理13.3.1 在n阶无向图中，如果存在一条从vi到vj的通路，则从vi到vj必有一条长度不大于n-1的基本通路。证明 设从vi到vj存在的通路为vivj，若其中有相同的顶点vk，如vivkvkvj，则删去vk到vk的这些边，它仍是vi到vj的通路，如此反复进行，直到没有重复顶点为止，此时所得的通路就是vi到vj的基本通路。由于1条基本通路的长度比此通路中顶点数少1，而图中仅有n个顶点，故此基本通路的长度不大于n-1。 13.3.1 通路与回路13.3 路与回路定理13.3.2 在n阶无向图中，如果存在一条通过vi的回路，则必有一条长度不大于n的通过vi 的基本回路。 13.3.1 通路与回路13.3 路与回路13.3.2 图的连通性 定义13.3.2 设图G是无向图，u和v是图G中的两个顶点，如果u和v之间有通路，则称u，v是连通的，并规定u与自身是连通的。 容易验证，点的连通关系是等价关系，这个等价关系所对应的划分把图G的点集V分成若干个非空子集V1，V2，Vk，其中每一个子集Vi（i=1，2，k）中的顶点和G中以Vi中的顶点为端点的边组成的G的子图（即点集Vi的导出子图）称为图G的一个连通分支。 13.3 路与回路13.3.2 图的连通性 定义13.3.3 若图G是平凡图或G中任意两点都是连通的，则称图G为连通图，否则称G为非连通图或分离图。 例如，图13.3.2是连通图，图13.3.3是非连通图，它由两个连通分支构成。 图13.3.2 连通图 图13.3.3 非连通图13.3 路与回路定义13.3.5 在有向图G=中，若从顶点u到v有通路，则称u可达v。一般来说，可达性不是对称的，因为如果从u到v有通路，但不一定存在从v到u的通路。如果u可达v，它们之间可能不止一条路，在所有这些路中，最短路的长度称为顶点u和v之间的距离，记作d，它满足下列性质：d=0d0d+dd如果从u到v是不可达的，则通常写为d=。注意当u可达v，且v可达u时，d不一定等于d。关于距离的概念对无向图也适用。通常把D=称为图的直径。 13.3.2 图的连通性 13.3 路与回路定义13.3.6 有向图的连通性分为强连通、单向连通和弱连通三种。强连通：在有向图中，如果图中任意两点vi，vj存在着vi到vj的通路，并且存在着vj到vi的通路，则称此有向图为强连通图。单向（侧）连通：在有向图中，如果图中任意两点vi，vj存在着vi到vj的通路，或者存在着vj到vi的通路，则称此有向图为单向（侧）连通图。弱连通：如果有向图的底图是无向连通图，则称此有向图为弱连通图。13.3.2 图的连通性 13.3 路与回路例如，在图13.3.5（a）中，由点集v1，v2，v3，v4或v5导出的子图是强分支。由点集v1，v2，v3，v4，v5导出的子图是单向分支也是弱分支。在图7.22（b）中，由点集v1，v2，v3，v4导出的子图是强分支。由点集v1，v2，v3，v1，v3，v4导出的子图是单向分支，由点集v1，v2，v3，v4导出的子图是弱分支。图13.3.5 连通分支13.3.2 图的连通性 13.3 路与回路定理13.3.3 在有向图G=中，它的每一个顶点位于且仅位于一个强分支中。13.3.2 图的连通性 例13.3.1 设图G是n阶无向简单图，且图G中任意不同的两个顶点的度数之和大于等于n-1,证明图G是连通图。证明 用反证法。假设图G不是连通图，则G是由多个连通分支构成，不妨设有k个连通分支G1，G2，Gk构成，并设连通分支G1中含有n1个顶点，连通分支G2中含有n2个顶点，连通分支Gk中含有nk个顶点。显然n1+n2+nk=n如果在连通分支G1中任取一点u，由于连通分支G1是简单图，G1中任意一点的度数小于等于n11，所以有deg（u）n1-1再在连通分支G2中任取一点v，同理有deg（v）n2-1于是有deg（u）+deg（v）n1 1+n2-1=（n1+n2）-2n-2这与题设：“图G中任意不同的两个顶点的度数之和大于等于n-1”相矛盾，所以图G是连通图。 13.3 路与回路13.3.3 欧拉图与哈密顿图 定义13.3.8 给定无孤立顶点图G，如果图中存在一条通过图中各边一次且仅一次的回路，则称此回路为欧拉回路，具有欧拉回路的图，称为欧拉图。如果图中存在一条通过图中各边一次且仅一次的通路，则称此通路为欧拉通路，具有欧拉通路的图，称为半欧拉图。在图13.3.7中，图（a）具有欧拉回路，所以图（a）图是欧拉图。图（b）具有欧拉通路，所以图（b）是半欧拉图，图（c）图既不是欧拉图也不是半欧拉图。图13.3.7 欧拉图、半欧拉图、既不是欧拉图也不是半欧拉图13.3 路与回路定理13.3.4 无向连通图G是欧拉图的充分必要条件是图中各点的度数为偶数。证明 如果图G为平凡图则定理显然成立。所以我们下面讨论的都是非平凡图。首先证必要性。设C是图G的欧拉回路，则当通过C的每一顶点时，该顶点总有进出两个方向的边，把该顶点的度数增加2，又因为C中每条边仅出现一次，所以每个顶点的度数必是偶数。13.3.3 欧拉图与哈密顿图 充分性。对图G的边数采用数学归纳法。当边数m=1时，显然图仅由一个自回路构成，此自回路即为欧拉回路。由于图G是连通图，并且每个点至少为2度，所以图G中必有一条回路。设此回路为C。如果C包含G中所有边，则定理得证。如果C不所包含G中所有的边，从图G中删去C中所有边，得到图H，当然，图H可能是不连通的，但图H的边数比图G的边数少，并且图H中的每个顶点仍为偶数度点。由归纳假设可知，图G的每一个连通分支是欧拉图，又因为G是连通图，所以图H的每一个连通分支与回路C至少有一个公共点，于是我们从C中任一点出发，沿C中的边行走到达与图H的一个连通分支的公共点u，然后在图H的这个连通分支中通过一条该连通分支的欧拉回路再回到u，继续沿C的边行走到达与图H的另一个连通分支的公共点w，重复整个过程，最后得到一条包含G中所有边的欧拉回路。13.3 路与回路定理13.3.5 无向连通图是半欧拉图的充分必要条件是：图中至多有两个奇数度顶点。 定理13.3.6 设图G是有向连通图，图G是欧拉图的充分必要条件是：图中每个顶点的入度和出度相等。 13.3.3 欧拉图与哈密顿图 定理13.3.7 设图G是有向连通图，图G是半欧拉图的充分必要条件是：至多有两个顶点，其中一个顶点的入度比它的出度多1，另一个顶点的出度比它的入度多1，而其他顶点的入度和出度相等。 13.3 路与回路定义13.3.9 给定图G，如果图中存在一条通过图中各顶点一次且仅一次的回路，则此回路称为哈密尔顿回路，具有哈密尔顿回路的图,称为哈密尔顿图。如果图中存在一条通过图中各个顶点一次且仅一次的通路，则此通路称为哈密尔顿通路，具有哈密尔顿通路的图,称为半哈密尔顿图。例如，在图13.3.11中，（a）是哈密尔顿图，（b）是半哈密尔顿图，（c）既不是哈密尔顿图也不是半哈密尔顿图。图13.3.11 哈密尔顿图、半哈密尔顿图和非半哈密尔顿图 13.3.3 欧拉图与哈密顿图 13.3 路与回路13.3.3 欧拉图与哈密顿图 定理13.3.8 设图G=是哈密尔顿图，则对于顶点集V的每个非空子集S，都有W（G-S）|S|成立，其中W（G-S）是G-S中的连通分支数。证明 设C是图G的哈密尔顿回路，则对于V的任何一个非空子集S在C中删去S中任一顶点a1，则C-a1是连通的非回路，若再删去S中另一顶点a2，则W（C-a1-a2）2，由归纳法可得：W（C-S）|S|同时C-S是G-S的一个生成子图，因而W（G-S）W（C-S）所以，W（G-S）|S|。利用这个定理，可以判定某些图不是哈密尔顿图。13.3 路与回路定理13.3.9 设图G是具有n个顶点（v1，v2，vn）的无向简单图，如果图G中任意两个不同顶点的度数之和大于等于n-1，即deg(vi)+deg(vj)n-1则图G具有哈密尔顿通路，即G是半哈密尔顿图。 13.3.3 欧拉图与哈密顿图 定理13. 3.10 设图G是具有n个顶点（v1，v2，vn）的无向简单图，如果图G中任意两个不同顶点的度数之和大于等于n，即deg（vi）+deg（vj）n则图G具有哈密尔顿回路，即G为哈密尔顿图。 13.3 路与回路定义13.3.10 给定图G=，V中有n个顶点，若将图G中度数之和至少是n的非邻接顶点连接起来得到图G，对图G重复上述步骤，直到不再有这样的顶点存在为止，所得到的图，称为图G的闭包，记作C（G）。13.3.3 欧拉图与哈密顿图 定理13.3.11 当且仅当一个简单图G的闭包是哈密尔顿图时，则图G是哈密尔顿图。例13.3.3 设有n个人，其中任意两个人合在一起能认识其余n-2个人，证明当n4时，这n个人可以围成一圈，使每个人的两边都是他认识的人。（这里所说的“认识”是指相互认识）。13.3 路与回路13.3.3 欧拉图与哈密顿图 证明 设用n个点表示n个人，如果两人认识，就在表示这两个人的两点之间连一条边，从而得到一个n阶无向简单图。题意可知，即要求证明这个n阶无向简单图具有哈密尔顿回路。由题设可知，此图中的任意不同两点都有deg（vi）+deg（vj）n-2现分两种情况讨论。第一种情况：如果vi和vj之间有边相连，则deg（vi）+deg（vj）n，见图13.3.14（a）。第二种情况：如果vi和vj之间没有边相连，也即vi所表示的人与vj所表示的人是不认识的（以后简称为vi和vj是不认识的）。则可以证明：vi和余下n-2个人都认识，vj也和余下n-2个人都认识，见图13.3.14（b）。因为如果存在vk，它仅与vi有边相连，而与vj没有边相连，见图13.3.14（c），则可考察点vi和vk，易见，这两个点与vj都没有边相连，因此对于vi和vk，他们合起来不能认识余下n-2个人（他们都不认识vj）。这与“任意两个人合起来认识余下的n-2个人”的题设矛盾，由此可得deg（vi）=n-2 deg（vj）=n-2 deg（vi）+deg（vj）=2n-4易见，当n4时，deg（vi）+deg（vj）n。综合这两种情况可知，此图是哈密尔顿图。 13.3 路与回路13.3.4 赋权图与最短通路狄克斯特拉算法。假定无向赋权图G=有n个顶点，要求从v1到其余各顶点的最短路径，狄克斯特拉算法的基本思想是：（1）将顶点集合V分成两部分：一部分称为具有P（永久性）标号的集合，另一部分称为具有T（临时性）标号的集合。初始时，P=v1，T=V-P。（2）对T中每一个元素v计算D（v），根据D（v）值找出T中距v1最短的一个顶点，写出v1到v的最短路径的长度D（v）。（3）令P=Pv，T=T-v，如果P=V或T=，则停止，否则转到（2）。 13.3 路与回路13.3.4 赋权图与最短通路在（2）中，D（v）表示从v1到v的不包含T中其它顶点的最短通路的长度，但D（v）不一定是从v1到v的距离，因为从v1到v的更短通路可能包含T中另外的顶点。首先证明“若v是T中具有最小D值的顶点，则D（v）是从v1到v的距离”，用反证法证明。若有另外一条含T中顶点的更短通路，不妨设这个通路中第一个属于T-v的顶点是t，于是D（t） D（v），但这与题设矛盾。这就证明了论断正确。其次，说明计算D（v）的方法。初始时，D（v）=d（v1，v），如果（v1，v）E，则D（v）=，现在假设对T中的每一个v计算了D值。设t是T中D值最小的一个顶点，记P=Pt，T=T-t，令D（t）表示T中顶点t的D值，则D（t）=minD(t)，D(t)+d（v，t）下面分情况证明上式：（1）如果从v到t有一条最短路径，它不包含T中的其它顶点，也不包含t点，则D（t）=D（t）。（2）如果从v到t有一条最短路径，它从v1到v，不包含T中的顶点，有边（v，t），这种情况下，D（t）= D（t）+d（v，t）。除了这两种情况外不再有其它更短的不包含D另外顶点的路径了。 13.3 路与回路例13.3.3 计算图13.3.15中v1到v5的最短路径。 图13.3.15 赋权图13.3.4 赋权图与最短通路解 初始P=v1，T=v2，v3，v4，v5，v6，v7，D（v1）=0，D（v2）=4，D（v3）=，D（v4）=，D（v5）=，D（v6）=，D（v7）=1。因为D（v7）=1是T中最小的D值，所以将v7加入到P中，即P=v1，v7，T=v2，v3，v4，v5，v6，然后计算T中各点的D值：D（v2）=min4，1+2=3； D（v3）=min，1+7=8；D（v4）=min，=； D（v5）=min，=； D（v6）=min，1+8=9；D（v2）是T中最小的D值，将v2加入到P中，即P=v1，v7，v2，T=v3，v4，v5，v6，然后计算T中各点的D值：D（v3）=min8，3+3=6； D（v4）=min，3+9=12；D（v5）=min，=； D（v6）=min9，=9；D（v3）是T中最小的D值，将v3加入到P中，即P=v1，v7，v2，v3，T=v4，v5，v6，然后计算T中各点的D值：D（v4）=min12，6+5=11； D（v5）=min，6+9=15； D（v6）=min9，6+1=7；D（v6）是T中最小的D值，将v6加入到P中，即P=v1，v7，v2，v3，v6，T=v4，v5，然后计算T中各点的D值：D（v4）=min11，=11； D（v5）=min15，7+3=10；D（v5）是T中最小的D值，所以，v1到v5的最短距离是10，如果每次在求T中最小的D值时，把各点通过的通路记录下来，就能得到最短通路所经过的顶点。本例中v1到v5的最短通路是v1v7v2v3v6v5。13.3 路与回路13.3 路与回路表格的形式给出 表13.1 求最短通路13.3 路与回路由表可知，v1到v2的最短通路长为3，最短路为v1v7v2。v1到v3的最短通路长为6，最短路为v1v7v2v3。v1到v4的最短通路长为11，最短路为v1v7v2v3v4。v1到v5的最短通路为10，最短路为v1v7v2v3v6v5。v1到v6的最短通路为7，最短路为v1v7v2v3v6。v1到v7的最短通路为1，最短路为v1v7。13.4 树及其应用 13.4.1 无向树及其性质定义13.4.1 设T是无回路的无向简单连通图，则称T为无向树，或简称为树。在树中，度数为1的点称为树叶，度数大于1的点称为内顶点或分枝点。定理13.4.1 设T是含n个顶点和m条边的简单无向图，则下列各结论都是等价的，都可作为无向树的定义。（1）T连通且无回路。（2）T中任意两个不同的顶点间，有且仅有一条通路相连。（3）T无回路且n=m+1。（4）T连通且n=m+1。（5）T连通，但删去树中任意一条边，则变成不连通图。（6）T连通且无回路，若在T中任意两个不邻接的顶点中添加一条边，则构成的图包含唯一的回路。 13.4 树及其应用定理13.4.2 设T是n阶非平凡的无向树，则T至少有两片树叶。 证明 因为T是连通的，对于任意的viV，有deg（vi）1并且deg（vi）=2（n-1）=2n-2。若T中每个顶点的度数都大于等于2，则deg（vi）2n，产生矛盾。若T中只有一个顶点度数为1，其他顶点的度数都大于等于2，则deg（vi）2（n-1）+1=2n-1，得出矛盾。所以T中至少有两个1度顶点，即T至少有两片树叶。 13.4 树及其应用13.4.1 生成树与最小生成树定义13.4.2 设G是无向连通图，若G的一个生成子图（含有图G的所有顶点的子图）T是一棵树，则称图T为图G的生成树。定义13.4.3 在图的所有生成树中，树权之和最小的生成树，称为最小生成树。 13.4 树及其应用定理13.4.3 设图有n个顶点，可用下面的算法产生最小生成树。（1）选取最小边e1，设边数k=1；（2）若k=n-1，结束，否则转（3）；（3）设已选择边为e1，e2，ek，在G中选择不同于e1，e2，ek的边ek+1，使ek+1是满足e1，e2，ek，ek+1中无回路的权最小的边。（4）k=k+1，转（2）。 上面给出的求最小生成树的算法，是克鲁斯卡尔在1956年首先提出的。 13.4 树及其应用13.4.3 有向树 定义13.4.4 如果一个有向图在去掉方向后为无向树，则称该有向图为有向树。 定义13.4.5 在有向树T中，如果有且仅有一个入度为0的点。其他点的入度均为1，则称有向树T为有根树，简称根树。入度为0的点称为根，出度为0的点称为树叶或叶片，出度不为0的点称为分枝点或内顶点。 13.4 树及其应用定义13.4.7 根树包含一个或多个顶点，这些顶点中某一个称为根，其他所有顶点被分成有限个子根树。 定义13.4.8 在根树中，如果每一个顶点的出度小于或等于k，则称这棵树为k叉树。若每一个顶点的出度恰好等于k或零，则称这棵树为完全k叉树，若所有树叶的层次相同，称为正则k叉树。当k=2时，称为二叉树。 13.4.3 有向树 13.4 树及其应用例如，在图13.4.7中，（a）是4叉树，（b）是完全4叉树，（c）是正则3叉树。图13.4.7 4叉树、完全4叉树和正则3叉树13.4.3 有向树 13.4 树及其应用定义13.4.9 在根树中，如果每一个顶点的儿子都规定次序（一般采用自左到右），则称此树为有序树。图13.4.8 有序树 图14.4.9 两个不同的有序树例如，图13.4.8为有序树，图13.4.9所示的是两个不同的有序树。13.4.3 有向树 13.4 树及其应用编码是指用一些二进制序列来表示某种信息，一个二进制序列称为一个码字，由码字作为元素构成的集合称为码。最常用一种编码就是前缀码。定义13.4.10 如果在码中，没有一个码字是另一个码字的前缀，则称这样的码为前缀码。例如，A=01，10，11，000，0010，0011，由于A中没有一个码字是另一个码字的前缀，所以A是前缀码。13.4.3 有向树 13.4 树及其应用13.4.3 有向树 利用完全二叉树，很容易编制一个前缀码。在一棵完全二叉树中，把每个分枝点引出的左面那条边标记0，右面那条边标记1。把从根到每一片树叶所经过的边的标记串作为这片树叶的标记，由这些树叶的标记作为码字构成的集合就是前缀码，因为每个码字（树叶）的前半部分都在分枝点上。例如，在图13.4.11中，得到的前缀码为0000，0001，001，01，100，101，11。图13.4.11 利用完全2元树编制前缀码13.4 树及其应用13.4.3 有向树 定理13.4.4 任意一棵给定的二叉树，可以产生唯一的一个二元前缀码。 定理13.4.5 任何一个前缀码都对应一棵二叉树。13.4 树及其应用13.4.3 有向树 定义13.4.11 设T是具有n片树叶t1，t2，tn的完全二叉树，且各片树叶所含的权为w1，w2，wn，令W（T）=L1w1+L2w2+Lnwn其中，Li（i=1，2，n）是完全二叉树T的根到树叶ti的通路长度，则称W(T)为完全二叉树T的权。在所有带权w1，w2，wn的二叉树中，w(T)最小的那
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号