交大离散数学复习课.ppt

《交大离散数学复习课.ppt》由会员分享，可在线阅读，更多相关《交大离散数学复习课.ppt（106页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、交大离散数学复习课 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望考试 形式闭卷，90分钟题型：选择题（30分，152分）计算（50分）证明（20分）考题示例选择题：1、设R 是X=1,2,3,4上的关系，x,y X，如果x y，则(x,y)R。R=(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)，则关系R 是（）A)自反的、B)传递的、C)等价的 D)对称的 2、设B是不含变元x的公式，谓词公

2、式(x)(A(x)B)等价于（）A)(x)(A(x)B B)(x)(A(x)B C)A(x)B D)(x)A(x)(x)B3.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是（）A)10 B)12 C)16 D)14计算题1假设p为真，q为假，并且r为真，求下列表达式的真值：（1）pq r（2）pq r(a)用ABCDE五个字母可以组成多少个不重复的长度为4的字符串？(a)中有多少个字符串以字母B开头？考题示例知识点提示1 逻辑与证明1.2 命题命题是一个陈述句，或真或假，不可以既真又假。命题是逻辑的基本构成单元下列句子(a)(e)哪个为真，哪个为假（不能既真又假）(a)能整除7 的

3、正整数只有1 和7 本身。(b)多伦多是加拿大的首都。(c)对于每个正整数n，存在一个大于n 的素数。(d)地球是宇宙中惟一存在生命的星球。(e)买两张星期五去“大剧院”音乐会的票。(a)真真(b)假假(c)真真(d)不知真假，但一定是非真即假。因此是命题不知真假，但一定是非真即假。因此是命题(e)不是命题不是命题真值表复合命题的真值可以由真值表来表达。用T 代表真，F 代表假。v复合命题复合命题pqpq，p q的真值由下列真值表的真值由下列真值表 p q pq T T T T F F F T F F F F p q p q T T T T F T F T T F F F p:天正在下雨 q:

4、天很冷 pq:天正在下雨 并且天很冷 pq:天正在下雨或者天很冷例如：例如：v命题命题“天正在下雨天正在下雨”与与“天很冷天很冷”可以连可以连接成接成单一命题形式单一命题形式“天正在下雨天正在下雨与与天很冷天很冷”。v“与与”和和“或或”的形式化定义。的形式化定义。9v条件命题的真值表 p q p q T T T T F F F T T F F T例v考察：“如果今天天晴，那么我们将去海滩”v只有当 今天天晴，而我们不去海滩今天天晴，而我们不去海滩 时，这个命题为假，否则上述命题成立。v考察：“如果今天是星期五，那么2+3=5”v该命题总是成立，因为2+3=5总是为真v考察“如果今天是星期五，

5、那么2+3=6”v该命题 当今天不是星期五 时，成立1.1.4逻辑运算符的优先级逻辑运算符的优先级 优先级优先级:()假设：假设：p 真真 q假假 r真，给出下面每个命题的真真，给出下面每个命题的真值值(a)(p q)r(b)(p q)r(c)p (q r)(d)p(q r)1.1.5 复合命题的真值表构造真值表(p q)(p q)pq qp qp q(p q)(p q)TTFTTTTFTTFFFTFFFTFFTTFF1.1.6 翻译语句形式化表示“只有你主修计算机科学或不是新生，才可以从校园网访问因特网”设：a:你可以从校园网访问因特网c:你主修计算机科学 f:你是个新生问题：该语句的等价说

6、法（）：A“如果你主修计算机科学，或者你不是新生，那么你可以从校园网访问因特网”B“如果你可以从校园网访问因特网，那么你主修了计算机科学，或者你不是新生”所以，形式化表示为：a(c f)证明命题:p(q r)与(pq)(pr)等价pqrq rp(q r)pqpr(pq)(pr)TTTTTTTTTTFFTTTTTFTFTTTTTFFFTTTTFTTTTTTTFTFFFTFFFFTFFFTTFFFFFFFF1.2.3 德摩根定律的运用用德摩根律表达“麦克有一部手机和一台电脑”的否定解：p麦克有一部手机，q麦克有一台电脑那么原命题表示为：p q则其否定（pq）等价于 p q即：“麦克没有一部手机或没

7、有一台电脑”用德摩根律表达“John或者Jessi将去看电影”的否定解：p:John去看电影，q：Jessi去看电影那么原命题表示为：p q则其否定（p q）等价于 p q即：“John和Jessi都不去看电影”1.3.3 量词量化：谓词在一定范围内的取值谓词演算：处理谓词和量词的逻辑领域全称量词：P(x)的全称量化表示语句“P(x)对x在其论域中的所有值都为真”存在量词：P(x)的存在量化表示语句“论域中至少有一个值满足P(x)为真”量词命题何时为真何时为假全称量词x P(x)对每一个x，P(x)都为真有一个x，使得P(x)为假存在量词x P(x)有一个x，使得P(x)为真对每一个x，P(x

8、)为假例：P(x)表示语句“x20”，论域为不超过4的正整数，x P(x)的真值是什么？解：论域为1，2，3，4，P(1),P(2),P(3)为真。17v例例vP(x)表示语句“x20”，论域为不超过4的正整数，则：x P(x)的真值是什么？v解：x P(x)就是合取式P(1)P(2)P(3)P(4)由于P(4)为假，所以 x P(x)为假1.3.5 约束论域量词x0)x(x0)y0(y3 0)y(y0 y3 0)全称量词的约束等价于一个条件语句的全称量化z0 (z2=2)z(z0 z2=2)存在量词的约束等价于一个合取的存在量化1.3.8 涉及量词的逻辑等价定义3：涉及量词的语句是逻辑等价的

9、，当且仅当无论什么谓词代入这个语句，也不论用哪个个体论域于这些命题函数里的变量上，它们都有相同的真值。vx(P(x)Q(x)xP(x)xQ(x)v x(P(x)Q(x)xP(x)xQ(x)vx(P(x)Q(x)与xP(x)xQ(x)不逻辑等价vx(P(x)Q(x)与 xP(x)xQ(x)不逻辑等价191.3.9 否定量化词表达式 考虑语句的否定：“班里每个学生都学过微积分”即 xP(x)其中P(x)：x学过离散数学其否定：“并非班里每个学生都学过微积分”也就是：“班里有学生没有学过微积分”，即 xP(x)等价关系：xP(x)xP(x)1.4.3 将数学语句翻译成嵌套量词语句翻译语句“两个正整数

10、的和是正数”xy(x0)(y 0)(x+y 0)嵌套语句翻译成数学语句：考虑命题 x y(x y0)论域为实数域。这个命题为真，因为对每个实数x，至少存在一个y（可选取y=-x），使x+y=0为真。这个命题用文字表达为：对每个实数x，存在一个实数y，可使x 与y 的和为零。例确定论证p q,p/q是否有效 p q p q p q T T T T T T F F T F F T T F T F F T F F注意：只要前提注意：只要前提pq和和p为真，结论为真，结论q就为真。就为真。所以论证过程是有效的。所以论证过程是有效的。1.5.3命题逻辑的推理规则假言推理假言推理/分离定律分离定律合取合取

11、拒取拒取附加附加化简化简假设段论假设段论析取段论析取段论q p q_ppp q_qPq _pqpq _pp _pqp qq r_prpqp _qpqp r _q r消解消解23例给出定理“若3n+2是奇数，则n是奇数”的证明若用直接法证明，设3n+2是奇数，则存在k使得3n+2=2k+1能否从中得出n是奇数的结论？反正法：第一步：假设条件语句结论是假，即“3n+2是奇数，n不是奇数”，那么n是偶数。即：n=2k+1,第二步：根据上面的假设，则3n+2=3(2k)+2=6k+2=2(3k+1),也就是得出3n+2是偶数，这与原命题的假设“3n+2”是奇数”矛盾所以原来的条件语句为真，定理得证。反

12、例证明法反驳x P(x)只需在论域内找到一个x，使P(x)为假。例 1.5.19命题“n(2n+1)是素数”为假。反例为n3时，239，不是素数2.集合、函数、数列与求和2.1.2 幂集如X是Y的子集但X不等于Y,则X是Y的一个真子集空集是任何集合的子集定义7：集合X的所有子集的集合，称为X的幂集，用P(X)表示28例如A=a,b,cP(A)的成员：,a,b,c,a,b,a,c,b,c,a,b,cA=3，P(A)=23=82.1.3 笛卡儿积一个由两个元素组成的有序对(或序偶)，写为(a,b)(a,b)=(c,d)当且仅当a=c,b=d.定义8：有序n元组（a1,a2,an）是以a1为第一个元

13、素，a2为第二个元素，an为第n个元素的有序组定义9：X,Y集合，XY称为X和Y的笛卡儿积，是所有有序对(x,y)的集合，其中xX,yY。即XY=(x,y)|xX,yY例X=1,2,3 Y=a,bXY=1,a,1,b,2,a,2,b,3,a,3,bYX=a,1,a,2,a,3,b,1,b,2,b,3XX=1,1,1,2,1,3,2,1,2,2,2,3,3,1,3,2,3,3YY=a,a,a,b,b,a,b,b Venn图：关于集合的形象化表示1243AB1243AB1243AB划分一个由集合X的非空子集的整体组成的S，如X的每个元素都只属于S的某一个元素，S就称为X的一个划分。v例：v集合X=

14、1,2,3,4,5,6,7,8vS=1,4,5,2,6,3,7,8vS是X的一个划分2.3.2 一对一函数和映上函数单射满射函数映上函数一对一的例证明从正整数集合到正整数集合的函数f(n)=2n+1是一对一的。张明：必须证明对所有正整数n1 和n2，如果f(n1)=f(n2)，则n1=n2。先假定f(n1)=f(n2)，依据f 的定义，将这个等式变形为 2n1+1=2n2+1将两边同时减1，然后同除以2，可得 n1=n2 所以，f 是一对一的。例定义序列s 为 sn=2n+43n，n 0(a)求s0。(b)求s1。(c)求si 的公式。(d)求sn-1 的公式。(e)求sn-2 的公式。(f)

15、证明序列sn满足 sn=5sn-1-6sn-2，对所有n 23、计数乘法原理乘积法则：乘积法则：假定一个过程可以被分解成两个任务，完成第一个任务有n1种方式，在第一个任务完成之后有n2种方式完成第二个任务，那么完成这个过程有n1n2种方式。如果一种活动由连续t步组成，第一步有n1种方法，第二步有n2种方法，.第t步有nt种方法，那么不同的活动数目有 n1*n2*.*nt 当一活当一活动由由连续几步几步组成成时，把每一步的方法数乘起来，把每一步的方法数乘起来.例题讲解例1 用一个字母和一个不超过100的正整数给礼堂的座位编号。那么不同编号的座位最多有多少？解解：给一个座位编号的过程分两个任务：从

16、26个字母中选取一个字母；从100个正整数中选取一个整数。根据乘法原理，座位的编号方式可以有：26*100=2600种例2 有多少个不同的7位二进制串？解：7位二进制串的每一位都可以有两种选择，因此有27 例如果不允许重复，用ABCDE可以组成多少长度为4的字符串？其中有多少是以B开头的？1*4*3*2=24例如果不允许重复，用ABCDE可以组成多少长度为4的字符串？其中有多少不是以B开头的？4*4*3*2=96120-24加法原理 假设X1,.,Xt是集合且第i个集合有 ni个元素，如果X1,.,Xt两两不相交，则可以从X1或X2或.Xt选择元素的可能性有n1 +.+nt v当被计数的元素可

17、以被分解到不相交的子集时，可将每个子集的元素数相加得到总的元素数.例由A、B、C、D、E、F 6人委员会要选一个主席，一个秘书，一个书记1.有多少种选法？2.如果A或B必须是主席，有多少种？3.如果E必须任3职之一，有多少种？4.如果D和F必须任职，有多少种？3.2.1 鸽巢原理定理定理1：如果：如果k+1个或更多的物体放入个或更多的物体放入k个盒子，那个盒子，那么至少有一个盒子包含了么至少有一个盒子包含了2个或更多的物体个或更多的物体第一种形式第一种形式如果如果n只鸽子飞入只鸽子飞入k个巢且个巢且kn,则某些巢至少有两则某些巢至少有两只鸽子。只鸽子。解题关键：解题关键：鸽子？鸽子？鸽巢？鸽巢

18、？一组367个人中一定至少有2个人有相同的生日。有366个不同的生日。（367人鸽子，366个生日鸽巢）27个英文单词中一定至少有2个单词以同一个字母开始。26个英文字母如果考试给分从0100，班上必须有多少学生才能保证这次期末考试中至少有2个学生得到相同的分数？101个分数，至少102个学生3.2.3 巧妙使用鸽巢原理例：在30天的一个月里，某棒球队一天至少打一场比赛，但至多打45场。证明一定有连续的若干天内这个对恰好打了14场。解：令aj是第j天之前（包括第j天）所打的场数，则a1,a2,a30是严格递增序列，且1 aj 45那么 a1+14,a2+14,a30+14也是严格递增的，且14

19、 aj+14 59 则：在1，59 的60个正整数 a1,a2,a30，a1+14,a2+14,a30+14 根据鸽巢原理，必然有两个正整数相等。aj+14=ai 也就是说：从第j+1天到第i天，恰好打了14场3.3.2 排列 n个不同的元素 x1,.xn的一个排列就是这n个元素的一个次序。定理：具有n个不同元素的集合的r排列是P(n,r)=n(n-1)(n-2)(n-r+1)推论：如果n和r都是整数，且1 r n，则例字母ABCDEF中有多少个包含DEF的排列？ABCDEF例字母ABCDEF中有多少个包含DEF任意顺序的排列？ABCDEF3！*4！3.3.3 组合不考虑顺序的对象的选取叫做组

20、合例5个学生想和校长谈奖学金的事，校长办公室安排3个人去谈，问有多少种方法从5选3？C(5，3)=10 3.5 广义的排列组合有重复元素允许重复元素多重集 的排列组合问题3.5.2 有重复的排列当元素允许重复时，使用乘积法则很容易计数排列当元素允许重复时，使用乘积法则很容易计数排列数数例：用英文字母可以构成多少个例：用英文字母可以构成多少个r位字符串位字符串26r定理：具有定理：具有n个物体的集合允许重复的个物体的集合允许重复的r排列数是排列数是nr3.5.3 有重复的组合例：考虑例：考虑3本书本书(计算机，数学、历史计算机，数学、历史)，每本书图，每本书图书馆有书馆有6本拷贝，选择本拷贝，选

21、择6本书有多少种可能？本书有多少种可能？v分析计算机|数学|历史*|*|*计算机|数学|历史|*|*8个元素中 6个*2个|的排列数例（1）满足x1+x2+x3+x4=29的非负整数解有多少种？解：每一个解相当于从4类元素中选取29个，其中从第i类元素中选取xi个，i=1,2,3,4。29个1，4-1个|，C(29+4-1，4-1)可辨别的物体可辨别的物体可辨别的盒子可辨别的盒子例：有多少种方式把52张标准的扑克牌发给4个人使得每人5张牌不可辨物体不可辨物体可辨的盒子可辨的盒子例：将10个相同的球放入8个可辨别的桶，共有多少种方法？解：从8个元素的集合中取出的10组合的个数可辨别的物体可辨别的

22、物体不可辨别的盒子不可辨别的盒子例：将4个不同的雇员安排在3间不可辨别的办公室，有多少种方式？其中每间办公室可以安排任意个数的雇员。解：C(4,4)+C(4,3)+C(4,2)+C(3,1)不可辨别的物体不可辨别的物体不可辨别的盒子不可辨别的盒子例：将同一本书的6个副本放到4个相同的盒子里，其中每个盒子都能放下6个副本5、高级计数问题 4.1 递推关系基础1.以5开始2.给定了某一项，+3得到下一项5 8 11 14 17 20 23 va1=5v an=an-1+3 n 2v a2=a1+3 =5+3=8v a3=a2+3=8+3=11v递推关系是由数列第n项前的若干项确定第n项，并由此确定

23、数列。例确定an是否为递推关系an=2an-1-an-2,n=2,3,4，的解，其中an=3n,n是非负整数。解：2an-1-an-2=2*3(n-1)-3(n-2)=3n=an若an=2n2an-1-an-2=2*2n-1-2n-2=2n-2n-2an若an=5，2an-1-an-2=2*5-5=5=an例 投资$1000,利息12%An 第n年底的总金额，An An=An-1+(0.12)An-1=1.12An-1 n 1 A0=1000 A3=1.12A2=1.12*1.12A1=1.12*1.12*1.12 A0=1.12 3(1000)An=1.12An-1=1.12 n(1000)

24、通项公式4.2求解线性递推关系数列a0,a1,.的通项公式an代入法定义：一个k阶常系数阶常系数 线性齐次线性齐次递推关系：an=c1an-1+c2an-2+ckan-k其中c1,c2,ck是实数，ck0例：cn=1.12 cn-1是一阶线性齐次递推关系fn=fn-1+fn-2是二阶线性齐次递推关系an=2an-5是5阶线性齐次递推关系an=an-1+an-12不是线性的；Hn=2 Hn-1+1 不是齐次的。求递推关系的显示表达式an=an-1+2an-2,其中a0=2，a1=7，解：递推关系的特征方程是：r2-r-2=0 r1=2,r2=-1因此an=b2n+d(-1)n根据初始条件可得：b

25、+d=22b-d=7得出b=3,d=-1因此an=32n-(-1)nan=5an-1 -6an-2其中a0=7 a1=16 解：递推关系的特征方程为：t2-5 t+6=0 t=2,t=3 a n=b2n+d3n 是解 根据初始条件：7=a 0=b20+d30=b+d16=a 1=b21+d 31=2b+3d b=5,d=2 因此：a n=5*2n+2*3n例 鹿群 n=0:200 n=1:220 从n-1到n的增长头数为n-2到n-1的增长头数的两倍，写出递推关系，求通项公式。解：设dn为时间n时数目 d0=200，d1=220dn-dn -1=2(dn-1-dn -2)递推关系：dn=3dn

26、 -1-2 dn -2t2 -3 t +2=0r1=1，r2=2dn=b r1 n+d r2 n=b 1 n+d 2n200=d0=b+d220=d1=b+2d b=180,d=20dn=180+20*2n4.5.2 容斥原理|AB|=|A|+|B|-|AB|例：一个离散数学班包括25个计算机专业的学生，13个数学专业的学生，8个同时主修计算机和数学两个专业的学生。如果每个学生主修数学专业、计算机专业或者同时主修这两个专业，那么班里有多少个学生解：25+13-8=305 关系 5.1.4 关系的性质集合集合X上的关系上的关系R，如果对于每个，如果对于每个x X 都有都有(x,x)R，则称，则称

27、R是是自反的自反的。例例7：下面是集合：下面是集合1，2，3，4上的关系上的关系R1=(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)R2=(1,1),(1,2),(2,1)R3=(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)R4=(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)R5=(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)R6=(3,4)其中其中R3,R5是自反的。是自反的。对称关系，反对称关系 集合集合A上的关

28、系上的关系R，如果对于每个，如果对于每个a,b A，如，如(a,b)R必必有有(b,a)R,则称则称R是是对称的对称的。集合集合A上的关系上的关系R，如果对于每个，如果对于每个a,b A，仅当，仅当a=b时，时，(a,b)A有有(b,a)R,则称则称R是是反对称的反对称的。v反对称：反对称：如果对于每个如果对于每个a,bA,如如(a,b)R且且a b,必有必有(b,a)R例11下列关系哪些是对称的，哪些是反对称的？R1=(a,b)|abR2=(a,b)|abR3=(a,b)|a=b或a=bR4=(a,b)|a=bR5=(a,b)|a=b+1R6=(a,b)|a+b3解：R3,R4,R6是对称的

29、R1,R2,R4，R5是反对称的。传递关系集合集合A上的关系上的关系R，如果对于每个，如果对于每个a,b,cA，如，如(a,b)R,且且(b,c)R,必有必有(a,c)R,则称则称R是是传递传递的的。例：正整数集合上的“整除”关系是自反的？对称的？反对称的？传递的？解：对于任意正整数a，a|a，自反的对于任意两个正整数，ab,如果a|b,那么b不能整除a.不是对称的，是反对称的。对于三个正整数a,b,c,如果a|b,b|c,那么a|c.所以是传递的。例X=1,2,3,4 到到 Y=a,b,c,d的关系的关系R=(1,b),(1,d),(2,c),(3,c),(3,b),(4,a)关系矩阵为关系

30、矩阵为关系矩阵依赖于X和Y的顺序 a b c d1 0 1 0 12 0 0 1 03 0 1 1 04 1 0 0 0例a,b,c,d上的关系R=(a,a),(b,b),(c,c),(d,d),(b,c),(c,b)对应于顺序a,b,c,d 的矩阵是其平方是可见，只要A2 的ij 项非零，A 的ij 项就非零。所以R 是传递的。5.4 关系的闭包R是集合是集合A上的关系。上的关系。如果存在包含如果存在包含R的具有性质的具有性质P的关系的关系S,并且并且S是是包含包含R且具有性质且具有性质P的每个关系的子集。的每个关系的子集。S叫做叫做R的关于的关于P的闭包。的闭包。自反闭包，自反闭包，对称闭

31、包对称闭包传递闭包传递闭包76例例1：整数集上的关系：整数集上的关系R=(a,b)|ab的自反的自反闭包是什么？闭包是什么？包含包含R的自反闭包是的自反闭包是R =(a,b)|ab(a,a)|a Z=(a,b)|ab集合集合A=1,2,3上的关系上的关系R=(1,1),(1,2),(2,2),(2,3),(3,1),(3,2)不是对不是对称的。称的。产生一个包含关系产生一个包含关系R的尽可能小的对称关系的尽可能小的对称关系R=(1,1),(1,2),(2,2),(2,3),(3,1),(3,2),(2,1),(1,3)R的自反闭包为：的自反闭包为：R R-1R-1 =(b,a)|(a,b)R例

32、：正整数集合上的关系例：正整数集合上的关系R=(a,b)|ab的的对称闭包？对称闭包？R R-1=(a,b)|ab (b,a)|ab=(a,b)|ab5.5 等价关系基础等价关系等价类划分例：1,2,3,4,5,6上的一个等价关系R=(1,1),(1,3),(1,5),(3,1),(3,3),(3,5),(5,1),(5,3),(5,5),(2,2),(2,6),(6,2),(6,6),(4,4)定义3.4.35.5.2 等价关系等价关系v定定义1：集合：集合X 上的一个自反的、上的一个自反的、对称的和称的和传递的关系称的关系称为X 上的上的等价关系等价关系v定定义2：等价元素，：等价元素，a

33、b例：考虑例：考虑1,2,3,4,5上的关系上的关系 R=(1,1),(1,3),(1,5),(2,2),(2,4),(3,1),(3,3),(3,5),(4,2),(4,4),(5,1),(5,3),(5,5)因为因为(1,1),(2,2),(3,3),(4,4),(5,5)R，所以，所以R是是自反的自反的。因为只要因为只要(x,y)在在R 中，则中，则(y,x)也在也在R 中，所以中，所以R 是是对称的对称的。最后，因为只要最后，因为只要(x,y)和和(y,z)在在R 中，则中，则(x,z)也在也在R 中，所以中，所以R 是是传递的传递的。所以所以R是是1,2,3,4,5上的等价关系。上的

34、等价关系。例X=1,2,3,4,5,6上的关系R=(1,1),(1,3),(1,5),(3,1),(3,3),(3,5),(5,1),(5,3),(5,5),(2,2),(2,6),(6,2),(6,6),(4,4)是等价关系。包含的等价类1由所有使得(x,1)R 的x 组成。所以1=1,3,5类似地可以找出其余的等价类：3=5=1,3,5，2=6=2,6，4=45.6 偏序定义1：集合S上的关系R,如果它是自反的、反对称的、传递的，那么就称之为偏序。集合S和偏序R一起叫做偏序集，记作(S,R)例：证明“大于等于”（）关系R是整数集合上的偏序。证明：自反的，aa反对称的，(a,b)R,ab，那

35、么b不大于等于a，即(b,a)R传递的，ab,bc,则ac例 正整数集合上的正整数集合上的”整除整除”关系关系R是偏序。是偏序。自反的，反对称的和传递的。自反的，反对称的和传递的。如果R 是集合X 上的一个偏序，有时用符号x y 来表示(x,y)R。这个符号表示将这种关系看做X 中元素的序。5.6.2 字典顺序例，确定在偏序集(ZZ,)中是否有(3,5)(4,8),(3,8)(4,5),(4,9)(4,11)？例，(1,2,3,5)(1,2,4,3)例，discreetdiscrete ,discrete=3)是由n个顶点v1,v2,vn以及边(v1,v2),(v2,v3),(vn-1,vn)

36、,(vn,v1)组成。C3C4C5轮图：对于n=3，当给圈图 Cn添加另一个顶点，并将这个新的顶点与Cn里的n个顶点逐一连接，则得到轮图WnW3W4W5n立方体图Qn,用顶点表示2n个长度为n的位串的图，两个顶点相邻当且仅当它们所表示的位串恰好相差一位Q2Q10110110001Q30000010100111011001101116.2.4 偶图图G=(V,E)称为二部图(偶图)，即存在V 的子集V1 和V2（其中任意一个可以为空集），满足V1 V2=,V1 V2=V，且与E 中的每条边相关联的两个顶点一个在V1 中，一个在V2 中。称是(V1,V2)图G顶点集的一个二部划分v1v2v3v4v

37、5例无向图G是偶图，从a,b,d到c,f,g,eabcdefgabcdef无向图H不是偶图，其顶点集无法分成两个互不相交的子集图G图H平行平行边表示？表示？abdcv例,用邻接矩阵表示下图v解，顶点顺序为a,b,c,d,邻接矩阵为无向无向图的的邻接矩接矩阵是是对称的称的v有向图的邻接矩阵v有向图G=(V,E),从vi到vj有边，则其邻接矩阵在(i,j)位置上有1，其中v1,v2,vn是有向图的任意顶点序列，G的邻接矩阵是一个nn的0-1矩阵，A=aij有向有向图的的邻接矩接矩阵不必是不必是对称的称的平面图在一个平面上画出一个连通的平面图时，该平面被分成几个连续的区域(称为面)，面的边界由一个图

38、的回路组成，可以用该回路标识该面。定理1，欧拉公式，设G是带e条边和v个顶点的连通可平面简单图。设r是G的可平面表示的面数。则 r=e-v+2r=e-v+2r=4(面数)e=8V=67 树7.1.2 树的性质定理定理2，带，带n个顶点的树有个顶点的树有n-1条边条边定理定理3，带有，带有i个内点的正则个内点的正则m元树含有元树含有n=mi+1个个顶点顶点T是一具有是一具有n个节点的图，则下面的结论是等价的个节点的图，则下面的结论是等价的(a)T是一树是一树(b)T是连通，无环的是连通，无环的(c)T是连通的，且有是连通的，且有n-1条边条边(d)T是无环的，且有是无环的，且有n-1条边条边定义树是没有简单回路的连通无向图。树不含多重边、没有环任何树都是简单图满足，如果v,w是T中的节点，v和w之间只有一条唯一的简单路径。一棵有根树是有一个特殊的顶点被设计成根节点的一棵树。例1，哪些是树？abcdfeabcdfeabcdfeabcdfeG1G2G3G4