12-1-aolm-离散数学.ppt

??第第1 1篇篇数理逻辑数理逻辑??第第2 2篇篇集合论集合论??第第3 3篇篇代数结构代数结构??第第4 4篇篇图论图论第第4 4篇篇图论图论模型化是数学中的一个基本概念,它处于所模型化是数学中的一个基本概念,它处于所有的数学应用之心脏,也处于某些最抽象的纯数有的数学应用之心脏,也处于某些最抽象的纯数学核心之中。学核心之中。 R R . . C C . . Buck Buck 第第4 4篇篇图论图论??第第 10 10 章章图图??第第 11 11 章章特殊图特殊图??第第 12 12 章章树树第第4 4篇篇图论图论??第第 12 12 章章树树?? 树的概念树的概念?? 生成树生成树?? 根树、二叉树及其应用根树、二叉树及其应用?? 典型例题解析典型例题解析第第 12 12 章章树树几何、理论算术和代数,这些学科除了定义和几何、理论算术和代数,这些学科除了定义和公理之外,没有其它原则,除了演绎以外,没有其公理之外,没有其它原则,除了演绎以外,没有其它证明过程。但就在这一过程中,却已综合了简单它证明过程。但就在这一过程中,却已综合了简单性、复杂性、严密性和一般性,这一特性是不为其性、复杂性、严密性和一般性,这一特性是不为其它学科所具有的。它学科所具有的。 Whewell Whewell W. W. 首先介绍树的基本概念; 首先介绍树的基本概念; 然后将分别介绍生成树、根树及特殊的一类根然后将分别介绍生成树、根树及特殊的一类根树树————二叉树及其应用。二叉树及其应用。第第 12 12 章章树树树是一类特殊的二分图(偶图)。作为计算机科学树是一类特殊的二分图(偶图)。作为计算机科学中常用的一种数据结构,树有许多非常好的性质,因此树中常用的一种数据结构,树有许多非常好的性质,因此树被广泛地应用于算法设计、数据结构、网络、人工智能、被广泛地应用于算法设计、数据结构、网络、人工智能、软件工程、知识工程以及其他领域。软件工程、知识工程以及其他领域。 树的概念树的概念定义定义 一个连通且无回路的无向图称为一个连通且无回路的无向图称为树树。在树中度数。在树中度数为为 1 1 的结点称为的结点称为树叶树叶,度数大于,度数大于 1 1 的结点称为的结点称为分枝点分枝点( (内内点点)。单一孤立结点称为)。单一孤立结点称为空树空树。如果一个无回路的无向图的。如果一个无回路的无向图的每一个连通分图是树,且连通分支数大于等于每一个连通分图是树,且连通分支数大于等于 2 2,那么称为,那么称为森林森林。。 v v 3 3v v 2 2v v 7 7v v 4 4v v 1 1v v 9 9v v 5 5v v 8 8v v 6 6( (a a) )树树( (b b) )树树( (c c) )森林森林定理定理 ““给定图为树给定图为树””与下列任一命题等价: 与下列任一命题等价: ( (1 1)无回路的连通图; )无回路的连通图; ( (2 2)无回路且)无回路且 e=v-1 e=v-1 ,其中,其中 e e 是边数, 是边数, v v 是结点数; 是结点数; ( (3 3)连通且)连通且 e=v-1 e=v-1 ; ; ( (4 4)无回路,但增加一条新边,得到一个且仅有一个回路; )无回路,但增加一条新边,得到一个且仅有一个回路; ( (5 5)连通,但删去一边后就不再连通; )连通,但删去一边后就不再连通; ( (6 6)每一对结点之间有且仅有一条路。)每一对结点之间有且仅有一条路。证明:将一次证明证明:将一次证明⑴⑴??⑵⑵、、⑵⑵??⑶⑶、、⑶⑶??⑷⑷、、⑷⑷??⑸⑸、、⑸⑸??⑹⑹、、⑹⑹??⑴⑴,从而证明,从而证明 6 6 个命题之间的等价性,使定理得证。个命题之间的等价性,使定理得证。( (1 1)归纳法证明)归纳法证明⑴⑴??⑵⑵??设在图设在图 T T 中,当中,当 v v= = 2 2 时,连通无向图, 时,连通无向图, T T 中中的边数的边数 e e= =1 1,因此,因此 e e= =v v??1 1成立。成立。??设设v v= =k k?? 1 1 时命题成立,当时命题成立,当 v v= = k k 时,因无向图时,因无向图且连通,故至少有一条边其一个端点且连通,故至少有一条边其一个端点 u u 的度数为的度数为 1 1。设。设该边为该边为( ( u, w u, w ) ),删去结点,删去结点 u u,便得到一个,便得到一个 k k?? 1 1 个结点个结点的连通无向图的连通无向图 T T’’,由归纳假设