《(完整word版)离散数学知识点整理.pdf》由会员分享，可在线阅读，更多相关《(完整word版)离散数学知识点整理.pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、.离散数学一、逻辑和证明1.1 命题逻辑命题：是一个可以判断真假的陈述句。联接词：、?、?。记住“p仅当 q”意思是“如果 p，则 q”，即p。记住“q除非 p”意思是“?pq”。会考察条件语句翻译成汉语。构造真值表p q pq pq pq p?q pq?p T T T T T T F F T F F T F F T F F T F T T F T T F F F F T T F T 1.2 语句翻译系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq 无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。1.3 命题等价式逻辑等价：在所有可能情况下都有相同的真值的两个复合命题
2、，可以用真值表或者构造新的逻辑等价式。证逻辑等价是通过p 推导出 q，证永真式是通过p 推导出 T。逻辑等价式pT?p pF?p 恒等律pF?F pT?T 支配律pp?p 幂等律?(?P)?p 双否律pq?q p 交换律(p q)r?p(qr)结合律p(q r)?(p q)(pr)p(q r)?(p q)(pr)分配律?(pq)?p?q?(pq)?p?q 德摩根律p(p q)?pP(p q)?p 吸收律p?p?F p?p?T 否定律条件命题等价式pq?pq pq?q?p pq?pq pq?(p?q)?(pq)?p?q(p q)(pr)?p(qr).(p r)(qr)?(pq)r(p q)(pr
3、)?p(qr)(p r)(qr)?(pq)r 双条件命题等价式p?q?(p q)(q p)p?q?p?q p?q?(p q)(?p?q)?(p?q)?p?q 1.4 量词谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如?x0P(x)。当论域中的元素可以一一列举，那么?xP(x)就等价于P(x1)P(x2).P(xn)。同理，?xP(x)就等价于 P(x1)P(x2).P(xn)。两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如?x（P(x)Q(x)和(?xP(x)(?xQ(x)。量词表达式的否定：?x
4、P(x)?x?P(x)，?xP(x)?x?P(x)。1.5 量词嵌套我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。1.6 推理规则一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证不代表结论正确，因为也许有的前提是假的。推理规则，都是基于永真式的，用来证明一个前提蕴含一个结论。而基于可满足式的推理规则叫谬误。p pq(p(pq)q 假言推理q pq qr(p q)(qr)(pr)假言三段论pr?q pq(?q(pq)?p 取拒式?p pq?p(p q)?p)q 析取三段论q p
5、 p(p q)附加律pq pq(p q)p 化简律p p q（pq）（pq）合取律文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK
6、7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S
7、9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK
8、7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S
9、9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK
10、7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S
11、9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9.pq pq?pr(p q)(?pr)(q r)消解律qr 量化推理规则?xP(x)全称实例P(c)P(c)，任意 c 全称引入?P(x)?xP(x)存在实例P(c)，对某个 c P(c)，对某个 c 存在引入?xP(x)命题和量化命题的组合使用。二、集合、函数、序列、与矩阵2
12、.1 集合说的是元素与集合的关系，?说的是集合与集合的关系。常见数集有N=0,1,2,3.，Z 整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。A和 B相等当仅当?x(x A?xB)；A是 B的子集当仅当?x(x AxB)；A是 B的真子集当仅当?x(x AxB)?x(x?AxB)。幂集：集合元素的所有可能组合，肯定有?何它自身。如?的幂集就是?，而?的幂集是?，?。笛卡尔积：AB，结果是序偶，其中的一个子集叫一个关系。带量词和集合符号如?xR（x20）是真的，则所有真值构成真值集。集合恒等式名称(AB)=A B(AB)=A B 德摩根律A(AB)=A A(AB)=A 吸收
13、律2.3 函数考虑 AB 的函数关系，定义域、陪域（实值函数、整数值函数）、值域、像集（定义域的一个子集在值域的元素集合）。一对一或者单射：B可能有多余的元素，但不重复指向。映上或者满射：B中没有多余的元素，但可能重复指向。一一对应或者双射：符合上述两种情况的函数关系。反函数：如果是一一对应的就有反函数，否则没有。合成函数：f g(a)=f(g(a)，一般来说交换律不成立。2.4 序列无限集分为：一组是和自然数集合有相同基数，另一组是没有相同基数。前者是可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一一对应的关系。如果 A和 B是可数的，则 AB也是可数的。文档编码:C
14、M7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3
15、A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:C
16、M7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3
17、A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:C
18、M7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3
19、A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:C
20、M7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9.如果存在一对一函数f 从 A到 B和一对一函数 g 从 B到 A，那么 A和 B之间是一一对应的。求和公式：a+ar+ar2+ar3+.+arn=(arn+1-a)/(r-1)1+2+3+.+n=n(n+1)/2 1+22+32+.+n2=n(n+1)(2n+1)/6 1+23+33+.+n3=n2(n+1)2/4 2.6 矩阵普通矩阵和、减、乘积，0-1 矩阵还可以
21、、（和相乘类似，用代替+，用代替）九、关系9.1 关系及其性质设 A和 B是集合，从 A到 B的二元关系是 AB的子集。一个从 A到 B的二元关系是集合 R，第一个元素取自A，第二个元素取自 B，当(a,b)属于 R时写作aRb。集合 A上的关系是 A到 A的关系，有 n 个元素就有 n2个有序对，n2个有序对就有 2n2个关系。考虑集合 A到 A 的关系 R：任意 aA都有（a，a）R，则 R是集合 A上的自反关系。任意 a，bA，若（a，b）R都有（b，a）R，则 R是对称关系。任意 a，bA，若（a，b）R且（b，a）R一定有 a=b，则 R是反对称关系。任意 a，b，cA，若（a，b）
22、R且（b，c）R一定有（a，c）R，则 R是传递关系。若 R是 A到 B的关系，S是 B到 C的关系，R与 S的合成 RS是有序数对（a，c）。其中 aA，cC，且存在一个bB 使得（a，b）R，（b，c）S。二元关系的 5 种复合要会翻译成汉语。9.3 关系的表示0-1 矩阵法：A有 n 个元素，B有 m个元素，用一个 nm的矩阵 MR表示，mij=1表示有关系。自反关系的0-1 矩阵主对角线全为1；对称关系的 0-1 矩阵是对称阵；反对称关系的0-1 矩阵关于主对角线反对称。MR1R2=MR1MR2，MR1 R2=MR1MR2，MR1R2=MR1MR2。有向图法：A有 n 个元素，每一个关
23、系是一条有向边。自反关系的图每一个顶点都有一个环；对称关系的图在不同顶点之间每一条边都存在与之对应的反方向边（也可用无向图）；反对称关系的图在不同顶点之间每一条边都不存在与之对应的反方向边；传递关系的图在3 个不同顶点之间构成正确方向的三角形。9.4 关系的闭包自反闭包：R，其中=（a，a）|a A 对称闭包：R并 R-1，其中 R-1=（b,a）|（a，b）R 传递闭包：R矩阵传递闭包=MRMR2MR3.MRn，了解沃舍尔算法9.5 等价关系：自反、对称且传递的关系集 合 A 的 元 素a 在R 上 的 等 价 类 a=s|(a,s)R s A。如A=1,2,3,4,5,6,7,8，R=(a
24、,b)|a=b(mod 3)的等价类划分如下文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4
25、S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 H
26、K7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4
27、S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 H
28、K7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4
29、S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 H
30、K7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9.1=4=7=1,4,7,2=5=8=2,5,8,3=6=3,6 9.6 偏序关系：自反、反对称且传递的的关系偏序集（S，）中如果既没有ab，也没有 ba，则 a 和 b 是不可比的。全序集：如果偏序集中每个元素都可比，则为全序集，如（Z，）是全序集，但（Z+，|）不是，因为有5 和 7 是不可比的。良序集：如果是
31、全序集，而且S的每个非空机子都有一个最小元素，则为良序集。哈塞图：对有穷偏序集，去掉环，去掉所有由传递性可以得到的边，排列所有的边使得方向向上。极大元极小元：图中的顶元素和底元素，可能有多个最大元最小元：只有唯一的一个，比其他都或上界下界：只有唯一的一个，比其他都或格：每对元素都有最小上界和最大下界十、图10.1 图的概念简单图：每对顶点最多只有一条边多重图：每对顶点可以有多条边无向图：边没有方向有向图：边有方向10.2 图的术语无向图中，点 v 的度为 deg(v)，如果 v 是一个环，则度为2。度为 0 的点是孤立的，度为 1 的点是悬挂的。有 m条边的无向图则 2m=deg(v)。无向图
32、有偶数个度为奇数的点，因为2m=deg(Vi)+deg(Vj)。有向图中，点 v 的入度为 deg-(v)，出度为 deg+(v)，且 deg-(v)=deg+(v)=边数。有向图忽略边的方向后得到的图叫做基本无向图，它们有相同的边数。会画完全图 Kn、圈图 Cn、轮图 Wn。二分图，将点分成 2 部分，每条边都连着一部分和另一部分。用着色法判读文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:C
33、M7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3
34、A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:C
35、M7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3
36、A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:C
37、M7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3
38、A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9.是否是二分
39、图。完全二分图Kn,m是边最多的二分图。10.3 图的表示邻接表：无向简单图包括顶点和相邻顶点，不太好表示无向多重图因为边的数量不好表示。有向图包括起点和终点。邻接矩阵：无向简单图按顶点排列，如果vi和 vj之间相邻则 aij是 1，否则是 0。无向多重图这时aij是 vi和 vj之间的边数。可知无向图的邻接矩阵都是对称阵。有向简单图也按照顶点排列，如果vi，vj是边则 aij是 1，否则是0。有向多重图也按顶点排列，只不过aij是vi，vj 之间的边数。关联矩阵：将图 G按 v 行 e 列排列，如果 vi和 ej关联，则 aij是 1，否则是 0。图的同构：简单图G1和 G2，如果存在一一对
40、应的从V1 到 V2的函数 f，且对 V1的 a 和 b 来说，a 与 b 相邻当仅当 f(a)与 f(b)在 G2中相邻，则 G1和 G2是同构的，f 称为同构。图形不变量如顶点数、边数、度数，如果不同则不同构，如果相同则可能同构。当我们找到 f 后，还要比较两个图的邻接矩阵，看 f 是否是保持边的。10.4 图的连通性简单图中，用 x0=u，x1.xn=v 来表示一条通路，若u=v 且路长度大于 0，则是回路，如果不包含重复的边，则这条通路是简单的。无向图中每对不同顶点之间都有通路则这个图是连通的，割点（关节点）、割边（桥）去掉后就会使图变得不连通，不含割点的图叫做不可割图。有向图中，任意
41、一对顶点a 和 b，都有从 a 到 b 以及从 b 到 a 的通路，则这个有向图是强连通的，如果只是基本无向图能保持联通则叫做弱联通的，会求强连通分支。通路与同构：可以用长度为k2 的简单回路的存在性来证不同构或者是潜在的同构映射 f，同样找到 f 后还要验证 f 保持边。图 G（允许是有向和无向、多重边和环）的vi到 vj的长度为 n 的不同通路的条数等于 Ani,j，A是 G的邻接矩阵。10.5 欧拉回路与哈密顿回路欧拉回路：包含 G的每一条边的简单回路。欧拉通路：包含 G的每一条边的简单通路。含有至少2 个顶点的连通多重图有欧拉回路当仅当它的每个顶点度都为偶数，有欧拉通路但无欧拉回路当仅
42、当它恰有2 个度为奇数的顶点。哈密顿回路：包含G的每一个顶点恰好一次的简单回路。哈密顿通路：包含G的每一个顶点恰好一次的简单通路。含有至少 3 个顶点的简单图，若每个顶点的度都(n/2)，或者每一对不相邻的顶点 u 和 v 都有 deg(u)+deg(v)n，则有哈密顿回路。最短通路算法：迪克斯特拉算法和旅行商问题（枚举）10.7 平面图欧拉公式：G是有 e 条边和 v 个顶点的平面连通简单图，r 是 G的平面图表示中的面数，则有 r=e-v+2。根据上述条件，有3 个推论，可以用来判断不是平面图：推论 1：若 v3，则 e3v-6。推论 2：G中有度不超过 5 的顶点。推论 3：v3且没有长
43、度为 3 的回路，则 e2v-4。库拉兔斯基定理：若G是平面图，则删掉一条边 u,v 并添加一个新顶点w文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7
44、I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1
45、 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7
46、I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1
47、 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7
48、I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1
49、 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9.和两条边 u,w 和v,w 得到的仍然是平面图。若G1和 G2都是这样得到的，则G1和 G2是同胚的。一个图是非平面图当仅当它包含一个同胚于K3,3或者 K5的子图。10.8 着色图地图转换为对偶图时，区域变顶点，相邻的区域则顶点相连。图的着色数是指着色
50、所需的最少颜色数(G)，这个值不超过 4。(Kn)=n，(Km,n)=2，(Cn)=2 当 n 为偶数且 4；(Cn)=3 当 n 为奇数且 3。文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A1 ZU7E4U4G4S9文档编码:CM7I7K2V1T7 HK7N3G4B3A