图论第4,5章E,H图,匹配(10.3)

1、第4章，欧拉图和哈密尔顿图，4.1欧拉图，定义1让G是一个没有孤立点的图。穿过G的每条边的(闭)迹叫做欧拉迹，有欧拉闭迹的图叫做欧拉图。欧拉闭合轨迹也叫欧拉之旅。在上图中，(a)和(f)是欧拉图；(二)、(四)欧拉轨迹，但不是欧拉图；(c)和(e)没有欧拉轨迹。例1定理1下列语句等价于连通图G: (1) G是欧拉图。G的每个点的度数都是偶数。(3)G的边集可分为圈。设C是g中的欧拉闭合轨迹。每次C中的任何给定点出现在C中，都只有两条边。因为G的每条边在C中只出现一次，所以这个点的度数应该是这个点在C中出现的次数乘以2，这是一个偶数。结论是连通图G有欧拉迹，当且仅当G最多有两个奇点。证明定理1:

2、当且仅当G具有零奇点时，G具有欧拉闭迹。如果连通图G有欧拉闭迹C，并且点U和V分别是C的起点和终点，则通过增加一条连接U和V到C的新边E得到的图是ce。显然，C e是欧拉闭迹，所以已经证明C E有零奇点，因此C，即G，有两个奇点。相反，设G是一个恰好有两个奇点u和v的连通图，在u和v之间加一条新边e得到ge，则G e没有奇点。根据已证明的结论，G e有欧拉闭迹，所以G e有欧拉迹。综上所述，推论结论成立。从上面的讨论，我们也有：1。图G有欧拉迹，G可以是“一笔画”，G是连通的，G中的奇数不超过2、2。如果奇数是0，那么笔画与起点无关；如果奇点的数量是2，那么笔划的起点和终点都是奇点。3.在有向

3、图(即每条边都是有向边的图，其系统讨论将在第9章中进行)中也得到类似的结论。在有向图D中，从点U开始的弧的数量(即有向边)称为U的度数，它被记录为DD (U)。在点u处结束的弧的数量称为u的穿透，表示为dD-(u)。定理3下列陈述等价于连通有向图：(1) D是欧拉有向图。(2)D的每个点的内角等于外角。(3)d的弧集可分为有向圈。4.2高效电脑鼓的设计。转鼓在计算机中的位置是通过转鼓表面上的一系列电触点产生的二进制信号来识别的。该表面分为m个部分，每个部分由绝缘体或导体材料组成。绝缘部分给出信号0(无电流)，导电部分给出信号1(电流)。对于： S周期内的任何正整数n，为1。有一个最小的正整数。

4、为了提高效率，我们期望每次滚筒旋转时读出的由k位组成的m的数量(m个段)应该彼此不同。此外，对于给定的k，最大m应该是多少？如何构造这样一个鼓？涉及这一问题的数学模型的几个概念：设S=(a1，a2，a，n)，be (0，1)无限序列，以及k-部分序列S1，S2，之2。s是由k个元组组成的序列，由s中的k个连续元素组成，即S1=(a1，a2，AK) 3。De Brewin序列：是指对于一个固定的正整数K，具有最大一(0，1)周期的序列S，这使得S的K部分序列S1、S2和S不同。很容易知道，恰好有2k个不同的k元(0，1)序列S1，即=2k。对于一个固定的k，上述问题的数学模型：找到解布鲁林序列s

5、。在实例1中，假设k=3，那么=23=8。八个不同的3部分序列是：(000)(001)(010)(101)(011)(111)(110)(100)，相应的Debruin序列是S=(0001011100010111)，它将该序列的前八位排列成一个圆，de Brewin序列：的构造，步骤1，构造一个点是2k-1个不同有序(k-1)元组的有向图H:对于点V=(B1，B2，bk-1)，将点V连接到点v1=(b2，b3，BK-1，0)和V2。=(B2，B3，BK-1，1)用两条弧，并得到有向边v，v1和v，v2。当然，上述点v=(b1，b2，bk-1)也具有由指向V的点u1和u2连接的两侧，其中u1=(

6、0，b1，b2，bk-2)和u2=(1，b1，b2，bk-2)。(1)h的每一个点v都有d (v)=d -(v)=2并且是连通的，所以h是一个欧拉有向图，称为de Brewin图。(2) H有2k个弧。如果从点(B1，B2，bk- 1)到点(B2，B3，bk)的每个弧a表示一个k元组(B1，B2，bk)，则可以获得2k个不同的k元组。在第二步中，我们找到了H的欧拉有向闭迹，然后我们得到了k-部分序列S1，S2，S和相应的德布鲁林序列S。在一个例子中，下图是一个德布鲁林图，其中k=4 (=24=16)，相应的欧拉有向闭迹和相应的德布鲁林序列。本示例有16个解决方案，其中一些是(abcdkijef

7、jhlmnpq)=(0000101101001111)(abcdkippghlmjefq)=(00010111101)(abcdkijedklmnpq)=(0001001111)(abhibijklmnpgcdefq)=(000111110010101)(abhibijdklkldklmnpq)如何选择路线？图论模型：在一个具有非负权重的连通加权图g中，找到一条每条边(允许重复)和边权重之和最小的封闭路径，这称为最优路径。对于这个问题(1)，如果图G是一个欧拉图，可以找到图G的欧拉路径。(2)对于一般图，解决方法是增加重复边，使G成为欧拉图G*并最小化增加的重复边的边权之和，然后找到G*的欧拉

8、路径。(3)对于恰好有两个奇数度点的图G，可以证明要重复的边恰好是从一个奇数度点到另一个奇数度点的最短路径，即问题是欧拉问题和最短路径问题的综合。它表明： (1)如果G是一个欧拉图，那么G的任何欧拉旅行都是最好的旅行。(2)如果G不是欧拉图，当增加重复边使G成为欧拉图G*时，增加的重复边的特征由定理3给出。定理3如果W是包含G中所有边的封闭通道，那么W在这样的封闭通道中具有最短的长度。(2)在G的每个圆上，重复边的数量不超过圆长度的一半。该算法的思想是从任意一点开始，按照不重复边的方法画出一条轨迹，这样在每一步中，只有当没有其他边可供选择时，才画出未着色子图的切割边。确定欧拉图中欧拉行程的弗勒

9、里算法，弗勒里算法，1。任意选择一个顶点v0，并设置w0=v0。2。假设已经选择了迹线wi=v0e 1v 1 Ivi，从EE1、E2、ei中选择边缘ei 1，如下所示：(1)将EI1与VI相关联；(2) ei 1不是G=G-E1、E2、ei的一个优势，除非没有其他优势可供选择。3.当无法再执行步骤2时，算法停止。可以证明，Fleury算法是一种很好的算法。博物馆一楼的布局如下，边缘代表走廊，节点E是入口，节点G是礼品店，通过礼品店我们可以离开博物馆。请找出从博物馆E进入的路线，每条走廊恰好经过一次，最后从G离开。解决方法：图中只有两个奇数顶点E和G，所以有一条起点为E、终点为G的欧拉轨迹。为了

10、找到一条起点为E、终点为G的欧拉轨迹，在E和G之间增加一条平行边M， 并利用Fleury算法求出欧拉行程为：egjeijdghdbhcbafcg，设G=(n，M)为欧拉图，从Fleury算法可知该算法需要M个循环； 算法中的主要操作是判断：这个判断的时间复杂度是n2的数量级。因此，Fleury算法的时间复杂度为O(n2m)，是一种很好的算法。算法复杂度分析，(2)检查G的循环，如果存在循环C，其中重复边的总长度大于循环长度的一半，则交换循环C上的重复边和非重复边，得到图G”。重复这个过程，直到得到一个图G*，并且在G*中没有循环，其中重复边的总长度大于循环长度的一半。欧拉图不是寻找最佳行程的方

11、法。(1)通过向每条边添加至多一条边，随意添加一些重复的边，使得图G成为欧拉多重图G。(3)使用Fleury算法来找到图G*的欧拉行程，并且示例图G如图(a)所示(每条边的权重为1)，其具有10个奇数点。任意添加一些边得到一个欧拉多重图(b)。在(b)中，彩色圆的重复边数是5，这超过了圆长度8的一半。交换这个圆上的重复边和非重复边，得到(c)。(c)中每个圆的重复边数不超过圆长的一半。因此，在(c)中的每个欧拉闭合轨迹对应于原始图像的闭合通道，其包含所有边缘并且具有最短的长度。(a)、(b)，4.4哈密尔顿图，只通过图中每个点一次的路径(圈)称为哈密尔顿路径(圈)，具有哈密尔顿圈的图简称哈密尔

12、顿图。汉密尔顿路也简称h路。只有哈密尔顿路径，但没有哈密尔顿图、哈密尔顿图，也没有哈密尔顿路径。例如，证明了C在G中是一个哈密尔顿圈，如果取V中的非空子集S，因为C是包含G的G的哈密尔顿圈的所有点，S也是子图C的非空子集，根据点不重复的圈的特征，任意删除C中的| S |点，最多将C分成| S |“段”，即(C-S) | S | (*)， 而C是G的生成子图，并且有(G-S) (C- S)，所以(G- S) | S |，定理5它们都有(G-S)|S | (4.1)。 根据定理4，可以判断下面的图(a)不是哈密尔顿图，因为如果S=v并且(G-S)=2 1=| S |，则可以验证彼得森图(在上面的图

13、(b)中示出)不是哈密尔顿图，而是满足公式()这表明定理5给出的条件仅仅是图G是哈密尔顿图的必要条件，而不是充分条件。设G是简单图，U和V是G中不相邻的顶点，G是H图，当且仅当G uv是H图。证明必要性：如果G是h-图，那么显然G uv是h-图。充分性：让G uv为h图。G=(G紫外)-紫外表明，如果G紫外的h环不包含边缘紫外，则G中存在h环。如果G uv的h圆包含uv边，则让h圆为C=uvv3v4vnu。当G1=紫外线，因此，如果i (3in-1)使u adj vi，v adj vi 1(如图所示)，那么有一个h循环，C1=紫外线-1 v3 v v1 VI 2 VN u in G，也就是说，

14、G是一个h图。如果没有这样的I，则有-2个点，并且在v3、v4、vn-1和VN-1中。因此，这与已知的条件相矛盾。因此，在dG(u) dG(v) n的假设下，必须有I，如上图所示，所以g中有一个h循环，所以g是一个h图。定义1在一个简单的N阶图G中，如果对于D (U) D (V) N的任意一对点U和V，G是一个闭图，如果G1和G2是同一个点集的两个闭图，那么G就是一个闭图。G1和G2是闭图，并且U和V在G1和G2中是相邻的，所以U和V在G中也是相邻的，所以G是一个闭图。证明了对于任何wV，具有DG (w)和DG (w)的闭图不一定是闭图。例如，定义2如果具有与G相同点集的闭图是G，并且对于任何

15、不同于G H的图H，H不是闭图，那么它被称为G的闭包，也就是说，G的闭包是包含G的最小闭图。图：的闭包的构造方法递归地连接非相邻的顶点对，这些顶点对在图中的度数之和至少是图的顶点数，直到这样的顶点对不再存在。下图显示了具有六个顶点的图的闭包的构造过程。是唯一的。引理3图G的闭包是唯一的。G，证明如果和是G的两个闭包，然后由G证明如果G是h图，显然，它是h图。定理7(邦迪1969)简单图G是一个H图，当且仅当它的闭包是一个H图。如果是h图，当G=时，结论成立；当G，必须有几个连续的边，所以G e1 e2 ek=，其中eiG，(i=1，2，k)。根据闭包的定义，对于中间边ek的端点u和v，因为G

16、e1 e2 ek是h-图，所以从引理1可知G e1 e2 ek-1是h-图，并且引理1的重复应用表明G是h-图。注：图G的闭包不一定是一个完整的图。例如，下图中的(a)和(b)不是完全图，但它们是自己的闭包。推论1:让它成为一个简单的n 3图。如果它是一个完整的图，那么G就是一个H图。推论2 (1)让G是一个简单的n 3图。如果G中每个点的度数是d(v) n/2，那么G就是一个H图。(由此，我们得到定理6) (2)设G是一个简单的n 3图。如果G中任意两个不相邻的点U和V有d(u) d(v) n，那么G就是一个H图。描述：要判断一个图是否是哈密尔顿图，通常需要结合定义。根据定义，如果一个图有一个度为1的顶点，它一定不是哈密尔顿图，而只是哈密尔顿路径；如果图是哈密尔顿图，与图中2度顶点相关的边必须属于所有哈密尔顿圈；有更多的边与一个顶点相关联，在