下载文档原格式
离散数学（微课版）第4章1. 引言在离散数学的第4章中，我们将讨论图论的基本概念和应用。
图论是研究图及其在现实生活中的应用的数学分支，它在计算机科学、网络设计、运筹学等领域中具有重要的应用价值。
本章将介绍图的定义、图的表示方法、图的遍历算法等内容。
2. 图的定义图由一组节点和一组节点之间的边构成。
节点通常表示现实世界中的对象，而边则表示对象之间的关系。
图可以用于描述各种问题，如社交网络中的用户关系、城市之间的交通网络等。
2.1 有向图和无向图图可以分为有向图和无向图两种类型。
在有向图中，边具有方向，表示节点之间的单向关系。
而在无向图中，边没有方向，表示节点之间的双向关系。
2.2 顶点和边图由顶点和边组成。
顶点是图的节点，用来表示对象。
边连接两个顶点，表示两个对象之间的关系。
2.3 路径和环路径是指在图中从一个顶点到另一个顶点的连接序列。
环是一条路径，其起点和终点相同。
3. 图的表示方法在计算机中，图可以用不同的数据结构来表示。
常见的表示方法包括：3.1 邻接矩阵邻接矩阵是用二维数组表示图的连接关系。
对于无向图，邻接矩阵是对称的，而对于有向图，则不对称。
A B CA010B101C010上述邻接矩阵表示了一个无向图，其中顶点A与顶点B相连，顶点B与顶点C相连。
3.2 邻接表邻接表是用链表表示图的连接关系。
对于每个顶点，邻接表保存了与其相连的其他顶点的信息。
A ->B -> NULLB -> A ->C -> NULLC -> B -> NULL上述邻接表表示了一个无向图，顶点A与顶点B相连，顶点B与顶点A、C相连，顶点C与顶点B相连。
4. 图的遍历算法图的遍历算法是指按照一定的方式访问图中的所有节点。
常见的图的遍历算法有深度优先搜索和广度优先搜索。
4.1 深度优先搜索深度优先搜索从起点开始，尽可能深地访问尚未访问的节点，直到无法继续深入为止，然后回溯到上一个节点，继续深入其他未访问的节点。
图学基础教程习题集答案第一章：图学基本概念1. 图的定义是什么？答案：图是由顶点（或称为节点）和边组成的数学结构，其中边是顶点之间的连接。
2. 什么是有向图？答案：有向图是一种图，其中的边具有方向性，从一个顶点指向另一个顶点。
第二章：图的表示方法1. 邻接矩阵的优缺点是什么？优点：易于实现，可以快速判断任意两个顶点之间是否存在边。
缺点：空间复杂度高，对于稀疏图来说效率较低。
2. 邻接表的优缺点是什么？优点：空间效率高，对于稀疏图特别适用。
缺点：需要额外的时间来检查两个顶点之间是否存在边。
第三章：图的遍历1. 深度优先搜索（DFS）的基本思想是什么？答案：从图中的一个顶点开始，沿着边尽可能深地搜索，直到无法继续，然后回溯到上一个顶点，继续搜索其他路径。
2. 广度优先搜索（BFS）的基本思想是什么？答案：从图中的一个顶点开始，逐层遍历所有可达的顶点，直到所有顶点都被访问过。
第四章：最小生成树1. 最小生成树问题的定义是什么？答案：在无向图中，最小生成树是一棵连接所有顶点的树，且边的总权重最小。
2. Kruskal算法的基本步骤是什么？答案：Kruskal算法通过按权重递增的顺序选择边，确保选择的边不会形成环，直到所有顶点都被连接。
第五章：最短路径问题1. Dijkstra算法的工作原理是什么？答案：Dijkstra算法通过维护一个优先队列，不断地选择距离起点最近的顶点，并更新其邻接顶点的距离。
2. Bellman-Ford算法与Dijkstra算法的主要区别是什么？答案：Bellman-Ford算法可以处理带有负权重边的图，而Dijkstra算法不能。
第六章：图的着色1. 图的着色问题的定义是什么？答案：图的着色问题是指给图中的每个顶点分配一种颜色，使得相邻的顶点颜色不同。
2. 贪心算法在图的着色问题中的应用是什么？答案：贪心算法在图的着色问题中，从顶点集合中选择一个顶点，为其分配一种颜色，然后移动到下一个顶点，并为其分配一种与相邻顶点不同的颜色。
有向图（4.dijkstra算法详解）在图的应⽤中，有⼀个很重要的需求：我们需要知道从某⼀个点开始，到其他所有点的最短路径。
这其中，Dijkstra算法是典型的最短路径算法。
它的关键思想是以起始点为中⼼，向外⼀层层扩散，直到扩展到终点为⽌。
Dijkstra算法能够得出最短路径的最优解，不过它需要遍历计算的节点相当多，所以效率不⾼。
⾸先，⽤最通俗的语⾔解释。
假定有3个顶点，A、B、C，如图：要求A到其余各点的最短路径。
很明显，A到C⽐A到B更短。
有疑惑的是从A->B的最短距离，要么是直接A->B的边，要么是A经过C到B的边更短。
我们⾸先找到最短的边（A->C),然后在此基础上扩展，于其余边去对⽐找到最⼩值。
顶点再进⼀步扩充增加，按照这个思想，我们总可以找到A到所有点的最短路径。
算法描述：从节点1开始到其余各点的dijkstra算法，其中Wa->b表⽰边a->b的权，d(i)即为最短路径值，顶点集合为V={1,2,3...n}1.置集合S={1}，置顶点集合U={2,3,4...n}，数组d(1)=0,d(i)=W1->i（1，i之间存在边）or ⽆穷⼤（1，i之间不存在边）；2.在U中，令d(j)=min{d(i),i属于U}，将j从U中移⾄S中，若U为空集则算法结束，否则转3；3.对全部i属于U，如果存在边j->i,那么置d(i)=min{d(i), d(j) + Wj->i},转2Dijkstra算法的思想为;设G=(V, E)是⼀个带权有向图，把图中顶点集合V分为两部分，第⼀组为已求出最短路径的顶点集合（⽤S表⽰，初始时S中只有源点，以后每求出⼀条最短路径，就将顶点加⼊到S中，直到所有顶点都加⼊到S中，算法结束），第⼆组为其余未求出最短路径的顶点集合（⽤U表⽰），按最短路径的长度次序依次将第⼆组中的顶点加⼊到第⼀组中。
在加⼊过程中，总保持着从源点v到S中各顶点的最短路径不⼤于从源点v到U中各顶点的最短路径长度。
第四章 有向图4.1 有向图与有向Euler 图边为有向的图称为有向图，用D=(V,A)表示，此时有向边称为弧。
定义1：点的出弧数称为出次数，记为i v d +()。
i v 点的入弧数称为入次数，记为i v d −()。
i v 则的次数d(v )=i v i d +()+d i v −(v )i 且==m (边的个数)1()ni i dv +=∑1()ni i d v −=∑定义2：无向图G，每边指定方向后成为有向图，称为与G相伴的有向图，给定一有向图D，去掉方向后得一有向完全图称为竞赛图定义有向路径(道路);点不重复的有向边列构成的回路，称为有向回路。
在有向图D 中，若从每一点到其他任何一点至少存在一条有向路径，称图D 是强连通的；若D 非强连通而其基础图是连通的，称图D 是弱连通的。
强连通弱连通定义4：若D 是弱连通图，且每一点的出次数d +(v)等于入次数d(v),则称D 为有向Euler 图；经过D 的每条边的一个有向闭边列称为有向Euler 链−定理1：当且仅当一个连通有向图D 中有一条有向闭E—链时，图D 是一个有向Euler 图。
定理2：每个竞赛图都有有向Hamilton 回路 定理3：若D 是弱连通有向图，且()()()()⎪⎩⎪⎨⎧+−=+++−11v d v d v d v d 2121,v v v v v v v ==≠则D 中有以起点，为终点的Euler 1v 2v 路径，即可“一笔画”例：有向Euler图的应用：计算机磁鼓 v 1（起点）v2（终点）3v 设计问题。
把一旋转鼓轮表面等分，每一部分用导体或绝缘体组 2n 成（分别用1，0表示），接触器的位置表示一个二进制 数010（如图），当磁鼓顺时针转动一倍，得101；再转一格的010，这个状态与开始的状态无法区别，因此这样设计就不好了。
接触器面等分成格子，每个格子上分2n配数字0或1，但必须满足“不 重复，不遗漏”条件1） 不重复：即相继的k 个接触器随着鼓的转动所读出2个k 位二进制数要两两互异。
因此要求2n k ≥2n 2） 不遗漏：2个不同的k 位二进制数，每个都对应于鼓的某一状态，为此k 2k ≤2n 故有 k=n k=n 的不重复，不遗漏的磁鼓叫做有效磁鼓。
下面用Euler 回路解决这一问题 构作有向图,①顶点集合D n V()={v=│=0或1，1n D 1p 12−⋅⋅⋅n p p i p ≤i ≤n-1} 共个顶点。
12n −②对，作边集E（）(n D v v v ∈∀21,)n D 边=12,v v ()n E D ∈⇔1v 121−⋅⋅⋅n p p p ，=2v 231...n n p p p p − 此时记边=12v v 1231...n n p p p p p −③因每个i p 的选取有两种可能0或1，故对()n v V D ∀∈ 易知(v)= d (v)=2，如点d−+1232...n p p p p −0故由定义4，图是一有向Euler 图，则由Thm1，图存在一条有向闭E 链 n D n D 以k=3为例顶点集合={3()V D }12V p p =={}00,01,10,11000可知，经过有向图的每一边的有向3D 5678e e e e 取每边标号的最前一码可 构成8=个数字码作为 32磁鼓面的设计码00011101注：若取每边的中间码可得00111010 }循环码若取每边的最后一码可得01110100 n=4,=16位 42 e13154.2 有向树有向树在电网络分析，计算机程序设计等科学等学科中都有应用。
外向树：在有向树中存在一点，从到其它各点有一条有向路径。
0v 0v i v ()=0 称为树根，用R（root）表示d −0v 0v 外向树（二元树）内向树（三元树）定义：在有向树T 中1）若顶点引出次数的最大值为m，称T 为m 元树 2）除树叶外，每点引出的次数均为m,称T 为完全m 元树 3）若树叶的层次均相同，称T 为正则树完全三元树 正则三元树 完全正则三元树定理1：外向树中，除根以外每点的入次数d −(v)=1定理2：关于有向树的几个等价命题（参[]3，）156P 设D 的顶点数为n,则 1） D 是一棵有根树2） D 是没有回路的拟强连通图 3） D 是拟强连通的，且有n-1条弧4） 存在一点使对其他每个顶点都有且仅有一条以v 为起点的有向路径r v r r 5） D 是拟强连通的，但从D 中去掉任何一条弧都使这个性质不成立6） D 是拟强连通的，并有一个顶点，使得 v ,()0=−r v d ()1=−i v d ,r i ≠7） D 没有回路，并且有一个顶点，使得 r v ,()0=−r v d ()1=−i v d ,r i ≠推论：当且仅当D 是拟强连通时，D 有有向生成树例 外向树在程序设计中的应用一个代数表达式中的（被运算对象）（运算符号）（运算对象） 可用树表示表示a ÷ba+b+a÷(b+c)注意：一般程序设计中的计算次序为：()zy b ae x 1+−()[]z y b x e a /1+∗−↑∗③ ② ⑤ ④ ① ⑥需要往返扫描（从下往上） 现考虑运算次序：从上到下，从左至右，左式可表达为/-*a↑ex*b+y1z上式称为波兰表达式，不仅没有括号，而且只要从右到左一次扫描就可完成整个式子的计算。
即在从右到左的扫描中，每遇到一个运算符号就对紧跟其后的两个数字进行运算 前者为被运算对象，后者为运算对象。
运算如下：z y b ex a 1/+∗↑∗− z y b ex a )1(/+∗↑∗−= z y b ex a )]1([/+↑∗−= z y b ae x )]1([/+∗−= z y b ae x )]1()[(/+−=z y b ae x )]1(/[+−=z y b ae x /)]1([+−=练习：把下面算式表示成外向树，并写出波兰表达式 1．xcd a b g f +−− 2. 512346(v v v v v v +++a-b/*cd-↑gxf56+654321/v v v v v v +∗∗4.3 Huffman 树（1952年）霍夫曼提出了一种构作最优的m 元有序树的方法，它在通信理论和软件科学中都有重要应用设有k 个由{}0,1,2,...,1M =m −中符号构成的码要在通信信道中传输。
假设码一个接一个的传输，每个码出现的概率是12,,...x p p p ，且出现的概率和前向传输的码无关（独立的），要求找一组前缀码，码长，使得平均码长12,,...k l l l 1ki i i p l =∑为最短。
由此得到的树，称为最优m 元树。
先考虑最优二元树定理1：设T 为树叶带权k ωωω≤⋅⋅⋅≤≤21的最优树，其带最小权的两片树叶是兄弟，且其通路长路最长。
证：（一）首先证明带最小权1ω的树叶的通路长路为最长1v ()1v l 反证法：若存在树叶带权，它的通路长路 ,i v 1i w w >1()()i l v l v >此时二元树的权为111()()()i w T w l v w l v Q =++ 其中Q 为除，外，其余树叶的权与通 1v i v 路乘积之和，将与上的权互换，位置 1v i v)1ωi i v )1不变，则新二元树的权'T '11()()()i i w T w l v w l v Q =++∴'11()()()(()())0i i w T w T w w l v l v −=−−<即< '()w T ()w T ∴T 不是最优树，矛盾（二）其次证明，权最小的二片树叶必是兄弟设树叶带最小权，若无兄弟（如图1），此时考虑 1v 1w 1v11v 图1(1v 图2图2，显然图2中树的权比图1中树的权要小 故图1不是最优树。
矛盾必有兄弟⇒1v 若的兄弟不是树叶，而是分枝点（如图2），则的通路不是最长的，由前面（一）知，该树不可能是最优树，矛盾⇒带最小权的树叶必有一片树叶是它的兄弟。
1v 2v 1v 1w 1v 定理2：设T 是一棵带权12...k w w w ≤≤≤的最优树，去掉带最小权的树叶，使它们的父亲为带权（12,w w 1w w 2+）的树叶，得到的新的带权树，则也是最优树 'T 'T 证；是[2] 5657P −以上两个定理，为我们提供了构造最优树的方法，即Huffman 算法：（1） 权最小的两片树叶是兄弟，去掉这两片树叶，并以它们的父亲作树叶，使它带的权是它的两个儿子带权之和，于是得到比前少一树叶的树'T （2） 对得到的新树重复（1），最后得到树根（3） 从树叶到树根的构造过程中得到的树，就是所求的最优树。
例1：M={0，1}，k=8 即m=2,有8个0，1构成的码，它们出现的概率分别为=0.6,=0.2,==0.05,===0.03, =0.01构作一个二元有序树1P 2P 3P 4P 5P 6P 7P 8P 解：原则：尽可能使概率大的码短小，以便于传递。
先把概率以不增次序排列0.6, 0.2, 0.05, 0.05, 0.03, 0.03, 0.03, 0.01 把最小的俩个概率相加后重排：0.6, 0.2, 0.05, 0.05, 0.04, 0.03, 0.030.6, 0.2 ，0.06, 0.05, 0.05, 0.04 ⇒⇒⇒⇒0.6, 0.2, 0.09, 0.06, 0.05 0.6, 0.2, 0.11, 0.09 0.6 ，0.4意指定其为或…… 3P 4P码字：0 10 1101 1110 11000 11001 11110 11111概率：0.6 0.2 0.05 0.05 0.03 0.03 0,030.01码长：1 2 4 4 5 5 5 5 对于m=2的二元码，总是取当前的个概率中，概率最小的两个相加；对于m>2的m 元码，取'k d=⎪⎩⎪⎨⎧−ρ1m m()()()()()()2m 21mod 1mod 01mod 1'''−≤≤−≡−≡−≡ρρ且m k m k m k 最理想的编码方案是取d=m 个概率相加，但不一定满足1 (mod(m-1))，故在前面每步中加以调整，使得最后一步（靠近树根的第一层节点）恰好有m 个概率 'k 'k ≡例2，设有12个数，即k=12，构作m=4元有序树，已知每个数出现的概率为：0.09，0.08，0.08，0.07，0.06，0.06，0.06，0.05，0.05，0.04，0.03，0.03解（1）k=12 k (m-1)=12÷(4-1)=4 取d=3÷0.10，0.09，0.08，0.08，0.07，0.06，0.06，0.06，0.05，0.05（2）=k-d+1=12-3+1=10, 10'k ÷3=3……..1 即101（mod3） 取d=m=4≡0.22，0.10，0.09，0.08，0.08，0.07，0.06 （3）-d+1=10-4+1=7 7'k ⇒'k ≡1(mod3) 取d=m=40.29，0.22，0.10，0.09（4）=4'k最优4元树为：∴习题：设10个码出现的概率分别为0.2，0.18，0.12，0.10，0.10，0.08，0.06，0.06，0.06，0.04，分别对m=2，3和4构作平均码长最短的m元前缀码。
