第11章 特殊图.ppt

2020/6/9，第11章特殊图，2020/6/9，11.2欧拉图，11.2.1欧拉图的介绍和定义，2020/6/9，定义11.2.1，设g是没有孤立节点的图。如果有一条路径(循环)穿过图的每一边一次并且只穿过一次，那么这条路径(循环)被称为图的欧拉路径(循环)。具有欧拉路径的图称为欧拉图形。规则：普通图是欧拉图。上述定义适用于无向图和有向图。2020/6/9，欧拉路径和欧拉路径的特点。欧拉路径是穿过图中所有边的路径中长度最短的路径(边数，不是加权图)，即穿过图中所有边的简单路径；欧拉路径是穿过图中所有边的环中长度最短的环(边数，而不是加权图)，即穿过图中所有边的简单环。如果只用边来描述，欧拉路径和欧拉路径是图中所有边的完整排列。2020/6/9，示例11.2.1，判断以下6个数字是否为欧拉数字？有欧拉路径吗？Euler，Euler，不是Euler，而是Euler路径，不是Euler路径，不是Euler路径，不是Euler路径，不是Euler路径，而是Euler路径，2020/6/9，11.2.2欧拉图的判定-无向图，定理11.2.1无向图G=有一个Euler路径，当且仅当G是连通的并且只有0或2个奇数度节点。推论11.2.1无向图G=有欧拉路径，当且仅当G是连通的，并且所有节点的度数是偶数。通过计算图中每个节点的度数，我们可以知道它是否有欧拉路径和欧拉路径，从而知道它是否是欧拉图。2020/6/9，11.2.2欧拉图的判断-有向图，定理11.2.2有向图G具有欧拉路径，当且仅当G被连接并且除了两个节点之外的其他节点的进入度等于外出度，并且在这两个例外节点中，一个节点的进入度比外出度大1，并且另一个节点的外出度比进入度大1。推论11.2.2当且仅当G是连通的并且所有节点的进入度等于退出度时，有向图G具有欧拉路径。通过计算图中每个节点的进出度，我们可以知道它是否有欧拉路径和欧拉路径，从而知道它是否是欧拉图。2020/6/9，欧拉路径的搜索桥的定义，集合G=，eE，如果p (g-e) p (g)调用例如桥或Cutedge。显然，所有悬边都是桥。其中p(G-e)是通过从例如2020/6/9，欧拉路径的搜索-弗勒里算法，欧拉路径的算法11.2.1弗勒里算法中删除而获得的图的连通分支数，G=(1)设P0=v0V，I=0；(2) ei1: a. ei1选自e-E1，E2，ei根据以下方法与vi相关联；B1不应该是g=g-E1，E2，ei除非没有其他边缘可供选择；(3)将边缘ei 1添加到路径P0，使得P0=v0e1v1e2.1维1维1，1=1；(4)如果i=|E|，结束，否则转到(2)。2020/6/9，示例11.2.2，使用Fleury算法找到欧拉图的欧拉路径。本文作者分析了事故的原因，指出事故是由事故引起的。例如，当p7=v1e 1 v2 e2v 3 E3 v4 E4 V5 e5v 6 e6v 7 e7v 8被获得时，e8在g=g- E1，E2，E7是一座桥，所以下一步是选择e9而不是e8。从v1开始的欧拉路径的解是：P12=V1 E1 V2 E2V 3E 3V 4 E4 V5E 5V 6V 7E 7V 8E 9 V2e 110 V4E 111 V6E 12V 8V 8 V1，2020/6/9，11.2.4欧拉图的应用。1.所谓“一笔一画”就是画一个图形，笔不与纸分开，每一面只画一次，不重复，图形就完成了。“一笔画问题”本质上是一个无向图中是否存在欧拉路径(环)的问题。如果绘图是欧拉绘图，绘图可以一次完成，并且笔返回到起点。如果图形中只存在欧拉路径，图形可以用一个笔画完成，但是笔画不能到达起点。如果图形中没有欧拉路径，图形就不能一次完成。，2020/6/9，示例11.2.3，图表中的三个图表可以有一个笔画吗？为什么？因为在图(a)和(b)中分别有0和2个奇数度节点，它们是欧拉图，并且分别有欧拉路径，所以可以画一个笔画，并且笔可以返回到(a)中的起点，而笔不能返回到(b)中的起点。在图C中，有4个3度的节点，所以没有欧拉路径，所以没有一个笔画。2020/6/9，11.2.3欧拉图小节，只有欧拉路径没有欧拉路径图不是欧拉图；确定图中是否存在欧拉路径和欧拉路径图非常简单，只需计算图中节点的度数。当使用弗勒里算法来寻找欧拉路径(循环)时，一次一条边，如果可能的话，没有桥。2020/6/9，11.3哈密尔顿图，11.2.1哈密尔顿介绍和定义，2020/6/9，哈密尔顿图，定义11.3.1在图中通过每个节点一次且仅一次的路径(回路)称为哈密尔顿入口/回路。哈密尔顿环的图称为哈密尔顿图。规则：普通图是哈密顿图。上述定义适用于无向图和有向图。2020/6/9，哈密尔顿路径和哈密尔顿回路的特征。哈密尔顿路径是通过图中所有节点的最短长度(指边数和加权图)的路径，即通过图中所有节点的基本路径；哈密尔顿环是图中所有节点中长度(边数，没有权重的图)最短的环，即通过图中所有节点的基本环。如果我们只使用节点来描述哈密尔顿路径，它是图中所有节点的完全置换，哈密尔顿环是图中所有节点的完全置换加上置换中第一个节点的置换。2020/6/9，例11.3.1，判断以下六个数字是否为哈密顿图？有哈密尔顿路径吗？哈密尔顿图，没有哈密尔顿路径，不是哈密尔顿图，但有哈密尔顿路径，哈密尔顿图，不是哈密尔顿图，但有哈密尔顿路径，没有哈密尔顿路径，2020/6/9，11.3.2哈密尔顿图的必要条件，定理11.3.1设置无向图G=哈密尔顿图(有哈密尔顿环)，V1是V的任何非空子集，那么p(G-V1)|V1|推论对于V的任何非空子集V1，都有p(G-V1)|V1| 1。定理11.3.1给出了哈密尔顿图的一个必要条件，而不是一个充分条件。其他逆否命题是非常有用的：如果存在v的非空子集V1，使得p (g-v1) | v1 |，则g不是哈密顿图。2020/6/9，例11.3.2，证明图中没有哈密顿回路。分析并使用定理11.3.1的逆no命题来寻找v的非空子集V1，使得p (g-v1) | v1 |，那么g不是哈密尔顿图。发现v1=d，e，f符合要求。证明了在图中，删除节点d，e，f的子集会产生一个有4个连通分支的新图。从定理11.3.1可知，图不是哈密尔顿图，因此不存在哈密尔顿环。2020/6/9，哈密尔顿图的充分条件，定理11.3.2让G=是具有n个节点的简单无向图。如果任意两个不相邻的节点u，vV有deg(u) deg(v)n-1，则在G中有一个哈密顿路径。推论11.3.2设G=是一个有n个节点的简单无向图。如果任意两个不相邻的节点u，vV有deg(u) deg(v)n，则G中有一个哈密尔顿环。推论11.3.3设G=是一个有n个节点的简单无向图，n3。如果对于任何vV，有度(v)n/2，则G是哈密顿图。应该注意，定理11.3.2给出了哈密尔顿图的一个充分条件，而不是一个必要条件。在六边形中，任意两个不相邻节点的度数之和是4 6，但六边形是哈密顿图。2020/6/9，例11.3.3，一个地方有5个景点，如果每个景点有2条道路与其他景点相连。询问游客他们是否能通过每个景点一次来完成这五个地方。该方案将五个景点看作一个有五个节点的无向图，两个景点之间的道路作为无向图的边。因为每个点有两条路与其他节点连通，所以每个节点的度数是2，所以任何两个不相邻节点的度数之和等于4，这正好是和点之和减去1的和。因此，图中有一条哈密尔顿路径，所以游客只需穿过每个景点一次，就可以游过这五个地方。2020/6/9，有向图上的哈密尔顿路径，设G=是一些具有n(n2)个节点的简单有向图。如果忽略g中边的方向得到的无向图包含生成的子图完全图Kn，那么在有向图g中有一个哈密顿路径。在右图中，其对应的无向图包含完全图K5，这从定理11.3.3可知。该图包含哈密尔顿路径。事实上，路径v3v5v4v2v1是哈密尔顿路径。2020/6/9，11.3.3哈密尔顿图分段，只有哈密尔顿路径但没有哈密尔顿环的图不是哈密尔顿图；没有简单的判断定理来判断图中是否存在欧拉路径和欧拉路径图。我们只能凭经验判断节点较少的图。哈密尔顿图中有一个定理，它只是一个必要条件。必要条件的正态性不能用来判断一个图是否是哈密顿图。这时，定理是无用的，但等价逆陈述的必要条件是非常重要的。使用这个逆命题，人们可以判断一个图是否不是哈密尔顿图。2020/6/9，11.3.4哈密顿图的应用，1。旅行商问题G=是一个有n个节点的加权完全图，其中V=V1，V2，VN是一组城市，E是一组连接城市的道路，W是从E到一组正实数的函数(即，W(vi，vj)是城市vi和vj之间的距离)，尝试找出加权图上的最小权重(距离)哈密尔顿环。2020/6/9，11.4偶图，11.4.1偶图的定义11.4.1如果无向图G=的节点集V可以分成两个子集V1，V2，V1；V2=，和V1V2=V，这样G的任一边的两个端点，一个属于V1，另一个属于V2，那么G称为二部图或二部图。V1和V2被称为互补节点子集，甚至图通常被表示为G=。偶图没有自循环。普通图和零图可视为特殊偶图。2020/6/9，定义11.4.2。在偶图G=中，如果的每个节点都有且只有一条边与的每个节点相关联，则偶图G被称为完全偶图或完全二部图，并被表示为Ki，j，其中i=|V1|，j=|V2|。2020/6/9，例11.4.1，判断图中的几个图，哪些是偶数图？那些是完整的二部图吗？偶数图，偶数图，偶数图，偶数图，非偶数图，完全偶数图K2，3，完全偶数图K3，3，完全偶数图K3，3，2020/6/9，11.4.2偶数图判定，定理11.4.1无向图G=是偶数当且仅当G的所有环的长度是偶数。直觉理解：两个方向都有，无向图g甚至不是图。充要条件是G中存在奇数长度的环，2020/6/9，11.4.3匹配，偶数图中定义11 . 4 . 2G=V1= v1，V2，vq，如果有子集E=(v1，v1 )，(V2，v2 )，(vq，VQ)，其中v1，v2，vq 是v2中的q个不同节点，那么G的子图G=是从v1到v2的完全匹配，这只是一个匹配。2020/6/9，必要条件。在偶数图G=，如果V1到V2有一个单极性f，那么对于任何vV1都有(v，f(v)E，那么V1和V2之间有一个匹配。根据单态的性质，不是所有的偶图都有匹配，匹配的必要条件是|V1|V2|。然而，这个条件是不够的。2020/6/9，示例11.4.2，以下3个偶数图中哪一个具有V1到V2匹配？给出了具有匹配的偶图的匹配。没有匹配，没有匹配，有匹配，2020/6/9，霍尔定理，定理11.4.2(霍尔定理)偶数图G=中从V1到V2匹配的充要条件是，V1的任何k个节点至少与V2的k个节点相邻，k=1，2，| v1 |。定理11.4.2中的条件通常被称为多样性条件。例如，2020/6/9不满足各向异性条件，因此不存在匹配。满足各向异性的条件，所以有一个匹配，2020/6/9，定理11.4.3，让G=是一个偶图。如果满足条件(1)V1，每个节点至少与T条边相关联；(2)V2中的每个节点最多与T个边相关联；然后是从V1到V2的比赛，t是正整数。定理11.4.3中的条件通常称为t条件。判断T条件很简单，只需计算V1的最小节点度和V2的最大节点度。，2020/6/9，11.5平面图，11.5.1平面图定义将在电路板布线中找到，不仅需要允许每条边在节点处相交，而且还应该允许每条边在某个非节点点处相交，这样的点称为交叉点；相交的边称为交叉边。2020/6/9，定义11.5.1。如果无向图G的所有节点和边都可以画在一个平面上，这样除了公共节点之外，任何两条边之间都没有其他交点，G称为平面图，否则G称为非平面图。当且仅当图的每个连通分支都是平面图时，图才是平面图。应该注意的是，它的一些边缘在表面上是交叉的，但不能确定它不是平面图。平面图，2020/6/9，非平面视图，无论如何改变一些图形，除了节点，总有边交叉。也就是说，无论如何改变图形，至少一条边与其他边相交，所以它是非平面图形。2020/6/9，11.5.2观察，让G为在平面上画出的图形，并让C=V1.V2.V3.V4.V1是g中的任何一个基本环。另外，让P1=V1.V3和P2=V2.V4是G中没有公共节点的任何两条基本路径。观察方法，2020/6/9，示例11.5.1。观察方法用于确定图K3、3和3是非平面视图。2020/6/9，11.5.3欧拉公式，它定义了11.5.2在平面图G的平面表示中，由不包含图的节点和边的边包围的区域称为G的曲面，由包围曲面的边形成的环称为曲面的边界，曲面的边界的长度称为曲面的度数，并表示为D(r)。面积有限的面称为