二部图欧拉图哈密尔顿图平面图教学课件

二部图·欧拉图哈密尔顿图·平面图离散数学·第6章特殊的图Contents课程目录图论核心专题概览——从匹配理论到平面嵌入，系统梳理四大经典问题。01二部图与匹配理论02欧拉图与欧拉回路03哈密尔顿图与哈密尔顿回路04平面图与平面嵌入CHAPTER01二部图与匹配理论从顶点划分到完备匹配，掌握二部图的结构特征与判定方法GraphTheory二部图的定义二部图的本质是顶点集的二划分：将V分为互补子集V1与V2，使得每条边跨子集连接。这一结构特征使二部图成为建模"两类对象之间关系"的天然工具，如人与岗位、学生与课程。01设无向图G=<V,E>，若V可划分为V1与V2（V1∪V2=V,V1∩V2=∅），使每条边的两端点分属不同子集，则G为二部图V1∩V2=∅02完全二部图Kr,s：V1中每个顶点均与V2中每个顶点相邻，其中r=|V1|,s=|V2|，是完全二部图的参数化表达Kr,s03n阶零图（无边图）满足二部图定义的平凡情形，因为不存在违反跨子集连接条件的边平凡情形04二部图记为<V1,V2,E>，V1和V2称为互补顶点子集，这一记法直接体现了顶点划分结构<V1,V2,E>二部图板书示意·V1与V2的跨子集连接GraphTheory二部图的判定定理无向图G是二部图当且仅当G中无奇圈（奇数长度的回路）。这一定理将二部图的顶点划分问题转化为回路长度的奇偶性检验，提供了简洁有效的判定手段。01Theorem无向图G=<V,E>是二部图当且仅当G中不存在奇数长度的回路，即所有回路长度均为偶数。这是二部图的本质特征。无奇圈02Necessity二部图的边只能在V₁与V₂之间交替，任何回路从V₁出发经V₂再回V₁，步数必为偶数。奇圈将破坏二分结构。交替回路03Sufficiency取顶点u，按d(v,u)的奇偶性划分V₁和V₂，若同子集内存在相邻点则构成奇圈，与前提矛盾。故划分有效。距离划分04Algorithm对图进行BFS/DFS着色，若能成功二着色（相邻顶点不同色），则该图为二部图。算法时间复杂度为O(|V|+|E|)。二着色BIPARTITEGRAPHS二部图的判定实例通过具体图例验证判定定理：能成功二着色的图为二部图，包含奇圈的图则不是。K_n（n≥3）因包含三角形（奇圈）而非二部图，但路径图、偶圈图、树等均为二部图。完全图K_nK3（三角形）含长度为3的奇圈，无法二着色，因此不是二部图；推广可知K_n（n≥3）均非二部图n≥3圈图C_n偶圈C_{2k}长度为偶数，可交替着色为两组，是二部图；奇圈C_{2k+1}含奇圈本身，不是二部图C_{2k}树树是特殊的二部图：树中无回路（自然无奇圈），按层次奇偶性即可完成二划分无回路完全二部图K_{r,s}本身即为二部图的典型构造，其边数为r×s，所有边均跨子集连接r×sGRAPHTHEORY·MATCHING匹配的基本概念匹配是图中互不相邻的边子集，从极大匹配到最大匹配再到完美匹配，约束逐级增强。完美匹配要求所有顶点均被覆盖，是最强的匹配形式，但并非所有图都存在完美匹配。匹配图G中任两条边均不相邻的边子集M，即M中任意两边无公共端点边独立集极大匹配在M基础上添加任何一条边都不再是匹配，局部最优但未必边数最多局部最优最大匹配所有匹配中边数最多的匹配，边数记为β1(G)，代表匹配能力上界β1(G)完美匹配每个顶点都是M的饱和点，要求图的顶点数为偶数全顶点覆盖饱和点顶点v与M中某条边关联则为饱和点，否则为非饱和点v∈MGraphTheory·Matching二部图中的完备匹配完备匹配是二部图特有的匹配概念：当|V₁|≤|V₂|时，若V₁中所有顶点均为匹配M的饱和点，则M为V₁到V₂的完备匹配。它是实际分配问题的数学模型基础。完备匹配定义—设G=<V₁,V₂,E>且|V₁|≤|V₂|，若最大匹配M使V₁中每个顶点都是M饱和点，则M为V₁到V₂的完备匹配完美匹配等价—当|V₁|=|V₂|时，完备匹配即为完美匹配，此时V₁和V₂的顶点全部被覆盖，无剩余存在前提—完备匹配要求|V₁|≤|V₂|，即被分配方数量不超过目标方数量，否则不可能全覆盖实际建模—将人员集合设为V₁、岗位集合设为V₂，边表示"胜任关系"，完备匹配即为每人分配一个胜任岗位的方案GRAPHTHEORY·MATCHINGHall定理与完备匹配判定Hall定理给出了二部图完备匹配存在的充要条件——相异性条件：V1中任意k个顶点至少邻接V2中k个顶点。t条件则提供了更简便的充分条件，只需比较V1的最小度数与V2的最大度数。01Hall定理G=<V1,V2,E>中存在V1到V2的完备匹配，当且仅当V1中任意k个顶点至少与V2中k个顶点相邻（k=1,2,...,|V1|）这是判定完备匹配存在的核心定理，具有理论完备性02相异性条件V1的任意子集S，其邻域N(S)满足|N(S)|≥|S|，即"能选的目标不少于选人数量"直观理解：不存在"人多坑少"的瓶颈子集03t条件（充分条件）若V1中每个顶点至少关联t条边，V2中每个顶点至多关联t条边，则完备匹配必然存在t条件比Hall条件更易验证，是实用的充分判定准则04简便验证仅需计算δ(V1)≥Δ(V2)，即V1的最小度数不小于V2的最大度数即可判定δ表示最小度数，Δ表示最大度数，计算简便高效APPLICATION二部图匹配的应用实例二部图匹配理论可直接建模"分配与调度"类问题：将需求方与供给方分别置于V1和V2，按约束建边后用Hall定理或t条件判断可行性，从而将实际问题转化为图论判定。01人员派遣问题5人(a,b,c,d,e)选3人分赴上海、广州、香港，a只去上海、b只去广州、c/d/e可去广州或香港令V1={上海,广州,香港},V2={a,b,c,d,e}，按偏好建边后验证满足相异性条件，完备匹配为a→沪,b→穗,d→港02组长选拔问题3个课外小组（物理/化学/生物）从5名学生中选3位不兼职组长，分三种成员组成情况讨论情况(1)满足t条件存在完备匹配；情况(2)不满足t条件；情况(3)不满足相异性条件，无法选拔Chapter02欧拉图与欧拉回路从哥尼斯堡七桥问题出发，研究"一次走遍所有边"的图论条件GraphTheory·Euler欧拉通路与欧拉回路的定义欧拉通路要求经过每条边恰好一次（起点终点可不同），欧拉回路则要求回到起点。存在欧拉回路的图称为欧拉图。这一概念解决的核心问题是"能否一笔画完所有边"。哥尼斯堡七桥问题—欧拉图论的起源01欧拉通路—经过图中每条边恰好一次的通路，起点与终点可以不同，是一条简单通路02欧拉回路—经过图中每条边恰好一次的回路，起点与终点相同，是一条简单回路03欧拉图—存在欧拉回路的图称为欧拉图，必然也存在欧拉通路（回路本身即是通路）04适用范围—定义对无向图和有向图均适用；平凡图被规定为欧拉图；环不影响图的欧拉性定理6.8·推论无向图欧拉图的判定定理连通且全偶度则有欧拉回路；恰两奇度顶点则有通路无回路；否则均不存在。01欧拉回路充要条件无向图G具有欧拉回路，当且仅当G连通且无奇度顶点——所有顶点度数均为偶数。02欧拉通路条件有欧拉通路但无回路，当且仅当G连通且恰有两个奇度顶点，分别为通路的起点与终点。03判定推论G是欧拉图⟺G连通且无奇度顶点，给出了判断欧拉图的简洁充要条件。04直觉理解经过每个顶点需"一进一出"消耗两条边，故偶度数是形成回路的必要条件。EULERIANDIGRAPH有向图欧拉图的判定定理有向图D是欧拉图当且仅当D连通且所有顶点入度等于出度。有向图的判定将无向图的'偶度数'条件推广为'入度=出度'，保持了'进出平衡'的核心思想。01定理6.9有向图D有欧拉回路当且仅当D连通且所有顶点的入度等于出度入度=出度02欧拉通路有欧拉通路但无回路：恰有一个顶点入度比出度大1（终点），一个入度比出度小1（起点），其余入度=出度起点→终点03推论有向图D是欧拉图⟺D连通且所有顶点入度=出度，与无向图判定形成对称结构⟺对称04对比无向图看度数奇偶性，有向图看入度与出度的平衡性，本质都是"进出守恒"进出守恒GRAPHTHEORY欧拉图判定实例分析通过实例验证欧拉图判定流程：先检验连通性，再统计奇度顶点数——0个为欧拉图、2个有欧拉通路、其他情况两者皆无。判定流程第一步检查图的连通性，不连通则直接排除；第二步统计奇度顶点数量进行分类判定。该流程是判断一笔画问题的标准方法。连通性检验奇度统计2-STEPMETHOD欧拉图所有顶点均为偶度且图连通时，存在欧拉回路。可从任一顶点出发，遍历每条边恰好一次后回到起点，实现真正的一笔闭合回路。闭合回路任意起点0奇度顶点欧拉通路恰有两个奇度顶点且图连通时，存在欧拉通路但无回路。必须从一个奇度顶点出发，在另一个奇度顶点结束，路径不闭合。开放路径奇度起止2奇度顶点两者皆无奇度顶点数为1、3、4或更多时，既无欧拉回路也无欧拉通路。此类图无法一笔画完，必须中断或重复经过某些边才能完成遍历。不可一笔画需重复边≥3奇度顶点APPLICATIONS&ALGORITHMS欧拉图的应用与构造算法欧拉图理论直接服务于一笔画问题和中国邮递员问题等实际场景。Fleury算法通过"避免桥边"的策略构造欧拉回路，是求解欧拉通路的经典方法。中国邮递员问题的现实应用背景01一笔画问题判断图形能否不抬笔、不重复地画出来，本质是判断该图是否存在欧拉通路或回路02Fleury算法核心从任一顶点出发逐步选边行走，除非别无选择，否则不走桥边——即删去后使图不连通的边03中国邮递员问题邮递员需走遍所有街道后回到邮局，若街道图为欧拉图则最优路线恰好经过每条路一次04非欧拉图转化当图有欧拉通路但非欧拉图时，添加重复边使所有顶点变为偶度，转化为欧拉图求解最优环游CHAPTER03哈密尔顿图与哈密尔顿回路探索"一次走遍所有顶点"的条件，理解NP完全问题的图论原型GraphTheory哈密尔顿通路与哈密尔顿回路的定义哈密尔顿通路/回路要求经过每个顶点恰好一次，与欧拉图的"经过每条边恰好一次"形成对偶，但判定远比欧拉问题困难，是NP完全问题的经典原型。正十二面体—哈密尔顿图的经典案例哈密尔顿通路经过图中每个顶点恰好一次的通路，关注顶点覆盖而非边覆盖哈密尔顿回路经过每个顶点恰好一次的回路（起点出现两次），是"周游"问题的数学抽象哈密尔顿图存在哈密尔顿回路的图，正十二面体图是其经典案例核心差异欧拉图有多项式判定算法（检查度数），哈密尔顿图判定为NP完全问题，无简洁充要条件GraphTheory·NecessaryCondition哈密尔顿图的必要条件若G是哈密尔顿图，则对V的任意非空真子集S，有W(G-S)≤|S|。此条件常用于反证法——找到使不等式不成立的S即可证明非哈密尔顿图。01定理表述若G是哈密尔顿图，则对V的任意非空子集S，W(G-S)≤|S|，其中W(G-S)为删去S后的连通分支数。该条件是判断哈密尔顿图的必要条件而非充分条件。W(G−S)≤|S|02证明思路哈密尔顿回路C经过S中每个顶点时最多连接两个分支，故C−S的分支数≤|S|，而G−S的分支数≤C−S的分支数，由此推出原不等式成立。C−S连通分支03反证法应用找到某个S使W(G-S)>|S|，即可判定G不是哈密尔顿图。这是最常用的"排除法"，在图论证明中具有重要实用价值。排除法04彼得森图PetersenGraph去掉特定5个顶点后产生超过5个连通分支，证明其不是哈密尔顿图。这是该必要条件最经典的反例之一。5顶点反例HAMILTONIANGRAPH·SUFFICIENTCONDITIONS哈密尔顿图的充分条件Dirac定理和Ore定理给出了哈密尔顿图的两个经典充分条件：最小度≥n/2或不相邻顶点度数之和≥n均可保证哈密尔顿回路存在。但这些条件非必要——不满足时图仍可能是哈密尔顿图。01Dirac定理n阶简单图（n≥3），若每个顶点度数δ(G)≥n/2，则G是哈密尔顿图。δ(G)≥n/202Ore定理n阶简单图（n≥3），若任意两个不相邻顶点u、v满足deg(u)+deg(v)≥n，则G是哈密尔顿图。deg(u)+deg(v)≥n03Dirac是Ore的推论δ≥n/2时，任意不相邻两点度数之和≥n/2+n/2=n，自然满足Ore条件。Dirac→Ore04充分非必要完全图K_n（n≥3）满足条件；偶圈C_6不满足δ≥n/2却仍是哈密尔顿图。K_n∨C_6HamiltonianGraphApplication哈密尔顿图的应用：旅行商问题旅行商问题（TSP）是哈密尔顿回路问题的经典应用：在赋权完全图中寻找最短哈密尔顿回路。作为NP难问题的代表，TSP在物流配送、电路板布线、基因测序等领域有广泛应用。TSP问题定义推销员访问n个城市后回到起点，每城恰访一次，求最短路线——即在赋权完全图中找最短哈密尔顿回路计算复杂度精确求解需遍历(n-1)!/2条回路，计算量呈阶乘级增长，属于NP难问题近似算法策略最近邻法、最小生成树法、Christofides算法等可在多项式时间内给出近似最优解实际应用领域物流路径规划、电路板钻孔优化、DNA片段组装、天文望远镜调度物流配送中的路线规划是旅行商问题的典型应用场景GraphTheory·Comparison欧拉图与哈密尔顿图的系统对比欧拉图与哈密尔顿图虽结构对称，但理论完备性差异巨大：前者有充要条件和多项式算法，后者仅有必要/充分条件且判定为NP完全。这揭示了'边遍历'与'顶点遍历'在计算复杂性上的本质不同。欧拉图CoreProblem经过每条边恰好一次，关注边的遍历Condition充要条件：连通且无奇度顶点（无向图）或入度＝出度（有向图），可在多项式时间内判定AlgorithmFleury算法可有效找出欧拉回路，时间复杂度O(|E|²)哈密尔顿图CoreProblem经过每个顶点恰好一次，关注顶点的遍历Condition仅有必要条件（W(G-S)≤|S|）和充分条件（Dirac/Ore定理），无已知充要条件ComplexityNP完全问题，精确求解需指数时间，实际应用依赖近似算法CHAPTER04平面图与平面嵌入研究图的无交叉绘制条件，掌握欧拉公式与库拉托夫斯基定理GRAPHTHEORY·DEFINITIONS平面图与平面嵌入的定义平面图是能在平面上无交叉边绘制的图，其无交叉的具体画法称为平面嵌入。平面图性是图的拓扑不变量——同一图的不同平面嵌入本质等价，且任何面均可作为外部面。平面图若图G能除顶点外边不相交地画在平面上，则称G为平面图。这一性质刻画了图的内在拓扑特征，与具体画法无关，是图论中判断图结构复杂度的基本标准。可平面性平面嵌入将平面图实际画出的无边交叉图形称为G的一个平面嵌入，是平面图的具体几何实现。同一平面图存在无穷多种嵌入方式，它们通过球极投影相互转化。几何实现非平面图无论如何绘制都无法避免边交叉的图称为非平面图。完全图K₅和完全二分图K₃,₃是两个最基本的非平面图实例，任何含它们作为收缩子图的图均非平面。K₅·K₃,₃平面嵌入的等价性同一平面图可有不同嵌入方式，任何面均可被选为外部面。内外面的区分不是本质的，这种等价性揭示了平面图的深层拓扑性质，是研究图曲面嵌入的基础。拓扑不变量GRAPHTHEORY平面图的面与面的次数平面嵌入将平面划分为若干面（含一个外部面），每个面的次数为其边界长度。所有面的次数之和等于2|E|，与顶点度数的握手定理形成完美对偶，是推导欧拉公式的基础。01面的定义平面嵌入将平面划分的区域称为面，无界区域为外部面R₀，有界区域为内部面R₁,R₂,…02面的次数deg(R)围绕面R的边界走一圈所经过的边数，桥边（割边）在边界上计算两次03面的次数之和定理Σdeg(Rᵢ)=2|E|，每条边恰好属于两个面的边界（或同一面边界上出现两次），与顶点握手定理对偶04实例分析一个有4个面、7条边的平面图，各面次数之和=2×7=14，可据此验证平面嵌入的正确性GraphTheory·Euler欧拉公式及其推论欧拉公式V-E+R=2揭示了连通平面图的顶点、边、面之间的拓扑不变量关系。由此推导出的E≤3V-6不等式是判定非平面图的重要工具，也是图着色理论的基础。欧拉公式连通平面图满足V−E+R=2，其中V为顶点数、E为边数、R为面数（含外部面）V−E+R=2证明思路对树（R=1,E=V−1），公式成立；每添加一条非树边增加恰好一个面，V−E+R值不变归纳法推论1·简单平面图若V≥3，则E≤3V−6；因每个面的次数≥3且Σdeg(Ri)=2E，代入欧拉公式即得E≤3V−6推论2·无三角形平面图若V≥3且无三角形（无C3），则E≤2V−4；因每个面的次数≥4E≤2V−4GRAPHTHEORY·NON-PLANARITYK5与K3,3的非平面性证明利用欧拉公式推论可优雅地证明K5和K3,3的非平面性：K5违反E≤3V-6（10>9），K3,3作为无三角形图违反E≤2V-4（9>8）。这两个图构成了库拉托夫斯基定理的核心。COMPLETEGRAPHK5的非平面性VerticesV=5EdgesE=10按推论E≤3V−6=9，但实际E=10>9，产生矛盾，故K5不是平面图。K5是阶数最小的非平面完全图；K4（V=4,E=6,3V−6=6）恰好满足条件，仍为平面图。10>9矛盾→非平面BIPARTITEGRAPHK3,3的非平面性VerticesV=6EdgesE=93V−6=12虽然满足，但K3,3是无三角形的二部图，须用更强推论E≤2V−4=8，而9>8矛盾。K3,3和K5一起构成所有非平面图的"基本障碍"——库拉托夫斯基定理的核心构件。9>8矛盾→非平面GRAPHTHEORY·PLANARITY库拉托夫斯基定理库拉托夫斯基定理给出了平面图的充要条件：图G是平面图当且仅当G不含与K₅或K₃,₃同胚的子图。这一定理将所有非平面图归结为两个基本障碍，是图论中最优美的定理之一。01定理表述图G是平面图⟺G不包含与K₅或K₃,₃同胚的子图（也称"库拉托夫斯基子图"）02同胚的概念两个图若可通过在边上反复插入或删除2度顶点而互相转化，则称它们同胚03实际判定方法在图中寻找可收缩为K₅或K₃,₃的子结构——找到即为非平面图，找不到则为平面图04定理意义将无穷多种非平面图归结为K₅和K₃,₃