一所用教材.doc

《离散数学2》考前辅导资料 一： 所用教材 教材名称：离散数学 编 著 者：王双 ?刘福荣 ?主编 ?????刘克安 ?主审 出 版 社：哈尔滨工业大学出版社 1．理解图的概念：结点、边、有向图，无向图、简单图、完全图、结点的度数、边的重数和平行边等.理解握手定理． 图是一个有序对V，E，V是结点集，E是联结结点的边的集合． 掌握无向边与无向图，有向边与有向图，混合图，零图，平凡图、自回路(环)，无向平行边，有向平行边等概念． 简单图，不含平行边和环(自回路)的图、 在无向图中，与结点v((V)关联的边数为结点度数(v)；在有向图中，以v((V)为终点的边的条数为入度－(v)，以v((V)为起点的边的条数为出度＋(v)，deg(v)=deg+(v) +deg－(v)． 无向完全图Kn以其边数；有向完全图以其边数． 了解子图、真子图、补图和生成子图的概念． 生成子图——设图G＝V, E，若E((E，则图V, E(是V, E的生成子图． 知道图的同构概念，更应知道图同构的必要条件，用其判断图不同构. 重要定理： (1) 握手定理 设G=V，E，有； (2) 在有向图D＝V, E中，； (3) 奇数度结点的个数为偶数个． 2．了解通路与回路概念：通路(简单通路、基本通路和复杂通路)，回路(简单回路、基本回路和复杂回路)．会求通路和回路的长度．基本通路(回路)必是简单通路(回路)． 了解无向图的连通性，会求无向图的连通分支．了解点割集、边割集、割点、割边等概念．了解有向图的强连通强性；会判别其类型． 设图G＝V，E，结点与边的交替序列为通路．通路中边的数目就是通路的长度．起点和终点重合的通路为回路．边不重复的通路(回路)是简单通路(回路)；结点不重复的通路(回路)是基本通路(回路). 无向图G中，结点u, v存在通路，u, v是连通的，G中任意结点u, v连通，G是连通图．P(G)表示图G连通分支的个数． 在无向图中，结点集V((V，使得P(G－V()P(G)，而任意V((V(,有P（G－V(）＝P(G)，V(为点割集. 若V(是单元集，该结点v叫割点；边集E((E，使得P(G－V()P(G)，而任意E((E(，有P（G－E(）＝P(G)，E(为边割集．若E(是单元集，该边e叫割边(桥)． 要知强连通单侧连通弱连通 第2章 几种特殊图 复习要点 1．理解欧拉通路(回路)、欧拉图的概念，掌握欧拉图的判别方法． 通过连通图G的每条边一次且仅一次的通路(回路)是欧拉通路(回路)．存在欧拉回路的图是欧拉图. 欧拉回路要求边不能重复，结点可以重复．笔不离开纸，不重复地走完所有的边，走过所有结点，就是所谓的一笔画． 欧拉图或通路的判定定理 (1) 无向连通图G是欧拉图(G不含奇数度结点(即G的所有结点为偶数度)； (2) 非平凡连通图G含有欧拉通路(G最多有两个奇数度的结点； (3) 连通有向图D含有有向欧拉回路(D中每个结点的入度＝出度． 连通有向图D含有有向欧拉通路(D中除两个结点外，其余每个结点的入度＝出度，且此两点满足deg－(u)－deg＋(v)＝(1． 2．理解汉密尔顿通路(回路)、汉密尔顿图的概念，会做简单判断． 通过连通图G的每个结点一次，且仅一次的通路(回路)，是汉密尔顿通路(回路)．存在汉密尔顿回路的图是汉密尔顿图. 汉密尔顿图的充分条件和必要条件 (1) 在无向简单图G=V，E中，(V((3，任意不同结点，则G是汉密尔顿图．(充分条件) (2) 有向完全图D＝V，E, 若，则图D是汉密尔顿图. (充分条件) (3) 设无向图G=V，E，任意V1(V，则W(G－V1)((V1((必要条件) 若此条件不满足，即存在V1(V，使得P(G－V!)(V1(,则G一定不是图(非图的充分条件)等概念． 重要结论：(1)平面图． (2)欧拉公式：平面图 面数为r，则(结点数与面数之和＝边数＋2)． 会用定义判定一个图是不是平面图． 4．理解平面图与对偶图的关系、对偶图在图着色中的作用，掌握求对偶图的方法． 给定平面图G＝〈V，E〉，它有面F1，F2，…，Fn，若有图G*＝〈V*，E*〉满足下述条件： ⑴对于图G的任一个面Fi，内部有且仅有一个结点vi*∈V*⑵对于图G的面Fi，Fj的公共边ek，存在且仅存在一条边ek*∈E*，使ek*＝(vi*，vj*)，且ek*和ek相交 ⑶当且仅当ek只是一个面Fi的边界时，vi*存在一个环ek*和ek相交则图G*是图G的对偶图． G*是G的对偶图，则G也是G*的对偶图．一个连通平面图的对偶图也必是平面图． 5．掌握图论中常用的证明方法． 重点：欧拉图和哈密顿图、平面图的基本概念及判别． 第3章 树及其应用 复习要点 1．了解树、树