第8章 计算机专业应用数学

第8章计算机专业应用数学8.1行列式矩阵及其应用(见第3章)8.2命题逻辑介绍8.3图论及其应用返回8.2命题逻辑介绍数理逻辑是用数学方法研究思维规律的一门学科.所谓数学方法是指用一套数学的符号系统来描述和处理思维的形式与规律.因此，数理逻辑又称为符号逻辑.本章介绍数理逻辑中最基本的内容一一命题逻辑.首先引人命题、命题公式等概念.然后，在此基础上研究命题公式间的等值关系和蕴含关系.8.2.1命题的概念1.命题人们的思维活动是靠自然语言来表达的.然而，由于自然语言易产生二义性，用它来表示严格的推理就不合适了.为了解决这个问题，在数理逻辑中引进了一种形式化的语言，这就是一种符号语言.命题逻辑是数理逻辑中最基本的内容，是以命题为基本对象的数学化的下一页返回8.2命题逻辑介绍逻辑系统.我们把能够判断真假的陈述句称作命题.这种陈述句的判断只有两种可能的结果“真”或“假”，称为命题的真值，其中真值为真(用1或T表示)的命题称为真命题，真值为假(用0或F表示)的命题称为假命题，因此，命题是具有唯一真值(真或假)的陈述句.例8-1判断下列语句是不是命题.(1)13是质数.(2)3比5大.(3)我是大学生.(4)昨天是阴天.(5)明年国庆节是晴天.(6)宇宙中有些星球现在还没有被发现.上一页下一页返回8.2命题逻辑介绍(7)你上网了吗?(8)请保持安静!(9)今年春节真热闹啊!(10)x+i=1.(11)他在说谎.(12)他对这句话的判断是错误的.例8-1中(1)～(6)都是命题,(7)～(12)都不是命题.说明:(1)是真命题.(2)是假命题.(3)的真值要看说话者本人是否是大学生而定.(4)的真值要看当时的天气而定.(6)的真值要到明年国庆节而定.(6)的真值随着科学技术的发展总有一天能够确定.(9}是疑问句.(8)是祈使句.(9)是感叹句.(10)的真值无法确定.(11)和(12)虽然是陈述句，上一页下一页返回8.2命题逻辑介绍但是其表达的含义和结论之间有矛盾，这样的语句称为悖论.2.命题的表示命题的表示方法一般有如下三种:(1)用大写字母A,B,C,...,y,Z来表示;(2)大写字母加下标的方式;(3)数字加中括号的方式.例如，A:他通过了这次考试;P1:他通过了这次考试;「10」:他通过了这次考试.表示命题的符号称为命题标识符，A,P1都是命题标识符.表示任意命题的命题标识符称为命题变元.上一页下一页返回8.2命题逻辑介绍3.命题的分类命题分为原子命题和复合命题.我们把不能再分解为其他命题的命题称为原子命题，由原子命题通过连接词复合而成的命题称为复合命题.例8-1中的(1)～(6)都是原子命题.而“王琳是学生党员”就是复合命题，因为它是由原子命题“王琳是学生”和“王琳是党员”复合而成.说明:“小李与小王是朋友”是原子命题，因为朋友关系必须是由两个人构成，单独一个人不能构成朋友关系.4.真值表将命题变元的所有取值可能全部列出来，构成的一个表，以确定某个命题(或式子)的真值，该表称为命题的真值表.上一页下一页返回8.2命题逻辑介绍8.2.2命题连接词表示复合命题内部联结关系的符号，称为命题连接词.常见的命题连接词有五个.1.否定连接词若P是一个命题，复合命题“非P”称为P的否定，记作﹁P.

﹁称为否定连接词.P的真值为真当且仅当﹁P的真值为假.真值表如表8-1所示.上一页下一页返回8.2命题逻辑介绍例8-2设P:承德是旅游城市，则﹁P:承德不是旅游城市.由于P的真值为1,所以﹁P的真值为0.说明:命题的否定对于命题的表示有多种解释，只要能表达对原命题的否定含义就可以了，不要求说法完全一致.2.合取联结词若P,Q是两个命题，则由合取联结词八和命题P,Q组成的复合命题P∧Q称为PQ的合取式，读作“P且Q".P∧Q为真当且仅当P,Q都为真.复合命题P∧Q的真值表如表8-2所示.合取词是自然语言中的连接词“并且”、“和”、“及”等的逻辑抽象.上一页下一页返回8.2命题逻辑介绍例8-3将下列命题符号化.(1)王红既聪明又漂亮.(2)王红虽聪明但不漂亮.(3)李大强喜欢上网和玩游戏.(4)2+2=4且雪是黑的.上一页下一页返回8.2命题逻辑介绍解设P:王红聪明，Q:王红漂亮，R:李大强喜欢上网，S:李大强喜欢玩游戏，M:2+2=4，N:雪是黑的.(1)“王红既聪明又漂亮”可符号化为P∧Q.(2)“王红虽聪明但不漂亮”可符号化为P∧﹁Q.(3)“李大强喜欢上网和玩游戏”可符号化为∧S.(4)“2+2=4且雪是黑的”可符号化为M∧V.3.析取连接词若P,Q是两个命题，则由析取连接词∨和命题P,Q组成的复合命题P∨Q称为P,Q的析取式，读作“P或Q”.P∨Q为真当且仅当P,Q至少有一个为真，因此只有P,Q同时为假时，P∨Q才为假.复合命题P∨Q的真值表如表8-3所示.析取词∨是自然语言中的连接词“或者”、“或”等的逻辑抽象.上一页下一页返回8.2命题逻辑介绍例8-4判断下列命题是否可表示成析取式并符号化.(1)明天下雨或湿度很高.(2)老王在教室里上课或者参加长跑比赛.解(1)设P:明天下雨，Q:明天湿度很高.则“明天下雨或湿度很高”可符号化为P∨Q.上一页下一页返回8.2命题逻辑介绍(2)设A:老王在教室里上课，B:老王参加长跑比赛.则“老王在教室里上课或者参加长跑比赛”不能表示成A∨B，但可以表示成(A∧﹁B)∨(﹁A∧B).例8-4命题(2)中的“或”为“不可兼或”用

来表示，其真值表见表8-4.上一页下一页返回8.2命题逻辑介绍注意:需要特殊说明的是，虽然析取可以理解成汉语中的“或者”、“或”等形式，但是并不是所有的汉语表达中的“或者”、“或”都可以理解成析取连接词.如，“这个屋子里大概有30或40个同学上自习”，这里的“或”不能表示成析取，只是表示屋子里上自习的同学数不确定，大概有三四十个左右.4.条件联结词若P,Q是两个命题，则由条件联结词~和命题P、Q组成的复合命题P→Q称为P、Q的条件式，读作“如果P，则Q".P→Q为假当且仅当P为真而Q为假.因此，P为假时，不管Q为真还是为假，P→Q都为真(我们称其为逻辑学中善意的推测);而P,Q同时为真时，P→Q也为真.复合命题P→Q的真值表如表8-5所示.上一页下一页返回8.2命题逻辑介绍例8-5将下列命题符号化.(1)如果他努力学习，就会门门功课90分以上.(2)若∠1和∠2是对顶角，则∠1=∠2.解(1)设A:他努力学习，B:他门门功课90分以上.则“如果他努力学上一页下一页返回8.2命题逻辑介绍习，就会门门功课90分以上”可符号化为A→B.

(2)设A:∠1和∠2是对顶角，B:∠1=∠2.则“若∠1和∠2是对顶角，则∠1=∠2”可符号化为A→B.可见，A是B的充分条件，或B是A的必要条件.例8-6将下列命题符号化.(1)只要不下雨，我就骑自行车上班.(2)只有不下雨，我才骑自行车上班.解设P:天下雨，Q:我骑自行车上班.上一页下一页返回8.2命题逻辑介绍说明:在(1)中，“不下雨”是“我骑自行车上班”的充分条件.在(2)中，“不下雨”是“我骑自行车上班”的必要条件.5.双条件连接词若P,Q是两个命题，则由双条件连接词H和命题P、Q组成的复合命题P↔Q称为P、Q的双条件式，读作“P当且仅当Q".P↔Q为真当且仅当P、Q的真值相同.复合命题P↔Q的真值表如表8-6所示.上一页下一页返回8.2命题逻辑介绍上一页下一页返回8.2命题逻辑介绍8.2.3命题公式1.命题公式的概念命题符号化的结果常以命题公式的形式呈现出来.那么，什么是命题公式?下面我们以递归的形式给出命题公式的定义.定义8.1(1)单个命题变元是命题公式;(2)若P是命题公式，则，P是命题公式;(3)若P、Q是命题公式，则P∧Q,P∨Q,P→Q,P↔Q都是命题公式;(4)当且仅当有限次地应用(1)、(2)、(3)所得到的包括命题变元、连接词和圆括号的符号串是命题公式.上一页下一页返回8.2命题逻辑介绍命题公式简称公式.在命题公式的递归定义中，(1)是递归的基础，(2)、(3)是归纳，(4)是界限.2.命题公式的赋值一个含有命题变元的命题公式是没有确定真值的，只有将公式中的每个命题变元用指定的命题替代后，命题公式才有确定的真值.将命题变元指派为真命题相当于指定其真值为1，将命题变元指派为假命题相当于指定其真值为0.定义8.2设P1P2,…,Pn，是出现在命题公式中的全部命题变元，对P1,P2,...,Pn指定一组真值，称这组真值为公式G的一个赋值(解释)，记作I，公式G在赋值I下的真值记作T1(G).上一页下一页返回8.2命题逻辑介绍3.命题公式的真值表定义8.3将命题公式G在其所有赋值下所取真值列成一个表，称为命题公式G的真值表.上一页下一页返回8.2命题逻辑介绍上一页下一页返回8.2命题逻辑介绍4.命题公式的分类定义8.4(1)若公式G在所有赋值下的取值都为真，则称G为永真式(重言式);(2)若公式G在所有赋值下的取值都为假，则称G为永假式(矛盾式);上一页下一页返回8.2命题逻辑介绍(3)若至少有一种赋值使公式G的取值为真，则称G为可满足式.由上述定义可知:(1)永真式一定是可满足式，反之不一定.(2)永假式一定是不可满足式.在例8-8中，(2)为永真式，(3)为永假式，(1)为可满足式.8.2.4等价式例如，P→Q与﹁P∨Q形式上看来是两个不同的命题公式，但在任意赋值下它们都具有相同的真值.定义8.5若命题公式A和B在任意赋值(指派)下都具有相同的真值，则称A与B等价，记作

称为命题等价式.上一页下一页返回8.2命题逻辑介绍(分配律)上一页下一页返回8.2命题逻辑介绍代入规则对永真式中任意一个命题变元，可用任意一个命题公式代人，所得公式仍为永真式.置换规则上一页下一页返回8.2命题逻辑介绍设公式Φ(A)是一个含有公式A的命题公式，Φ(B)是用公式B置换了Φ(A)中的A后得到的公式，若上一页下一页返回8.2命题逻辑介绍8.2.5蕴涵式1.蕴涵的概念逻辑的一个重要功能是研究推理.当然，利用等价关系可以进行推理，但在逻辑推理时，不一定必须依靠等价关系，在推理中更多的是用到蕴涵关系.定义8.G设A、B是公式，若A→B是永真式，则称A蕴涵B，记作

称为蕴涵式.常用的墓本蕴涌式:上一页下一页返回8.2命题逻辑介绍上一页下一页返回8.2命题逻辑介绍2.蕴涵的性质蕴涵具有下列常用性质:上一页下一页返回8.2命题逻辑介绍上一页下一页返回8.2命题逻辑介绍8.2.6范式1.析取范式与特异析取范式1)析取范式的特点:(1)析取范式是一个析取式.(2)析取范式中的每个析取项是一个合取式.(3)这个析取式只包含命题变元及其否定.2)特异析取范式的特点(1)特异析取范式是一个析取范式.(2)在特异析取范式的每个析取项中，该公式的所有命题变元均出现，它或以命题变元或以命题变元的否定形式出现，且仅出现一次.上一页下一页返回8.2命题逻辑介绍(2)利用等价式

将否定符号深入至命题变元，并利用

减少否定符号，使命题变元前的否定符号最多为一个.上一页下一页返回8.2命题逻辑介绍(3)利用分配律将公式化归成析取式.(4)除去析取范式中所有为永假的析取项，即出现有﹁P∧P形式的项.(5)若析取项中同一命题变元出现多次，则利用等价式

将其简化成只出现一次.(6)若析取项中不是公式中的所有命题变元都出现，利用

在析取项中将变元Q或P补充进去，且利用分配律将它展开成几个析取项，并除去相同之析取项.上一页下一页返回8.2命题逻辑介绍2.合取范式与特异合取范式1)合取范式的特点(1)合取范式是一个合取式.(2)合取范式中的每个合取项是一个析取式.上一页下一页返回8.2命题逻辑介绍(3)这个合取式只包含命题变元及其否定.2)特异合取范式的特点(1)特异合取范式是一个合取范式.(2)在特异合取范式的每个合取项中，该公式的所有命题变元均出现，它或以命题变元或以命题变元的否定形式出现，且仅出现一次.上一页下一页返回8.2命题逻辑介绍将公式中出现的连接词→及↔之处化归成合取式.(2)利用等价式

将否定符号深入至命题变元，并利用

减少否定符号，使命题变元前的否定符号最多为一个.(3)利用分配律将公式化归成合取式.(4)除去合取范式中所有为永真的合取项，即出现有

形式的项.(5)若合取项中同一命题变元出现多次，则利用等价式

将其简化成只出现一次.(6)若合取项中不是公式中的所有命题变元都出现，利用

或

在合取项中将变元Q或P补充上一页下一页返回8.2命题逻辑介绍进去，且利用分配律将它展开成几个合取项，并除去相同之合取项.上一页返回8.3图论及其应用图论(GraphTheory)是数学的一个分支.它以图为研究对象.图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系.8.3.1基本概念1.图的基本概念现实世界中很多状态可以用某种图形来描述，这种图形是由一些点和一些连接两点间的连线所组成，对于点的位置及连线的长度无关紧要.例如，有a,b,c,d四个足球队进行友谊比赛.为了描述4个队之间比赛的情况，可以用图8.1来表示.下一页返回8.3图论及其应用在图8.1中4个小圆圈分别表示这四个足球队，称之为结点.如果两队进行过比赛，则在表示这两队的结点之间用一条线连接起来，称之为边.设A,B为任意的两个集合，{(a,b)}|a A∧b B}称为A上一页下一页返回8.3图论及其应用解图8.2中分别给出了无向图G和有向图D的图形.上一页下一页返回8.3图论及其应用定义8.8如果两个结点之间有多条边(对于有向图，则有多条同方向的边)，则称这些边为平行边，两结点a,h间平行边的条数称为边的重数.含有平行边的图称为多重图，不含平行边和自回路的图称为简单图.2.图中结点的度数我们常常需要关心图中有多少条边与某一结点关联，这就引出了图的一个重要概念一结点的度.上一页下一页返回8.3图论及其应用如图8.2(a)中，上一页下一页返回8.3图论及其应用如图8.2(b)中，上一页下一页返回8.3图论及其应用由此结点数|V1|必为偶数.定义8.10在图中，度数为0的结点称为孤立点.如图8.2(b)中，结点e为0度，是一个孤立点.3.几种常见的图定义8.11具有n个结点和m条边的图称为(n,m)图.一个(n,0)图称为零图(即该图只有n个孤立结点).只有一个结点的图，即(1,0)图称为平凡图.定义8.12任意两个不同的结点都是邻接的简单图称为完全图.n个结点的无向完全图记为Kn，其边的条数为n(n一1）/2.从图8.3中的K3和K4看出K3有3条边，K4有6条边.容易证明Kn(n-1)/2条边.上一页下一页返回8.3图论及其应用定义8.13设G=〈V（G）,E（G）〉是一个具有ｎ个结点的简单图.以V为结点集，以从完全图Kn，中删去G的所有边后得到的图称为G的补图(或称为G的补)，记为 .如图8.4给出了一个图G和G的补.定义8.14给每条边赋以一个实数(称为该边的权)的图叫有权图.边e的权记为WG(e).有权图G=〈V(G),E(G)〉中所有边的权之和称作图G的权，记为WG(G).例8-14证明在任何一个有6个人的小组中，存在3个人互相认识，或者存在个人互相不认识(拉姆齐问题).分析用6个结点来代表人，并用邻接性来表示两人之间认识关系.这样一来，该例就是要证明:任意一个有6个结点的图中G，或者有3个互相邻接的点，或上一页下一页返回8.3图论及其应用上一页下一页返回8.3图论及其应用4.子图在描述和研究图的性质时，还涉及到另一重要概念一子图.图8.5给出了图G以及它的真子图G1和生成子图G2.上一页下一页返回8.3图论及其应用8.3.2路与回路1.路、回路和连通性上一页下一页返回8.3图论及其应用例如在图8.6中，下面我们利用通路的概念解决一个古老的著名问题.例8-15(渡河问题)一个摆渡人，要把一只狼、一只羊和一捆干草运过河去，河上有一只术船，每次除了人以外，只能带一样东西.并且，上一页下一页返回8.3图论及其应用如果人不在旁时，狼就要吃羊，羊就要吃干草.问这人应该怎样才能把它们运过河去?解用F表示摆渡人，W表示狼，S表示羊，H表示干草.如果用FWSH表示人和其他三样东西在河的左岸.这样，在左岸全部可能出现的状态如下表所示16种:这里Φ表示左岸是空集，即人、狼、羊、干草都已运到右岸去了.上一页下一页返回8.3图论及其应用根据题意，考查一下这16种情况就可以知道，其中有6种情况不允许出现.它们分别是:WSH、FW、FH、WS、SH、F.如FH表示人和干草在左岸，而羊和狼在右岸，狼要吃羊，这当然是不行的.因此，允许出现的情况只有10种，如图8.7所示.定义8.18在图G中，若结点vi到vj有路连接(这时称vi和vj是连通的)，则其中长度最短的路称为从vi到vj的短程.短程的长度称为vi到vj的距离，用符d(vi，vj)表示.例如在图8.6中，d(v1，v3)=2.定理8.3设G是具有n个结点的图，如果从结点vi到另一结点vj，存在一条路，则其短程是一条长度不大于n-1的通路.证明设从结点vi到结点vj存在一条路μ，该路上的结点序列为

可用反证法证明，当μ是短程时，μ一定是通路.上一页下一页返回8.3图论及其应用推论设图G=(V,E)，|V|=n,则G中任一基本回路的长度不大于n.如果一个图的任何两个结点之间都有一条路，那么我们称这个图是连通的，否则是不连通的.定义8.19图G的一个连通的子图(称为连通子图)若不包含在G的任何更大的连通子图中，它就被称作G的连通分支，常把图G的连通分支数记作W(G).在图8.8中，G是不连通的，W(G)=2，而G′是连通的，W(G′)=1.任何一个图都可划分为若干个连通分支.显然，仅当图G的连通分支数W(G)=1时，图G是连通的.2.有权图的最短路径问题有权图经常出现在图的应用中.如在交通图中，权可以表示两地的距离;在通讯图中，权可以表示各种通讯线路的建造或维修费用等等.上一页下一页返回8.3图论及其应用上一页下一页返回8.3图论及其应用上一页下一页返回8.3图论及其应用为清楚起见，将本算法用流程图表示，见图8.9所示.例8-16在图8.10所示的有权图中，用迪克斯特拉算法求结点v0到其余各点的最短路径.上一页下一页返回8.3图论及其应用算法共执行6次，求解示意图见图8.11所示.上一页下一页返回8.3图论及其应用上一页下一页返回8.3图论及其应用8.3.3图的矩阵表示上面介绍了图的一种表示方法一用图形表示图.它的优点是形象直观，但是这种表示在结点与边的数日很多时是不方便的.下面介绍另一种表示方法一用矩阵表示图.利用这种方法，可以把图用矩阵存储在计算机中，利用矩阵的运算还可以了解到它的一些有关性质.定义8.21设G=(V,E)是有n个结点的图，则n阶方阵A=(aij)称为G的邻接矩阵.其中如图8.12所示的图G，其邻接矩阵A为上一页下一页返回8.3图论及其应用显然，无向图的邻接矩阵一定是对称的.在邻接矩阵A的幂A²，A³，…矩阵中，每个元素有特定的含义，下面定理进行了说明.上一页下一页返回8.3图论及其应用上一页下一页返回8.3图论及其应用例8-17图G=(V,E)的图形如图8.13所示，求邻接矩阵A和A²,A³,，并分析其元素的图论意义.解上一页下一页返回8.3图论及其应用上一页下一页返回8.3图论及其应用上一页下一页返回8.3图论及其应用8.3.4树树是图论中的一个重要概念.在1847年克希霍夫就提出用树的理论来研究电网络，1857年凯莱在计算有机化学中C2H2n+2的同分异构物数日时一也用到了树的理论.而树在计算机科学中应用更加广泛.本节介绍树的基本知识，其中谈到的图都假定为简单图.1.树的概念定义8.22一个连通无回路图称为树.树中度数为1的结点称为树叶(或终端结点)，度数大于1的结点称为分枝点(或内点，或非终端结点)一个无回路图称为森林.显然，若图G是森林，则G的每个连通分支是树.如图8.14(a)图所示的是一棵树;（b）图所示的是森林.上一页下一页返回8.3图论及其应用定理8.5一个(n,m)图G是树的充分必要条件是G连通且m=n-1.上一页下一页返回8.3图论及其应用定理8.G设T是一棵(n,m)树，则T有如下性质:(1)T中去掉任意一条边后，所得的图G是不连通的.(2)T中每一对结点间有且仅有一条通路相连.(3)在T中不相邻接的任意两结点间添加一条边后形成的图有且仅有一个回路.(4)若树T的结点数n≥2，则T至少有两片树叶.证明(1)如果G是连通的，那么G仍是树.由定理8.5知，G有n-1条边，即与T的边数相同，矛盾.(2)因为T连通，由定理8.3知，T的任一对结点u、v之间有一条通路相连.若u,v间通路不唯一，则T中必有回路，与树的定义矛盾.所以仅有一条通路连接u与v.上一页下一页返回8.3图论及其应用上一页下一页返回8.3图论及其应用由定理8.5所描述的树的特征得出:在结点数给定的所有图中，树是边数最少的连通图，是边数最多的无回路图.由此可知，在一个(n，m)图G中，若m<n-1,则G是不连通的;若m>n-1，则G必定有回路.2.生成树定义8.23若连通图G的生成子图是一棵树，则称该树是G的生成树，记为TG.生成树TG中的边称为树枝，图中其他边称为TG的弦，所有这些弦的集合称为TG的补.如图8.15(b)所示的树T1是图8.15(a)的生成树，而8.15(c)(d)所示的树T2,T3不是8.15(a)图的生成树一般的，图的生成树不唯一上一页下一页返回8.3图论及其应用例8-18某地要兴建5个工厂，拟修筑道路连接这5处.经勘测其道路可依如图8.16的无向边铺设.为使这5处都有道路相通，问至少要铺几条路?解这实际上是求G的生成树的边数问题.

一般情况下，设连通图有n个结点，m条边.由树的性质知，T有n个结点，n-1条树枝，m-n+1条弦.在图8.16中，n=5，则n-1=5-1=4,所以至少要修4条路才行.3.最小生成树定义8.24设G=(V,E)是一连通的有权图，则G中具有最小权的生成树TG称为G的最小生成树.求最小生成树问题是有实际意义的.上一页下一页返回8.3图论及其应用上一页下一页返回8.3图论及其应用例8-19求图8.17中有权图的最小生成树.解因为图中n=8，所以按算法要执行n-1=7次，其过程见图8.17中(a)～(g)8.3.5根树及其应用1.根树、有序树、M叉树定义8.25一个有向图，若不考虑边的方向，它是一棵树，则这个有向图称为有向树一棵有向树，如果仅有一个结点的人度为0，其余所有结点的人度都为1,则称为根树，其中人度为0的结点称为根，出度为0的结点称为叶，出度不为0的结点称为分枝点或内点.如图8.18(a)表示一棵根树，其中v1为根，v2，v3为分枝点，其余结点为叶，一般情况下，习惯把根树的根画在上方，叶画在下方.这样就可以省去根树的箭头，如上一页下一页返回8.3图论及其应用图8.18(b).在根树中，称从树根到结点v的距离为该点的层次.这样对图8.17中的根树，v1的层次为0，v2、v3的层次为1，其余结点的层次均为2.我们用家族关系表示根树中各结点的关系.上一页下一页返回8.3图论及其应用定义8.28如果在根树中规定了每一层次上结点的次序，这样的根树称为有序树.在有序树中规定同一层次结点的次序是从左至右.在树的实际应用中，经常研究完全刀m叉树.定义8.29在根树中，若每个结点的出度小于或等于m，则称这棵树为m叉树.如果每个结点的出度恰好等于0或m，则称这棵树为完全m叉树.二又树的每个结点v至多有两棵子树，分别称为v的左子树和右子树.例8-20甲、乙两人进行象棋比赛，规定三局两胜，表示出比赛可能出现的各种情况.解图8.19表示了比赛可能出现的所有情况，图中结点标甲者表示甲胜，标乙者表示乙胜.由定义可知，这是一颗完全二又树.上一页下一页返回8.3图论及其应用2.二叉树m叉树中，二叉树应用得最为广泛.由于在计算机中最易处理的是二叉树，所以常常要把一棵有序树转换为二叉树.转换的一般步骤为:(1)从根开始，保留每个父亲与其最左边孩子的连线，撤销与别的孩子的连线;(2)兄弟间用从左向右的有向边连接;(3)用如下方法选定二叉树的左孩子和右孩子:直接处于给定结点下面的结点作为左孩子;对于同一水平线上与给定结点右邻的结点作为右孩子，依次类推.例8-21将图8.20(a)所示的三叉树转换为一棵二叉树.解对图8.20(a)进行步骤(1),（2)得8.20（b)，再按步骤(3)得8.20(c).图8.20(c)即为所求的二叉树.上一页下一页返回8.3图论及其应用反过来，我们一也可将8.20(c)还原为8.20(a).一个森林一也可转换为二叉树.其步骤为:(1)先把森林中的每一棵树表示成一棵二叉树;(2)除第一棵二叉树外，依次将每棵二叉树作为左边二叉树的根的右子树，直到所有的二叉树都连成一棵二叉树为止.例8-22将图8.21(a)所示的森林转换为一棵二叉树.解如图8.21(b)的二叉树即为所求.

反过来，我们一也可将二叉树转换成森林.研究二叉树有一个十分重要的问题，就是要找到一些方法能系统地访问树的结点，使得每个结点恰好被访问一次，这就是二叉树的遍历问题.上一页下一页返回8.3图论及其应用下面介绍二又树的三种常用的遍历方法.1)先根次序遍历法，分三步.(1)访问根;(2)按先根次序遍历根的左子树;(3)按先根次序遍历根的右子树.2)中根次序遍历法，分3步.(1)按中根次序遍历根的左子树;(2)访问根;(3)按中根次序遍历根的右子树.3)后根次序遍历法，分3步.(1)按后根次序遍历根的左子树;(2)按后根次序遍历根的右子树;上一页下一页返回8.3图论及其应用

(3)访问根.

对一棵树的遍历有两种方法，即先根次序遍历和后根次序遍历.以图8.21(a)和相应的二又树图8.21(c)为例讨论如下:图8.21(a)的先根次序遍历的结果为图8.21(c)的先根次序遍历的结果一也为图8.21(a)的后根次序遍历的结果为图8.21(c)的中根次序遍历的结果一也为分析以上结果可以看出如下结论:(1)树的先根次序正是相应二叉树的先根次序;(2)树的后根次序正是相应二叉树的中根次序.该结果具有普遍的意义.上一页下一页返回8.3图论及其应用定义8.30在根树中，一个结点的通路长度，就是从树根到此结点通路的边数.把