离散数学-图论-平面图
离散数学图论与系中有图题目
离散数学图论与系中有图题目
————————————————————————————————作者：————————————————————————————————日期：
图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8个结点的三次正则图 (2) (1) (3) (2)(1)
离散数学测验题--图论部分(优选.)
离散数学图论单元测验题 一、单项选择题(本大题共10小题，每小题2分，共20分) 1、在图G ＝
离散数学 ( 第1次 )
第1次作业 一、单项选择题（本大题共30分，共 15 小题，每小题 2 分） 1. 图G所示平面图deg(R3)为 A. 4 B. 5 C. 6 D. 3 2. 在完全m叉树中，若树叶数为t，分枝点数为i，则有（）。 A. (m-1)i
C. (m-1)i=t-1 D. (m-1)i≤t-1 3. 命题a）：如果天下雨，我不去。写出命题a）的逆换式。 A. 如果我不去，天下雨。 B. 如果我去，天下雨。 C. 如果天下雨，我去。 D. 如果天不下雨，我去。 4. 设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点（） A. 5 B. 4
C. 2 D. 6 5. 假设A={a,b,c,d},考虑子集S={{a,b},{b,c},{d}}，则下列选项正确的是（）。 A. S是A的覆盖 B. S是A的划分 C. S既不是划分也不是覆盖 D. 以上选项都不正确 6. 没有不犯错误的人。M(x)：x为人。F（x）：x犯错误。则命题可表示为（）。 A. (?x)(M(x)→F(x) B. (?x)(M(x)?F(x) C.
（?x）(M(x)?F(x)) D. (?x)(M(x)→F(x) 7. 命题逻辑演绎的CP规则为（） A. 在推演过程中可随便使用前提 B. 在推演过程中可随便使用前面演绎出的某些公式的逻辑结果 C. 如果要演绎出的公式为B→C形式，那么将B作为前提，演绎出C D. 设?(A)是含公式A的命题公式，B<=>A，则可以用B替换?(A)中的A 8. 设G是有6个结点的完全图，从G中删去（）条边，则得到树。 A. 6 B. 9 C. 10 D.
离散数学 第二讲
1.1.3 命题符号化 1.1.2介绍的5种常用的联结词也可称为真值联结词或逻辑联结词。在命题逻辑中，利用这些联结词可将各种各样的复合命题符号化，基本的步骤如下： 9找出各简单命题，将它们符号化； 9使用合适的联结词，将简单命题逐个联结起来，组成复合命题的符号化形式。
例1.12将下列命题符号化： （1）小王是游泳冠军或百米赛跑冠军。 （2）小王现在在宿舍或在图书馆里。 （3）选小王或小李中的一人做班长。 解：根据以上步骤，上述命题可符号化为： （1）p ∨q，其中，p：小王是游泳冠军，q：小王是百米赛跑冠军。 （2）p ∨q，其中，p：小王在宿舍，q：小王在图书馆。这里的“或”是排斥或，但因p与q不能同时发生，所以仍然符号化为p ∨q。 （3）(p ∧?q) ∨(q ∧?p)，其中，p：选小王做班长，q：选小李做班长。这里的“或”是排斥或，因p与q可能同时发生，所以须符号化为(p ∧?q) ∨(q ∧?p)。
例1.13将下列命题符号化： （1）如果我上街，我就去书店看看，除非我很累。 （2）小王是电子工程学院的学生，他生于1983年或1984年，他是三好学生。 解：上述命题可符号化为： （1）?r→(p→q)，其中，p：我上街，q：我去书店看看，r：我很累。（该命题也可符号化为(p∧?r)→q或p→(?r→q)） （2）p∧(q∨r)∧s，其中，p：小王是电子工程学院的学生，q：他生于1983年，r：他生于1984年，s：他是三好生。
1.1 命题符号化及联结词 5个联结词的优先级顺序为： ?、∧、∨、→、? 例我们写符号串： p ∨q ∧r→q∧?s ∨r 即为如下公式：(p ∨(q ∧r))→((q∧(?s)) ∨r)
离散数学图论练习题
图论练习题 一.选择题 1、设G是一个哈密尔顿图，则G一定是( )。 (1) 欧拉图(2) 树(3) 平面图(4)连通图 2、下面给出的集合中，哪一个是前缀码？() (1) {0，10，110，101111}(2) {01，001，000，1} (3) {b，c，aa，ab，aba}(4) {1，11，101，001，0011} 3、一个图的哈密尔顿路是一条通过图中()的路。 4、设G是一棵树，则G 的生成树有( )棵。 (1) 0(2) 1(3) 2(4) 不能确定 5、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。 6、一棵无向树的顶点数n与边数m关系是()。 7、一个图的欧拉回路是一条通过图中( )的回路。 8、有n个结点的树，其结点度数之和是()。 9、下面给出的集合中，哪一个不是前缀码( )。 (1) {a，ab，110，a1b11} (2) {01，001，000，1} (3) {1，2，00，01，0210} (4) {12，11，101，002，0011} 10、n个结点的有向完全图边数是( )，每个结点的度数是( )。 11、一个无向图有生成树的充分必要条件是( )。 12、设G是一棵树，n,m分别表示顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 13、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。 14、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。 15、设G是有n个结点m条边的连通平面图，且有k个面，则k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 16、设T是一棵树，则T是一个连通且( )图。 17、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 18、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12
离散数学图论复习
离散数学11春图论部分综合练习辅导 大家好！本学期的第二次教学辅导活动现在开始，本次活动主要是针对第二单元图论的重点学习内容进行辅导，方式同样是通过讲解一些典型的综合练习作业题目，帮助大家进一步理解和掌握图论的基本概念和方法． 图论作为离散数学的一部分，主要介绍图论的基本概念、理论与方法．教学内容主要有图的基本概念与结论、图的连通性与连通度、图的矩阵表示、最短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用等． 本次综合练习主要是复习这一单元的主要概念与计算方法，与集合论一样，也安排了五种类型，有单项选择题、填空题，判断说明题、计算题、证明题．这样的安排也是为了让同学们熟悉期末考试的题型，能够较好地完成这一部分主要内容的学习． 下面是本学期第4，5次形考作业中的部分题目． 一、单项选择题 单项选择题主要是第4次形考作业的部分题目． 第4次作业同样也是由10个单项选择题组成，每小题10分，满分100分．在每次作业在关闭之前，允许大家反复多次练习，系统将保留您的最好成绩，希望大家要多练几次，争取好成绩．需要提醒大家的是每次练习的作业题目可能不一样，请大家一定要认真阅读题目． 1．设图G ＝
离散数学之图论
第四篇图论 自从1736年欧拉（L.Euler）利用图论的思想解决了哥尼斯堡（Konigsberg）七桥问题以来，图论经历了漫长的发展道路。在很长一段时期内，图论被当成是数学家的智力游戏，解决一些著名的难题。如迷宫问题、匿门博奕问题、棋盘上马的路线问题、四色问题和哈密顿环球旅行问题等，曾经吸引了众多的学者。图论中许多的概论和定理的建立都与解决这些问题有关。 1847年克希霍夫（Kirchhoff）第一次把图论用于电路网络的拓扑分析，开创了图论面向实际应用的成功先例。此后，随着实际的需要和科学技术的发展，在近半个世纪内，图论得到了迅猛的发展，已经成了数学领域中最繁茂的分支学科之一。尤其在电子计算机问世后，图论的应用范围更加广泛，在解决运筹学、信息论、控制论、网络理论、博奕论、化学、社会科学、经济学、建筑学、心理学、语言学和计算机科学中的问题时，扮演着越来越重要的角色，受到工程界和数学界的特别重视，成为解决许多实际问题的基本工具之一。 图论研究的课题和包含的内容十分广泛，专门著作很多，很难在一本教科书中概括它的全貌。作为离散数学的一个重要内容，本书主要围绕与计算机科学有关的图论知识介绍一些基本的图论概论、定理和研究内容，同时也介绍一些与实际应用有关的基本图类和算法，为应用、研究和进一步学习提供基础。
第4-1章无向图和有向图 学习要求：仔细领会和掌握图论的基本概论、术语和符号，对于图论研究的一些最基本的课题，如道路问题、连通性问题和着色的问题等，应掌握主要的定理内容和证明方法以及基本的构造方法，以便为下一章研究提供理论工具。学习本章要用到集合和线性代数矩阵运算的知识，特别是集合数和矩阵秩的概念。 §4-1-1 图的基本概念 图是用于描述现实世界中离散客体之间关系的有用工具。在集合论中采用过以图形来表示二元关系的办法，在那里，用点来代表客体，用一条由点a指向点b的有向线段来代表客体a和b之间的二元关系aRb，这样，集合上的二元关系就可以用点的集合V和有向线的集合E构成的二元组（V，E）来描述。同样的方法也可以用来描述其它的问题。当我们考察全球航运时，可以用点来代表城市，用线来表示两城市间有航线通达；当研究计算机网络时，可以用点来表示计算机及终端，用线表示它们之间的信息传输通道；当研究物质的化学结构时，可以用点来表示其中的化学元素，而用线来表示元素之间的化学键。在这种表示法中，点的位置及线的长短和形状都是无关紧要的，重要的是两点之间是否有线相连。从图形的这种表示方式中可以抽象出图的数学概念来。 一、图 定义4-1-1.1一个（无向）图G是一个二元组（V（G），E（G）），其中V （G）是一个有限的非空集合，其元素称为结点；E（G）是一个以不同结点的无序对为元素，并且不含重复元素的集合，其元素称为边。 我们称V（G）和E（G）分别是G的结点集和边集。在不致引起混淆的地方，常常把V（G）和E（G）分别简
离散数学图论部分经典试题及答案
离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝
图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( )． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ? ? ? ? ? c a b e d ? f 图四
离散数学图论与关系中有图题目
图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8 个结点的三次正则图 (2) (1) (3) (2) (1)
离散数学(图论)课后总结
第八章图论 例1、下面哪些数的序列,可能是一个图的度数序列?如果可能,请试画出它的图. 哪些可能不是简单图?a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4) d) (1,1,1,1,4) e) (1,2, 2,4,5) 解:a)不是, 因为有三个数字是奇数. b) c) d)是. e) 不是简单图,因为它有5个结点, 有一个结点度为5, 必然有环或平行边. 例2、已知无向简单图G中,有10条边,4个3度结点,其余结点的度均小于或等于2,问G中至少有多少个结点?为什么? 解:已知边数|E|=10, ∑deg(v)=2|E|=20其中有4个3度结点, 余下结点度之和为: 20-3×4=8 因为G是简单图, 其余每个结点度数≤2, 所以至少还有4个结点.所以G中至少有8个结点. 强连通、单侧连通和弱连通 在简单有向图G中,如果任何两个结点间相互可达, 则称G是强连通. 如果任何一对结点间, 至少有一个结点到另一个结点可达, 则称G是单侧连通. 如果将G看成无向图后(即把有向边看成无向边)是连通的,则称G是弱连通. 在简单有向图中,具有强连通的最大子图,称为强分图.具有单侧连通的最大子图,称为单侧分图. 具有弱连通的最大子图,称为弱分图. 注：我每次都会被各种分图弄糊涂！！考试时要注意啊，千万不要错了 利用可达性矩阵求强分图，注意初等矩阵变换的知识不要忘了！！ 令图G=
离散数学(第一讲)
一、离散数学介绍 离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。 离散数学常常被分成三门课程进行教学，即集合论与图论、代数结构与组合数学、数理逻辑。 其中各部分内容在本书中又有如下涉及： 1．集合论部分：集合及其运算(3.1)、二元关系(3.2)与函数(3.5)、自然数及自然数集、集合的基数注：集合这个概念比较了解，在数学上，基数(cardinal number)也叫势(cardinality)，指集合论中刻画任意集合所含元素数量多少的一个概念。这是康托尔在1874年～1884年引入最原始的集合论（现称朴素集合论）时, 给出的基数概念。他最先考虑的是集合{1,2,3} 和 {2,3,4}，它们并非相同，但有相同的基数。 那何谓两个集合有相同数目的元素？ 康托尔的答案，是所谓一一对应，即把两个集合的元素一对一的排起来，若能做到，两个集合的基数自然相同。 这个答案虽然简单，却起到了革命性的作用，因为用相同的方法即可比较任意集合，包括无穷集合的大小。 2．图论部分(第5章)：图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配
集、覆盖集、独立集与匹配、带权图及其应用3．代数结构部分（第6、7章）：代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数4．组合数学部分：组合存在性定理、基本的计数公式、组合计数方法、组合计数定理 组合数学在本书中没有介绍，而关于组合数学的问题却是十分有趣的，可以供大家思考一下。 组合数学中的著名问题 ?计算一些物品在特定条件下分组的方法数目。这些是关于排列、组合和整数分拆的。 ?地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是 否总共只需四种颜色？这是图论的问题。 ?船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、 狼就会吃羊。船夫的船每次只能运送一种东西。 怎样把所有东西都运过河？这是线性规划的问 题。 ?中国邮差问题：由中国组合数学家 ?管梅谷教授① ?提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全 问题，存在多项式复杂度算法：先求出度为奇数 的点，用匹配算法算出这些点间的连接方式，然 后再用欧拉路径算法求解。这也是图论的问题。 ?任务分配问题（也称婚配问题）：有一些员工要完成一些任务。各个员工完成不同任务所花费的时 间都不同。每个员工只分配一项任务。每项任务 只被分配给一个员工。怎样分配员工与任务以使 所花费的时间最少？这是线性规划的问题。 ?如何构作幻方。
离散数学图论部分综合练习讲解
离散数学图论部分综合练习 1．设图G ＝
离散数学 第五讲
2.2 一阶逻辑谓词公式及解释 简单命题函数+ 逻辑联结词?谓词表达式 问题：怎样的谓词表达式才能成为谓词公式，并能进行逻辑演算？
定义2.4在形式化中，我们将使用如下7种符号： 1.个体常项：用小写英文字母a ，b ，c ，…表示，当个体域D 给出时，它可以是D 中某个元素。 2.个体变项：用小写英文字母x ，y ，z ，…表示，当个体域D 给出时，D 中任意元素可代入个体变项。 3.函数符号：用小写英文字母f ，g ，…表示，当个体域D 给出时，n 元函数符号f (x 1，…，x n )可以是D n 到D 的任意一个映射。 4.谓词符号：用大写英文字母F ，G ，H ，…表示，当个体域D 给出时，n 元谓词符号F (x 1，…，x n )可以是D n 上的任意一个谓词。 2.2.1 合式公式与翻译
5.量词符号：?，? 6.联结词符号：?，∧，∨，→，? 7.括号和逗号：（、）、， 定义2.5谓词逻辑中的项，被递归定义为： 1.个体常项是项； 2.个体变项是项； 3.若?(x 1, …, x n )是n元函数，t 1 , …, t n 是项，则?(t 1 , …, t n )也是项； 4.所有项都是有限次使用1、2、3、生成的符号串才是项。 2.2.1 合式公式与翻译
2.2.1 合式公式与翻译——说明 1.有了项的定义，函数的概念就可用来表示个体常项和个体变项。如：P(x)：x是教授，f(x)：x的父亲，a：张三，那么P(f(a))则表示：“张三的父亲是教授” 2.函数的使用给谓词表示带来很大的方便。如：用谓词表示命题：对任意的整数x，x2 –1=(x+1)(x-1)是恒等式。 令：I(x)：x是整数，f(x)=x2 –1，g(x)= (x+1)(x-1)，E(x,y)：x=y，则该命题可表示为：?x(I(x)→E(f(x), g(x)))
离散数学试题及解答
n 离散数学 2^m*n 一、选择题（2*10） 1．令P：今天下雨了，Q：我没带伞，则命题“虽然今天下雨了，但是我没带伞”可符号化为（）。 （A）P→Q（B）P∨Q ?? （C）P∧Q（D）P∧Q ? 2．下列命题公式为永真蕴含式的是（）。 （A）Q→（P∧Q）（B）P→（P∧Q） （C）（P∧Q）→P（D）（P∨Q）→Q 3、命题“存在一些人是大学生”的否定是(A)，而命题“所有的人都是要死 的”的否定是（）。 （A）所有人都不是大学生，有些人不会死 （B）所有人不都是大学生，所有人都不会死 （C）存在一些人不是大学生，有些人不会死 （D）所有人都不是大学生，所有人都不会死 4、永真式的否定是（）。 （A）永真式 （B）永假式 （C）可满足式（D）以上均有可能 5、以下选项中正确的是（）。 （A）0= ? （B）0 ? （C）0∈?（D）0?? ? 6、以下哪个不是集合A上的等价关系的性质？（）
（A）自反性（B）有限性（C）对称性（D）传递性 7、集合A={1,2,…,10}上的关系R={
离散数学第三讲
二、容斥原理与鸽巢原理 1、 容斥原理(§1。3。) （计数原理、包含排斥原理） 容斥原理（包含排斥原理）： 设A ，B 是有限集，则 B A B A B A -+= 容斥原理的相关推论： (i) C B A C A C B B A C B A C B A +---++= (ii) 利用归纳法 n n n k j i k j i n j i j i n i i n A A A A A A A A A A A A A 211111321)1(-<<≤≤<≤=-+++ - =∑∑∑ (iii) U A A =+, A U A -= (iv)
n n A A A U A A A 2121-= （注意基的具体含义） 设S 是有限集，r P P P ,,, 21 是r 条性质， i A 是S 中具有性质 i P 的子集，即 }{ i i P x S x x A 具有性质,∈= （i=1,2,…，r ） 则 （1）S 中至少具有性质 r P P P ,,,21 一条的元素数是： r r r k j i k j i r j i j i r i i r A A A A A A A A A A A A A 211111321)1(-≤<<≤≤<≤=-+++ - =∑∑∑ （2）S 中不具有性质r P P P ,,,21 的 元素数是： r r A A A U A A A 2121-=
e.g 1 设2≥n ，)(n ?表示不超过n 且与n 互质的 正整数的个数，求)(n ? 该函数在计算机中称为EURTER 函数。 解： }{n S ,,3,2,1 = 不妨令： r r p p p n ααα??= 1121 r p p p ,,,21 为互异的质 数； 设 } {r i p x S x x A i i ,,2,1, =∈=且 则 j i j i i i p p n A A p n A = =, r A A A n 21)(=?…… 2、 鸽巢原理（抽屉原理、鞋盒原理）（教材P63） n+1个鸽子飞进n 个鸽巢，则可以找到一鸽巢里至少有2只鸽子。 或者：
离散数学及其应用图论部分课后习题答案
作业答案：图论部分 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； 由于是简单图，①②两种情形不可能 图形如下：
离散数学 第十二讲
第6章几个典型的代数系统 内容提要 6.1 半群与群 6.2 环与域 6.3 格与布尔代数 重点：群 2006-5-12北京邮电大学电子工程学院1
6.1 半群与群 6.1.1 半群 半群是一种特殊的代数系统，它在形式语言、自动机等领域中有具体的应用。 定义6.1设
定义6.2设
2006-5-12北京邮电大学电子工程学院4 例6.1 判断下列代数系统是否为半群： （1）
2006-5-12北京邮电大学电子工程学院5 例6.2 判断下列代数系统是否为半群： 是代数系统，其中S k ={x | x ∈Z ∧x ≥k }，k ≥0，+为普通加法。 解：+在S k 上封闭；且普通加法运算满足可结合，则是半群。 注意：k ≥0这个条件是非常重要的，若k ＜0，则+在S k 上不封闭。 另：代数系统和