离散数学之4_图的基本概念PPT课件

.图论部分，主要内容，图的基本概念路径和电路图的矩阵为Euler图和哈密顿图*平面图*对偶图和着色*树和生成树*根树及其应用，图的基本概念，图的定义图的一些概念和规定节点的度数和握手定理简图和多重图完整图和正则图和补充图的同体学习要点和基本要求事例分析， 图的定义7-1.1图是三元组，V(G )是非空节点集合，E(G )是边集合，g是从边集合到节点无序(有序偶)集合的函数。 例如，下图所示图，V(G)=a，b，c，dE(G)=e1，e2，e3，e4，e5，e6:E(G)V&V(e1)=(a，b )，(e2)=(a，c)(e3)=(b，d )，(e4)=(b，c)(e5)=(c，d )，(e6)=(a，d ) )，图的说明是边的长度图中G=，其中v可缩写为非空节点集合，e可缩写为边缘集合。图的几个概念和规定、集合的无序积： a、b为任意两个集合，a，b|aAbB为a和b的无序积，记为AB。 可将无序乘积中的无序对a，b表示为(a，b )，并且由于a=b允许为(a，b)=(b，a )，而不管a，b是否相等，因此成为AB=BA。 多个集合：元素重复的集合。 元素重复的次数称为元素重复度。 无向图： E(G )是V(G)V(G )的多重子集。 eE(G )称为无方向边缘。 有向图： E(G )是V(G)V(G )的多重子集。 eE(G )称为有向边。图的一些概念和规定，在图中一部分边为有向边，一部分边为无向边的情况下，此图被称为混合图。 方向边ei=，这里，vj称为ei的开始节点，vk称为ei的结束节点。 在一个图中，在两个节点由一条有向边或无向边连接的情况下，这两个节点称为邻点。 一个图中与任何节点都不相邻的节点称为孤立节点。 将只由孤立节点构成的图称为零图，将包含n个节点的零图记为Nn。 n-1被称为平凡的图。图的一些概念和规定，将顶点集合规定为空集合的图作为空图，记作空图。 与同一节点相关联的一边叫做环或自环。 将有向图的各有向边变为无向边的无向图称为原图的基图。 易知额定图和非额定图是可以相互变换的，对任何无向图g的各边都加上箭头就可以得到以g为基图的有向图。 g表示的是无向图，但也可以用g指向图。 d只能显示有向图。 例如以下的4个图。节点的度数，在定义7-1.2图G=中，将与节点v(vV )关联的边的数称为该节点的度数，记为deg(v )。 g的最大度(g)=maxdeg(v)|vvg的最小度(g)=mindeg(v)|vv关于悬挂顶点：度为1的顶点悬挂边：和悬挂顶点的边注意：环对节点度的贡献为2。图像度数例如d(v1)=4(注意，环提供2度)、4、=1、v4为悬挂顶点，e7为悬挂边缘。握手定理、定理7-1.1在各图中，节点度数总和等于边数的2倍。 虽然各边与两个节点相关联，但由于一边有助于与其关联的各节点的度数，因此在计算g中的各顶点度数之和时，各边给出2度，|E|边给出总计2|E|度.握手定理的推论在任何图中，度数为奇数的节点总是偶数个证明G=为任意图，V1=v|vVd(v )为奇数V2=v|vVd(v )为偶数时，V1V2=V，V1V2=，由握手定理可知，V1中顶点度数均为奇数，明显为偶数，2m也为偶数，因此|V1|必定为偶数。 问题研究：一个部门的25人之间，因为意见不同，每个人有没有可能正好和其他5人在一起a :不可能。 考虑一个图，顶点表示人，两人的意见相同的话，可以用边缘连接，所以各顶点为奇数度。 不可能存在奇数的度数为奇数的图。 说明： (1)许多离散问题可用图模型求解。 (2)为了制作图模型，有必要决定顶点和边分别表示什么。(3)在一个图表模型中，边缘总是表示两个顶点之间的关系。有向图的节点的度，在定义7-1.3有向图中，进入一个节点的边的数据称为该节点的入度d-(v )，出自一个节点的边的数据称为该节点的出度d (v )。 节点的曝光度与曝光度之和是节点的曝光度deg(v )。 d (a)=4，d-(a)=1(环e1提供角度1，提供角度1，d(a)=4 1=5)。 =5，=3，=4(在a点到达)=0(在b点到达)=3(在b点到达)-=1点和c点到达)，有向图的握手定理，定理7-1.3在有向图中，所有节点的输入度之和等于所有节点的输出度之和。 证书的各有向边与1个输入度和1个输出度对应，由于1个节点具有1个输入度或输出度必定与有向边相关联，所以图中各节点的输入度之和等于边的数，各节点的输出度之和等于边的数，所以在任何有向图中，输入度之和都等于输出度之和.握手定理的应用，例1(3、3、3、4 )、(2、3、4、6、8 )不能理解是否成为图的度数列。 有奇数个奇数。 例2图g有10边，有4个3度的顶点，剩下的顶点的度数在2以下，您知道g至少有几个顶点吗？ 解g有n个顶点。 握手定理，432(n-4)210到n-8，多重视图和简单视图，平行边连接在同一对节点之间的多个边称为平行边。 包括平行于多路复用图33至354的边的图被称为多路复用图。 简单图不包含平行边和环的图称为简单图。 注意：在定向图中，平行边的方向必须一致。 因为它是不同的节点。例如，在将g设为任意的n次无方向单纯图时，例如g为(G)n-1。 由于g没有平行边也没有环，因此g中的任何顶点v最多与剩下的n-1个顶点邻接，从d(v)n-1、v的任意性可以证明为(G)n-1。 (1) (5，5，4，4，2，1 ) (2) (5，4，3，2，2 ) (3) (3，3，3，1 )解(1)不能用曲线图表示，实例2以下的各非负整数列是判断哪个成为图的度列的简单的图。 (2)可制图，不易制图。 如果能够简单地进行曲线图化，则将所得到的简单的曲线图设为g时，(g )=max 5，4，3，2，2 =5与(G)4不一致。例2、(3)(3、3、3、1 )可以图表化，不能简单地图表化。 假设这个系列可以简单的图表化，G=这个系列为度系列。 也可以设为V=v1，v2，v3，v4且d(v1)=d(v2)=d(v3)=3，d(v4)=1。 由于d(v4)=1，因此v4仅能够邻接v1、v2、v3之一，由于v1、v2、v3不是全部为3度的顶点，因此存在矛盾，在(3)中系列也不能简单地图示。练习题、下一个顺序是简单的图表度数顺序吗？ 为什么(d1，d2，dn )，d1d2dn1且偶数。完全图、完全图：在简单图G=中，如果各节点之间有边缘连接，则将该图称为完全图。 n个节点的无向完整图标记为Kn，也称为n次完整图。 定理7-1.4n个节点的无向完全图Kn的边数是n(n-1)/2。 在Kn中，由于证明了任意2点之间边相连，所以每个节点的度为n-1，所有节点的度数之和为n(n-1 )，根据握手定理，Kn的边数=n(n-1)/2。 思考问题： n阶有向图的边数是多少，正则图，n阶k正则图：所有节点的度为k的n阶无向单纯图。 将由性质：边数m=nk/2、=k、补偿图、定义7-1.6个图G=、v为顶点位置、g为完整图Kn的追加边构成的集合作为边位置的图称为g的补偿图，求出下图的补偿图。、子图、定义7-1.7图G=、图G=、(1)如果有vv且ee，则将g记为g子图，将g记为g母图，将gg记为gg。 (2)如果gg且v=v，则将g称为g的生成子图。 (3)如果是vv或ee的话，将g称为g的真子图。 (4)将vv且v为顶点位置、两端点为v的所有边为边缘位置的g的子图称为v的导出子图，将g v (5)将ee且e为边缘位置、边与e相关联的所有顶点为顶点位置的g的子图称为e的导出子图.例如下图、(b )、(c )都是(a )的子图. 问题： (b )和(c )中哪个是(a )的生成子图，哪个是(a )的导出子图。在(b )中删除节点c以后会发生什么样的情况，例如下图，(b )、(c )都是(a )的生成子图。相对互补图将G=定义为图G=的子图，将另一个图G=定义为e=e-e，v仅包括与e边缘相关联的节点。 g称为子图g对图g的补充图。 (c )是(b )对(a )的补充图，(b )不是(c )对(a )的补充图。 此外，图中的同构体，定义7-1.9图G=和图G=，当存在双射函数f:VV时，对于vi和vjv，如果(f(vi )，f(vj)e(e )，(vi，vj ) ()和(f(vi )，f(vj ) ) ()的重量相同，则g和g是同构体，gg .例如，同构体的同构体的重量相同。 另外，重复f:au3、bu4、cu1、du2f()=-f ()=，f ()=，如果自补偿图，例如图g与其他补偿图相同，则g称为自补偿图。 证明下面的图g是自补图。 证明图的补充图如右图所示。 另外，在g及其补充图中，因为双射：v1u1、v2u3、v3u5、v4u2、v5u4，所以g与补充图相同，所以g是自补充图。关于同体的说明，g和g同体的充分条件是，两个图的节点和边分别一一对应，并且保持相关关系。 图之间的同族关系有自反性、对称性和传递性。 可以找到多个同族的必要条件，如果所有的条件都是不同的(1)边数，而顶点数相同的(2)度数相同，即，破坏了度数列相同的(没有度数的顺序)必要条件，则这两个图具有不同的结构。 迄今为止，没有找到判断两个图同体的多项式时间算法。 例如，下图的两幅图是否相同？ 为什么解节点数和边数相同，度数系列都是4、4、3、3、2。 同系，如果对应节点的温度相同，则c对应于c，c的邻接点温度系列为4、3、3、c的邻接点温度系列为3、3、2，因此结构不同。对于图的其他定义，定义为G=无向图。 (1)设ee，用G-e表示从g删除边缘e，称为删除e。 设为ee，从g中用g-e删除e中的所有边叫做删除e。 (2)设vv，从g到v以及所有相关联的边都用G-v表示的情况称为删除顶点v。 作为vv，从g中用g-v删除v的所有顶点称为删除v。 (3)设边e=(u，v)E，用Ge表示从g中删除了e后，将e的两个端点u，v替换为新的顶点w (或者将u或者v设为w )，除了w以外，将与u，v相关联的所有边称为边e的收缩。 (4)作为u，vV(u，v有可能相邻也有可能不相邻)，在u，v之间加上边(u，v )后用G(u，v )表示，称为新边。 指示在收缩边或添加新边的过程中，可能会出现与环路平行的边。 可以理解，例如g，G-e5，G-e1，e4，G-v5，G-v4，v5，Ge5，学习点和基本要求，关于图的定义的许多概念及其相互关系。 深刻理解握手定理和推理，并将其应用于实际问题。 了解简图、完整图、正则图、子图、补充图、二部图等概念，并利用它们的性质来解决实际应用。 回到练习题7-1(1)(3)(5)，事例分析，例题1证明了以下两个图是同体的。 另外，v1u1、v2u3、v3u5、v4u2、v5u4、v6u6、v7u8、v8u10、v9u7、v10u9、易于验证的边也对应。 取得证据。 证明最初标定了两个图。 全单射函数f :彼得森(Petersen )图，事例分析，例题2描绘了K4的所有非同系的生成子图。 另外，事例分析，例题3判断下面的各对的图是否为相同的：由于解：度数列分别与4、3、3、2和5、3、2、2不同，所以是不同的结构。事例分析、例题4中，4楼3边的全部非同族无向单纯图解4楼3边的无向单纯图的全部节点温度之和为6，相对于此，在单纯图中由于每个节点的度数总边数，因此在满足条件的图中每个节点的度数3。由于存在偶数个奇数度节点，因此在(G)=3)情况下，如果度序列为3，1，1，1 (g )2，则度序列绘制具有2，2，1，1和2，2，0，练习题： 5个节点的所有三个边的无向简图。 Ramsey问题(拉姆齐问题)、Ramsey问题(拉姆齐问题):任何6人在一起，6人中有3人彼此认识，或3人彼此不认识。 证明： 6人分别用v1、v66的节点表示。 相互认识的两个人通过将对应的节点连接在一起，构成了一个6节点的简单图g。 两个人不知道或者住在一边。 因此，对于g中的任何节点a，剩馀五个节点中