离散数学-第七章 树及其应用-内容提要
离散数学课件 第七章 树trees
第7章树trees 分类 §7.1 树 定义1： T是集合A上一个二元关系，T称为树tree，
如果存在v0∈A，任意v∈A，v≠v0，到v0都有唯一一条路径，（v0, v0） T. T叫做根树，记做（T，v0）。 A中元素称为T的顶点vertex，T中元素称为边，v0称为根root。 定理1. 设（T，v0）是树，则 (a)T中没有回路。 (b)只有一个根v0。 (c)任意v∈A，v≠v0，v有入度1，v0入度是0。 证明： 定义2 层次level v0的层次为0，v0的子女offspring层次为1，v0是子女的父母parent。 v i的层次为k，v i的子女offspring层次为k ＋1，v i是子女的父母parent， T的最大层次称为高度height。 无子女的顶点叫叶leaf。
v i的子女叫同胞sibling，同胞如有长幼，从左到右，老大，老二，老三等，组成线性序，T称为有序树，ordered tree 定理2. 设（T，v0）是根树，则 (a)T反自反。 (b)T反对称。 (c)(a,b)∈T，(b，c)∈T ? (a，c)?T。 定义3： n－树：每个顶点至多n个子女。 二叉树：2－树。 完全n－树：每个非叶顶点恰有n个子女。定义4 A rooted binary tree is a rooted tree in which every node has at most two children. A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which
离散数学第三版课后习题答案
离散数学辅助教材 概念分析结构思想与推理证明 第一部分 集合论
离散数学习题解答 习题一（第一章集合） 1. 列出下述集合的全部元素： 1）A={x | x ∈N∧x是偶数∧x＜15} 2）B={x|x∈N∧4+x=3} 3）C={x|x是十进制的数字} [解] 1）A={2，4，6，8，10，12，14} 2）B= 3）C={0，1，2，3，4，5，6，7，8，9} 2. 用谓词法表示下列集合： 1）{奇整数集合} 2）{小于7的非负整数集合} 3）{3，5，7，11，13，17，19，23，29} [解] 1）{n n∈I∧(?m∈I)(n=2m+1)}； 2）{n n∈I∧n≥0∧n<7}； 3）{p p∈N∧p>2∧p<30∧?(?d∈N)(d≠1∧d≠p∧(?k∈N)(p=k?d))}。 3. 确定下列各命题的真假性： 1） 2）∈ 3）{} 4）∈{} 5）{a，b}{a，b，c，{a，b，c}} 6）{a,b}∈(a，b，c，{a，b，c}) 7）{a，b}{a，b，{{a，b，}}} 8）{a，b}∈{a，b，{{a，b，}}} [解]1）真。因为空集是任意集合的子集； 2）假。因为空集不含任何元素； 3）真。因为空集是任意集合的子集； 4）真。因为是集合{}的元素； 5）真。因为{a，b}是集合{a，b，c，{a，b，c}}的子集； 6）假。因为{a,b}不是集合{a，b，c，{a，b，c}}的元素；
7）真。因为{a，b}是集合{a，b，{{a，b}}}的子集； 8）假。因为{a,b}不是集合{a，b，{{a，b}}}的元素。 4. 对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B∈C，则A∈C。 2）如果A∈B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A∈C。 [解] 1）假。例如A={a}，B={a，b}，C={{a}，{b}}，从而A∈B∧B∈C但A∈C。 2）假。例如A={a}，B={a，{a}}，C={{a}，{{a}}}，从而A∈B∧B∈C，但、A ∈C。 3）假。例如A={a}，B={a，b}，C={{a}，a，b}，从而ACB∧B∈．C，但A∈C。5．对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B C，则A∈C。 2）如果A∈B∧B C，则A C。 3）如果A B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A C。 [解] 1）真。因为B C x（x∈B x∈C），因此A∈B A∈C。 2）假。例如A={a}，B={{a}，{b}}，C={{a}，{b}，{c}}从而A∈B∧B C，但A C。 3）假。例如A={a}，B={{a，b}}，C={{a，{a，b}}，从而A B∧B∈C，但A C。 4）假。例如A={a}，B={{a，b}}，C={{a，b}，b}，从而A B∧B∈C，但A C。 6．求下列集合的幂集： 1）{a，b，c} 2）{a，{b，c}} 3）{} 4）{，{}} 5）{{a，b}，{a，a，b}，{a，b，a，b}} [解] 1）{，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}} 2）{，{a}，{{b，c}}，{a，{a，b}}} 3）{，{}} 4）{，{}，{{}}，{，{}}}
离散数学及其应用 重要名词中英对应以及重要概念解释与举例
离散数学及其应用重要名词中英对应以及重要概念解释与举例 1 The Foundations: Logic and Proofs（逻辑与证明） 1.1 Propositional Logic（命题逻辑） Propositions（命题）——declarative sentence that is either true or false, but not both.判断性语句，正确性唯一。 Truth Table（真值表） Conjunction（合取，“与”，and），Disjunction（析取，or，“相容或”），Exclusive（异或），Negation（非，not），Biconditional（双条件，双向，if and only if） Translating English Sentences 1.2 Propositional Equivalences（命题等价） Tautology（永真式、重言式），Contradiction（永假式、矛盾式），Contingency（偶然式） Logical Equivalences（逻辑等价）——Compound propositions that have the same truth values in all possible cases are called logical equivalent.（真值表相同的式子，p<->q是重言式） Logical Equivalences——Page24 Disjunctive normal form(DNF，析取范式) Conjunctive normal form(CNF，合取范式) 见Page27～29 1.3 Predicates and Quantifiers（谓词和量词） Predicates——谓词，说明关系、特征的修饰词 Quantifiers——量词 ? Universal Quantifier(全称量词) "
(完整版)离散数学及其应用(课后习题)
习题1.1 2. 指出下列命题是原子命题还是复合命题。 （3）大雁北回，春天来了。 （4）不是东风压倒西风，就是西风压倒东风。 （5）张三和李四在吵架。 解：（3）和（4）是复合命题，（5）是原子命题。 习题1.2 1. 指出下列命题的真值： （1）若224+>，则太阳从西方升起。 解：该命题真值为T （因为命题的前件为假）。 （3）胎生动物当且仅当是哺乳动物。 解：该命题真值为F （如鸭嘴兽虽是哺乳动物，但不是胎生动物）。 2. 令P ：天气好。Q ：我去公园。请将下列命题符号化。 （2）只要天气好，我就去公园。 （3）只有天气好，我才去公园。 （6）天气好，我去公园。 解：（2）P Q →。 （3）Q P →。 （6）P Q ?。 习题1.3 2. 将下列命题符号化（句中括号内提示的是相应的原子命题的符号表示）： （1）我去新华书店（P ），仅当我有时间（Q ）。 （3）只要努力学习（P ），成绩就会好的（Q ）。 （6）我今天进城（P ），除非下雨（Q ）。 （10）人不犯我（P ），我不犯人（Q ）；人若犯我，我必犯人。 解：（1）P Q →。 （3）P Q →。 （6）Q P ?→。 （10）()()P Q P Q ?→?∧→。 习题1.4 1. 写出下列公式的真值表： （2）()P Q R ∨→。
解：该公式的真值表如下表： 2. 证明下列等价公式： （2）()()()P Q P Q P Q ∨∧?∧???。 证明： ()(()()) ()()) ()() ()() P Q P Q P Q P Q P Q P Q P Q P Q P Q ????∧∨?∧???∧∧??∧???∧∧∨?∨∧?∧ （4）()()()P Q P R P Q R →∧→?→∧。 证明： ()()()() () () P Q P R P Q P R P Q R P Q R →∧→??∨∧?∨??∨∧?→∧ 3. 甲、乙、丙、丁4人参加考试后，有人问他们谁的成绩最好，甲说，不是我。乙说：是丁。丙说：是乙。丁说：不是我。已知4个人的回答只有一个人符合实际，问成绩最好的是谁？ 解：设A ：甲成绩最好。B ：乙成绩最好。C ：丙成绩最好。D ：丁成绩最好。 四个人所说的命题分别用P Q R S 、、、表示，则 P A ??；Q A B C D ??∧?∧?∧；R A B C D ??∧∧?∧?；S D ??。 则只有一人符合实际的命题K 符号化为 ()()()() K P Q R S P Q R S P Q R S P Q R S ?∧?∧?∧?∨?∧∧?∧?∨?∧?∧∧?∨?∧?∧?∧
离散数学 树 知识点总结
第六章树 一、掌握基本概念 树的子树是互不相交的，树可以为空（空树） 非空的树中，只有一个结点是没有前趋的，那就是根。 非空树只有一个树根，是一对多的关系。 叶子结点、结点的度、树的度、结点的层次、树的深度、树的四种表示方法 二、二叉树的定义、特点、五种基本形态 二叉树是有序树，左右子树不能互相颠倒 二叉树中结点的最大度为2，但不一定都是2。 三、二叉树的性质要掌握 性质1：二叉树的第i层上至多有2 i-1（i 1）个结点。 性质2：深度为k的二叉树中至多2k-1个结点。 性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。 证明：1)结点总数n=n0+n1+n2 (n1是度为1的结点数) 2)进入分支总数m(每个结点唯一分支进入) n=m+1 3)m个分支是由非叶子结点射出m=n1+2n2 性质4：具有n个结点的完全二叉树的深度k为[log2n]+1 四、满二叉树和完全二叉树的区别是什么？ 满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树。 深度为k的二叉树，最少有k个结点，最多有2k-1 深度为k的完全二叉树，最少有2k-1-1+1个结点,最多有2k-1 五、二叉树的存储结构（可以通过下标找结点的左右孩子） 1.顺序存储结构适用于满二叉树和完全二叉树。（其缺点是必须把其他二叉树补成完全二叉树，从上到下，从左到右依次存储在顺序存储空间里，会造成空间浪费） 2.二叉链表存储结构（其优点是找左孩子和右孩子方便，但缺点是找父节点麻烦） lchild Data rchild （重点） 3. 三叉链表存储结构
不仅找其左、右孩子很方便，而且找其双亲也方便 六、遍历的概念是什么？ 七、二叉树的遍历有三种：前序（先序、先根）遍历、中序（中序、中根）遍历、后序（后序、后根）遍历 1.给出一棵二叉树，要会二叉树的三种遍历 2.给出两种遍历（必须有中序遍历），要求会画该二叉树。 八、了解引入线索（中序、先序、后序）二叉树的原因是什么？ 九、会在二叉树上画先序线索化、中序线索化、后序线索化。 在线索二叉树的格式中，可以找到任意结点的直接后继。（错） 在线索二叉树中，如果某结点的右孩子为空，那么可以找到该结点的直接后继。（对） 在线索二叉树中，如果某结点的左孩子为空，那么可以找到该结点的直接前趋。（对）十、树.森林和二叉树的相互转换 树转换成二叉树后，转换后的二叉树根的右子树为空。 十一、森林的遍历（只有先序遍历和后序遍历） 先序遍历一棵树，相当于先序遍历该树所对应的二叉树。 后序遍历一棵树，相当于中序遍历该树所对应的二叉树。 十二、赫夫曼树（又称最优二叉树或哈夫曼树）、赫夫曼树编码 1. 赫夫曼树中，权越大的叶子离根越近，其形态不唯一，但是WPL带权路径长度一定是最小。 2.一定要会构造哈夫曼树，在构造好的哈夫曼树上会构造哈夫曼编码。（认真看题目要求）第6章算法设计题 1．已知二叉树中的结点类型用BiTNode表示，被定义描述为： Typedef struct BiTNode { TElemType data ; struct BiTNode * LChild , *RChild; } BiTNode,*BiTree; 其中data为结点值域，LChild和RChild分别为指向左、右孩子结点的指针域，编写出求一棵二叉树高度的算法。 Int BTreeHeight(BiTree BT){
离散数学章练习题及答案
离散数学练习题 第一章 一．填空 1.公式) ∨ ? ∧的成真赋值为 01；10 ? p∧ ( (q ) p q 2.设p, r为真命题，q, s 为假命题，则复合命题) ? ? →的真值为 0 p→ ( q (s ) r 3.公式) ∨ ? p∧ q ?与共同的成真赋值为 01；10 ? ∧ p ( ) ) (q q p ( 4.设A为任意的公式，B为重言式，则B A∨的类型为重言式 5．设p, q均为命题，在不能同时为真条件下，p与q的排斥也可以写成p与q的相容或。 二．将下列命题符合化 1. 7不是无理数是不对的。 解：) ? ?，其中p: 7是无理数；或p，其中p: 7是无理数。 (p 2.小刘既不怕吃苦，又很爱钻研。 解：其中 ?p: 小刘怕吃苦，q：小刘很爱钻研 p∧ ,q 3.只有不怕困难，才能战胜困难。 解：p →，其中p: 怕困难，q: 战胜困难 q? 或q →，其中p: 怕困难， q: 战胜困难 p? 4.只要别人有困难，老王就帮助别人，除非困难解决了。 解：) → ?，其中p: 别人有困难，q:老王帮助别人，r: 困难解决了 p (q r→ 或：q ?) (，其中p:别人有困难，q: 老王帮助别人，r: 困难解决了r→ ∧ p 5.整数n是整数当且仅当n能被2整除。 解：q p?，其中p: 整数n是偶数，q: 整数n能被2整除 三、求复合命题的真值 P：2能整除5， q：旧金山是美国的首都， r：在中国一年分四季 1. )) p∧ → q ∨ r → ∧ ((q r ( ) ( ) p 2.r ?) → (( → (( ∨ ) ( )) p r p ∨ p q ? ∧ ? q∧ 解：p, q 为假命题，r为真命题 1.)) p∧ → q ∨的真值为0 r → ∧ ( ) ( ) ((q p r
离散数学-最小生成树
实验五 实验名称： 得到最小生成树 实验目的： 1.熟悉地掌握计算机科学技术常用的离散数学中的概念、性质和运算；通过实验提高学生编写实验报告、总结实验结果的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。 2.掌握图论中的最小生成树及Prim 和 Kruskal 算法等，进一步能用它们来解决实际问题。 实验内容： 输入一个图的权矩阵，得到该图的生成树，用Kruskal算法的最小生成树，用Prim算法的最小生成树。
Kruskal算法 假设T中的边和顶点均涂成红色，其余边为白色。开始时G中的边均为白色。 1）将所有顶点涂成红色； 2）在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红； 3）重复2）直到有n-1条红色边，这n-1条红色边便构成最小生成树T的边集合。 Prim算法 假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则prim算法通过以下步骤可以得到最小生成树: 1)初始化:U={u 0},TE={f}。此步骤设立一个只有结点u 0的结点集U和一个空的边集TE作为最小生成树的初始形态,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止。 2)在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u 0,v 0)，将此边加进集合TE中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U 中,其次边的权要最小。找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中。这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解算法时要密切注意。 3)如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当U=V时,步骤2共执行了n－1次(设n为图中顶点的数目),TE中也增加了n－1条边,这n－1条边就是需要求出的最小生成树的边。
离散数学及应用课后习题答案
离散数学及应用课后习题答案 【篇一：离散数学及其应用图论部分课后习题答案】 p165:习题九 1、给定下面4个图（前两个为无向图，后两个为有向图）的集合 表示，画出它们的图形表 示。 （1）g1??v1,e1?，v1?{v1,v2,v3,v4,v5}， e1?{(v1,v2),(v2,v3),(v3,v4),(v3,v3),(v4,v5)} （2）g2??v2,e2?， v2?v1，e1?{(v1,v2),(v2,v3),(v3,v4),(v4,v5),(v5,v1)} （3） d1??v3,e3?,v3?v1,e3?{?v1,v2?,?v2,v3?,?v3,v2?,?v4,v5?,?v5,v 1?} （4） d2??v4,e4?,v4?v1,e3?{?v1,v2?,?v2,v5?,?v5,v2?,?v3,v4?,?v4,v 3?} 解答：（1） （2） 10、是否存在具有下列顶点度数的5阶图？若有，则画出一个这样 的图。 （1）5，5，3，2，2；（2）3，3，3，3，2；（3）1，2，3，4，5；（4）4，4，4，4，4 解答：（1）（3）不存在，因为有奇数个 奇度顶点 。 14、设g是n(n?2)阶无向简单图，g是它的补图，已 知?(g)?k1,?(g)?k2，求?(g)， ?(g)。 解答：?(g)?n?1?k2；?(g)?n?1?k1。 15、图9.19中各对图是否同构？若同构，则给出它们顶点之间的双 射函数。 解答： （c）不是同构，从点度既可以看出，一个点度序列为4，3，3，3，3而另外一个为4，4，3，3，1 （d）同构，同构函数为 ?1?2??f(x)??3 ?4???5 解答： （1）三条边一共提供6度；所以点度序列可能是
离散数学第10章习题答案
第10章习题答案 1.解 (1)设G 有m 条边，由握手定理得2m ＝∑∈V v v d )(＝2＋2＋3＋3＋4＝14，所以G 的边数7条。 (2)由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度数列。 (3) 由握手定理得∑∈V v v d )(＝2m ＝24，度数为3的结点有6个占去18度，还有6度由其它结点占有， 其余结点的度数可为0、1、2，当均为2时所用结点数最少，所以应由3个结点占有这6度，即图G 中至多有9个结点。 2.证明 设1v 、2v 、…、n v 表示任给的n 个人，以1v 、2v 、…、n v 为结点，当且仅当两人为朋友时其对应的结点之间连一条边，这样得到一个简单图G 。由握手定理知 ∑=n k k v d 1 )(＝3n 必为偶数，从而n 必为偶数。 3. 解 由于非负整数列d ＝(d 1，d 2，…，d n )是可图化的当且仅当∑=n i i d 1 ≡0(mod 2)，所以(1)、(2)、 (3)、(5)能构成无向图的度数列。 (1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。 (5)是不可简单图化的。若不然，存在无向图G 以为1，3，3，3度数列，不妨设G 中结点为1v 、2v 、 3v 、4v ，且d(1v )＝1，d(2v )＝d(3v )＝d(4v )＝3。而1v 只能与2v 、3v 、4v 之一相邻，设1v 与2v 相邻，于 是d(3v )＝d(4v )＝3不成立，矛盾。 4.证明 因为两图中都有4个3度结点，左图中每个3度结点均与2个2度结点邻接，而右图中每个3度结点均只与1个2度结点邻接，所以这两个无向图是不同构的。 5. 解 具有三个结点的所有非同构的简单有向图共16个，如图所示，其中(8)~(16)为其生成子图。 6. 解 (1)G 的所有子图如图所示。 (1)(3)(5) (6) (9)(10) (13) (14)
离散数学答案解析
离散数学 1、在由3个元素组成的集合上，可以有 ( B ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ D ） 。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（D ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ C ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ C ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ C ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ B ）。 [A]3个 [B]6个 [C]8个 [D]9个 8、一个连通图G 具有以下何种条件时，能一笔画出：即从某结点出发，经过图中每边仅一次回到该结点（ A ）。 [A] G 没有奇数度结点 [B] G 有1个奇数度结点 [C] G 有2个奇数度结点 [D] G 没有或有2个奇数度结点 9、设〈G,*〉是群，且|G|>1，则下列命题不成立的是（ B ）。 [A] G 中有幺元 [B] G 中么元是唯一的 [C] G 中任一元素有逆元 [D] G 中除了幺元外无其他幂等元 10、令p ：今天下雪了，q ：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ） [A] p →┐q [B] p ∨┐q [C] p ∧q [D] p ∧┐q 11、设图G=
离散数学--最小生成树实验报告
一、实验目的：掌握图的存储表示和以及图的最小生成树算法。 二、实验内容： 1.实现图的存储，并且读入图的内容。 2.利用克鲁斯卡尔算法求网络的最小生成树。 3.实现构造生成树过程中的连通分量抽象数据类型。 4.以文本形式输出对应图的最小生成树各条边及权值。 三、实验要求： 1．在上机前写出全部源程序； 2．能在机器上正确运行程序； 3．用户界面友好。 需求分析： 1、利用克鲁斯卡尔算法求网的最小生成树； 2、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列； 3、输入为存在边的顶点对，以及它们之间的权值；输出为所得到的邻接矩 阵以及按权排序后的边和最后得到的最小生成树； 克鲁斯卡尔算法：假设WN=(V,{E}) 是一个含有n 个顶点的连通网，按照构造最小生成树的过程为：先构造一个只含n 个顶点，而边集为空的子图，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至只有一棵树，也即子图中含有n-1条边为止。 测试数据： 自行指定图进行运算
四、详细设计 源程序 #include
离散数学
1.设G有16条边，有三个四度顶点，四个三度顶点，其余顶点的度数都小于3，问G中至少 有几个顶点？ 答：总度数=16*2=32 3*4+4*3=24 （32-24）/2=4 至少有3+4+4=11 至少有11个顶点 2．设9阶无向图G中，每个顶点的度数不是5就是6，证明G中至少有5个六度定点或者至少 有6个5度顶点 证明，因为：4*6+5*5=24+25=49不可能， 所以当n6<4 时，n5>=6 满足条件 当n6>=5时，满足条件 得证 3.空间不可能存在奇数个面而且每个面均有奇数条棱的多面体 答：假如有奇数个面n 每个面都有奇数个棱mi(I=1,2,…n)， 那么m1+m2+…+mn= D mi为奇数，n奇数，所以D为奇数 但对于上式来说，每条棱都记了两次，那么D=2*(总棱数) 为偶数矛盾 所以空间不可能存在奇数个面而且每个面均有奇数条棱的多面体 4.在一次象旗比赛中，任意两个选手之间至多只下一盘棋，又每个人至少下一盘，证明总能找到两名选手，他们下过的盘数是相同的 证明：建一个图的模型：每个选手相当于图的顶点，选手下的盘数相当于顶点得度数，两个选手的对局相当于两个顶点的边，已知顶点的度数是1----n-1, 选手有n个，根据鸽 巢原理 可知，比存在两个顶点的度数相同，也就是总能找到两名选手，他们下过的盘数是相同的。 5.设n阶无向简单图G为3次图(3-正则图)，边数m和n满足以下关系2n-3=m 问G有几种非同构的情况？并证明你的结论 解：3n=2m 2n-3=m => n=6 m=9 所以G是6阶3正则图.设G1，G2均为无向简单图，G1同构于G2 等价于G1的补图同构 于G2的补图。所以可知有两种同构的情况 6．下面给出的两个整数列，哪个是可图化的，对于可图化的请至少给出三个非同构的图1）d=(1,2,2,4,4,5) 可图化 2）d=(1,1,2,2,3,3,5) 不可图化 非同构的图，赫赫在BBS上没法画！ 7.判断下列三个整数列中哪些是可以简单图化的？对于可简单图化的试给出两个非同构的图.
离散数学及其应用集合论部分课后习题答案
作业答案：集合论部分 P90:习题六 5、确定下列命题是否为真。 （2）?∈? （4）{}?∈? （6）{,}{,,,{,}}a b a b c a b ∈ 解答：（2）假（4）真（6）真 8、求下列集合的幂集。 （5）{{1,2},{2,1,1},{2,1,1,2}} （6）{{,2},{2}}? 解答： （5）集合的元素彼此互不相同，所以{2,1,1,2}{1,2}=，所以该题的结论应该为 {,{{1,2}},{{2,1,1}},{{1,2},{2,1,1}}}? （6）{,{{,2}},{{2}},{{,2},{2}}}??? 9、设{1,2,3,4,5,6}E =，{1,4}A =，{1,2,5}B =,{2,4}C =,求下列集合。 （1）A B （2）()A B 解答： （1）{1,4}{3,4,6}{4}A B == （2）(){1}{2,3,4,5,6}A B == 31、设A,B,C 为任意集合，证明 () ()()()A B B A A B A B --=- 证明： ()() {|}{|()()}{|()()()()} {|()()}{|()()}{|()()} {|()()}{|()(A B B A x x A B x B A x x A x B x B x A x x A x B x B x B x A x A x B x A x x A x B x B x A x x A B x A x B x x A B x A x B x x A B x B x x A B x A --=∈-∨∈-=∈∧?∨∈∧?=∈∨∈∧?∨∈∧∈∨?∧?∨?=∈∨∈∧?∨?=∈∧?∨?=∈∧∈∨∈=∈∧∈=∈∧∈)} B A B A B =-
离散数学16章练习题及答案
离散数学练习题 第一章 一.填空 １.公式)()(q p q p ∧?∨?∧的成真赋值为 01；１0 2．设p ， r 为真命题，q, s 为假命题，则复合命题)()(s r q p →??→的真值为 0 3．公式)()()(q p q p q p ∧∨?∧??与共同的成真赋值为 ０1;10 ４.设A 为任意的公式,B 为重言式,则B A ∨的类型为 重言式 5．设p, ｑ均为命题，在 不能同时为真 条件下,p 与q 的排斥也可以写成p 与ｑ的相容或。 二.将下列命题符合化 １． 7不是无理数是不对的。 解:)(p ??,其中p: 7是无理数; 或ｐ,其中p ： 7是无理数。 2.小刘既不怕吃苦,又很爱钻研。 解:其中,q p ∧?p ： 小刘怕吃苦,q:小刘很爱钻研 ３.只有不怕困难,才能战胜困难。 解:p q ?→,其中ｐ: 怕困难，q: 战胜困难 或q p ?→，其中p: 怕困难， q: 战胜困难 ４.只要别人有困难，老王就帮助别人，除非困难解决了。 解：)(q p r →→?，其中p: 别人有困难，q:老王帮助别人 ,r: 困难解决了 或：q p r →∧?)(,其中p:别人有困难，q: 老王帮助别人,ｒ: 困难解决了 5.整数n 是整数当且仅当n 能被２整除。 解：q p ?,其中ｐ： 整数n 是偶数,q: 整数n 能被2整除 三、求复合命题的真值 P:2能整除５， q:旧金山是美国的首都， r ：在中国一年分四季 1. ))(())((q p r r q p ∧→∧→∨ ２.r q p p r p q ∧?∧?∨∨→→?)(())()(( 解：p, ｑ 为假命题，ｒ为真命题
计算机学科发展中离散数学的作用与运用_1
计算机学科发展中离散数学的作用与运用离散数学是一种数学工具，在计算机发展与学科的研究中起着至关重要的作用，下面是小编搜集整理的一篇相关论文范文，欢迎阅读借鉴。 在数学中适合用于离散对象的部分知识属于离散数学内容，离散主要指的是不同的不连接在一起的元素。离散数学具有独特的特点，比较重视可行性问题的研究，需要通过证明一个问题解的存在性，并找出该问题解的步骤，但是步骤是有限的且有规则的。在计算机学科中，离散数学逐渐成为其基本数学工具，由于计算机属于一个离散结构，其研究对象均为离散形式，因此，需要离散数学知识的支持，以便促进计算机学科的发展。 一、离散数学在计算机学科中的作用 离散数学是一种数学工具，在计算机发展与学科的研究中起着至关重要的作用。可以利用离散数学中的自动机理论来研究形式语言，通过谓词演算内容来对程序正确性问题进行细致的研究，也可以利用袋鼠结构来对编码理论进行研究等。离散数学在计算机学科中发挥出越来越大的作用，通过以离散数学作为计算机学科研究的依据与方法，可以促进计算机学科逐渐趋于完善。在现代化的计算机学科中，如果对离散数学的相关知识不够了解，就会影响到对计算机学科的学习与研究。因此，需要重视离散数学在计算机学科中的作用。 二、计算机学科中离散数学的应用 1.在数据结构中的应用
在计算机科学中，需要利用数据结构知识来解决具体的问题，在问题中所处理的数据，需要从具体问题中抽象出一个适当的数学模型，并对其模型算法进行设计，之后编出程序，进行有效的测试与调整，以便对问题进行解答。其中数学模型属于数据结构研究内容之一，对数学模型实质进行分析，并提取出操作的对象，了解之间的关系，使用数学的语言对其进行描述。在数据结构中，操作对象之间的关系可以分为集合、树形结构、线性结构、图状结构、网状结构等。其研究的主要内容包括数据的逻辑结构、基本运算操作以及物理存储结构等。其中逻辑结构与基本运算操作主要是来源于离散数学中的离散结构与算法思考。在离散数学中的集合论、关系、树以及图论几个章节的知识充分反映出数据结构的结构知识。 2.在数据库中的应用 数据库技术在其他领域中均得到较好应用，关系数据库逐渐成为主流，离散数学中的笛卡尔积是一种纯数学理论，主要是亚久关系数据库的主要途径，具有无可替代的作用，不仅是对理论与方法进行有效的支持，也可以有效的促进数据库技术的发展。集合代数可以为关系数据模型的建立提供基础条件，其数据的逻辑结构需要以行与列组成的二维方式来描述。使用二元关系理论来解决关系操作数据的查询与维护功能、关系分解的无损连接性分析问题等。 3.在编译原理中的应用 在计算机中编译程序是比较复杂的，典型的编译程序包括词法、语法、语义、代码优化、中间代码生成、目标代码生成、错误检查与
离散数学及其应用
离散数学及其应用 第一章命题逻辑 习题： 1.判断下列语句是否是命题，为什么？若是命题，判断是简单命题还是复合命题。 （1）离散数学是计算机专业的一门必修课。 （2）李梅能歌善舞。 （3）这朵花真美丽！ （4）3+2>6. （5）只要我有时间，我就来看你。 （6）x=5. （7）尽管他有病，但他仍坚持工作。 （8）太阳系外有宇宙人。 （9）小王和小张是同桌。 （10）不存在最大的素数。 2.判断下列各式是否是命题公式，为什么？ （1）P→（P∧Q）。 （2）（?P→Q）→（Q→P）））。 （3）（（?P→Q）→（Q→P））。 （4）（Q→R∧S）。
（5）（P∧QR）→S。 （6）（（R→(Q→R)→(P→Q))。 3.将下列命题符号化： （1）我们不能既划船又跑步。 （2）我去新华书店，仅当我有时间。 （3）如果天下雨，我就不去新华书店。 （4）除非天不下雨，我将去新华书店。 （5）张明或王平都可以做这件事。 （6）“2或4是素数，这是不对的”是不对的。 （7）只有休息好，才能工作好。 （8）只要努力学习，成绩就会好的。 （9）大雁北回，春天来了。 （10）小张是山东人或河北人。 4.构造下列命题公式的真值表，并据此说明哪些是其成真赋值，哪些是其成假赋值。 （1）?（P∨?Q）。 （2）P∧（Q∨R）。 （3）?（P∨Q）?（?P∧?Q）。 （4）?P→（Q→P）。 5.分别用真值表法和公式法判断下列命题公式的类型： （1）（P∨Q）→（P∧Q）。 （2）（P∧Q）→（P∨Q）。
（3）（?P∨Q）∧?（Q∨?R）∧?（R∨?P∨?Q）。 （4）（P∧Q→R）→（P∧?R∧Q）。 （5）（Q→P）∧（?P∧Q）。 （6）（?P?Q）?（P?Q）。 （7）（P∧Q）∧?（P∧Q）。 6.分别用真值表法和公式法证明下列各等价式： （1）（P∨Q）→（P∧Q）。 （2）?（P∨Q）∨（?P∧Q）??P。 （3）（P∧Q）∨?P??P∨Q。 （4）P→（Q∧R）?（P→Q）∧（P→R）。 （5）（P→Q）∧（R→Q）?（P∨R）→Q。 （6）（P∧Q∧A→C）∧（A→P∨Q∨C）?（A∧（P?Q））→C。（7）?（P Q）??P ?Q。 （8）?（P Q）??P ?Q。 7.设A，B，C为任意的三个命题公式，式问下面的结论是否正确？（1）若A∨C?B∨C，则A?B。 （2）若A∧C?B∧C，则A?B。 （3）若?A??B，则A?B。 （4）若A→C?B→C，则A?B。 （5）若A?C?B?C，则A?B。 8.试给出下列命题公式的对偶式： （1）（P∧Q）∨R。
离散数学第九章树知识点总结
图论部分 第九章、树 9.1 无向树及生成树 无向树、森林 无向树的性质 定理设G=
生成树的存在性 定理任何无向连通图都有生成树. 证用破圈法. 若图中无圈, 则图本身就是自己的生成树. 否则删去圈上的任一条边, 这不破坏连通性, 重复进行直到无圈为止,剩下的图是一棵生成树. 推论1 设n阶无向连通图有m条边, 则m≥n-1.
推论2 设n阶无向连通图有m条边, 则它的生成树的余树 有m-n+1条边. 推论3 设为G的生成树T 的余树，C 为G 中任意一个 圈，则C与一定有公共边. 基本回路与基本回路系统 定义设T是n阶m条边的无向连通图G的一棵生成 树，设e1', e2', … , e'm-n+1为T的弦. 设C r为T添加弦e r' 产生的G中惟一的圈(由e r'和树枝组成), 称C r为对应 弦e r'的基本回路或基本圈, r=1, 2, …, m-n+1. 称{C1, C2, …, C m-n+1}为对应T的基本回路系统. 求基本回路的算法: 设弦e=(u,v), 先求T中u到v的路径 Γuv, 再并上弦e, 即得对应e的基本回路. 基本割集与基本割集系统定义设T是n阶连通图G的一棵生成树, e1', e2', …, e'n-1为T的树枝，S i是G的只含树枝e i', 其他边都是弦 的割集, 称S i为对应生成树T由树枝e i'生成的基本割 集, i=1, 2, …, n-1. 称{S1, S2, …, S n-1}为对应T的基本 割集系统. 求基本割集的算法: 设e'为生成树T的树枝, T-e'由两 棵子树T1与T2组成, 令 S e'={e | e∈E(G)且e的两个端点分别属于T1与T2} 则S e'为e'对应的基本割集.
离散数学各章要点16
主要内容 1. 无向树的定义及其性质. 2. 生成树的定义及存在定理. 3. 基本回路及基本回路系统. 4. 基本割集及基本割集系统. 5. 最小生成树. 6. 根树及其分类. 7. 最优树、Huffman算法. 8. 最佳前缀码. 9. 波兰符号法与逆波兰符号法. 学习要求 1. 深刻理解树的定义和性质. 2. 熟练地求解无向树. 3. 准确地求解最小生成树（见例题）. 4. 深刻理解基本回路、基本割集、基本回路系统、基本割集系统等概念. 5. 深刻理解根树、分类、家族树等诸多概念. 6. 会画阶数n较小的非同构的根树. 7. 熟练掌握用Huffman算法求最优树的方法. 8. 熟练掌握求最佳前缀码的方法. 9. 会用二叉树表示算式. 10 会求算式的波兰符号法和逆波兰符号法表示的算式. 典型习题
1. 无向树T有n i个i度顶点, i=2,3,…,k, 其余顶点都是树叶, 求T的树叶数t. 2. 设T为非平凡的无向树, 最大度△(T)≥k（k≥1）, 证明T至少有k片树叶. 3. 设G'是无向连通图G的无圈子图, 证明G中存在生成树T, 使得E(G')E(T). 4. 设C为无向图G中一个圈, 边e1与e2在C中, 证明G中存在割集S, 使得e1,e2∈S. 5. 设G为n阶无向简单图, n≥5, 证明G或必含圈. 6. 关于顶点和度数选择题. 7. 画出5阶所有非同构的根树, 并分析它们都是几叉树. 8. 设T是正则二叉树, 有t片树叶. 证明T的阶数n=2t-1. 9. 设7个字母在通信中出现的频率如下： a：35% b：20% c：15% d：10% e：10% f：5% g：5% 用Huffman算法求传输它们的前缀码. 要求画出最优树, 指出每个字母对应的编码. 并指出传输10n个按上述频率出现的字母, 需要多少个二进制数字. 10 下图所示的2叉树表达一个算式. （1）用中序行遍法还原算式. （2）用前序行遍法写出该算式的波兰符号法表示式. （3）用后序行遍法写出该算式的逆波兰符号法表示式.
离散数学及其应用图论部分课后习题答案
作业答案：图论部分 P165:习题九 1、 给定下面4个图（前两个为无向图，后两个为有向图）的集合表示，画出它们的图形表 示。 （1）111,G V E =<>，112345{,,,,}V v v v v v =，11223343345{(,),(,),(,),(,),(,)}E v v v v v v v v v v = （2）222,G V E =<>，21V V =，11223344551{(,),(,),(,),(,),(,)}E v v v v v v v v v v = （3）13331,,,D V E V V =<>=31223324551{,,,,,,,,,}E v v v v v v v v v v =<><><><><> （4）24441,,,D V E V V =<>=31225523443{,,,,,,,,,}E v v v v v v v v v v =<><><><><> 解答： （1） （2） 10、是否存在具有下列顶点度数的5阶图？若有，则画出一个这样的图。 （1）5，5，3，2，2；（2）3，3，3，3，2；（3）1，2，3，4，5；（4）4，4，4，4，4 解答：（1）（3）不存在，因为有奇数个奇度顶点
。 14、设G 是(2)n n ≥阶无向简单图，G 是它的补图，已知12(),()G k G k δ?==，求()G ?， ()G δ。 解答：2()1G n k ?=--；1()1G n k δ=--。 15、图9.19中各对图是否同构？若同构，则给出它们顶点之间的双射函数。 解答： （c ）不是同构，从点度既可以看出，一个点度序列为4，3，3，3，3而另外一个为4，4，3，3，1 （d ）同构，同构函数为 12()3 45 x a x b f x x c x d x e =??=??==??=?=?? 16、画出所有3条边的5阶简单无向图和3条边的3阶简单无向图。 解答： （1）三条边一共提供6度；所以点度序列可能是 ①3，3，0，0，0，0；②3，2，1，0，0，0；③3，1，1，1，0，0；④2，2，2，0，0，0；⑤2，2，1，1，0，0；⑥2，1，1，1，1，0；⑦1，1，1，1，1，1； 由于是简单图，①②两种情形不可能 图形如下：