离散数学及其应用重要名词中英对应以及重要概念解释与举例Word文档下载推荐.docx
- 文档编号:4492735
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:13
- 大小:22.38KB
离散数学及其应用重要名词中英对应以及重要概念解释与举例Word文档下载推荐.docx
《离散数学及其应用重要名词中英对应以及重要概念解释与举例Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《离散数学及其应用重要名词中英对应以及重要概念解释与举例Word文档下载推荐.docx(13页珍藏版)》请在冰点文库上搜索。
yP(x,y)Û
"
y"
xP(x,y)
$x$yP(x,y)Û
$y$xP(x,y)
yP(x,y)Þ
$y"
xP(x,y)
y"
xP(x,y)Þ
$x"
yP(x,y)
$x"
y$xP(x,y)
$y"
x$yP(x,y)
x$yP(x,y)Þ
y$xP(x,y)Þ
$x$yP(x,y)
Prenexnormalform(PNF前束范式):
所有量词变换到最前面,否定变换到后面。
1.5RulesofInference(推理规则)
ValidArgumentsinPropositionnalLogic(命题逻辑中的正确论点)
Premises(前提)——allbutthefinalpropositionintheargument
Conclusion(结论)
RulesofInferenceforPropositionnalLogic
Page66~67,证明方法及过程示范
Resolution(归结):
((p∨q)∧(┐p∨r))→(q∨r)合取,若两子句有互补文字,则可消去。
Fallacies(谬论)
RulesofInferenceforQuantifiedStatements
Universalinstantiation(全称量词实例化)
Universalgeneralization(全称量词一般化)
Existentialinstantiation(存在量词实例化)
Existentialgeneralization(存在量词一般化)Page70
以上四点,其实就是一般和特殊之间的转换。
名字是骗人的。
1.6IntroductiontoProofs
Directproof:
证明p->
q
ProofbyContraposition:
对位证明,通过证明其逆反命题来证明原命题
VacuousandTrivialProofs
ProofbyContradiction:
反证法
1.7ProofMethodsandStrategy
2BasicStructures:
Sets,Functions,SequencesandSums(集合、函数、序列与和)
Cardinality集合的势,即其中元素的个数。
PowerSet:
thesetofallsubsetsofthesetS.原集合的所有子集组成的集合。
Cartesianproduct:
笛卡尔积、直积,A×
B={(a,b)|a∈A∧b∈B}
Function
Onto:
满射
Injective=One-to-One:
单射
Bijection:
双射=单射加满射
3~7略
8Relations(关系)
8.1relationsandTheirProperties
Reflecxive自反:
if(a,a)∈Rforeveryelementa∈A都有环
Irreflexive反自反:
一个环也没有
Symmetric对称:
if(b,a)∈Rwhenever(a,b)∈R,foralla,b.有从a到b,必有从b到a。
Antisymmetric反对称:
除非a=b,有从a到b,必无从b到a。
Asymmetric不对称:
有从a到b,必无从b到a。
Transitive传递:
a到b,b到c,则有a到c。
CombiningRelations(复合关系):
S·
R(空心圆圈)
分配率:
并集满足等价,交集满足包含
(1)Fo(GÈ
H)=FoGÈ
FoH
(2)Fo(GÇ
H)Í
FoGÇ
FoH
(3)(GÈ
H)oF=(GoF)È
(HoF)
(4)(GÇ
H)oFÍ
GoFÇ
HoF
Rn+1=RnoR
TherelationRonasetAistransitiveifandonlyifRn属于Rforn=1,2,3……
8.2n-aryRelationsandTheirApplications
8.3RepresentingRelations(表示关系)
RepresentingRelationsUsingMatrices——Zero-OneMatrix
Reflexive自反:
主对角线上的数都为1。
Symmetric对称:
以主对角线为轴对称。
RepresentingRelationsUsingDigraphs(有向图)
8.4ClosuresofRelations(关系的闭包)
闭包是指在原关系的基础上添加最少的有序对,构成满足一种特性的新的关系。
自反闭包、对称闭包和传递闭包。
Reflexiveclosure(自反闭包):
在所有元素上加环。
Symmetricclosure(对称闭包):
对于所有的(a,b),添加(b,a)。
TransitiveClosure(传递闭包):
⊙:
先合取再析取
M(R*)=M(R)∨(M(R)∧M(R))∨(M(R)∧M(R)∧M(R))……直到第n项
*Warshall’sAlgorithm沃舍尔算法
8.5EquivalenceRelations
ArelationonasetAiscalledanequivalencerelationifitisreflexive,symmetric,andtransitive.
等价=自反+对称+传递
A的全域关系和恒等关系都是等价关系,空关系不具自反性。
²
全域关系:
全部有序偶。
恒等关系:
对称且反对称,有且只能有环。
Equivalent等价量
EquivalenceClasses等价类
集合中具有等价关系的一个子集。
集合中与一个元素具有等价关系的全部元素构成的子集。
Partitions分割
非空、无交集、其并集为全集。
LetRbeanequivalencerelationonasetS.ThentheequivalenceclassesofRformapartitionofS.Conversely,givenapartition{Ai|i∈I}ofthesetS,thereisanequivalencerelationRthathasthesetsAi,i∈I,asitsequivalenceclasses.
8.6PartialOrderings偏序关系
ArelationRonasetSiscalledapartialorderingorpartialorderifitisreflexive,antisymmetric,andtransitive.AsetStogetherwithapartialorderingRiscalledapartiallyorderedset,orposet,andisdenotedby(S,R).
自反+反对称+传递
Comparable可比:
Theelementsaandbofaposet(S,*)arecalledcomparableifeithera*borb*a.
Totallyorderedorlinearlyordered(全序或线序):
没两个元素都是可比的。
这样的集合又称作链(chain)
LexicographicOrder(字典序)Page569
Well-ordered(良序):
Achain(A,R)iswell-ordered良序iffeverynonemptysubsetofAhasaleastelement.
HasseDiagrams(哈斯图)
ToconstructaHassediagram:
1)Constructadigraphrepresentationoftheposet(A,R)sothatallarcspointup(excepttheloops).(所有的弧指向上)
2)Eliminateallloops(删除环)
3)Eliminateallarcsthatareredundantbecauseoftransitivity(删除由于传递而多余的弧)
4)Eliminatethearrowsattheendsofarcssinceeverythingpointsup.(删除箭头)
MaximalandMinimalElements
GreatandLeastElement(唯一)
UpperandLowerBounds
LeastUpperandGreatestLowerBound(唯一)Page572~574
Lattices格
对于一个偏序集A,若其中任意两个元素a、b,都有最大下界和最小上界,则称这样的偏序集为格。
TopologicalSorting拓扑排序
Notonlyonepossibleorder.可能有多种排序方式。
9Graphs(图论)
9.1GraphsandGraphModels
Type
Edges
MultipleEdgesAllowed
LoopsAllowed
Simplegraph简单图
Undirected
No
Multigraph多重图
Yes
Pseudograph伪图
Simpledirectedgraph简单有向图
Directed
Directedmultigraph多重有向图
Mixedgraph混合图
Both
简单图+多重边——>
重图,重图+环——>
伪图
GraphModels
Page592~595
9.2GraphTerminologyandSpecialTypesofGraphs(图论术语和特殊图)
AdjacentandIncident(连接和关联):
一条边相连的两点为连接,该边与这两点关联。
这两点称作端点(endpoints).
Degree:
度,与一个点相关联的边数,deg(v).
IsolatedVertex:
孤立点,dev(v)=0.
PendantVertex:
悬挂点,dev(v)=1.
TheHandshakingTheorem(握手定理)
LetG=(V,E)beanundirectedgraphwitheedges.Then2e=∑deg(v).
度数是边数的两倍。
Anundirectedgraphhasanevennumberofverticesofodddegree.奇数度顶点有偶数个。
In-degree(入度):
deg-(v),thenumberofedgeswithvastheirterminalvertex(终点).
Out-degree(出度):
deg+(v),thenumberofedgeswithvastheirinitialvertex(起点).
LetG=(V,E)beagraphwithdirectededges.Then∑deg-(v)=∑deg+(v)=|E|.
SomeSpecialSimpleGraphs
CompleteGraphs(全图)istheSimplegraphthatcontainsexactlyoneedgebetweeneachpairofdistinctvertices.Kn顶点数:
n,边数:
n(n+1)/2.
Cycles(圈图),Cn顶点数n,边数n.
Wheels(轮图),Wn顶点数n+1,边数2n.
Cube(方图),Qn顶点数2n,边数2n-1*n
BipartiteGraphs(偶图,二分图)
可通过着色法判断,有边相连的两点颜色不同,总共只有两种颜色。
CompleteBipartiteGraphs(完全二分图)
NewGraphsfromOld——Subgraph(子图)
生成子图SpanningSubgraph:
与原图顶点相同,边是真子集。
导出子图:
顶点是原图顶点的子集,而边为与它们相连的原图的所有边。
Theunionofthesimplegraphs:
所有简单图的边与顶点的并集所得到的简单图。
9.3RepresentingGraphsandGraphIsomorphism(图的表示与同构)
AdjacencyListsandMatrices(邻接表与邻接矩阵)Page612点与点的关系
对于有向图的邻接矩阵,行数字相加为该点出度,列数字相加为该点入度,所有数字相加为度数的一半,即边数。
IncidenceMatrices(关联矩阵)点与边的关系。
IsomorphismofGraphs(图的同构)
必要条件:
1,相同顶点数
2,相同的边数
3,对应顶点的度数相同
4,子图相同
5,路径相同
使用矩阵判断两图是否同构:
邻接矩阵:
任意交换行列,调整至两矩阵相同,即为同构。
关联矩阵:
行与对应列同时做相同变动,调整至两矩阵相同,为同构。
9.4Connectivity连通
Paths(路径)——有向图路径和无向图路径
Circuit(回路),Traverse(遍历)
简单路径:
每条边只出现一次。
初级路径:
每个点只出现一次。
ConnectednessinUndirectedGraphs(无向图的连通)
Anundirectedgraphiscalledconnectedifthereisapathbetweeneverypairofdistinctverticesofthegraph.
Connectedcomponent连通分支:
MaximalconnectedsubgraphofG.
Cutvertices(割点)/cutedge(割边、或bridge桥):
扔掉它们就会产生更多连通分支的东西。
ConnectednessinDirectedGraphs
Stronglyconnected强连通——路径a到b和b到a同时存在。
Weaklyconnected弱连通——两点之间有线存在(underlyingundirectedgraph看作无向图路径即可)。
强连通一定是弱连通。
CountingPathsbetweenVertices
使用该图的邻接矩阵A,长度为n,就计算An。
对应行乘以对应列。
The(i,j)thentryofAr+1equals:
bi1a1j+bi2a2j+bi3a3j+…+binanj.
9.5EulerandHamiltonPaths
EulerPathsandCircuits:
欧拉路径、回路,周游原图的每一条边。
HamiltonPathsandCircuits:
哈密顿路径、回路,周游每个顶点。
一个连通重图具有欧拉回路,当且仅当它的每个顶点都是偶数度。
一个连通重图具有欧拉路径(称为半欧拉图),当且仅当它有且只有两个奇度数顶点。
对于一个有向图而言:
欧拉回路的条件:
1,每个顶点都有偶数度。
2,出度等于入度。
欧拉路径的条件:
1,仅有两个顶点有奇数度。
2,对于偶度数顶点,出度等于入度。
3,对于奇数度顶点,出度和等于入度和。
HamiltonPathsandCircuits
充分条件:
Ore’sTheorem:
IfGisasimplegraphwithnverticeswithn≥3suchthatdeg(u)+deg(v)≥nforeverypairofnonadjacentverticesuandvinG,thenGhasaHamiltoncircuit.任意两顶点度数之和不小于总的顶点数。
Dirac’sTheorem:
IfGisasimplegraphwithnverticeswithn≥3suchthatthedegreeofeveryvertexisatleastn/2,thenGhasaHamiltoncircuit.每一点的度数都不小于总顶点数的一半。
IfGisaHamiltoniangraph,thenforeverynonemptypropersetSofverticesofG,K(G-S)≤|S|.删去任意顶点后的连通分支数不大于删去的顶点数。
9.6Shortest-PathProblems
Weightedgraphs(带权图)——边带权和顶点带权。
AShortest-PathAlgorithm
TheTravelingSalesmanProblem
9.7PlanarGraphs
定义:
可以画在一个平面内,而没有任意两条边交叉的图。
最小非平面图:
删去一条边可以变成平面图的非平面图。
最大平面图:
任意加一条边都会变成非平面图的平面图。
Euler’sFormula平面图欧拉公式
Region=edge-vertice+2(connectedplanarsimplegraph平面连通简单图)
所有面的度数之和等于边数的两倍。
区域度数计算:
围成该区域的边数,悬挂边记作两度。
Corollary1:
IfGisaconnectedplanarsimplegraphwitheedgesandvvertices,wherev≥3,thene≤3v-6.
Corollary2:
IfGisaconnectedplanarsimplegraph,thenGhasavertexofdegreenotexceedingfive.
Kuratowski’sTheorem(库拉图斯基/苦辣兔斯基定理)
Elementarysubdivision(初等分割)&
Homeomorphic(同胚)
增加新的点只能是有两度的点,删点也只能删两度的点。
‘K’Theorem:
AgraphisnonplanarifandonlyifitcontainsasubgraphhomoeomorphictoK3,3orK5.
9.8GraphColoring
DualGraph——对偶图:
指原图中的每个封闭区域对应一个点,每条边对应一条边(连接两顶点,与原来的边相交)而形成的新图。
环对应悬挂边。
同构的图,对偶图不一定同构。
ChromaticNumber(色数):
为一个图上色所需的最少颜色数。
TheFourColorTheorem:
Thechromaticnumberofaplanargraphisnogreaterthanfour.
10Trees(树)
10.1IntroductiontoTrees
Definition:
atreeisaconnectedundirectedgraphwithnosimplecircuits.
Anundirectedgraphisatreeifandonlyifthereisauniquesimplepathbetweenanytwoofitsvertices.(任意两点之间只有一条通路)
Arootedtree(根树)isatre
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 及其 应用 重要 名词 对应 以及 概念 解释 举例