离散数学 通路、回路与图的连通性.ppt

1、1，7.2路径、环与图形的连接、简单走刀(回)公路、基本走刀(回)公路、复合走刀(回)公路连接图表、连接分支弱连接图表、单向连接图表、强连接图切削集和切削点边切削集和切削边(其中第一条边的终点为第二条边的起点和终点)第一个角的起点称为路径的起点，最后一个角的终点称为路径的终点。路径的端点和起点重合时称为循环。路径或循环包含的边数称为路径或循环的长度。一个，路径和循环，3，1，简单路径：如果路径的每个边都不同，简单路径：v1v2 V5 V6 v2 v3 v4长度6，简单循环：v1v2 v3 V5 v2 V6 v1长度6，2，简单循环：如果回路的每个边都不同。4、3、基本路径：如果路径的每个顶点都

2、不同。4，基本回路：回路中的各个顶点不同。基本过程：v1v6 v3 v4长度3，基本过程(循环)必须是简单过程(循环)，例如v1v6 v3 v2 v1。反之则不然。5，如果路径(循环)上重复了角，则称为复杂路径(循环)。6，路径和循环的一些茄子说明，显示方法使用顶点和边的备用序列(定义)。例如，=v0e1v1e2elvl边序列，例如，=直接简单图形中所有圆的长度2。7，在两个茄子意义上计算的圆的个数定义意义上，长度为l(l3)的圆被认为是2l个不同的圆。例如，v0v1v2v0、v1v2v0v1和v2v0v1v2被视为三个不同的圆。长度为l(l3)的圆被视为L个不同的圆。同构意义上，长度相等的所

3、有圆都是同构的，因此圆1，8，定理有从N阶图G到顶点VI到vj(vivj)的路径，有从VI到vj的长度小于n1的路径。然后有一条从VI到VJ的长度小于或等于n1的初级路径。清理在N次图G中，如果VI有自己的回路，则VI必须有自己长度小于或等于N的回路。在N阶图G中，如果VI中有自己的简单循环，则必须存在长度小于或等于N的初级循环。9，如图所示。1.无向图的连接性为无向图时，任意两点可以到达，图形为连接图。否则，没有连接的图形。如果地物未连接，则将由几个连接的子图形组成。这种连接度称为连接地。第二，图形的连接性：10，无向图形的连接性，无向图形设置G=，U和V连接性： U和V之间有通道。规定u与

4、其本身的总连接。连接关系R=| U，V，uv是V对应的连接图形3360一般图形。Vk，GV1，GV2，GVk由p(G)=k. G连接度p(G)=1，11，A=1，2，证明是反证法证明的。如果两个顶点没有连接，则它们必须属于两个徐璐不同的连接分支，对于每个连接分支，G的子图形只有一个奇数角顶点，其馀顶点是偶数角顶点，并且与握手清理相矛盾。因此，如果地物中只有两个奇数角顶点，则必须连接这两个顶点。13，例在国际会议上，由7人组成的A、b、c、d、e、f、g中，A会说英语、阿拉伯语。b英语、西班牙语；c中文、俄语；d日语、西班牙语；会说e德语、汉语和法语。f日语、俄语；g会说英语、法语、德语。问题：

5、他们谁能对话(如果需要，可以通过别人翻译)？14，使用顶点代表人，如果两个人使用相同的语言，在代表两个人的顶点之间连接边，就可以得到下图。问题包括：在牙齿图中，两个顶点之间是否有路径？下图是连接图，如果需要的话，通过别人翻译，他们任何人都可以对话。15，定理是N阶简单图G中G的每个顶点对U和v，deg(u) deg(v) n1的G是连接图。假设证明g没有连接，g至少有两个分度。一个图形中有Q个顶点，其他每个图形中有n个Q顶点。由于牙齿的两个部分分别获取顶点u和v，0deg(u)q 1和0deg(v)n q 1，因此deg(u) deg(v)n 2获取deg(u)deg(;u)deg(;u)；1

6、6，短距离和距离，u和v之间的短距离线： u和v之间的最短路径(u和v连接)u和v之间的距离d(u，v): u和v之间的短距离线长度u和v未连接时d(u，v)=。V) d(v，w)d(u，w)，17，在实际问题上，除了调查图片是否连接外，还经常研究图片连接的程度作为部分系统的可靠性测量。图的连通性在计算机网络、通信网络、电网等领域有着重要的应用。删除图形的连接应用节目，18，点切削集，连接图形中的某些顶点或边可能会影响图形的连接。从图中删除顶点V是删除与顶点V和V关联的所有边。删除边只需删除相应的边。19.例如，如果“国际会议对话”是任何人休假，图G-v连接在一起，组对话可以继续进行，但是如果

7、F，G同时缺席，G-f，G是分离度，组内的对话就不能再进行了。20，点切集，从Gv: G中删除V和关联边Gv:从G中删除V的所有顶点和关联边Ge :从G中删除e GE:从G中删除E的所有边定义如果无方向图G=，VV，p(GV)p(G)，则V称为G如果v是一组点切削，则v称为切削点。21，点切削集(继续)，示例v1，v4，V6是点切削集，V6是切削点。22，示例v2，V7，23，边切削集，定义设置无向图G=，EE，p(GE)p(G)和EE，p(GE)=p没有剪切和剪切的连接图需要减去几条边或几个点，这样图片才能不连接。25，几个茄子说明：Kn无点切削集N次零度没有点切削集，没有无限切削集。如果G

8、是连接的，E是边切削集，p(GE)=2 G是连接的，V是点切削集，p(GV)2我们用元素数最小的点切削集和边切削集来描述连接度，26，下面从数量角度描述图形的连接性。定义设置G=(V，E)是连接图，k(G)=min| V | | V是点连接图，其中G的点集称为G。(G)=min| E | | E是将G的边切割集称为G的边连接图。图形G中的点连接图是为了使G成为未连接图形而必须删除的最小点数。如果图G中有剪切点，则k(G)=1。图G的边连接度是为了使G成为未连接图而必须删除的最小边数。如果地物G具有剪切边(G)=1。27，是下图中的两个连接图形为n=8，e=16。其中(G1)=4，(G1)=4，

9、(G2)=1，(G2)，28，N个顶点表示N个站，E条边表示铁路或桥或电话线，en-1。为了避免N个工作站之间的连接容易断开，您需要配置包含N个顶点E边的连接图，并最大化点连接和边连接。在图中，根据G1的连接法，如果三个车站被破坏，或者三条铁路被破坏，剩下的车站可以继续徐璐连接。也就是说，仍然有连接性。但是在图中，根据G2的连接方法，如果V站被破坏，剩下的站将无法继续连接。29，任意图形G=(V，E)的定理，如果k(G)(G)(G)(G)(*)证明G是普通图形或未连接图形，则k (g)=(g)=0，G以下证明k (G) (G)。(G)=1时，G具有剪切边，k(G)=(G)=1，(*)格式成立。

10、30，(G)2，(G)删除边以防止G连接，(G)删除其中一条边，G仍然连接，腿e=u，v。(G)对于一条边，选择u、v和其他顶点。(G)删除一个顶点时，必须至少删除(G)一个面。如果其馀地物未连接，则k(G)(G)1(G)；如果连接了其馀的图，则E仍然是腿。如果在牙齿时删除U和V，则会生成未连接的图形和k (G) (G)。总之，所有的图G都有k(G)(G)(G)(G)。31，在下图中，k(G)=1，(G)=2，(G)=3由图形G=(V，E)定义，如果k(G)h，则G称为G(G)h，如果G为h-。范例上图中显示的插图是1-连接，2-边。32，简单的图都是1-连接和1-边连接。n阶整体图形是(n1

11、)-连接的总和(n1)-边连接。对于所有N阶连通图，只有在没有切除的情况下，2-连通图。只有在没有修剪边的情况下，双边才会连接。如果图G是h-连接，则G也连接到h-边。(k(G) (G)从定义上看，h1h2，如果图G是h1-连接，那么G也是h2-连接。H1h2，如果图G是h1-边连接，则G也是h2-边连接。图的连接度越大，连接性能越高。33(例如，下图中的边连接度为3，因此连接了3个面，连接了2个面和1个面，但没有连接4个面。34，2，有向图的连通性，对于有向图的情况，“图的两点都有通道连接”的要求很高。这是因为直接图形是连接的，但受边的方向限制，所以任何两点都不需要有路径。讨论以下三种茄子情

12、况：35，1)强连接图表：在直接图中，A，B可以徐璐到达。图(a) 2)单向连接图表：在直接图中，两点A、B具有A-B或B-A路径。图(b) 3)弱连接图表：在直接图中，如果参考底图是无向连接图，则图(C)，显然：在直接图中，如果存在通过图形中所有点的循环，则牙齿图具有强连接。如果有通过图中所有点的路径，则牙齿图形是单向连接图形。(a) (b) (c)，36，单向连接图形都是弱连接图形，但弱连接图形不一定是单向连接图形。弱连接图中有顶点a，b，从a到b不能到达，从b到a不能到达。强连接度不仅是单向连接度，也是弱连接度。也就是说，强连接单向连接弱连接，37，直接图的连接(继续)，定理(强连接判别法)D强连接，D至少通过每个顶点一次的循环清理(单向连接判别法)，只有D有通过每个顶点一次或多次的路径时，D才有38，38，思考：，(a)、(b)、(d)、(c)、回答3360 (a)、(d)强