离散数学PPT教学图论.ppt

欢 迎 进 入 第 11 章 图 论,本章重难点:,重点了解图的各种概念，理解并掌握握手定理的应用以及各种矩阵的表示。 难点是图的最短路径和关键路径的求法。,第11章 图 论,第一节 图的基本概念 第二节 图的矩阵表示 第三节 生成树、最短路径和关键路径 第四节 特殊图（欧拉图和哈密顿图等） 第五节 树、二叉树和哈夫曼树,一 、图的基本概念,图的定义： 图（graph）G由三个部分所组成： （1）非空集合V(G)称为图G的结点集，其成员称为节点或顶点（nodes or vertices） （2）集合 E(G)，称为图G的边集，其成员称为边(edges)。 （3）函数G：E(G)(V(G)，V(G)，称为边与顶点的关联映射。 度的相关定义： 在任何图中，结点v的度（degree）d(v)是v所关联边的数目。 而在有向图中，结点v的出度（out-degree）d+(v)是v作为有向边起点的数目，v的入度（in-degree）d-(v)是v作为有向边终点的数目，这时结点v的度是它的出度与入度的和；结点v的环使其度增加2。,一 、图的基本概念,连通图、强连通图、弱连通图 若无向图中的任意两个顶点都相互可达，则称无向图G是连通的（connected）； 若有向图G的任何两个顶点都是相互可达的，则称有向图G是强连通的； 如果G的任何两个顶点都是相互可达的，称有向图G是单向连通的； 如果G的任何两个顶点中，至少从一个顶点到另一个顶点是可达的，称有向图G是弱连通的。,一 、图的基本概念,邻接和关联 无向图和有向图 零图和平凡图 简单图 完全图（无向完全图和有向完全图） 有环图,一 、图的基本概念,有限图和无限图 设图G为 （l）当V和E为有限集时，称G为有限图，否则称G为无限图。 （2）当G为单射时，称G为单图；当G为非单射时，称G为重图，又称满足(e1) = (e2)的不同边e1，e2，为重边,或平行边。 正则图 各顶点的度均相同的图称为正则图（regular graph）。 各顶点度均为k的正则图称为k-正则图。 同构图,一 、图的基本概念,子图、真子图、生成子图,设图G1，G2， 称G1为G2的子图（subgraph）； 如果V1V2，E1E2，1 2，称G1为G2的真子图； 如果G1是G2的子图，且G1 G2，称G1为G2的生成子图 （spanning subgraph）；如果G1是G2的子图，且V1 = V2。,握手定理的证明,每个图中，节点度数的总和等于边的2倍。 证明： 因为每条边必关联两个节点，而一 条边给予关联的每个节点的度数为1，因此在一个图中，节点度数的总和等于边数的2倍。,握手定理的运用,定理1：在任何图中，度数为奇数的节点个数必定是偶数个。 证明： （自己思考！） 定理2：在任何有向图中，所有节点入度之和等于所有节点的出度之和。 证明： 因为每一条有向边必对应一个入度及一个出度，所以有向图中各节点入度之和等于边数，各节点的出度之和也等于边数。,例：设图G为下列情况： (1) 16条边，每个顶点都是2度； (2) 21条边，3个4度顶点，其余均为度顶点； (3) 24条边，各节点的度数均相同； 试求每个图有几个节点？,握手定理的应用,解答：利用握手定理，设图有x个节点，则 x=16*2 x=16 21*2=12+3*x x=10 故图中有个节点 (3) x*m=24*2,二、图的矩阵表示,关联矩阵 2. 邻接矩阵 3. 可达矩阵 4. 布尔矩阵 5. 代价矩阵,二、图的矩阵表示,关联矩阵 无向图的关联矩阵 - 以节点数为行,边数为列.若有环,则关联数为2,无关联则为0.每行之和为该顶点的度,列之和一定为2. 有向图的关联矩阵 - 以节点数为行,边数为列.节点与边无关系,为0,有关系,则起点为1,终点为-1;列之和一定为0,每行绝对值之和等于该节点的度数;其中1的个数为该节点的出度,-1的个数为对应节点的入度;所有元素的和为0,1的个数等于-1的个数,都等于边数m.,二、图的矩阵表示,2. 邻接矩阵 无向图的邻接矩阵 - 行和列均为节点的数目;是个对称距阵,行之和等于列之和,均等于该顶点的度;主对角线都为0,除非有环才为1;边的数目m为1的数目总和的一半. 有向图的邻接矩阵 - 行和列均为节点的数目;不是对称距阵,行之和等于该顶点的出度,列之和等于该顶点的入度;主对角线都为0,除非有环才为1;边的数目m为非0的数目的总和.,二、图的矩阵表示,可达矩阵 - 行和列均为节点的数目;节点和节点之间若至少存在一条路则为1,不存在路则为0. 4.布尔矩阵 - 由可达距阵转变,把非0的数值均改为1即可. 代价矩阵 - 若邻接距阵元素为1的以权值表示,距阵元素为0的则以表示.,三、生成树、最短路径和关键路径,生成树定义 1、深度优先遍历 2、广度优先遍历 最小生成树 构造最小生成树的三种方法： 1、Kruskal算法 2、管梅谷算法 3、Prim算法,第四节 欧拉图和哈密顿图,欧拉图的由来： 哥尼斯堡七桥问题哥尼斯堡城市有一条横贯全城的普雷格尔河，河中有两个小岛，城的各部分用七座桥连接，每逢假日，城中居民进行环城逛游，这样就产生了一个问题，能不能设计一次遍游，使得从某地出发对每座跨河桥只走一次，而在遍历了七桥之后却又能回到原地。,第四节 欧拉图和哈密顿图,通过图中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路（欧拉路）。通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。 只有具有欧拉回路的图才能称为欧拉图。 具有欧拉通路而无欧拉回路的图称为半欧拉图。,欧拉在1736年的论文中提出了一条简单准则，确定了哥尼斯堡七桥问题是不能解的。 定理1：无向图是欧拉图当且仅当G是连通图且没有奇度顶点。 定理2：无向图是半欧拉图当且仅当G是连通的且恰有两个奇度顶点。,第四节 欧拉图和哈密顿图,定理3：有向图D是欧拉图当且仅当D是强连通的且每个顶点的 入度等于出度。 定理4：有向图D是半欧拉图当且仅当D是单向连通的且恰有两个奇度顶点，其中一个顶点的入度比出度大1，另一个顶点出度比入度大1，而其余顶点的 入度等于出度。,第四节 欧拉图和哈密顿图,欧拉图的应用： 一笔画问题： 一个图能一笔画出是指从图某一点出发，不间断地画完整个图，最后回到起点。,第四节 欧拉图和哈密顿图,哈密顿图的由来周游世界问题： 一个数学游戏，能不能在一个十二面体中找到一条回路，使它含有这个图的所有结点？把每个结点看成一个城市，连接两个结点的边看成是交通线，也即能否找到旅游线路，沿着交通线经过每个城市恰好一次再回到原来的出发地？,第四节 欧拉图和哈密顿图,经过图中所有顶点一次且仅一次的通路称为哈密顿通路（哈密顿路）。通过图中所有顶点一次且仅一次的回路称为哈密顿回路。 只有具有哈密顿回路的图才能称为哈密顿图。 具有哈密顿通路而无哈密顿回路的图称为半哈密顿图。,第四节 欧拉图和哈密顿图,定理1（必要条件）：设无向图G=是哈密顿图，则对于任意V1 V且V1 空集 ，均有 P（G-V1）V1 定理2（充分条件）：设G是n阶无向简单图，若对于G中任意不相邻的顶点u，v，均有 d（u）+d（v）n-1，则G中存在哈密顿通路。 推论：设G为n（n3）阶无向简单图，若对于G中任意两个不相邻的顶点u，v均有 d（u）+d（v）n，则G中存在哈密顿回路。,第四节 欧拉图和哈密顿图,哈密顿图的应用 在某次国际会议的预备会中，共有8人参加，他们来自不同的国家，已知他们中任何两个无共同语言的人，与其余有共同语言的人数之和大于或等于8，试证明能将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。,一、无向树 1. 定义： 无回路的连通无向图称为无向树，简称树。 树中度数为1 的顶点称为树叶，度数大于1 的顶点称为内部结点或分枝点。 若图G的每个连通分图都是树,G称为森林 。,第五节 树、二叉树和哈夫曼树,2、树的五个等价定义 Th1.无向图T是树，当且仅当下列条件之一成立： 1.无回路且m=n-1的图 2.连通且m=n-1 的图 3.无回路，但增加任一新边，得到且仅得到 一个基本回路 4.连通但删去任一边，图便不连通。(n=2) 5.每一对顶点间有唯一的一条通路。(n=2),证明：证明思路 (1)树=1 (2)1=2 (3)2=3 (4)3=4 (5)4=5 (6)5=6,(1)树=1 即无回路的连通无向图=无回路且m=n-1 证明：对顶点数作归纳证明。 n=1时，m=0， m=n-1成立 设n=k命题成立，当n=k+1时，因树连通而无回路，所以至少有一个度数为1的顶点v，在T中删去v，及其关联边，得k个顶点的树T由归纳假设，它有k-1条边。 原图T边数为k-1+1,顶点数为k+1 m=n-1成立。 树是无回路且m=n-1的图。,(2)无回路且m=n-1的图=连通且m=n-1 的图 反证法. 证明：设T不连通，有k个连通分图 T1.Tk(k2)，顶点数及边数分别为 n1.nk,m1.mk,因每个连通分图是无回路连通图，故符合树的定义，所以ni=mi-1成立 n=m-k k1,这与m=n-1前提矛盾 T连通且具有m=n-1的图,(3)2=3 即连通且m=n-1 的图=无回路，但增加任一新边，得到且仅得到一个基本回路。 证明：(a)T无回路，因T是连通,并且m=n-1的图， 故当n=1时，m=n-1=0,无回路 设顶点数为n-1时无回路。 当顶点数为n时，m=n-1，故至少有一个顶点v， 使d(v)=1，删去v及其关连边得图T 则由归纳假设T无回路，再加回v及关联边得 图T，则T也无回路。,(b)在连通图T中,任意取两点vi，v j, 因为T连通所以vi，v j存在一路经， 若增加新边 (vi,vj)，则得一回路， 且该回路是唯一的。 ( 否则，删去新边，路经中必有回路。),(4) 3=4. 即无回路，但增加任一新边，得到且仅得到一个基本回路=连通，但删去任一边，图便不连通。(n=2) 证明：若图不连通，则存在vi,vj,，使vi,vj之间没有路，增加边不产生回路，与前提矛盾。 因T无回路，故删去任一边，图便不连通。,(5)4=5.即连通，但删去任一边，图便不连通。(n=2) =每一对顶点间有唯一的一条通路。 证明：因图连通，故任二顶点间有一条通路，若二顶点间路径不唯一，则T中有回路，删去回路上任一条边，图仍连通，与假设矛盾，所以，每一对顶点间必有唯一的一条通路 (6) 5=树定义 （无回路的连通无向图） 因每一对顶点有唯一的一条通路，故图连通，若图有回路，则任二顶点有两条不同通路，与题设矛盾。,证：若T中只有一片树叶， 则 d（vi）2（n-1）+1=2n-1 若T中没有树叶，则d（vi）2n 均与d（vi）=2m=2（n-1）矛盾。,3、Th2：结点数大于等于2 的任意树，至少有两片树叶。,二、生成树 1、生成树定义： 若无向图的一个生成子图T是树，则称T 为G的生成树，T中的边称为树枝，E（G）-E（T）称为树T的补，其中的每一边称为树T 的弦。 注：(1)由定义知，只有连通图才有生成树。,(2)连通图的生成树不唯一，至少有一棵，因通过不断地删去图G中的回路中的边，总能得到一棵生成树。,基本回路： 生成树 e1,e7,e5,e6 ， e1，e7，e5，e2，e4 e7,e2,e3,e4 ， e1，e6，e5，e2，e4 e5,e4,e8 ， e7，e6，e5，e2，e4,(3)设连通图G 有n个顶点，m条边，则G的任一生成树有n-1条边，m-(n-1)条弦，m-n+1称为连通图的秩。 2.图G中任一条回路和任何一棵生成 树的补至少有一条公共边。 证明：若G中一条回路和一生成 树的补无公共边，则表示该回路在该生成树中。这与生成树定义矛盾。 3.图G中任何一个边割集和任何一棵生成树至少有一条公共边。 证明：若G中一个边割集和一生成 树无公共边，则表示该边割集所分离的结点不在生成树中，这导致与生成树的定义矛盾。,三、最小生成树 1、最小生成树定义： 设图G=是赋权连通简单图，其中每一边的权W(i，j)是非负实数。生成树T的权定义为W(T)= W（i，j），（i，j）T，使W(T）具有最小值的生成树称为G的最小生成树。 2、最小生成树求法-kruskal算法。,设图G有n 个顶点，m条边，w(e1)w(em) k1，A 若Aek导出子图不包 含回路，则AA ek kk+1 N0 A=n-1 Yes 结束,证明：因T 是有n-1条边，且无回路的图。 由树的等价定义可知，它是树。 又T包含了n个顶点， 故包含了G的全部顶点。 T是G的生成树。,算法的正确性证明 证明边集A最后所得子图T是G的生成树。,、T是最小生成树,注：当G中的权相等时，仍可用本算法，只是所得之最小生成树不唯一。,证明T是最小生成树 （证明方法：T逐步转化T,证明：设T是最小生成树，T是由krusal算法生成的树，若T与T不同，但有公共边e1.ei(i=0),则ei+1Tei+1T,则在Tei+1中有一回路r,而T是树，因任一回路与生成树的补必有一公共边，所以在r中必存在一条边fT 对于树T(边集至少为e1.ei,f)，若用ei+1代换f，得一棵新树T1(边集至少为e1.eiei+1) 则T1的权W(T1)=W(T1)+W(ei+1)-W(f),因为T为最小生成树 W(T)W(T1) W(ei+1)W(f) 又根据T生成法 自e1.ei之后将取f而不是ei+1 而现在T取ei+1 W(ei+1)W(f) W(ei+1)=W(f) T1也是G的最小生成树。而T1与T的公共边比T与T的公共边多1，用T1置换T，重复上面论证直至T与T有n-1条公共边，从而证得T也是G的最小生成树。,一、有向树 定义: 1.若一个有向图T的底图是无向树，且恰有一个结点的入度为0，其余所有结点入度为1，称T为有向树。入度为0的结点称为根，出度不为0的结点称为分枝点或内部结点，出度为0的结点称为数叶或外部结点。 注意：有向树通常采用根在顶点上，所有边方向向下的图表示.(箭头也可省略),有 向 树 及 应 用,2.基本概念: 设a和b是树T的结点，若从a到b有一条边称a是b的父亲， b是a的儿子，同一个分枝点的儿子，称为“兄弟”。 若从a到c有一有向路径，称a是c的祖先，c是a的子孙. 由结点a和它所有的后代导的子图，称为T的子树. 从树根r到一结点a的路径所含的边数称为a的路径长度。 树T中最长的路径称为树T的高度。,例题:,a,b,c,由有向树的结构可知，它还可以递归定义如下: 3.有向树有一个根，其余的结点划分为m0个不相交的集合T1.Tm，且每个集合是子有向树。,4. 有向树的括号表示 若T中只有一个结点，则此结点就是它的括号表示。 若T由根v和子树T1T2.Tn组成，则T的括号表示为v(T1T2.Tn）.,5. m元完全树，正则树的定义 定义: 在树T中若每一结点的儿子个数小于或等于m ,称T为m元树;在树T中若每一结点的儿子个数等于m或者等于0，称T为完全m元树。若完全m元树所有树叶层次相同，称为正则m元树。,5.有向森林定义 一个有向图G，若它的每个连通分量是有向树，称G为(有向)森林，在森林中，若所有树是有序树，且给每棵树指定次序，称此森林为有序森林 .,b,c,b,c,a,b,c,完全3元树,完全2元树,正则2元树,6、有序树，有序森林与二元树相互转换 有序树转换为二元树，转换过程为： a)在各兄弟结点之间加一连线。 b)对任何结点，除最左的儿子之外，擦掉该结点与其余儿子的联线。 c)对新图向下旋转45度。,b,c,b,c,-,2. 有序森林转换为二元树转换过程 a)设置一个总根，联结各树的根，得T b)把T转换为二元树 c)删除总根,二.完全m元树性质 1.设完全m元树，叶数为t，分枝数为i，则t=(m-1)i+1,解: i =(t-1)/(m-1)=(10-1)/(3-1)=5 答:至少执行5次加法指令.,例：若 t=i(m-1)+1计算机有一计算三数之和的加法器,现求十个数之和,问至少执行多少次加法指令?,证明:若把完全m元树视为m个选手参加淘汰赛, 则t表示选手总数, i表示比赛场数,每场比赛淘汰 m-1人,共淘汰 i (m-1)人,剩下一个冠军,所以 t=(m-1)i+1,2 、内部通数长度I定义：各分枝点路径长度之和。 内部通数长度E定义：各 叶子路径长度之和. 性质：完全二叉树T有E=I+2n 其中: n为分枝点数,证：对n用数学归纳法: 当n=1, 则叶数为2，I=0，E=2， E=I+2n成立; 当n=2, 则叶数为3，I=1，E=5， E=I+2n成立; 设n=k-1时，结论成立; 则n=k时，若删去长度为e+l