6.7 对偶图、着色与二部图

06图论GRAPHTHEORY6.7对偶图、着色与二部图Duality,GraphColoring&BipartiteGraphsADVANCEDMATHEMATICS&COMPUTERSCIENCE|CORECONCEPTS目录CONTENTS016.7.1对偶图对偶图的概念、定义与自对偶图。理解平面图中面与顶点的一一对应关系，探索图论中的对称性与变换。026.7.2着色及其应用深入探讨著名的四色定理，掌握图的着色方法与算法，并分析其在地图绘制与资源分配中的实际应用价值。036.7.3二部图学习二部图的定义与判定定理，研究最大匹配问题，了解其在任务分配、人员调度及匹配推荐系统中的广泛应用。6.7.1对偶图定义6.30：对偶图(DualGraph)给定平面图G=<V,E>，它具有面F1，F2，…，Fn，若有图

G*=<V*,

E*>满足下述三个条件，则称图

G*

是图G

的对偶图：面→顶点的映射对于图G的任一个面Fi，在其内部有且仅有一个结点vi*

∈

V*与之对应。公共边→边的映射对于图G的面Fi，Fj的公共边界ek，存在且仅存在一条边ek*

E*，使ek*=(vi*,vj*)，且ek*与ek相交。割边→环的映射当且仅当ek只有一个面Fi的边界时，vi*存在一个环ek*和ek相交。对偶图示例右图直观展示了平面图G及其对偶图G*的构造逻辑。在图论中，对偶变换是将原图的“面”转化为“点”、“边”转化为“边”的重要拓扑方法。原图G(Graph)采用黑色实线与空心圆圈表示，代表原始的平面连通图结构，包含顶点、边和面。对偶图G*(DualGraph)采用红色虚线与实心圆点表示，是基于原图面与边的关系重新构造出的新图。构造对应法则1.原图的每个“面”对应对偶图的一个“顶点”。2.原图的每条“边”对应对偶图的一条“边”。图示：平面图G(黑)与对偶图G*(红)的映射关系包含了内部面与外部面（无限面）的完整映射定义6.31：自对偶图定义内容如果图G的对偶图G*同构于G，则称G是自对偶图。这意味着图在进行对偶变换操作后，其顶点和边的连接结构保持不变，展现了图结构的高度对称性与特殊性。典型示例图6.57（示例）：该图即为一个标准的自对偶图其最显著的特征是：将该图的对偶图绘制出来后，在不计顶点标号的情况下，其顶点数、边数及连接方式与原图完全一致，二者结构上没有本质区别。6.7.2着色及其应用着色问题的起源：四色猜想核心问题对任意平面或球面地图，若要求相邻国家（有共同边界）必须着以不同颜色，最少需要多少种颜色即可完成着色？19世纪50年代格色里(Guthrie)在绘制英国地图时提出著名的“四色猜想”。1890年希伍德(Hewood)虽未能证明四色猜想，但成功证明了“五色定理”。1976年阿佩尔&黑肯借助电子计算机运行1200小时，最终证明“四色定理”。地图着色示例：相邻区域使用不同颜色进行区分定义6.32&6.33：正常着色与色数定义6.32图的正常着色图G的正常着色(或简称着色)，是指对它的每一个结点指定一种颜色，使得没有两个邻接的结点有同一种颜色。定义6.33图的色数对于图G着色时，需要的最少颜色数称为G的色数，记作X(G)。证明思路证明色数为n的两步法1.证明用n种颜色可以正常着色该图（可行性）。2.证明用少于n种颜色无法正常着色该图（必要性）。定理6.20：四色定理(FourColorTheorem)核心结论任何平面图的顶点着色数都不超过4。适用范围限制该定理仅适用于平面图。若地图对应的图结构含有交叉的边（非平面图），则四色限制不再成立。非平面图的情况对于非平面图，着色数没有上限，理论上可以构造出任意大的色数的图。里程碑式的证明该定理的最终证明（1976年）首次大规模依赖计算机辅助，分析了海量子图情形，总计算耗时超过1200小时。韦尔·奇鲍威尔(WelchPowell)着色方法01排序顶点对图中的每个结点，按照其度数（连接的边数）从高到低进行递减排序。02贪心着色使用第一种颜色，先为排序后的第一个结点着色。随后，依次检查列表中的每个点，只要与之前已着此色的点不相邻，便着同样的颜色。03循环直至完成换用第二种颜色，对所有尚未着色的结点重复执行第二步操作。持续此过程，直到图中的全部顶点均被成功着色。例题6.23：应用韦尔·奇鲍威尔方法着色问题描述利用韦尔·奇鲍威尔(Welch-Powell)算法，对下图中的无向图进行正常着色。01求度数计算并求出图中每一个结点的度数。02降序排列将所有结点按度数从高到低进行排序。03按规则涂色依次用颜色给序列首结点及所有非邻接结点着色，循环至完成。结论：如图6.58所示的图，经过韦尔·奇鲍威尔算法着色，仅需三种颜色即可完成正常着色。图6.58：韦尔·奇鲍威尔方法着色示例图定理6.21：完全图的色数定理内容对于n个结点的完全图Kn，其色数满足：X(Kn)=n。必要性(Necessity)完全图的定义决定了任意两个顶点都直接相邻，因此任何两个顶点都无法被分配相同的颜色。基于此，给Kn着色至少需要n种颜色。充分性(Sufficiency)反之，如果我们为图中每一个顶点都分配一种独一无二的颜色，显然可以满足着色要求。这说明n种颜色也足够对Kn进行着色。图示：完全图\(K_5\)的着色图中展示了5个顶点的完全图，由于每两个顶点都相邻，所以每个顶点都必须分配不同的颜色，总共使用了5种颜色，直观验证了定理结论。定理6.22&6.23：平面图的性质定理6.22：平面图的结点度数性质定理内容：设G为一个至少具有三个结点的连通平面图，则G中必有一个结点u，使得deg(u)≤5。定理6.23：五色定理(FiveColorTheorem)定理内容：任意简单连通平面图G最多是5色的。即对任何平面图进行点着色，使用5种颜色就足够了。核心证明思路利用数学归纳法结合定理6.22：假设所有n-1个顶点的平面图都可5着色，对n个顶点的图G，由定理6.22可知G中存在度数≤5的顶点v。删去v后对剩余部分着色，最后为v寻找一种可用的颜色。应用案例：例题6.24考试安排核心问题如何科学地安排期末考试时间，才能确保没有任何学生需要在同一时间段参加两门不同的考试？图论建模转换•顶点(Vertex)：代表需要安排的各个科目。•边(Edge)：若有至少一名学生同时选修了两门科目，则在这两个顶点间连一条边。•颜色(Color)：每一种颜色代表一个独立的考试时间段。解决方案与结论将考试安排问题转化为对上述图的着色问题。该图的色数，即为安排所有考试所需的最少时间段数量。应用案例：例题6.25频率分配▍问题描述需要为本地区的多家电视台分配广播频道。关键约束是：任何两家距离在150里以内的电视台不能使用相同的频道，以避免信号干扰。▍图模型抽象•顶点(Vertex):代表每一个需要分配频道的电视台。

•边(Edge):若两个电视台的距离在150里以内，则在代表它们的顶点间连一条边。

•颜色(Color):代表可供选择的不同广播频道。▍解决方案将问题转化为图着色问题：对图进行着色，确保相邻顶点颜色不同，即为合法的频道分配方案。6.7.3二部图定义6.34：二部图与完全二部图二部图(BipartiteGraph)若能将无向图G=<V,E>的结点集V划分为两部分V1和V2，满足条件V1∪V2=V，V1∩V2=∅，使得G中任一条边的两个端点，一个属于V1，另一个属于V2，称G是二部图(也称为偶图、二分图)，V1和V2称为互补结点子集，将G记为G=<V1,V2,E>。完全二部图(CompleteBipartiteGraph)在简单二部图的基础上，若满足更强的连通条件：•若V1中任一结点与V2中所有结点有且仅有一条边相关联。记法：若|V1|=n，|V2|=m，则该完全二部图记作

Kn,m。二部图与非二部图示例二部图(BipartiteGraph)图中的所有顶点可以被划分成两个互不相交的独立集合。图中的每一条边，都只能连接不同集合中的两个顶点，而同一个集合内部的顶点间不存在边。非二部图(Non-bipartiteGraph)图中存在长度为奇数的回路（奇环），这使得顶点无法被划分成满足二部图定义的两个独立集合。奇环是判定一个图不是二部图的充要条件。定理6.24：二部图的判定定理定理内容一个无向图\(G=<V,E>\)是二部图，当且仅当G中所有回路的长度均为偶数。逆否命题（常用）无向图G不是二部图的充分必要条件是，G中存在长度为奇数的回路。匹配的概念与应用典型场景：二部图分配以“工人与任务分配”为例：将工人和任务分为两个互不相交的顶点集合，工人之间无关联，任务之间也无关联，所有的连接边都只存在于“工人”与“任务”两个集合之间，形成典型的二部图结构。核心定义：匹配(Matching)在二部图中找到一个边的子集，使得集合中任意两条边都没有公共的顶点。通俗地说，就是每个工人最多分配一个任务，且每个任务也只能分配给一个工人。图示说明：右图展示了一种有效的任务分配方案，即原图的一个“匹配”。图中蓝色的连线就构成了一个匹配集合。定义6.35：完备匹配与完全匹配定义内容：设G=<V1,V2,E>是一个二部图，M是G中的一个最大匹配，若|M|=min{|V1|,|V2|}，则称M是G的一个完备匹配。•完备匹配是图论中衡量匹配覆盖能力的重要概念，它保证了较小顶点集的所有顶点都能被匹配到。从V1到V2

的完备匹配当顶点集满足|V1|≤|V2|时，称M是从V1到V2的一个完备匹配。此时V1的所有顶点都被匹配，而V2

可能有未被匹配的顶点。完全匹配(PerfectMatching)当顶点集满足|V1|=|V2|时，称M是G的一个完全匹配。此时图中的每一个顶点都被匹配，是一种特殊且完美的完备匹配。核心本质：匹配问题的数学本质，是在二部图的两个顶点集合之间寻找一个满足条件的单射(InjectiveFunction)。定理6.25：Hall定理（相异性条件）▍定理内容(Hall'sMarriageTheorem)设二部图

G=<V1,V2,E>，|V1|≤|V2|，G中存在从

V1到

V2的完备匹配，当且仅当

V1中任意

k(k=1,2,

…,|V1|)个结点至少邻接

V2中

k个结点。算法复杂度分析虽然Hall定理给出了完美匹配的充要条件，但直接通过枚举所有子集来验证的复杂度是指数级。在实际应用中，我们通常采用效率更高的算法，如匈牙利算法，来求解最大匹配。定理6.26：t条件定理内容设二部图G=<V1,V2,E>，若满足：(1)V1中每个结点至少关联t(t>0)条边；(2)V2中每个结点至多关联t条边。结论：则图G中必存在从V1

到V2的完备匹配。核心说明：t条件是判断二部图存在完备匹配的充分条件（而非必要条件）。这意味着满足t条件一定存在完备匹配，但存在完备匹配的二部图不一定满足t条件。例题6.26：应用案例——课外小组组长选拔问题背景：某学校开设了物理、化学、生物3个课外小组，现有张、王、李、赵、陈5位同学报名。在三种不同的成员构成和报名意愿下，我们能否为每个小组选