《交大离散数学复习课.ppt》由会员分享，可在线阅读，更多相关《交大离散数学复习课.ppt（106页珍藏版）》请在三一文库上搜索。
1、复习,重点章节：第1、2、3、5章 选择复习章节：第4、7、8章,考试 形式,闭卷，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的公式，谓词公式(x)(A(x)B)等价于（ ） A)
2、 (x) (A(x)B B) (x)(A(x)B C) A(x) B D) (x)A(x)(x)B 3. 设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 逻辑与证明,6,1.2 命题,命题是一个陈述句，或真或假，不可以既真又假。 命题是逻辑的基本构成单元 下列句子(a) (e)哪个为真，哪个为假（不能既
3、真又假） (a) 能整除7 的正整数只有1 和7 本身。 (b) 多伦多是加拿大的首都。 (c) 对于每个正整数n，存在一个大于n 的素数。 (d) 地球是宇宙中惟一存在生命的星球。 (e) 买两张星期五去“大剧院”音乐会的票。,(a)真 (b)假 (c)真 (d)不知真假，但一定是非真即假。因此是命题 (e)不是命题,7,真值表,复合命题的真值可以由真值表来表达。 用T 代表真，F 代表假。,复合命题pq，p q的真值由下列真值表,8,p: 天正在下雨 q: 天很冷 pq: 天正在下雨 并且天很冷 pq: 天正在下雨或者天很冷,例如： 命题“天正在下雨”与“天很冷”可以连接成 单一命题形式“
4、天正在下雨与天很冷”。 “与”和“或”的形式化定义。,9,9,条件命题的真值表,10,例,考察： “如果今天天晴，那么我们将去海滩” 只有当 今天天晴，而我们不去海滩 时，这个命题为假，否则上述命题成立。 考察：“如果今天是星期五，那么2+3=5” 该命题总是成立，因为2+3=5总是为真 考察“如果今天是星期五，那么2+3=6” 该命题 当今天不是星期五 时，成立,11,1.1.4逻辑运算符的优先级,优先级: ( ) 假设：p 真 q假 r真，给出下面每个命题的真值 (p q) r (p q) r p (q r) p (q r),1.1.5 复合命题的真值表,构造真值表 (p q) (p q)
5、,12,1.1.6 翻译语句形式化表示,“只有你主修计算机科学或不是新生，才可以从校园网访问因特网” 设：a: 你可以从校园网访问因特网 c: 你主修计算机科学 f: 你是个新生 问题：该语句的等价说法（ ）： A“如果你主修计算机科学，或者你不是新生，那么你可以从校园网访问因特网” B“如果你可以从校园网访问因特网，那么你主修了计算机科学，或者你不是新生” 所以，形式化表示为： a (c f),13,证明命题: p(q r)与 (pq) (pr) 等价,14,1.2.3 德摩根定律的运用,用德摩根律表达“麦克有一部手机和一台电脑”的否定 解：p麦克有一部手机，q麦克有一台电脑 那么原命题表示
6、为：p q 则其否定（pq）等价于 p q 即：“麦克没有一部手机或没有一台电脑” 用德摩根律表达“John或者Jessi将去看电影”的否定 解：p:John去看电影，q：Jessi去看电影 那么原命题表示为：p q 则其否定（p q）等价于 p q 即：“John和Jessi都不去看电影”,15,16,1.3.3 量词,量化：谓词在一定范围内的取值 谓词演算：处理谓词和量词的逻辑领域 全称量词：P(x)的全称量化表示语句“P(x)对x在其论域中的所有值都为真” 存在量词：P(x)的存在量化表示语句“论域中至少有一个值满足P(x)为真”,17,例： P(x)表示语句“x20”，论域为不超过4的
7、正整数， x P(x)的真值是什么？ 解：论域为1，2，3，4，P(1),P(2),P(3)为真。,17,例 P(x)表示语句“x20”，论域为不超过4的正整数，则： x P(x)的真值是什么？ 解： x P(x)就是合取式P(1) P(2) P(3) P(4) 由于P(4)为假，所以 x P(x)为假,18,1.3.5 约束论域量词,x0) x(x0) y0 (y3 0) y(y0 y3 0) 全称量词的约束等价于一个条件语句的全称量化 z0 (z2=2) z(z0 z2=2) 存在量词的约束等价于一个合取的存在量化,19,1.3.8 涉及量词的逻辑等价,定义3：涉及量词的语句是逻辑等价的，
8、当且仅当无论什么谓词代入这个语句，也不论用哪个个体论域于这些命题函数里的变量上，它们都有相同的真值。 x(P(x) Q(x)xP(x) xQ(x) x(P(x) Q(x) xP(x) xQ(x) x(P(x) Q(x)与xP(x) xQ(x)不逻辑等价 x(P(x) Q(x)与 xP(x) xQ(x)不逻辑等价,19,1.3.9 否定量化词表达式,考虑语句的否定： “班里每个学生都学过微积分”即 xP(x) 其中P(x)：x学过离散数学 其否定：“并非班里每个学生都学过微积分” 也就是：“班里有学生没有学过微积分”，即 xP(x) 等价关系： xP(x) xP(x),20,21,1.4.3 将
9、数学语句翻译成嵌套量词语句,翻译语句“两个正整数的和是正数” xy (x0) (y 0) (x+y 0) 嵌套语句翻译成数学语句： 考虑命题 x y (x y0) 论域为实数域。这个命题为真，因为对每个实数x，至少存在一个y（可选取y = -x），使x + y = 0为真。这个命题用文字表达为： 对每个实数x，存在一个实数y，可使x 与y 的和为零。,22,例,确定论证p q,p/q是否有效,注意：只要前提pq和p为真，结论q就为真。所以论证过程是有效的。,23,1.5.3命题逻辑的推理规则,假言推理/分离定律,合取,拒取,附加,化简,假设段论,析取段论,q p q _ p,p p q _ q
10、,P q _ pq,pq _ p,p _ pq,p q q r _ pr,pq p _ q,pq p r _ q r,消解,例,给出定理“若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”是奇数”矛盾 所以原来的条件语句为真，定理得证。,24,反例证明法,反驳 x P(x)
11、只需在论域内找到一个x，使P(x)为假。 例 1.5.19 命题 “n (2n+1)是素数”为假。 反例为n3时，239，不是素数,25,2.集合、函数、数列与求和,2.1.2 幂集,如X是Y的子集但X不等于Y, 则X是Y的一个真子集 空集是任何集合的子集 定义7：集合X的所有子集的集合，称为X的幂集，用P(X)表示,28,28,例,如A=a,b,c P(A)的成员： ,a,b,c,a,b,a,c,b,c,a,b,c A=3，P(A) =23=8,29,2.1.3 笛卡儿积,一个由两个元素组成的有序对(或序偶)，写为(a,b) (a,b)=(c,d)当且仅当a=c,b=d. 定义8：有序n元组
12、（a1,a2,an）是以a1为第一个元素，a2为第二个元素，an为第n个元素的有序组 定义9：X,Y集合，XY称为X和Y的笛卡儿积，是所有有序对(x,y)的集合，其中xX, yY。即 XY=(x,y)| xX, yY,30,例,X=1,2,3 Y=a,b XY=1,a,1,b,2,a,2,b,3,a,3,b YX=a,1,a,2,a,3,b,1,b,2,b,3 XX=1,1,1,2,1,3,2,1,2,2,2,3,3,1,3,2,3,3 YY=a,a,a,b,b,a,b,b,31,Venn图：关于集合的形象化表示,1,2,4,3,A,B,1,2,4,3,A,B,32,划分,一个由集合X的非空子
13、集的整体组成的S，如X的每个元素都只属于S的某一个元素，S就称为X的一个划分。,例： 集合X=1,2,3,4,5,6,7,8 S=1,4,5,2,6,3,7,8 S是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 是一
14、对一的。,例,定义序列s 为 sn = 2n + 43n， n 0 (a) 求s0。 (b) 求s1。 (c) 求si 的公式。 (d) 求sn-1 的公式。 (e) 求sn-2 的公式。 (f) 证明序列sn满足 sn = 5sn-1 - 6sn-2， 对所有n 2,3、计数,乘法原理,乘积法则：假定一个过程可以被分解成两个任务，完成第一个任务有n1种方式，在第一个任务完成之后有n2种方式完成第二个任务，那么完成这个过程有n1n2种方式。 如果一种活动由连续t步组成， 第一步有n1种方法， 第二步有n2种方法， . . . 第t步有nt种方法， 那么不同的活动数目有 n1 * n2* . .
15、 . * nt,当一活动由连续几步组成时，把每一步的方法数乘起来.,例题讲解,例1 用一个字母和一个不超过100的正整数给礼堂的座位编号。那么不同编号的座位最多有多少？ 解：给一个座位编号的过程分两个任务： 从26个字母中选取一个字母； 从100个正整数中选取一个整数。 根据乘法原理，座位的编号方式可以有： 26*100=2600种 例2 有多少个不同的7位二进制串？ 解：7位二进制串的每一位都可以有两种选择，因此有 27,例,如果不允许重复，用ABCDE可以组成多少长度为4的字符串？其中有多少是以B开头的？ 1* 4 * 3 * 2 =24,例,如果不允许重复，用ABCDE可以组成多少长度为
16、4的字符串？其中有多少不是以B开头的？ 4 * 4 * 3 *2 = 96 120 - 24,加法原理,假设X1, . . . , Xt是集合且第i个集合有 ni个元素，如果X1, . . . , Xt两两不相交，则可以从X1或X2或 . . . Xt选择元素的可能性有 n1 + . . . +nt,当被计数的元素可以被分解到不相交的子集时，可将每个子集的元素数相加得到总的元素数.,例,由A、B、C、D、E、F 6人委员会要选一个主席，一个秘书，一个书记 有多少种选法？ 如果A或B必须是主席，有多少种？ 如果E必须任3职之一，有多少种？ 如果D和F必须任职，有多少种？,3.2.1 鸽巢原理,定
17、理1：如果k+1个或更多的物体放入k个盒子，那么至少有一个盒子包含了2个或更多的物体 第一种形式 如果n只鸽子飞入k个巢且kn,则某些巢至少有两只鸽子。 解题关键： 鸽子？ 鸽巢？,一组367个人中一定至少有2个人有相同的生日。 有366个不同的生日。 （367人鸽子，366个生日鸽巢） 27个英文单词中一定至少有2个单词以同一个字母开始。 26个英文字母 如果考试给分从0100，班上必须有多少学生才能保证这次期末考试中至少有2个学生得到相同的分数？ 101个分数，至少102个学生,3.2.3 巧妙使用鸽巢原理,例：在30天的一个月里，某棒球队一天至少打一场比赛，但至多打45场。证明一定有连续
18、的若干天内这个对恰好打了14场。 解：令aj是第j天之前（包括第j天）所打的场数， 则a1,a2,a30是严格递增序列，且1 aj 45 那么 a1+14, a2+14,a30+14也是严格递增的，且14 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)(
19、n-r+1) 推论：如果n和r都是整数，且1 r n ，则,例,字母ABCDEF中有多少个包含DEF的排列？,A,B,C,DEF,例,字母ABCDEF中有多少个包含DEF任意顺序的排列？,A,B,C,DEF,3！ * 4！,3.3.3 组合,不考虑顺序的对象的选取叫做组合,例,5个学生想和校长谈奖学金的事，校长办公室安排3个人去谈，问有多少种方法从5选3？ C(5，3)= 10,3.5 广义的排列组合,有重复元素 允许重复元素 多重集 的排列组合问题,3.5.2 有重复的排列,当元素允许重复时，使用乘积法则很容易计数排列数 例：用英文字母可以构成多少个r位字符串 26r 定理：具有n个物体的集
20、合允许重复的r排列数是nr,3.5.3 有重复的组合,例：考虑3本书(计算机，数学、历史)，每本书图书馆有6本拷贝，选择6本书有多少种可能？,分析 计算机 | 数学 |历史 * | * * | * 计算机 | 数学 |历史 | *| * 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张牌,不可辨物体可
21、辨的盒子 例：将10个相同的球放入8个可辨别的桶，共有多少种方法？ 解：从8个元素的集合中取出的10组合的个数,可辨别的物体不可辨别的盒子 例：将4个不同的雇员安排在3间不可辨别的办公室，有多少种方式？其中每间办公室可以安排任意个数的雇员。 解：C(4,4)+C(4,3)+C(4,2)+C(3,1),不可辨别的物体不可辨别的盒子 例：将同一本书的6个副本放到4个相同的盒子里，其中每个盒子都能放下6个副本,5、高级计数问题,60,4.1 递推关系基础,以5开始 给定了某一项，+3得到下一项,5 8 11 14 17 20 23,a1 =5 an = an-1 +3 n 2 a2 = a1 +3
22、= 5+3=8 a3 = a2 +3 = 8+3=11 递推关系是由数列第n项前的若干项确定第n项，并由此确定数列。,例,确定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=2n 2an-1-an-2=2*2n-1-2n-2=2n-2n-2an 若an=5，2an-1-an-2=2*5-5=5=an,61,62,例,投资$1000, 利息12% An 第n年底的总金额， An An = An-1 + (0.12) An-1 = 1.12An-1 n 1 A0=10
23、00 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) 通项公式,63,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不是线性的； H
24、n=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+d=2 2b-d=7 得出b=3,d=-1 因此an = 32n-(-1)n,64,65,an = 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+
25、d 16 = a 1 = b21 +d 31 =2b+3d b=5, d= 2 因此：a n = 5*2n +2*3n,66,例,鹿群 n=0 :200 n=1 : 220 从n-1到n的增长头数为n-2到n-1的增长头数的两倍，写出递推关系，求通项公式。,解：设dn为时间n时数目 d0=200， d1=220 dn - dn - 1 =2 (dn-1 - dn - 2 ) 递推关系：dn = 3dn - 1 - 2 dn - 2 t2 - 3 t + 2 = 0 r1 = 1， r2 = 2 dn = b r1 n+ d r2 n = b 1 n+ d 2n 200 = d0= b + d
26、220= d1= b + 2d b=180, d=20,dn = 180 + 20* 2n,4.5.2 容斥原理,|AB|=|A|+|B|-|AB| 例：一个离散数学班包括25个计算机专业的学生，13个数学专业的学生，8个同时主修计算机和数学两个专业的学生。如果每个学生主修数学专业、计算机专业或者同时主修这两个专业，那么班里有多少个学生 解：25+13-8=30,67,5 关系,5.1.4 关系的性质,集合X上的关系R，如果对于每个x X 都有(x,x) R，则称R是自反的。 例7：下面是集合1，2，3，4上的关系 R1=(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),
27、(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上的关系R，如果对于每个a,b A，如(a,b)R必有(b,a) R,则称R是对称的。 集合A上的关系R，如果对于每个a,b A，仅当a=b时，(a,b)A有(b,a)
28、 R,则称R是反对称的。,反对称： 如果对于每个a,bA,如(a,b) R且ab,必有 (b,a) R,例11下列关系哪些是对称的，哪些是反对称的？ R1=(a,b)|ab R2=(a,b)|ab R3=(a,b)|a=b或a=b R4=(a,b)|a=b R5=(a,b)|a=b+1 R6=(a,b)|a+b3 解：R3,R4, R6是对称的 R1,R2, R4，R5是反对称的。,传递关系,集合A上的关系R，如果对于每个a,b ,cA，如(a,b)R,且(b,c) R,必有(a,c) R,则称R是传递的。,例：正整数集合上的“整除”关系是自反的？对称的？反对称的？传递的？ 解： 对于任意正整
29、数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) 关系矩阵为,关系矩阵依赖于X和Y的顺序,例,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 项就非零。所以
30、R 是传递的。,76,5.4 关系的闭包,R是集合A上的关系。 如果存在包含R的具有性质P的关系S,并且S是包含R且具有性质P的每个关系的子集。 S叫做R的关于P的闭包。 自反闭包， 对称闭包 传递闭包,例1：整数集上的关系R=(a,b)|ab的自反闭包是什么？ 包含R的自反闭包是 R =(a,b)|ab(a,a)|aZ=(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)
31、R的自反闭包为：RR-1 R-1 =(b,a)|(a,b)R,例：正整数集合上的关系R=(a,b)|ab的对称闭包？ RR-1= (a,b)|ab (b,a)|ab =(a,b)|ab,5.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.3,5.5.2 等价关系 定义1：集合X 上的一个自反的、对称的和传递的
32、关系称为X 上的等价关系 定义2：等价元素，ab,例：考虑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,
33、 3, 4, 5上的等价关系。,例,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 = 4,5.6 偏序,定义1：集合S上的关系R,如果它是自反的、反对称的、传递的，那么就称之为偏
34、序。集合S和偏序R一起叫做偏序集，记作(S,R) 例：证明“大于等于”（）关系R是整数集合上的偏序。 证明：自反的，aa 反对称的，(a,b)R, ab， 那么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) 例，disc
35、reetdiscrete , discretediscretion,5.6.3 哈塞图,考察1,2,3,4上的偏序(a,b)|ab的有向图 一个包含足够表示偏序信息的图哈塞图 去掉换，由于传递性而出现的边，方向(默认自下向上）,1,1,1,3,2,4,2,2,3,3,4,4,表示1,2,3,4,6,8,12上的偏序(a,b)|a整除b 的哈塞图,5.6.4 极大元素与极小元素,例，偏序集(2,4,5,10,12,20,25,|)的哪些元素是极大的，哪些是极小的？ 极大元素：12,20,25 极小元素：2,5,6 图,6.2.3 一些特殊的简单图,n个节点的简单图，若每一对节点间都存在一条边，则
36、称为完全图，记为Kn。 考察n=1,2,3,4,5,6时的完全图,例子,K4,圈图Cn(n=3)是由n个顶点v1,v2,vn以及边(v1,v2),(v2,v3),(vn-1,vn),(vn,v1)组成。,C3,C4,C5,轮图：对于n=3，当给圈图 Cn添加另一个顶点，并将这个新的顶点与Cn里的n个顶点逐一连接，则得到轮图Wn,W3,W4,W5,n立方体图Qn,用顶点表示2n个长度为n的位串的图，两个顶点相邻当且仅当它们所表示的位串恰好相差一位,Q2,Q1,0,1,10,11,00,01,6.2.4 偶图,图G = (V, E)称为二部图(偶图)，即存在V 的子集V1 和V2（其中任意一个可以
37、为空集），满足V1 V2 = , V1 V2 = V，且与E 中的每条边相关联的两个顶点一个在V1 中，一个在V2 中。称是(V1 ,V2)图G顶点集的一个二部划分,例,无向图G是偶图，从a,b,d到c,f,g,e,无向图H不是偶图，其顶点集无法分成两个互不相交的子集,图G,图H,平行边表示？,a,b,d,c,例,用邻接矩阵表示下图 解，顶点顺序为a,b,c,d,邻接矩阵为,无向图的邻接矩阵是对称的,有向图的邻接矩阵 有向图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+2,r=e-v+2 r=4(面数) e=8 V=6,7 树,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，哪些是树？,G1,G2,G3,G4,