自考离散数学(02324)
2023-07-10 14:02:57 2 举报AI智能生成
登录查看完整内容
为你推荐
查看更多
自考离散数学(02324)每章核心重点
作者其他创作
大纲/内容
具有唯一真值的陈述句称为命题，命题的真值一定是唯一的，或者为真，或者为假，不能既真又假
语句本身是陈述句
它有唯一真值
判断命题的两个条件
可用大写字母或者小写字母表示
命题符号化
命题与命题的表示
不能再分解的命题称为原子命题或者简单命题
原子命题
在自然语言中，常使用连词来表示两个句子之间的关系。在命题符号化时，这样的连词将表示为联结词，联结词都有特定的符号
联结词
由原子命题通过联结词联结而成的命题，称为复合命题
复合命题
设P为命题，P的否定是一个复合命题，记作┐P
否定
设P和Q为两个命题，P和Q的合取是一个复合命题，记作P∧Q，当前仅当P和Q同时为T时，P∧Q为T，其余情况P∧Q为F
合取其根本含义是表示两个事件同时成立
并且
即···，又··
不但···，而且···
虽然···，但是···
自然语言中对应词语
合取具有对称性，两个原子命题可以互换位置
复合命题所含的多个原子命题之间可以没有逻辑关联性。我们仅关心它的表示，而忽略其语义。所以它的真值只与原子命题的真值有关，与语义无关
合取
设P和Q为两个命题，P和Q的的析取是一个复合命题，记作P∨Q。当且仅当P、Q同时为F时，P∨Q的真值为F，其余情况的真值为T
或
同或
或者
自然语言中有时会使用“或”来表示“相斥”的含义，即用“或”连接的两者不能同时成立，这样的语句不能表示为析取
析取具有对称性，两个原子命题可以互换位置
析取
设P、Q为两个命题，P和Q组成的条件命题是一个复合命题，记作P→Q，当且仅当P的真值为T，Q的真值为F时，P→Q的真值为F，其余情况真值为T
P称为前件或者前提，Q称为后件或结论
条件命题表示的是，当前件发生时后件是否发生。而当前件没有发生即P为F时，后件发生或不发生都没有关键
如果···，那么···
若···，则···
只有···，就···
因为···，所以···
只有···，才···
Q是P的必要条件
条件
设P和Q未两个命题，P和Q组成的双条件命题是一个复合命题，记作P↔Q。当P与Q的真值相同时，P↔Q的真值为T，否则P↔Q的真值为F
当P与Q的真值相同时，也可以看作P和Q是等价的，即P与Q互为充分必要条件
···当且仅当···
双条件
常用联结词
复合命题与联结词
命题与命题联结词
当符号P代表一个具体的命题时，此时P的真值是确定的，所以称为常项，符号P称为命题常项
命题常项
当符号P仅仅表示是一个命题，但并没有指明是哪个命题时，P为命题变远。一般地，命题变元不是命题
命题变元
命题用联结词和圆括号按一定的逻辑关系联结起来的符号称为合式公式
单个命题变元和命题常项是合式公式，并成为原子命题公式
若A是合式公式，则（┐A）是合式公式
若A、B是合式公式，则（P∧Q），（P∨Q），（P→Q），（P↔Q）也是
有限次地应用1~3形式的符号串是合式公式
命题演算的合式公式定义如下(1.6)
┐、∧、∨、→、↔
联结词优先顺序
合式公式的最外层括号可以省略
不影响运算次序的括号也可以省略
约定
合式公式
给定两命题A和B，设P1，P2，Pn为所有出现于A和B中的原子边元，若给P1，P2，Pn任一组真值指派，A和B的真值都相同，称A和B是等值或等价的，记作A⇔B。若至少存在一组真值指派，使得A与B的真值不相同，称A和B不等值或者等价，记作A<≠>B
两命题公式等价
设A为一命题公式，若A在她的各种指派情况下，其取值均为真，则称公式A为重言式或永真式
重言式或永真式（1.10）
设A为一命题公式，若A在她的各种指派情况下，其取值均为假，则称公式A为矛盾式或永假式
矛盾式或永假式（1.11）
设A为一命题公式，若A在它的各种指派情况下至少存在一组成真指派，则称A是可满足式。若可满足式A至少存在一个成假赋值，则称A为非重言式的可满足式
可满足式（1.12）
合式公式P是可满足式，等价于P至少存在一个成真赋值
重言式一定是可满足式，但可满足式不一定是重言式
若两个命题公式P和Q等价，则P↔Q是重言式
从1.10~1.12可知结论
德摩根律
蕴含等值式
等价等值式
吸收律
P28
命题定律
命题公式
设A、B为两个命题公式，A⇔B，当且仅当A↔B为一个重言式
定理1.2
当且仅当P→Q是一个重言式时，我们称P蕴涵Q，并记作PQ。PQ称P蕴涵Q或蕴涵式，亦称作永真条件式
对于任意公式A，有AA
对于任意公式A、B和C，若AB，BC，则AC
对于任意公式A、B和C，若AB，AC，则A(B∧C)
对于任意公式A、B和C，若AC，BC，则A∨BC
性质
永真条件式
设A和B为任意两个命题公式，A⇔B的充分必要条件是AB且BA
定理1.3
P32
推理定律
等值演算与蕴涵式
命题公式的等值演算
包含↔的公式等价变换为包含→和∧的公式
包含→的公式等价变换为包含￢和∨的公式
￢ ∧ ∨ → ↔
￢ ∧ ∨ →
￢ ∧
￢ ∨
￢ →
联结词完备集几种
联结词完备集
第1章 命题与命题公式
命题变元及其否定统称为文字
文字
仅由有限个文字构成的析取式称作简单析取式，简单析取式的联结词只有￢ ∨
简单析取式
仅由有限个文字构成的合取式称作简单合取式，简单合取式的联结词只有￢ ∧
简单合取式
一个简单析取式是重言式，当且仅当它同时含某个命题变元及它的否定式
一个简单合取式是矛盾式，当且仅当它同时含某个命题变元及它的否定式
简单析取式和简单合取式有以下性质
当且仅当它具有形式：A1∧A2∧···∧An，其中A1，A2，An是简单析取式
合取范式都是由简单析取式构成的，根据合取联结词的定义可知，当且仅当每个简单析取式都是重言式时，合取范式是重言式
合取范式
当且仅当它具有形式：A1∨A2∨···∨An，其中A1，A2，An是简单合取式
析取范式都是由简单合取式构成的，根据析取联结词的定义可知，当且仅当每个简单合取式都是矛盾式时，析取范式是矛盾式
析取范式
对任何一个命题公式，都存在与之对等的合取范式或析取范式
P38
求等值析取范式和合取范式的步骤
合取范式和析取范式等值
范式的概念
n个命题变元的简单合取式，称作布尔合取或极小项，简称为小项，其中每个命题变元与它的否定不能同时存在，但该命题变元必须出现且仅出现一次，或以变元的形式，或以变元的否定形式
定义
n个命题变元有2^n个小项，用字母m加上由编码构成的下标来表示每个小项，下标是个n位的二进制数。命题变元Pi则对应小项编码的第i位为1，若是命题变元Pi的否定，则对应i位为0。n位二进制也可以使用对应十进制数i来表示小项的编码。m011可以表示为m3
每一个小项具有一个相应编码，且只在一种情况下真值为T，即按照其编码值进行指派时，其真值为T，其他情况下，真值都为F。故每个小项有一个成真赋值，有2^n-1成假赋值。每个小项成真赋值均不相同。
任意两个小项的合取式为矛盾式
全体小项的析取式为重言式
小项
n个命题变元的简单析取式，称作布尔析取或极大项，简称为大项，其中每个命题变元与它的否定不能同时存在，但该命题变元必须出现且仅出现一次，或以变元的形式，或以变元的否定形式
大项
范式
对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称为原式的主析取范式
在公式的真值表中，所有真值为T的指派所对应的小项的析取，即构成该公式的主析取范式
定理
任何命题公式都存在与之等值的主析取范式，并且是唯一的
P42
等值演算方法求解主析取范式
主析取范式
对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称为原式的主合取范式
在公式的真值表中，所有真值为F的指派所对应的大项的合取，即构成该公式的主合取范式
任意含有n个命题变元的公式A，都存在与之等值的主合取范式，并且是唯一的
P44
等值演算方法求解主合取范式
主合取范式
P45
主析取范式求其主合取范式步骤
若A可化为与其等价的含2^n个小项的主析取范式，则A为重言式
若A可化为与其等价的含2^n个大项的主合取范式，则A为矛盾式
根据主范式的定义和定理得出结论
主范式
有效结论
CP规则推理
真值表法
主范式方法及等值演算
判断有效结论
自然推理系统
第2章 命题逻辑的推理理论
主语x是一个变量，称为个体词
谓语“大于3”表示主语的某一性质，称为谓词
P（x）表示句子\"x大于3\"，其中P表示的是性质，x表示的是变量
x大于3
个体词代表具体或特定的客体时
个体常项
个体词代表抽象或广泛的个体时
个体变项
个体变项的取值范围为个体域，或称论域。论域是个集合，即可以是又穷集合，也可以是无穷集合
论域
指明个体与个体性质之间的关系，用大写英文字母表示
表示形式
一个谓词、一些个体变量组成的表达式称为谓词变项或命题函数
命题函数不是命题，只有命题函数中的变元都取为特定具体的个体时，才是确定的命题
不带个体变项的谓词称为0元谓词
谓词变项
谓词
谓词的表示与概念
有些命题函数中，使用命题为真或为假的变量值并不是唯一的，即变量取不同的值时，得到命题真值是相同的
命题函数中表示数量的词称为量词，可以使用量词来表示个体常项与变项之间的数量关系，即对命题函数进行量化。量词分为两种，一是全称量词，二是存在量词。
量词
P(x)的全称量化是命题\"P(x)对x在其论域的所有值均为真\
一切、任意、所有、凡是
全称量词
P(x)的存在量化是命题\"论域中存在一个元素x使P(x)值为真\
存在着、有一个、至少有一个
存在量词
有些命题中需要指明论域，称为特性谓词。特性谓词是条件式的前件，在存在量词中特性谓词后跟一个合取项。
特性谓词
复合公式的联结词
原子谓词公式是合式公式
若A是合式公式，则￢A也是
若P、Q是合式公式，则（P∧Q），（P∨Q），（P→Q），（P↔Q）也是
若A是合式公式，x是A中出现的任何个体变元，则（∀x）A和（∃x）A也是
只有经过有限次应用规则1~4所得到的符号串才是合式公式
谓词演算的合式公式递归定义
自由变元与约束变元
将量词辖域中，量词的指导变元及其辖域中该变元的所有约束均改为本辖域中未曾出现过的个体变元，其余不变
约束变元改名规则
把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要替换该自由变元在公式中的所有出现出
自由变元代入规则
变元改名规则
量词与合式公式
∀xA(x)⇔A(a1)∧A(a2)∧···∧A(an)
∃xA(x)⇔A(a1)∨A(a2)∨···∨A(an)
论域确定后，有此等价关系
¬∀xA(x)⇔∃x¬A(x)
¬∃xA(x)⇔∀x¬A(x)
量词和否定联结词之间的关系（定理3.1）
E27
E28
谓词等式与蕴含式
谓词演算的等价式与蕴含式
一个公式，如果量词均在全式的开头，它们的作用域延伸到整个公式的末尾，则该公式称为前束范式
任意一个谓词公式，均存在与之等值的前束范式
存在定理
前束范式
对不同辖域的同名变元进行换名（换名规则）
利用定理3.1，将否定联结词深入到命题变元和谓词公式前面（量词转换规则）
利用等值式∀x（A∨B(x))⇔A∨∀xB(x)和∃x（A∧B(x))⇔A∧∃xB(x)，将量词移到全式最前面（量词前提规则）
谓词公式转前束范式步骤
第3章 谓词逻辑
空集的子集只有一个，即它本身，但空集的真子集不是本身
空集是唯一的
空集
对于任意集合A，必有一个子集是空子集（定理4.2）
设A为任意集合，以A的子集为元素所组成的集合，称为集合A的幂集
幂集有2^n个元素
幂集
集合的表示法
集合的基本概念
设任意两个集合A和B，属于A不属于B的所有元素组成的集合S，称A与B的差集，也称为B对于A的补集，或相对补
补集
A - B = A∩~B
A - B = A-（A∩B）
设A、B为任意两个集合，有如下关系式成立
集合运算的恒等式
设A、B为任意两个集合，A和B的对称差为集合S，其元素或属于A，或属于B，但不能既属于A又属于B，记作
对称差
集合的运算
有序对
不满足交换律
不满足结合律
任意集合X空集等于空集
若集合A有m个元素，集合B有n个，AXB有m*n个元素
笛卡尔积公式
笛卡尔积
有序对和笛卡尔积
第4章 集合
空关系
span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\
全域关系
恒等关系
特殊关系
R中所有有序对的第一元素构成的集合称为R的定义域，记为domR
定义域
R中所有有序对的第二个元素构成的集合称为R的值域，记为ranR
值域
集合A中所有的a都有aRa，关系R在A上是自反
集合A中所有的a都有，关系R在A上是反自反
关系
关系及关系的性质
设R是从X到Y的二元关系，如奖R中每一个二元组中的元素顺序互换，所得到的集合称为R的逆关系，简称为R的逆，记作
逆关系
二元关系的公式
关系的常规运算
设R为A到B的关系，S为B到C的关系，则称为R和S的复合关系，表示为
结合律
对任意的n≥4，均有R^n = R^3
复合关系
P90
复合关系的矩阵运算
关系矩阵的布尔运算
任意一个关系R，在R中添加新的二元组形成新的关系R'，仅添加必要的二元组，使得新关系具有我们想要的性质。得到的新关系称为原关系的闭包
原关系和恒等关系进行并运算使得新关系有自反
原关系和该关系逆运算进行并运算使得新关系有对称
原关系和该关系逆运算进行并运算使得新关系有传递
关系的闭包
关系的运算
给定集合A上的关系ρ，若ρ是自反的、对称的，则称ρ是A上的相容关系
相容关系
设R为非空集合A上的关系，若R是自反的、对称的和传递的，则称R为A上的等价关系
等价关系
等价类
划分不唯一
集合A的任一等价关系的等价类都构成A的一个划分
划分
设A是一个非空集合，如果A上的关系R满足自反性、反对称性及传递性，则称R是A上的一个偏序关系，记，集合A和A上的偏序关系一起称为偏序集
哈斯图P97
设是span class=\"equation-text\" data-index=\"0\" data-equation=\"\\preceq\" contenteditable=\"false\
全序关系
偏序关系
最小元是B中最小的元素，它与B中所有元素都可比，即与B中所有元素都存在偏序关系
最大元与B中所有元素是可比的，且都大于等于这些元素，即它是B中最大元素
极小元不一定与B中所有元素均可比，但只要可比，就一定是小于等于其他元素
极大元是B中没有比它更大的元素
最大元、最小元不一定存在，如果存在一定是唯一
极大元、极小元可能存在多个，如果极大元只有一个，那就是最大元，极小元同理
极大元、极小元、最大元、最小元
设span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\
上界和下界
设span class=\"equation-text\" data-index=\"0\" data-equation=\
最大上界和最小下界
序关系
等价关系与序关系
F:x→y或x→y
设F为二元关系，若都存在唯一的，使xFy成立，则称F为函数，也称为映射。从x到y的函数F记为
函数F要对定义域中的所有元素都有定义，而不能只对某个真子集进行定义。关系R可能只对定义域中的若干元素有定义
函数F和关系R的差异
设X、Y为集合，所有从X到Y的函数构成的集合记作Y^X
若X = ∅且Y = ∅，则Y^X = {∅}
若X ＝ ∅且Y ≠ ∅，则Y^X = {∅}
若X ≠ ∅且Y ＝ ∅，则Y^X = ∅
若X和Y均不为空集，设|X| = m，|Y| = n，|Y^X| = n^m
Y上X
一个x有唯一的y与之对应，y允许没有x
函数f称一对一，当且仅当对于f定义域中的所有x和y，f(x) = f(y)蕴含着x = y。一对一函数也被称为单射函数或入射函数
单射
Y中的每一个y至少要有一个x对应
给定函数f:X→Y，当且仅当对Y中所有的y，都有X中的x使用f(x) = y，则函数f称为满射或映上
满射
双射
当且仅当函数是双射函数时才存在反函数，所以双射函数也称为可逆的，它的反函数也称为逆函数
反函数
函数的概念
如果f的值域不是g的定义域的子集，则无法定义
函数复合不满足交换律
若f和g都是满射的，则复合函数f·g也是满射的
若f和g都是单射的，则复合函数f·g也是单射的
若f和g都是双射的，则复合函数f·g也是双射的
复合函数
函数
等价关系证明P94
P96
P98
序关系证明
关系证明例题
第5章 关系和函数
设A为任意集合，一个从A^n到B的映射，称为集合A上的一个n元运算。如果B是A的子集，则称该n元运算是封闭的
运算封闭
代数系统
运算表
设A为任意非空集合，*和span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"\\circ\
a*b 属于A，*关于集合A是封闭的
a*(b*c)=(a*b)*c，是满足结合律的
a*b=b*a，是满足交换律的
a*a=a，在A上是满足幂等律的
a(b*c) = (ab)*(ac)和(b*c)a = (ba)*(ca)成立，则称运算对*是可分配的，或称运算对*满足分配律
若和*均满足交换律，而且有：a(a*b) = a和a*(a) = a，则称运算和*是可吸收的
运算重要性质
设*为集合A上二元运算，若A存在el，使用A中任意的x都有el*x = x，则称el是A中关于*运算的左幺元
若A存在er，使用A中任意的x都有x*er = x，则称er是A中关于*运算的右幺元
若A存在e，e即是左幺元，又是右幺元，则称e是A中关于*运算的幺元，又称为单位元。e*x = x*e = x
幺元可能不存在，也可能不唯一
幺元
设*为集合A上二元运算，若A存在Ol，使用A中任意的x都有Ol*x = 0，则称Ol是A中关于*运算的左零元
若A存在Or，使用A中任意的x都有x*Or = 0，则称Or是A中关于*运算的右零元
若A存在O，O即是左零元，又是右零元，则称O是A中关于*运算的零元。O*x = x*O = 0
零元
若对A中某个元素a，存在A的一个元素b，使得a*b = e，则称b为a的右逆元
若一个元素b，既是a的左逆元，又是a的右逆元。则称b是a的一个逆元，记作
逆元
代数系统中存在幺元，则该幺元是所有元素的幺元。零元同理，故幺元和零元具有一般性
逆元具有个体性，有的元素可能存在逆元，有的元素可能不存在逆元。即使两个元素都有逆元存在，也不能保证两个逆元是相同的
幺元和零元和逆元
左右逆元唯一定理
半群
若半群中存在一个幺元，则称该半群为独异点或含幺元半群
独异点
半群和独异点
群满足独异点三个条件，封闭性、结合律、存在幺元，同时每个元素都有逆元
群
平凡群
Abel群
元素的阶
幂等元
G的阶有限时，称为有限循环群，生成元是a。否则称为无限循环群，生成元是a^-1
生成元可能不止一个，因此生成元也不唯一
循环群
整数环Z不是域，有理数环Q和实数环R是域
群与半群
运算*对于运算+是可分配的
为了表示上的方便，环的加法幺元记作0，乘法则记作1，换种任一元素啊，加法逆元称为负元，记为-a。若存在乘法逆元，称为逆元，记a^-1
P121
环的元素的加法和乘法一样满足交换律、结合律、分配率
环
零因子
交换环
含幺元环
无零因子环
环既是交换环、含幺元环、无零因子环，则称为整环
整环
环和域
第6章 代数系统的一般概念
全序集是格，偏序集不一定是
格的交运算和并运算
对偶
交换律
幂等律:a∨a = a，a∧a = a
格
格的运算满足交换律、幂等律、结合律、吸收律，但不是所有格都满足分配律，满足分配律的格是一种特殊的格，对于补元素也是一样，并不是所有格元素都存在补元素
钻石格和五角格不是分配格
小于五元的格或者任意一条链都是分配格
分配格
都有a≤x，则称a为格的全下界
都有x≤b，则称b为格的全上界
全下界就是偏序集的最小元，记为0
全上界就是偏序集的最大元，记为1
全上界和全下界
格font color=\"#e57373\
有界格
若b是a的补元，则a也是b的补元，a和b互为补元，简称互补
任何有界格中，全上界1和全下界0总是互补的。其他元素可能存在补元，也可能不存在补元。如果存在补元，可能不唯一也可能多个。
补元
有补格
分配格与有补格
如果一个格是有补分配格，则称它为布尔格或布尔代数
在分配格中，若一个元素存在补元，则补元是唯一的。故在布尔代数中，每个补元都存在唯一的补元
分配律
布尔格
布尔代数
格的基本概念
第7章 格和布尔代数
图的表示
一条边也没有的图
零图
只有一个顶点的图叫平凡图，平凡图必是零图
平凡图
若|V| = n(n > 0)，称为n阶图
n阶图
无向图
deg(v) = 0称孤立点
deg(v) = 1称悬挂点
若v有环，计算deg(v)增加2
顶点度数总和等于边数的两倍
对任意的图G，奇顶点必有偶数个
以顶点v为起点的有向边的个数称为v的出度，记为dev^+(v)
以顶点v为终点的有向边的个数称为v的入度，记为dev^-(v)
顶点的出度和入度之和就是该顶点的度数，即deg(v) = deg(v)^+(v)+deg^-(v)
在有向图中，所有顶点的入度之和等于出度
有向图
图最大的度记
图最小的度记
度
n阶有向完全图有n(n-1)条边
n阶无向完全图有边
边
生成子图
图的基本概念
若无向图中每个顶点的度数至少为2，这图G包含一条初级回路
在无向图中，顶点u和v之间若存在通路，则称顶点u和v是连通的。若图G中任何两个不同顶点都是连通的，则称G为连通图，否则称G为不连通图
对于连通图，它极大连通子图即是图的本身
连通图
在简单有向图G中，任何一对顶点间至少有一个顶点到另一个订单是可达的，则称这个图是单侧连通的
单测连通
如果对于图G中任何一对顶点，两者之间是相互可达，则称这个图是强连通的
强连通
在图G中，略去边的方向，将它看成无向图后，图是连通的，则该图称为弱连通
弱连通
割点
割点集
割边
割边集
无向连通图的点割集V1和边割集E1，则子图G-E1所含得连通分量个数必须为2，子图G-V1所含的连通分量个数不确定
图的连通性
无向图的邻接矩阵是对称矩阵，有向图这个结论不成立
无向图中，非0元素即顶点的度
有向图中，行中非零元素为顶点的出度，列中非零的元素为顶点的入度
邻接矩阵
M^k是简单图邻接矩阵顶点之间长度为k的的通路数目
通路数目
可达性矩阵
第8章 图
图G中每条边一次且仅一次的通路，称为欧拉通路或欧拉路。若欧拉通路为回路，则称为欧拉回路，具有欧拉回路的图叫欧拉图
无向连通图G是欧拉图的充分必要条件是G是连通的且无奇点
无向连通图G是欧拉通路充分必要条件是连通且恰有两个奇点，从一个奇点出发到另一个奇点结束
欧拉图
无向图G中，若存在一条路L，经过图的每一个顶点一次且仅一次，这称L为哈密顿路，简称H-路；若存在一条回路G，经过图中每个顶点一次且仅一次，C称作哈密顿回路，简称H-回路。具有哈密顿回路的图称作哈密顿图，简称H-图
含有度为1的顶点的图比不是哈密顿图
G是有n个顶点的简单图，如果G中每一对顶点度数之和大于等于n-1，则G中存在一条哈密顿路
G是有n个顶点的简单图，如果G中每一对顶点度数之和大于等于n，则在G中存在哈密顿回路
上述是哈密顿图的充分条件，但不是必要条件，即使不满足，图也有可能是哈密顿图
哈密顿图
欧拉图与哈密顿图
若一个图G能画在平面S上，且使G的边仅在端点处相交，则称图G可嵌入平面S，G称为可平面图，简称平面图
设G是一个连通平面图，G的边将G所在平面划分成了若干个区域，每个区域称为G的一个面，其中面积无限的区域称为无限面或外部面。面积有限的区域称为有限面或内部面。包围每个面的所有边组成的回路称为该面的边界，边界的长度称为该面的次数。若该区域记为R，则次数可记为deg(R)
设连通平面图G，面的次数之和等于其边数的两倍
n-m+r = 2
连通平面图G有n个顶点，m条边，r个面。有欧拉公式
欧拉公式
设连通平面图G，有v个顶点m条边，若v≥3，则m≤3v-6，可以用于判定某些图是非平面图
设连通平面图G，有v个顶点m条边，若v≥3且没有长度为3的回路，则m≤2v-4
平面图
树的节点数是n，则树的边是n-1
度为1的节点是叶子节点
破圈法求生成树
树的层从0开始，根结点是位于第0层
树的高从1开始算
设T是有n个节点的完全二叉树，则T有（n+1）/2个叶子结点
二叉树
树及其遍历
第9章 图的应用
自考离散数学
0 条评论
回复 删除
下一页
