第十五章-欧拉图与哈密顿图PPT课件

.第1，15章，欧拉和哈密尔顿图表，本章的内容是第14章，第2，1，康尼克斯堡7教时问题，15.1欧拉图，3，1。定义：(1)Euler通道，(2)Euler循环，(3)Euler图表，所有节点的每个边一次一个，所有节点的循环一次，具有Euler循环的图形，具有2，0 Euler图形，(4)没有Euler循环的Euler路径的图形，4，2。无向Euler图的确定，定理15.1无向图g是Euler图，仅在g连接且没有无限节点的情况下适用。需要，将c设置为g的欧拉回路。证明：如果g是普通图的结论，那么肯定成立。下面，将g设定为n阶m-边的全向图。(1)G连接很明显。(2) VIV (g)，VI每次出现在c中时，都会给定2度，因此VI是偶数节点。根据VI的随机性，结论为真。5，相反m的归纳法，恰当性(1)m=1，g是环的话g是欧拉图。(2)在设定MK (k1)时，结论成立，证明m=k 1时结论成立，如下：6，(a)满足诱导假设的多个小欧拉图的制造。连接和异常也必须由节点表示，(g) 2，g中必须有圆C1。如果通过删除C1的所有边(不破坏g中节点数的奇偶校验)获得g，则g为s (S1)的连接分支G1、G2、它具有GS，并且每个边的数量为k，因此它是一个小的Euler图。C1、C2、cs是G1、G2、GS的欧拉循环。(b)将C1的移除边从C1的节点还原到g的Euler循环c。7，flexury算法：(1)如果选择v0v (g)，则P0=v0。(2) pi=v10e1v1 E2.设置eivi，e (g)-E1，E2，ei中，选择ei1。(a) ei1与VI连接。(b)ei 1为gi=g-E1，E2，不能是，ei的腿。(3)无法继续时，算法停止。8，示例：在下图所示的Euler图中，查找从v1开始的Euler循环。解决方案：v1 E1 v2 E2 v3 ee7 E6 V6 E5 V5 E4 v4 E8 v2 e9 V7 e10 v1，注：P4=在v1e1v2e2v3e3v4e7v7上下车，然后不要走桥(E10不能走).9，定理15.2全向图g是一个具有连接g且只有两个奇节点的半欧拉图。如果有两个奇数度节点，则这是每个Euler过程的端点。反欧拉也判定，证明：必要性g的连通性很明显。因为g是半Euler图表，所以g具有Euler路径(没有Euler循环)，VI 0 e J1 vi1.由于vim在g中具有Euler路径，vi0 vim，因此将g设置为m边的n阶无向图。如果任何v出现没有v的端点，d(v)为偶数；如果v出现在端点，则d(v)为奇数，因为只有两个端点不同。因此，g只有两个奇数节点。10，适当：如果设置了G的两个奇数节点分别为u0和v0，G=g (u0，v0)，则G 是连接的且没有奇数节点的图形，因此G 是Euler图，因此有Euler循环C ，C=C-(u0，v0)，11，示例：下图是欧拉图，半欧拉图是什么？不是欧拉、欧拉、反欧、欧拉，也不是反欧。12，例如，2个蚂蚁赛跑问题：2个蚂蚁a，b分别位于图g中的节点a，b，设置每条边的长度相等。甲提议进行同龄人比赛。从他们所在的地点出发，经过图的所有边缘，最后到达节点c。如果速度相同，问谁最先到达目的地？解决方案：图中只有两个奇数度节点(b和c)，因此从b到c的Euler路径存在。蚂蚁b必须到达c的一条Euler路径，即只有9条边，蚂蚁a必须先到达b，再去一条Euler路径，才能到达c，因此蚂蚁a必须经过所有边。因此，b必胜。13， 7桥梁问题，d(B)=5，d(A)=d(C)=d(D)=3，7桥梁问题未解决。3，全方位欧拉图应用，14，能画出给定的画吗？一划问题，半欧拉图，欧拉图，15，判断一个笔划问题，(1)从图g中的一个节点开始，一次一个节点到达另一个节点。，(2)从g的一个节点开始，经过g的每一侧，仅返回到该节点一次。半欧拉图确定，欧拉图确定，16，例2:你能画下图吗？解决方案：(1)有四个奇数节点没有Euler循环或路径，不能一次绘制。(2)和(3)都是两个奇数节点，剩下的是偶数节点，可以通过Euler路径一次绘制。(4)图是具有欧拉回路的偶数节点，可以一次绘制。17，中国邮路问题，一名邮递员从邮局出发，将邮件送到管辖的街道，最后返回邮局，如果要在管辖的各条街中至少逛一次，如何选择递送路线，走的路最短呢？中国数学家关梅古教授1962年解决了这个问题，从国际数学界用中国邮政呼叫了这个问题。解决方案：用图论的语言描述。也就是说，在权重图g中，c至少包含g的每个角一次，并且c的长度最短，可以找到循环c吗？(1)如果g没有奇数度节点，则g是Euler图，因此Euler电路c是唯一的最小长度解决方案。18，(2) g有两个奇数度节点VI和VJ，g有Euler路径，邮局在节点VI，邮递员一次到达节点VJ。从Vj返回到VI后，可以选择其间的最短路径之一。这样，最短的邮件问题将转换为VI到VJ的Euler路径和VJ到VI的最短路径问题。(3)如果g中有两个或更多角度为奇数的节点，则必须向回路中添加更多重复边。步骤2:(a)“可行方案”(FeasibleScheme):添加边以创建新的非奇异节点。(b)优化程序(OptimalScheme):调整可行方案，以最小化增加的总边界值。19，15.3(具有权值)定义给定图形g(无向或无向)；W:er(r是实数集)；对任意边e标注W(e)=wij；对边e标注实数wij的权值；对边e标注wij将W (e)称为g的权限。20，示例：确定下图中从v1到v1的循环，将其权重最小。1 .第一个可行方案的决定奇数节点有四个：v1、v3、v4和v6。V1、v4、v3和v6成对出现。选择V1和v4的主要路径为v1v6v5v4、v3和V6的主要路径为v3v7v1v6，每个路径包含的边添加平行边，使其成为Euler图。增加边的总权重。w (v3，V7) w (V7，v1) 2w (v1，v6) w (V6，V5) w (V5，v4)=13，(a)，(a)，21，2。调整可行方案，以使增加的边总数等于图(b)中边(v1，v6)的重量3。移除两条边不会影响v1、V6的同位和连接性，因此可以移除两条边。通常，如果边的重量大于3，则移除两个边。因此，得出以下结论：(1)在最佳方案中，图中各边的权重小于2。22，此外，如果从主回路中删除平行边并将平行边添加到没有原始平行边的边，则不会影响图中节点的角度奇偶校验。因此，如果平行边的总权重大于主循环中相应循环的权重的一半，则进行此调整。在图(b)中，电路v1v2v3v7v1的权重为6，平行边的总权重为4，大于3，因此调整后的图应为图(c)。(c)，(2)在最佳方案中，图形中每个基本循环上的平行边的总权重不大于该循环的一半。调整后的平行边总权值=w (v1，v2) w (v2，v3) w (v4，V5) w (V5，V6)=5，23，3，有向Euler，清理15.3有向图形d是Euler图形，d连接牢固，每个节点的传入程度为出图时。24，定理15.4直接图d是半Euler图，d仅单向连接，d具有两个奇数节点，一个入射度为1，另一个出图大于入射度1，其馀节点的入射度均等于出图。25，15.2哈密尔顿图表，1，问题的建议汉密尔顿在1859年英国数学家汉密尔顿提出的“世界游戏之旅”中，用正十二面体的20个节点取代了20个城市(图(1)。这个正十二面体要求沿着一个平面(图(2)和同形十二面体的棱镜从一个城市出发，经过每个城市精确一次，回到起点。，图(1)、图(2)、26，汉密尔顿和汉密尔顿图1。通过15.2(1)哈密尔顿路径一次通过定义图中所有节点的路径。(2)哈密顿回路图中的所有节点一次通过一个循环(3)哈密顿图哈密顿回路的图。(4)具有哈密顿通路且没有哈密顿回路的半哈密顿图图。27，说明：平凡的图是汉密尔顿图。汉密尔顿过程是一次过程，汉密尔顿循环是一次循环。环和平行边对汉密尔顿没有影响。哈密尔顿图的本质是把图的所有节点排列在同一个圆上。28，是，汉密顿环，汉密顿环，汉密顿环，汉密顿环，没有汉密顿路。29，2。无向哈密顿图的必要条件，定理15.6无向度G=哈密尔顿图，所有V1 如果V1中的节点在C上不相邻，则p(C-V1)表示最大值|V1|，如果V1中的节点在C上相互连接，则p(C-v1)|V1|，否则(2) v1=a，g，h，35，G3，(3)V1=a，C，g，h，e，V2=b，d，I，j，f，|V1|=(1)如果g是汉密尔顿图表，则|V1|=|V2| |。(2)如果g是哈密顿图，则|V2|=|V1| 1。(3) | v2 | | v1 | 2时，g不是(半)哈密顿图。36，3。无向哈密顿图的充分条件定理15.7 g是n阶无向简单图，对于任何不相邻节点VI，如果VJ有d (VI) d (VJ) n1，那么g有哈密顿路径，g是n (n3)阶无向简单图，对于不相邻节点VI，VJ有d(。如果g是n (n3)阶无向简单图，并且所有节点v都有d (v) n/2，那么g有哈密顿回路，那么g就是哈密顿图。37，如：一个会议有12人参加，其中每人至少有6个朋友。12个人围坐在圆桌旁，每人相邻的两个人都算朋友吗？说明原因。解决方案：问题的需求可以通过以下原因实现：平面上12个节点表示12个人，如果两个人是朋友，则在这两个节点之间连接一个角，将结果图设置为g，则g的每个节点的度6，因此g的每个节点对的和为12。g在汉密尔顿图表上，即g有汉密尔顿循环，所以12个人围着桌子的时候，每个相邻的两个人都可以成为朋友。38，如：每条路与其他景点连接，某个地方就有5个风景点。问问游客是否可以经过各旅游景点一趟，游览这五个地方？解决方案：5个景观点为5个节点无向度g，2个景观点道路为无向度侧，根据主题，每个节点的度数为2，任意2个不相邻节点的度数之和为4，45-1，因此汉密尔顿过程存在于图g中，解决了这个问题。39，2，判断是否是汉密尔顿图表仍然很难。1.观察哈密顿回路。判断是汉密尔顿图还是不是汉密尔顿图的几种可能方法：例如(全球问题旅行)是汉密尔顿图，abcdefghijklmnpqrsta是图的汉密尔顿环。40，汉密顿回路，2。满足定理15.7的推理条件，并且在全图Kn (n3)中有两个节点u，v具有d (u) d (v)=2 (n1) n (n3)，因此Kn是哈密顿图。41，3。破坏定理15.6的条件图不是哈密顿图。因此，正如V1=a，b，c，d，p (gv1)=64，定理15.6所示，没有哈密顿回路。42，15.3货物和问题，n个城市之间有道路，道路长度等一位旅行家从哪个城市出发，每个城市只经过一次，最后回到出发的城市，问如何使他走的路最短。研究这个问题显然是有趣而有价值的，但还没有找到有效的算法。理论上，可以通过枚举方式解决，但是如果节点数很多，则会执行很多计算。实际上，使用接近算法和捷径算法给出了这个问题的近似值。43，例如：查找下图所示的四阶完全权重图的另一个哈密顿回路，并表示最短的哈密顿回路。44，解决方案：如果不考虑顺时针方向和逆时针方向之间的差异，则W(C1)=8，W(C2)=10，W(C3)=12。其中C1是最短的哈密顿回路。45，n阶完全带图的共享存在(n-1)！通过比较两种不同的汉密尔顿电路，可以找出最短的汉密尔顿电路。N=4: 3还有其他的哈密顿回路。N=5: 12个不