《离散数学》：学习笔记.pdf

《《离散数学》：学习笔记.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《离散数学》：学习笔记我做学习笔记的目的是将复杂的概念及公式压缩成几页并以图文并茂的形式表示出来，如此会便于去记忆理解，这样即使在若干年重回该领域研究时也可以快速掌握知识点。但光靠这是不行的，有扎实的基础知识还需要反复的练习做题，希望同学能好好努力，争取拿到一个很高的分数。第七章图的基本概念Aa,a,Bb,b则A&a,b,a,b,a,b, a,b无序积n

2、V

3、VGv,v,…,v,GV,Eev,vdv2m握手定理EGe

4、,e,…,e,顶点集边m

5、E

6、边顶点(或结点)端点度数：V做为边端点的次数概念：：：：关联e环v1、有限图：即V、E都是有穷集合e2、n阶图：顶点数为n

7、V

8、ve.3、零图：边E#e/ve0v4、平凡图：E#且

9、V

10、10/e15、多重图：含平行边相邻6、简单图：不含平行边和环孤立点v平行边17、n阶无向完全图K：所有v与v相邻dv4dv/1dv4dv018、子图G&,母图G：G'(G V&(V且E&(Edv132m246129、真子图：G'(G V&

11、(V且E&)E0101111)、j列元素之和为210、生成子图：G'(GV'V?211000C2)、i行元素之和为dvMG>001110B3)、所有元素之和为2m11、导出子图：与子集V关联的所有边构成的图>B>000001B4)、孤立点元素都为0与子集E关联的所有顶点构成的图=000000A5)、列jj&列平行边12、补图G*：

12、V

13、不变，两简单图互成完全图K13、连通图：任意两顶点连通ae1414、连通分支p G：根据连通关系R划分出若干个等价的b5子集V构成的导出子图d23cG6G

14、同构的，对应关系：a71,b72,c73,d74,e75PG1GPGFV'2PGFE'2(两两)连通当v;v,回路15、点割集/边割集：删掉顶点/边，使形成非连通图点割集只为1称割点Γv;eve…e

15、)生成树T：无向连通图G的生成子图（且为树）树枝：T的边v/v0基本公式：弦：除了树枝外的边tF1余树：所有弦集合的导出子图snFtv.vIrF1基本回路：T+1根弦形成回路。所有回路称系统仅正则树能用基本割集：即树枝与其对应弦。所有割集称系统dv2m根树：1个顶点入度为0，其余顶点入度为1的树mnF1分支点s：dvH2(包括树根，内点)Q树根：入度为0的顶点WTωlv求总传输位数内点：入度为1，出度>0的顶点(树)权层数(码长)树叶t：入度为1，出度为0的顶点带权(概率

16、)层数l：从树根到任意顶点的长度例：badcedbecbecdeddcee树高：最大的层数根层19路家族树：父亲、儿子、兄弟、祖先、后代(分枝)权子孙之和r元树：最多有r个儿子一层811r元正则树：每个爸爸都有r个儿子WT143R343R442R542R64242r元完全正则树：所有树叶层数相同二层4456前缀码：左树枝标0，左树枝标1cde最优前缀码：即最优r元树的前缀码三层带权(概率)13码字：前缀码从树顶到树叶组成的码字ab等长码：位数相同的码字前缀码：000传a，001传b，01传c，10传d，11

17、传eHuffman算法：(二元树)1、以2个最小带权为树叶连成分支，分支权为和2、分支权与其它树叶之间选最小权继续连成分支3、重复2，直到分支权和树叶用完