8图论-树的应用10-26.

作业问题：欧拉图的判定已经很完善，主要是关于哈密顿图的判定从哈密顿图的定义给定一个无向图G=V，E(a)穿程图G中的每个结点一次且仅一次的通路，称为该图G的哈密顿通路(b)穿程图G中的每个结点一次且仅一次的回路，定义为该图G的哈密顿回路。(c)具有哈密顿回路的图。称为哈密顿图。具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图从定义可以得出哈密顿图G必须满足：1、每一个哈密顿图G都必定是个连通无向图2、G中的边数m必须大于等于n3、哈密顿通路是一条初级通路哈密顿回路是初级回路4、G中存在哈密顿回路，则一定存在哈密顿通路。反之不成立。8题根据这些特征来判断K2不满足2，且回路不是初级回路，K2故不是哈密顿图16题：顶点分别为：v1,v2,…vnKn存在多少条不同的哈密顿回路？当起始点确定为v1时有（n-1）!当起始点不确定时有n!§16.3根树及其应用设D是有向图，若D的基图是无向树，则称D为有向树在所有的有向树中，根树最重要，所以在此只讨论根树一、根树1、定义：设T是n(n≥2)阶有向树若T中有一个顶点的入度为0，其余顶点的入度均为1，则称T为根树入度为0的顶点称为树根（相当于文件系统的盘符）入度为1出度为0的顶点称为树叶（具体文件）。入度为1出度不为0的顶点称为内点（文件夹），内点和树根统称为分支结点从树根到T的任意顶点v的通路(路径)长度称为v的层数。层数最大顶点的层数称为树高．将平凡树也称为根树在根树中，由于各有向边的方向是一致的，所以画根树时可以省去各边上的所有箭头，并将树根画在最上方2、根树中顶点的关系定义：设T为一棵非平凡的根树，∀vi,vj∈V(T)，若vi可达vj，则称vi为vj的祖先，vj为vi的后代；若vi邻接到vj(即vi,vj∈E(T)则称vi为vj的父亲，而vj为vi的儿子若vj,vk的父亲相同，则称vj与vk是兄弟3、有序树设T为根树，若将T中层数相同的顶点都标定次序，则称T为有序树根据根树T中每个分支点儿子数以及是否有序，可以将根树分成下列各类：(1)若T的每个分支点至多有r个儿子，则称T为r叉树；又若r叉树是有序的，则称它为r叉有序树．(2)若T的每个分支点都恰好有r个儿子，则称T为r叉正则树；又若T是有序的，则称它为r叉正则有序树．(3)若T是r叉正则树，且每个树叶的层数均为树高，则称T为r叉完全正则树，又若T是有序的，则称它为r叉完全正则有序树。4、r叉树的子树定义：设T为一棵根树，∀v∈V(T)称v及其后代的导出子图Tv为T的以v为根的根子树如：2叉正则有序树的每个分支点的两个儿子导出的根子树分别称为左子树和右子树．二、根树的应用1、最优2叉树定义：设2叉树T有t片树叶v1，v2，…，vt，权分别为w1，w2，…，wt，称W(T)＝∑wi|(vi)｜为T的权，其中|(vi)｜是vi的层数（也可以是从根到该叶子的通路长度）．在所有有t片树叶，带权w1，w2，…，wt的2叉树中，总权值权W(T)最小的2叉树称为最优2叉树三棵带权2叉树W(T1)＝2（2+2)+3*3+5*3+3*2＝38W(T2)＝4(3+5)+3*3+2*2+2＝47W(T3)＝3*(3+3)+5*2+2(2+2)＝36下面介绍一种算法：Huffman算法（在给定权值下，如何构造最优2叉树）给定实数(权值)：w1，w2，…，wt，按从小到大排序为w1≤w2≤…≤wt.(1)连接权为w1，w2的两片树叶，得一个分支点，其权为w1+w2(2)在w1+w2，w3，w4…，wt中选出两个最小的权，连接它们对应的顶点(不一定是树叶)，得新分支点及所带的权．(3)重复(2)，直到形成t—1个分支点，t片树叶为止．例：给定一组权值3，5，6，9，11，14，16，18构造相应的最优二叉树最优二叉树总的原则是：权值较大的叶子距根较近，权值较小的可以距根较远2、前缀编码在通信中，常用二进制编码表示符号．1）等长编码与不等长编码：不等长编码可以使总电文总长度较短2）不等长编码中编码的问题：如何识别？3)前缀编码定义：设a1a2，…，an-1an为长为n的符号串，称其子串a1,a1a2,…，a1a2…an-1分别为该符号串的长度为1，2，…，n-1的前缀．设A＝{b1，b2，…bm}为一个符号串集合，若对于任意的bi，bj∈A(i≠j)bi与bj互不为前缀，则称A为前缀码．若符号串bi(i＝1，2，…，m)中只出现0，1两个符号，则称A为二元前缀码{1，10，101，0101，1010，0100，01001}不是前缀码{1，00，011，0101，01001，01000}为前缀码．{1，01，111，1100，0111}不是前缀码2）利用二叉树产生二元前缀码规定二叉树的左子树的边为0，右子树的边为1则将从根到叶子结点的通路中边的序列即为叶子的二元前缀编码3）最优二元前缀码给定所需编码的字符的频率，构造字符的二元前缀编码使其总电文长度为最短－称为最优二元前缀码利用哈夫曼树构造最优二元前缀码1，10，01，101，0101a,b,c,d,e3、二叉树的周游（遍历）二叉树的周游：对于一棵二叉树的每一个结点都访问一次且仅一次的操作1）做一条绕行整个二叉树的行走路线（不能穿过树枝）2）按行走路线经过结点的位置（左边、下边、右边）得到周游的方法有三种：中序遍历（路线经过结点下边时访问结点）访问的次序：左子树－根－右子树前序遍历（路线经过结点左边时访问结点）访问的次序：根－左子树－右子树后序遍历（路线经过结点下边时访问结点）访问的次序：左子树－右子树－根例：给定二叉树，写出三种访问结点的序列例：给定二叉树周游的二种周游序列，画出该二叉树4、表达式的(逆)波兰式生成给定表达式：（a*(b+c)+d*e*f)/(g+(h-i)*j)对应的二叉树：后序遍历的结果:((a(bc+)*)(d(ef*)*)+)(g((hi-)j*)+)/逆波兰式=abc+*def**+ghi-j*+/计算机在运算该表达式时：仅按照一个原则：扫描到一个运算符就将它前面二个数进行运算前序遍历的结果：／(+(*a(+bc))(*d(*ef)))(+g(*(-hi)j))=/+*a+bc*d*ef+g*-hij仅按照一个原则：运算符入栈，当扫描到两个数就进行最上面的运算符的运算2)二叉排序树将一组需要排序的序列建立二叉排序树建立（不断添加结点为其子树：比根结点小的为左子树比根结点大的为右子树利用周游得出排序结果（中序遍历）作业：p31937、38、39、41、42第三部分代数结构第九章代数系统9.1二元运算及其性质一、运算从小学到现在我们学习了许多运算，这些运算的共同规律是什么？运算对象–集合中的元素运算符运算结果-集合中的元素为了研究一般运算的性质下面将运算抽象为是一种特殊的函数，从函数的观点来研究一般运算的性质是具有普遍的意义。１、定义设S为集合，函数f：SⅩS→S称为S上的二元运算，简称为二元运算·注：定义中要求：集合S上的二元运算是笛卡尔积到集合S的函数，从函数的要求来看验证一个运算是否为集合S上的二元运算关键考虑两点：1）S中任何两个元素都可以进行这种运算，且运算的结果是惟一函数对应的体现x,y→运算结果z=x*yx,y,z∈S2）S中任何两个元素的运算结果都属于S，即S对该运算是封闭的．二元运算的实例：2、二元运算的表示通常用＊、•、*、△、★…等抽象符号表示二元运算，称为算符．设f：S×S→S是S上的二元运算，对任意的x，y∈S，如果x与y的运算结果是z，即f(x，y)=z可利用算符＊简记为x＊y=z3、一元运算定义9．2设S为集合函数f：S→S称为S上的一个一元运算，简称为一元运算．一元运算实例4、用算符来表示一元运算．若f：S→S为S上的一元运算，则f(x)＝y可以用算符＊记为＊(x)＝y或＊x＝y其中x是参加运算的元素，y为运算的结果．例如上面的相反数-x、集合A的绝对补集～A，¬p都是上述表示形式，其中的-、～、¬都是算符．5、有限集合上的运算（可用一个表格来表示运算的过程和结果）设S={a1,a2,a3.a4,a5},*为其上的二元运算则该运算可用表来表示：中间是运算结果，运算次序为行标为先列标后＊a1a2a3a4a5a1a2a3a4a5运算可以推广为n元运算（操作）二、二元运算的一般性质（运算律）１、交换律定义9．3设＊为S上的二元运算．如果对于任意的x，y∈S都有x＊y=y＊x则称运算＊在S上是可交换的，或者说运算＊在S上适合交换律。2、结合律定义9．4设＊为S上的二元运算，如果对于任意的x，y，z∈S都有:(x＊y)＊z=x＊(y＊z)则称运算＊在S上是可结合的，或者说运算＊在S上适合结合律．3、等幂律定义9．5设＊为S上的二元运算，如果对于任意的x∈S都有x＊x＝x则称该运算＊适合幂等律．如果S中的某些x满足x＊x=x，则称x为运算＊的幂等元．如果S上的二元运算＊适合幂等律，则S中的所有元素都是幂等元．4、分配律定义9．6设＊和o是S上的两个二元运算，如果对任意的x，y，z∈S有x＊(yoz)＝(x＊y)o(x＊z)(左分配律)(yoz)＊x=(y＊x)o(z＊x)(右分配律)则称运算＊对o是可分配的，也称＊对o适合分配律．5、吸收律定义9．7设o和＊是S上两个可交换的二元运算，如果对于任意的x，y∈S都有x＊(xoy)＝xxo(x＊y)=x则称o和＊满足吸收律．命题的析取和合取运算（集合的交、并运算）三、二元运算中的特殊元素1、单位元（幺元）1）左、右单位元和幺元定义定义9．8设＊为S上的二元运算，如果存在el(或er)∈S使得对任何x∈S都有:el＊x=x(或x＊er=x)则称el(或er)是S中关于＊运算的一个左单位元(或右单位元)．若e∈S关于运算＊既是左单位元又是右单位元，则称e为S上关于＊运算的单位元．单位元也可以叫做幺元．单位元的唯一性定理9．1设o为S上的二元运算，el，er分别为o运算的左单位元和右单位元，则有el＝er＝e且e为S上关于o运算的惟一的单位元．2、零元1)定义9．9设o为S上的二元运算，若存在元素θl(或θr)∈S使得对于任意的x∈S有：θlox=θl(或xoθr＝θr)则称θl(或θr)是S上关于o运算的左零元(或右零元)．若θ∈S关于o运算既是左零元又是右零元，则称θ为S上关于o运算的零元．2)零元实例3）性质:零元的唯一性定理：设o为S上的二元运算，θl和θr分别为ㅇ运算的左零元和右零元，则有：θl＝θr＝θ定理：设ㅇ为S上的二元运算，e和θ分别为ㅇ运算的单位元和零元．如果S至少有两个元素，则e≠θ3、可逆元1）定义:设ㅇ为S上的二元运算，e∈S为ㅇ运算的单位元对于x∈S，如果存在yl∈S(或yr∈S)使得ylㅇx=e(或xㅇyr=e)则称yl(或yr)是x的左逆元(或右逆元)．若y∈S既是又的左逆元又是x的右逆元，则称y是x的逆元．如果x的逆元存在，则称x是可逆的．2)实例：3)可逆元的不唯一性逆元和单位元、零元不同．如果单位元或零元存在，一定是惟一的．换句话说，整个集合只有一个．而逆元能否存在，还与元素有关．有的元素有逆元，有的元素没有逆元，不同的元素对应着不同的逆元．（整数集合中对加法运算来说，每个整数均为可逆元）4）可逆元的逆元唯一性定理9．4设＊为S上可结合的二元运算，e为该运算的单位元，对于x∈S,如果存在左逆元yl和右逆元yr，则有yl=yr=y且y是x的惟一的逆元．4、消去律1)定义9．11设＊为S上的二元运算，如果对于任意的x，y，z∈S满足以下条件：(1)若x*y=x*z且x≠0，则y=z；(2)若y*x=z*x且x≠0，则y=z；那么称*运算满足消去律，其中(1)称作左消去律，(2)称作右消去律．注:被消去的x不能是运算的零元0．2)例：整数集合上的加法和乘法都满足消去律．幂集P(S)上的并和交运算一般不满足消去律．∀A，B，C∈P(S)，由A∪B＝A∪C不一定能得到B＝C．对称差运算满足消去律．⊕运算不存在零元，∀A，B，C∈P(S)，都有A⊕B＝A⊕C＝B＝CB⊕