离散数学 课件 第6章 图论

CHAPTER06图论6.1图的基本概念BasicConceptsofGraphs目录CONTENTS01图的基本定义和分类图的定义、阶、无向图、有向图、混合图02度数和握手定理结点度数、握手定理及其推论03完全图、补图、子图完全图、补图、子图和生成子图的定义04图的同构图同构的定义、必要条件和判定6.1.1图的基本定义和分类定义6.1：图的数学定义一个图G是一个三元组(V(G),E(G),φG)，其中V(G)是一个非空的结点集合，其元素称为结点(Vertex)；E(G)是边集合，其元素称为边(Edge)；

φG

是关联函数，用于将边集合E中的每一条边映射到结点的无序偶（无向边）或有序偶（有向边）集合上。💡关键特征说明图的本质是结点之间的连接关系，而与几何上的连线长度、曲直以及结点的具体位置无关。在图论研究中，我们只关注“哪些点是相连的”，而非“它们看起来长什么样”。图的阶与图形表示图的阶(OrderofaGraph)设图G的顶点集为V，边集为E。若|V|=n，|E|=m，则称图G为(n,m)图。在图论中，一个图的“阶”是一个基础且核心的概念，它严格定义为图中包含的顶点(结点)的总个数|V|。例如，一个拥有5个顶点的图，我们称之为“5阶图”。图形表示的不唯一性图的本质是顶点与边的关联关系，而不是其在平面上的几何画法。同一个抽象的图，可以对应多种不同的图形外观，我们称其为同构图。图6.3：同一抽象图的两种不同几何画法定义6.2&6.3：图的分类定义6.2：无向边与有向边•无向边：与结点无序偶(vj,vk)相关联的边。•有向边：与结点有序偶<vj,vk>相关联的边。定义6.3：无向图、有向图、混合图•无向图：每条边均为无向边的图。•有向图：每条边均为有向边的图。•混合图：既有有向边又有无向边的图。定义6.4&6.5：基本概念▍定义6.4：结点相关概念•邻接点(AdjacentVertices)：由一条边直接连接的两个不同的结点。•孤立结点(IsolatedVertex)：不与任何其他结点相连的点，即度数为0的结点。•零图(NullGraph)：仅由孤立结点构成的图，不含任何边。•平凡图(TrivialGraph)：特殊的零图，图中仅含有一个孤立结点。▍定义6.5：边相关概念•邻接边(AdjacentEdges)：至少共享一个公共端点的两条边。•环(Loop)：起点和终点为同一个结点的边，也称为“自回路”。定义6.6：多重图与简单图在图中，关联一对结点的边若多于一条，称这些边为平行边；含有平行边的图称为多重图(Multigraphs)；不含平行边和环的图称为简单图(SimpleGraph)。核心特征辨析•多重图：允许“平行边”连接同一对顶点，也可以包含自环。•简单图：结构最纯粹，严格禁止平行边和自环，是图论中最基础的研究对象。💡注：在大多数图论的入门与进阶分析中，若不做特殊说明，所指的“图”通常均为“简单图”。6.1.2度数和握手定理定义6.7：结点的度数在图G=<V,E>

中，与结点v关联的边数，称作是该结点的度数，记作deg(v)。•环(Loop)：每个环在其对应结点上度数增加2•极值：图的最大度数记作∆(G)，最小度数记作δ(G)。实例解析：度数计算•简单边：若结点v1和v2

分别连接三条边，则它们的度数均为3。•孤立点：若结点v4

不与任何边关联，则它的度数为0。孤立点在图分析中常被忽略，但数学定义上依然存在。•含环情况：若结点v3连接两条普通边和一个环，则度数计算为2+2=4。定理6.1：握手定理定理内容任何一个图G=<V,E>,其结点度数总和,等于边数的两倍,即:∑deg(v)=2|E|历史背景与形象解读由欧拉于1736年提出，揭示了图论中最基本的数量关系。形象比喻：若多人互相握手，两只手握在一起构成一次握手，那么所有人被握过手的总次数，一定是握手次数的两倍，故必为偶数。定理6.2：奇数度结点的性质▍定理内容在任何图中，度数为奇数的结点必定是偶数个。▍证明过程设V1，V2分别为图中奇数度数和偶数度数的结点集合。根据握手定理：由于偶数度数结点的度数之和

是偶数，且边数的两倍2|E|也是偶数，故奇数度数结点的度数之和

必为偶数。又因“奇数个奇数相加是奇数，偶数个奇数相加才是偶数”，因此，奇数度结点的个数一定是偶数。例题6.1：握手定理应用01/判断度数序列根据握手定理：图中所有顶点的度数之和等于边数的两倍，因此度数之和必为偶数。•序列(1,1,2,2,3)：度数之和=1+1+2+2+3=9(奇数)•序列(1,3,4,4,5)：度数之和=1+3+4+4+5=17(奇数)结论：两个序列的度数之和均为奇数，不满足握手定理，故均不能构成图的度数序列。02/计算最少结点数已知：图G有10条边，包含4个3度结点，其余结点度数≤2。求图G最少有多少个结点？1.由握手定理，度数总和=2×|E|=2×10=202.4个3度结点的度数之和=4×3=123.剩余度数=20-12=8。为使结点数最少，剩余结点度数应取最大值2。4.最少需要额外结点数=8÷2=4个结论：图中至少有4+4=8个结点。定义6.8&定理6.3：有向图的度数定义6.8：入度与出度入度(In-degree)deg⁻(vᵢ)定义：射入一个结点vᵢ的有向边的总数。出度(Out-degree)deg⁺(vⱼ)定义：由一个结点vⱼ射出的有向边的总数。总度数：该结点的出度与入度之和(deg(v)=deg⁻(v)+deg⁺(v))定理6.3：度数守恒定律在任意有向图G=<V,E>中，所有结点的入度之和与所有结点的出度之和总是相等的，并且都等于图中的边数|E|。直观理解：每条有向边都有一个起点和一个终点，因此每增加一条边，总出度和总入度各增加1。数学形式化表达：∑deg⁻(v)=∑deg⁺(v)=|E|（其中v∈V，即遍历图中所有顶点）6.1.3完全图、补图、子图定义6.9：完全图简单图G=<V,E>

中，若每一对结点间都有边相连，则称该图为完全图。其中，n阶无向完全图记为Kn。定理6.4：完全图的边数

定义6.10：补图定义内容：给定一个图G,由G中所有结点,以及所有能使G成为完全图的添加边组成的图,称为G的补图(Complementofgraph),记为G（上划线）。重要提示(Note)画补图时，边与原图呈互补关系，但结点数量与集合完全保持不变。

特别提醒：不要遗漏任何孤立结点。定义6.11：子图与生成子图定义：设图G=<V,E>，存在图G'=<V',E'>，且，则称G'为G的子图(Subgraph)。如果G的子图包含G的所有结点，则称该子图为G的生成子图(SpanningSubgraph)。子图·Subgraph判定：继承原图的一部分结点和一部分边。生成子图·SpanningSubgraph判定：继承原图的全部结点，但只保留一部分边。6.1.4图的同构定义6.12：图的同构设图G=<V,E>和图G'=<V',E'>，如果存在一一对应的映射g:vi→vi'且边的关联关系保持不变，则称G与G'同构，记作G≃G'。充要条件两个图的结点和边分别存在着一一对应，且保持关联关系。

形象地说，一个图可以通过变形（如拉伸、扭转、移动顶点但不改变顶点间的连接关系）变为另一个图，那么这两个图就是同构的。图的同构示例图6.11同构关系解析图6.11中的三个图是同构的。对图(a)和(b)而言，在结点间存在一一对应映射g:a→a',b→b',c→c',d→d'，并且边的关联关系也一一对应。这表明，尽管图的几何形状不同，但它们的抽象结构完全一致。两图同构的必要条件结点数相同两个图的顶点（Vertex）集合元素个数必须相等，即|V₁|=|V₂|。边数相同两个图的边（Edge）集合元素个数必须相等，即|E₁|=|E₂|。度数序列一致两个图中具有相同度数（Degree）的顶点数量必须分别相等，度数序列排序后相同。⚠️重要提示：必要非充分条件满足上述三个条件不能直接推出两个图是同构的。这些只是判断同构的必要前提，而非充分依据。例如：右图展示的两个图，虽然满足上述所有必要条件，但结构不同，因此它们并不是同构的。例题6.3：证明图的同构证明：设(a)图为G，(b)图为G'，构造结点之间的双射函数f:f(1)=a，f(2)=b，f(3)=c，f(4)=d，f(5)=e，f(6)=f，f(7)=g，f(8)=h，容易验证，f满足图的同构定义，所以G≃G'。例题6.4：画出所有非同构的图问题描述请画出所有包含4个顶点和3条边的非同构无向简单图。要求图中不包含重边和自环，且图之间在结构上互不相同。解答：所有满足条件的非同构图本章总结01/图的基本概念图是由离散的顶点集合与连接顶点的边集合共同组成的结构。依据边是否有方向，可分为无向图与有向图。02/度数与握手定理顶点的度数是指与该顶点相关联的边的数量。握手定理揭示了图的基本性质：图中所有顶点的度数之和，恒等于边数的两倍。03/特殊图结构包括完全图（任意两点都相连）、补图、子图与生成子图等。理解这些特殊结构是分析复杂网络拓扑的基础。04/图的同构若两个图的顶点间存在一一对应的映射关系，且保持边的连接性不变，则它们互为同构。关键在于“结构相同”而非“画法相同”。核心思想：图论关注的是顶点与边之间的逻辑关联关系，而非其在平面上的具体几何形状或物理位置。感谢观看THANKSFORWATCHINGCHAPTER06图论6.2路与回路PATHSANDCIRCUITSINGRAPHTHEORY目录CONTENTS01路和回路的概念定义、示例与连通性02删除边和删除点割点、割边与连通度03有向图的连通性强连通、单侧连通与弱连通6.2.1路和回路的概念定义6.13：路、回路、迹、通路、圈定义：给定图G=<V,E>，结点和边的交替序列v1

e1

v2

e2…envn，

称为联接v1

到vn

的路(Path)。路(Path)最基础的定义。图中由顶点和边交替构成的序列，用于描述从起点到终点的连接关系。回路(Cycle)闭合的“路”。当一条路的起点\(v_1\)与终点\(v_n\)为同一个结点时，该条路被称为回路。迹(Trail)强调边的不重复性。若一条路中包含的所有边都互不相同，无论顶点是否重复，这样的路被称作“迹”。通路(Path)强调点的不重复性。若一条路中包含的所有顶点都互不相同，这样的路被称作“通路”，也常直接称为“路径”。圈(Circuit)闭合的“通路”。即除了起点和终点重合外，其他所有顶点均不相同的闭合路径。路、迹、通路、圈示例路(Walk)|最宽泛的概念，边和点均可重复示例：a→e₁→b→e₄→c→e₂→a→e₁→b→e₅→d迹(Trail)|边不可重复，点可重复示例：a→e₁→b→e₄→c→e₂→a→e₃→d通路(Path)|结点不可重复，边自然也不可重复示例：a→e₁→b→e₄→c→e₆→d圈(Cycle)|特殊的闭合通路，起点与终点相同示例：a→e₁→b→e₄→c→e₆→d→e₃→a图论结构示例：图中的边与点构成不同的连接方式定理6.5：最短路径的边数限制定理内容在一个具有n个结点的图中，如果从结点vᵢ到结点vⱼ存在一条路，则从结点vᵢ到结点vⱼ必存在一条不多于n-1条边的路。证明思路如果一条路的边数l>n-1，那么根据“鸽巢原理”，该路径上包含的l+1个结点中必有重复的结点出现。我们可以不断移除重复结点之间的回路（即环），从而缩短路径的总长度，直到路径上的边数不超过n-1为止。定义6.14&6.15：连通性与连通图定义6.14连通性与连通分支在无向图G=<V,E>中，若从结点u到结点v存在一条路，称结点u和v是连通的。利用连通性对结点集V作划分，得到的子图称为连通分支。定义6.15连通图若图G的连通分支数W(G)=1，即图中所有的结点都在同一个连通分支中，就称图G是一个连通图。注：连通分支数W(G)是图论中衡量图连通程度的一个基本指标。核心结论“连通图”的定义本质上保证了：在连通图中，任意两个不同的结点之间一定存在通路，即任意两结点之间一定是连通的。连通图与非连通图示例图(a)：连通图连通分支数为1，图中所有的顶点都属于同一个连通分量，任意两点之间都存在路径相连，构成一个整体。图(b)：非连通图连通分支数为3，图被分割为三个互不连通的子图。不同连通分支上的顶点之间不存在路径，是独立的部分。例题6.5：摆渡问题(FerryProblem)问题描述一个人带着一只狼、一只羊和一捆草要渡河。人一次只能运送一个“乘客”。如果人不在，狼要吃羊，羊要吃草。问人如何安排摆渡，才能让所有东西都安全过河？图论建模思路将河左岸允许出现的安全状态视为图的“结点”。若一种状态通过一次合法摆渡变为另一种状态，则在两结点间连一条“边”。问题转化为：在图中寻找一条以“人、狼、羊、草”为起点，以“空”（左岸无物）为终点的简单路径。摆渡问题的解决方案问题转化：状态图视角摆渡问题本质上是一个图论问题：在状态图中寻找一条以初始状态“人、狼、羊、草”为起点，以最终状态“空（所有人/物都到达对岸）”为终点的简单路径。解决方案A：先带狼过河1.人带羊过河→人返回→带狼过河→放下狼并带回羊

2.人带草过河→人返回→最后带羊过河解决方案B：先带草过河1.人带羊过河→人返回→带草过河→放下草并带回羊

2.人带狼过河→人返回→最后带羊过河6.2.2删除边和删除点基本概念对于连通图，删除图中的点或边，可能会改变图的结构，从而影响图的连通性，甚至导致连通图变为非连通图。删除结点v(VertexDeletion)将图中的顶点v移除，同时删除与v关联的所有边。这种操作通常会移除图中的一个“枢纽”节点，对图的连通性影响较大。删除边e(EdgeDeletion)仅将图中的特定边e从图中移除，而保留边的两个端点。这是一种相对温和的操作，但如果该边是“桥”（割边），则会导致图分裂。图示：原图（左）与删除操作后的结果对比定义6.16：点割集、割点、点连通度点割集(VertexCutSet)设无向图G=<V,E>为连通图，若删除图中的一个顶点集合后，图变得不连通，且该集合在所有满足条件的集合中元素数量最少，则称该集合为点割集。割点(CutVertex)如果一个点割集中仅包含一个顶点，那么这个特殊的顶点就被称为割点。删除割点后，连通图会分裂成两个或多个不连通的子图。点连通度(VertexConnectivity)点连通度记为k(G)，它是图G的最小点割集的顶点数量。它反映了一个连通图的连通程度：k(G)越大，图越难被破坏连通性。性质一：存在割点的连通图若连通图G中存在割点，则图G的点连通度为1，即k(G)=1。性质二：完全图Kn对于n阶完全图，任意两个顶点都相邻，必须删除n-1个顶点才能使其不连通，故k(Kn)=n−1。例题6.6：点割集与割点示例图(a)分析•点割集：集合V={l}

是图的一个点割集。•割点：顶点l

被称为“割点”，因为删除它会导致图不连通。•点连通度：图的点连通度k(G)=1。图(b)分析•关键割点：图中顶点v2

和v6

均为割点。•影响：移除这两个顶点中的任意一个，都会将原图分割为两个或更多互不连通的子图，是维持整体连通性的核心节点定义6.17：边割集、割边、边连通度边割集(EdgeCutSet)设无向图G=<V,E>为连通图，若删除某一边集后，图变为不连通，且该边集是满足此条件的最小集合，则称为**边割集**。割边(Bridge)如果一个边割集中仅含有一条边，则这条边被称为“割边”，也常被形象地称作“桥”。边连通度λ(G)对于连通图G，其所有边割集中，元素个数最小的边割集的大小，被定义为图G的边连通度，记作λ(G)。性质01：割边与边连通度如果一个连通图G中存在割边，则其边连通度λ(G)=1。反之，如果λ(G)=1，则图中必含有割边。性质02：完全图的边连通度对于n阶完全图Kn，任意两点间都有边相连，其边连通度为λ(Kn)=n−1。这意味着需要切断连接任意一个顶点的所有边，才能使图不连通。边割集与割边示例单点边割集(割边/桥)•边子集E={m}

构成一个边割集，且边m是一条割边（Bridge）。•该图的边连通度λ(G)=1，说明其连通性较低，删除一条边即可导致图不连通。多点边割集•边子集V1={e,s}，V2={t,l}

均是图的边割集。•这表明，在图论中，边割集既可以是单条边，也可以是多条边的集合，它们共同决定了图的连通性。定理6.6：连通度的不等式定理内容：k(G)≤λ(G)≤δ(G)（点连通度≤边连通度≤最小度）

λ(G)≤δ(G)设顶点v是图G的一个最小度结点，即d(v)=δ(G)。删除与v关联的所有δ(G)

条边后，顶点v将成为孤立点，图G不再连通。因此，图的边连通度λ(G)

不超过δ(G)。k(G)≤λ(G)设S是图G的一个最小边割集，即|S|=λ(G)。删除S中的边后，图被分为两个不连通的子图G1和G2。通过在G1中选择S的所有端点并将其删除，也能使图断开，且删除的点数不会超过边数。因此点连通度k(G)不超过边连通度λ(G)。例题6.7：国际会议翻译问题问题描述有小组成员{a,b,c,d,e,f,g}，每位成员掌握不同的语言种类。试判断：他们中间任何两个人是否都能进行对话（必要时可通过其他人翻译）？建模思路：图论转化将每个人抽象为图中的一个顶点；若两个人掌握同一种语言，则在对应的两个顶点之间连一条边。此时，原问题等价于判断构建出的图是否为一个连通图。最终结论经检验，该图为连通图。因此，必要时通过他人的翻译协助，小组内任何两个人都可以实现对话交流。图：小组成员语言互通关系图示意注：顶点为参会者，连线表示语言互通例题6.8：网络可靠性分析💡问题描述：为了使n个站点之间的连接在部分链路或节点故障时不容易被破坏，应如何构造一个可靠的网络拓扑图？图(a)：高可靠性网络点连通度k(G)=4，边连通度λ(G)=4。

网络结构中无割点，容错能力强，需要破坏大量的点或边才会导致网络瘫痪，是更优的选择。图(b)：低可靠性网络点连通度k(G)=1，边连通度λ(G)=3。

存在关键的割点v，若该站点失效，网络将被分割成互不连通的部分，从而导致整体瘫痪，风险极高。6.2.3有向图的连通性定义6.18：强连通、单侧连通、弱连通强连通(StronglyConnected)在简单有向图G中，若对于任意两个结点u,v，均满足u可达v且v可达u，则称图G是强连通的。单侧连通(UnilaterallyConnected)在简单有向图G中，若对于任意两个结点u,v，至少满足u可达v或v可达u其中之一，则称图G是单侧连通的。弱连通(WeaklyConnected)在简单有向图G中，如果去掉所有边的方向后，得到的无向图是连通的，则称图G是弱连通的。包含关系：强连通⫋单侧连通⫋弱连通（强连通图一定是单侧连通图；单侧连通图一定是弱连通图）有向图连通性示例图(a)·强连通图在有向图中，若任意两个顶点之间都能相互到达，则称该图为强连通图。它是连通性最强的一种类型。图(b)·单侧连通图若有向图中任意两个顶点，至少存在一个方向的通路（例如：顶点a可达顶点b，但顶点b不可达顶点a），则称为单侧连通图。图(c)·弱连通图若将有向图的所有边的方向去掉，转化为无向图后是连通的，但作为有向图本身并不满足强连通或单侧连通的条件，则称为弱连通图。定理6.8：强连通的充要条件定理内容Statement一个有向图G是强连通的，当且仅当G中有一个回路，它至少包含G中所有结点一次。充分性Sufficiency若存在一个包含所有结点的回路，则图中任意两个结点都可以沿着这个回路互相到达，因此图满足强连通的定义。必要性Necessity若图是强连通的，则任意两结点相互可达。通过依次从任意起点出发访问所有结点并连接路径，可以构造出一条包含所有结点的回路。定义6.19：强分图、单侧分图、弱分图强分图StrongComponent在简单有向图G中，具有强连通性质的最大子图。单侧分图UnilateralComponent在简单有向图G中，具有单侧连通性质的最大子图。弱分图WeakComponent在简单有向图G中，具有弱连通性质的最大子图。定理6.9在有向图G中，它的每一个结点位于且只位于一个强分图中。本节总结01路与回路图中顶点和边的交替序列，是图论连通性分析的逻辑基础与基本构成单元。02连通性无向图：连通图、连通分支。有向图：强连通、单侧连通、弱连通。03连通度点连通度：衡量破坏连通性所需删除的最少点数。边连通度：衡量破坏连通性所需删除的最少边数。04实际应用图论连通性理论在生活与工程中有着广泛应用，典型场景如经典的摆渡问题求解、以及复杂网络的可靠性与鲁棒性分析。感谢观看THANKSFORWATCHINGCHAPTER06·图论6.3图的矩阵表示MatrixRepresentationofGraphs连接图论与线性代数的桥梁·量化分析·算法设计基础目录CONTENTS01核心概念引入图的矩阵表示及其优势02图的邻接矩阵定义、性质与应用03图的可达性矩阵定义、计算方法与应用04图的关联矩阵定义、性质与应用核心概念引入：图的矩阵表示节省存储空间相比于其他存储方式，矩阵在计算机内存中结构规整，更易于存储、检索和批量管理大规模图数据。支持量化分析可直接应用线性代数中的矩阵运算（如乘法、求逆）来解决路径计数、连通性判定等图论核心问题。实现计算转换将直观的几何图形描述转化为严谨的数学矩阵模型，为计算机算法实现提供了标准化的基础。应用价值与意义矩阵表示为分析图的连通性、可达性、中心性等性质提供了统一、严谨的数学框架。它是社交网络影响力分析、集成电路布线设计、交通路网优化等复杂系统建模与算法开发的基石。6.3.1图的邻接矩阵定义6.20：邻接矩阵(AdjacencyMatrix)设G=<V,E>是一个简单图，且有n个结点V={v1,v2,…,vn}，称n阶方阵A(G)=(aij)

为G的邻接矩阵，其中矩阵元素aij

的取值规则如下：矩阵维度：邻接矩阵是一个n×n的方阵，其中n是图G中包含的顶点数量。元素含义：矩阵中的元素aij

用于表示顶点vi

和vj

之间是否存在一条边相连。例题6.10：无向图的邻接矩阵性质：对称性无向图的邻接矩阵是对称矩阵(SymmetricMatrix)。因为无向图中边(vi,vj)与(vj,vi)代表同一条边，两点间的连接关系是相互的，所以矩阵满足Aij

=Aji。例题6.11：有向图的邻接矩阵关键性质：邻接矩阵不一定对称由于有向边具有明确的方向性，从顶点i指向j的边并不等价于从j指向i的边，因此矩阵中的元素aij与aji

没有必然相等的关系。邻接矩阵的性质01对称性无向图的邻接矩阵是对称矩阵。即矩阵中第i行第j列的元素等于第j行第i列的元素A=AT。02零图若一个图是零图（图中任意两个顶点之间都不存在边），则其对应的邻接矩阵是零矩阵，即所有元素均为0。03无向图的度在无向图中，邻接矩阵第i行所有元素相加的和，等于该顶点vi的总度数。04有向图的度•第i行元素之和=顶点vi

的出度(离开该顶点的边数)

•第j列元素之和=顶点vj

的入度(进入该顶点的边数)定理6.10：计算通路数量

基础步骤(l=2)对l用数学归纳法。当

l=2时，由上可知显然成立。归纳步骤(l→l+1)

例题6.12：通路数量计算问题描述：给定如图所示的无向图G1和有向图G2，分别求从结点v1

到结点v3

长度为2和3的通路数目。图G1

(无向图)

图G2

(有向图)

6.3.2图的可达性矩阵定义6.21：可达性矩阵(ReachabilityMatrix)

💡核心解读：可达性矩阵本质上是一种“存在性”判断工具，它仅关注顶点vi

到vj

之间是否存在通路，而完全不关心通路的具体数量、长度或形态。如何从邻接矩阵求可达性矩阵方法一：矩阵求和法01.计算矩阵和公式：

Bₙ=A+A²+⋯+Aⁿ02.将矩阵Bₙ中所有不为0的元素都替换为1，得到最终的可达性矩阵P。方法二：布尔运算法(更简洁)01.直接计算布尔矩阵的并集运算：

P=A∨A⁽²⁾∨A⁽³⁾∨⋯∨A⁽ⁿ⁾

注：A⁽ᵏ⁾为邻接矩阵的布尔幂(加法∨，乘法∧)02.无需额外转换，该方法直接计算出的结果就是标准的0-1可达性矩阵P。例题6.13：求可达性矩阵邻接矩阵AA=

[0100][0011][1101][1000]方法一：矩阵求和1.计算所有路径长度的矩阵之和：B₄=A+A²+A³+A⁴2.将矩阵B₄中所有的非零元素置为1，得到最终的可达性矩阵P。方法二：布尔运算直接利用布尔代数的逻辑并运算（∨）计算可达性矩阵，一步到位：P=A∨A⁽²⁾∨A⁽³⁾∨A⁽⁴⁾注：A⁽ⁿ⁾代表邻接矩阵A的第n次布尔幂。结果与结论P=[1111][1111][1111][1111]该图是强连通图6.3.3图的关联矩阵定义6.22：无向图的完全关联矩阵设G=<V,E>是一个无向图，有n个结点，m条边，称矩阵M(G)=(mij)n×m

为无向图G的完全关联矩阵，其中元素mij

表示顶点vi与边ej的关联次数，具体定义如下：

核心对象：顶点与边的关系关联矩阵是描述图结构的基本工具之一，其核心功能是建立并量化“顶点”集合与“边”集合之间的关联映射。矩阵维度：n×m矩阵的行数等于图的顶点数量(n)，列数等于图的边的数量(m)。因此矩阵通常不是方阵，维度取决于图的边与点的密度。例题6.14：无向图的完全关联矩阵图：无向图G的顶点与边结构示意解：构建完全关联矩阵M(G)顶点集V={v1,v2,v3,v4}|边集E={e1,e2,e3,e4,e5}[11100]

[01110]

[10012]

[00000]关键点分析•边e5是顶点v3上的环，故矩阵对应位置m35=2。

•顶点v4是孤立点，不关联任何边，故其对应行元素全为0。无向图完全关联矩阵的性质01/列的性质每列有且仅有两个1（表示一条边关联两个顶点），或者有一个2（表示一个环）。02/行的性质每一行中元素的和，恰好等于对应顶点的度数(Degree)。03/孤立点如果矩阵中某一行的元素全为零，则这一行所对应的顶点是孤立点。04/平行边如果矩阵中出现两个完全相同的列，这意味着这两列所对应的两条边是平行边。定义6.23：有向图的完全关联矩阵

核心解读：与无向图不同，对于有向边，我们需要在矩阵中明确区分起点和终点。

规定：1代表起点，-1代表终点，0代表不关联。这样矩阵结构就完整地包含了图的拓扑结构与边的方向信息。例题6.15：有向图的关联矩阵💡分析对于有向图的关联矩阵，规定：

•若边e以顶点v为起点，则关联项为1；

•若边e以顶点v为终点，则关联项为-1。

以边e₁为例：从v₁指向v₂，故矩阵中m₁₁=1，m₂₁=-1。

有向图完全关联矩阵的性质行的性质第i行中，数值1的个数，恰好等于顶点vᵢ的出度；数值-1的个数，恰好等于顶点vᵢ的入度。列的性质矩阵中的任意一列，都有且仅有两个非零元素：•一个1（对应有向边的起点）•一个-1（对应有向边的终点）孤立点判定若关联矩阵中存在一整行元素全为0，则该图中存在一个孤立点。注：孤立点指不与任何边相连的顶点。本章总结邻接矩阵描述顶点与顶点之间的关系。💡应用：计算通路数量。可达性矩阵描述顶点之间是否存在通路。💡应用：判断图的连通性。关联矩阵描述顶点与边之间的关系。💡应用：分析图的结构性质。核心思想将图的几何结构转化为代数形式，便于计算机处理和数学分析。感谢观看THANKYOUFORWATCHING第六章·图论6.4欧拉图EulerGraphs从“哥尼斯堡七桥问题”到图论的经典模型目录CONTENTS01欧拉图的概念与起源从经典的哥尼斯堡七桥问题切入，探究欧拉路与欧拉回路的数学定义与历史渊源。02欧拉图的判定方法系统梳理无向图与有向图的欧拉性判定定理，掌握核心的图论算法逻辑。03欧拉图的应用解析经典的“一笔画”谜题，并探讨欧拉图在“中国邮递员问题”中的最优路径规划应用。6.4.1欧拉图的概念：哥尼斯堡七桥问题18世纪普鲁士哥尼斯堡（今俄罗斯加里宁格勒）

普雷格尔河上的七座桥连接两岸和两个岛屿图论的起源与诞生历史背景：数学界的经典难题1736年，瑞士数学家欧拉(Euler)解决了该问题，并以此撰写了论文，标志着图论(GraphTheory)这一学科的诞生。核心问题：路径的可行性能否从任意一块陆地出发，经过每座桥恰好一次，最后返回到出发点？抽象化建模思维将陆地抽象为“结点(Vertex)”，桥抽象为“边(Edge)”。问题转化为寻找经过每条边一次且仅一次的回路。定义6.24：欧拉路与欧拉回路给定一个没有孤立结点的无向图G，若存在一条通路，经过图中每一边一次且仅一次，称该通路为欧拉路(Eulerpaths)；若存在一条回路，经过图中每一边一次且仅一次，称该回路为欧拉回路(Eulercircuits)。具有欧拉回路的图称为欧拉图(Euleriangraph)。欧拉路·最短通路欧拉路是经过图中所有边的通路中长度最短的通路，其长度等于图中边的总数。欧拉回路·最短回路欧拉回路是经过图中所有边的回路中长度最短的回路，其长度也等于图中边的总数。欧拉图、欧拉路与非欧拉图示例图(a)·欧拉图当图中所有结点的度数均为偶数时，该图存在欧拉回路，被称为欧拉图。图(b)·存在欧拉路当图中恰好有2个奇数度结点，其余均为偶数度时，该图存在欧拉路，但不是欧拉图。图(c)·无欧拉路当图中奇数度结点数量超过2个时，该图既不存在欧拉路，也不存在欧拉回路。6.4.2欧拉图的判定方法定理6.11：无向图欧拉路的判定无向图G存在欧拉路，当且仅当G是连通的，且有0个或2个奇数度结点。注：若奇数度结点数为0，则G存在欧拉回路(起点=终点)；若为2，则这两个结点分别是欧拉路的起点和终点。必要性证明思路在欧拉路中，除了起点和终点外，每一个中间结点都满足“每进入一次，必离开一次”。因此，这些中间结点的度数一定是偶数。只有起点和终点的度数可以是奇数（若存在）。充分性证明思路采用“构造法”证明：从奇数度结点出发（若无奇数度结点，则任选一点），每步选取一条未走过的边向前延伸，逐步构建出一条完整的通路。由于图是连通的且满足度数条件，最终可以遍历所有边形成欧拉路。推论6.2：无向图欧拉图的判定推论内容无向图G存在欧拉回路（即G是欧拉图），当且仅当G是连通的，并且所有结点的度数均为偶数。本质解析这是定理6.11的一个特例，即图中奇数度结点数量为0的情况。此时，欧拉路径的起点和终点完全重合，从而形成一条闭合的回路，即欧拉回路。推论6.3：有向图的判定欧拉回路(EulerCircuit)一个有向图G具有一条单向欧拉回路，当且仅当G是强连通的，并且：图中每个结点的入度等于出度。欧拉路(EulerPath)一个有向图G存在欧拉路，当且仅当G是连通的，且满足：●有且仅有一个结点的出度=入度+1（作为路径起点）●有且仅有一个结点的入度=出度+1（作为路径终点）●其余所有结点的入度等于出度例题6.16：判断欧拉路与欧拉图图(a)·欧拉图经过度数统计，图中所有结点的度数均为偶数。根据判定定理，该图存在欧拉回路，是欧拉图。图(b)·无欧拉路经计算，图中奇数度结点的数量超过2个。根据判定定理，该图既没有欧拉路，也不是欧拉图。图(c)·存在欧拉路经统计，图中恰好存在2个奇数度的结点。根据判定定理，该图存在欧拉路，但不是欧拉图。6.4.3欧拉图的应用：一笔画问题问题本质：判断一个图形能否“一笔画”，本质上就是判断该图形对应的图是否存在欧拉路或欧拉回路。1.欧拉路图中有且仅有两个奇数度结点，可以一笔画。从一个奇数度结点出发，到另一个结束。2.欧拉回路图中所有结点的度数均为偶数，可以一笔画。从任意结点出发，最后回到该结点。3.无解情况图中奇数度结点的数量超过两个，无法一笔画。例题6.17：无向图一笔画判断图(a)：存在欧拉路•度数分析：结点b和c的度数为3（奇数），其余所有结点的度数均为偶数。•结论：图中存在欧拉路，一笔画时必须从奇数度顶点出发，因此可以从b或c开始。图(b)：存在欧拉回路•度数分析：图中所有结点的度数均为4（偶数），无奇数度顶点。•结论：图中存在欧拉回路，可从任意结点出发，一笔画完整图后最终回到起点。例题6.18：有向图一笔画判断图(a)：无欧拉路不满足有向图欧拉路的判定条件。

图中结点的度数不满足“仅有一个入度比出度大1的终点和一个出度比入度大1的起点”的规则。图(b)：存在欧拉路满足有向图欧拉路的条件。

图中存在且仅存在：一个起点（出度比入度大1）和一个终点（入度比出度大1），其余所有结点入度等于出度。图(c)：存在欧拉回路满足有向图欧拉回路的条件。

图中所有结点的入度严格等于出度，可以从任意点出发，一笔画完所有边并回到起始点。应用：中国邮递员问题问题描述邮递员从邮局出发，需要走遍其负责街区的每一条街道至少一次，最后回到邮局。如何规划路线才能使总路程最短？这一问题由我国数学家管梅谷教授于1962年首次提出并研究，因此在国际上被称为“中国邮递员问题”(ChinesePostmanProblem,CPP)。图论建模将街区地图抽象为一个带权无向图G=(V,E,w)：•街道的交叉路口→图的顶点集V•连接路口的街道→图的边集E•街道的长度→边的权重函数w(e)问题转化为：在图G中寻找一条经过每条边至少一次的最短回路（最优投递路线）。中国邮递员问题的解决方案01/理想情况：直接利用欧拉回路如果图本身就是欧拉图（即图中所有结点的度数均为偶数），此时图中天然存在一条经过每条边一次且仅一次的回路。这条欧拉回路即为邮递员需要的最短投递路线，无需重复经过任何道路。02/一般情况：构造最优解策略若图中有2k个奇数度结点（k>1），则需重复经过部分边：

1.将这2k个奇数度结点进行两两配对；

2.找出每对结点间的最短路径并重复行走；

3.重复后形成的新图是欧拉图，其欧拉回路即为原问题的最优解。图：邮递员问题中的图论路径与结点度数示意本章总结欧拉图(EulerianGraph)定义：在连通图中，存在一条经过所有边一次且仅一次的回路。若一个图存在欧拉回路，则称它为欧拉图。欧拉路(EulerianTrail)定义：在连通图中，存在一条经过所有边一次且仅一次的通路（非闭合）。它与欧拉图最大的区别在于起点与终点不重合。判定定理(KeyCriteria)•无向图：欧拉路(0/2个奇度顶点)，欧拉图(0个奇度顶点)。•有向图：欧拉回路(全顶点入度=出度)，欧拉路(一点出度=入度+1，一点入度=出度+1)。典型应用(Applications)•一笔画问题：判断平面图形能否一笔不间断画完，是欧拉路最直观的体现。•中国邮递员问题：寻找遍历所有街道并回到起点的最短路径，是图论在运筹学中的经典应用。感谢观看THANKYOUFORWATCHINGCHAPTER0606图论6.5汉密尔顿图目录CONTENTS01引言：汉密尔顿图的起源汉密尔顿的“周游世界”游戏及其在现实与理论中的应用价值。026.5.1汉密尔顿图的概念深入解析汉密尔顿路、汉密尔顿回路和汉密尔顿图的严格数学定义。036.5.2汉密尔顿图的判定方法系统学习判定汉密尔顿图的必要条件、充分条件，以及利用图的闭包进行判定的技巧。引言：汉密尔顿图的起源正十二面体模型（汉密尔顿周游世界游戏）🎮游戏背景1859年，爱尔兰数学家威廉·罗万·汉密尔顿发明了一个基于正十二面体的数学玩具，以此向朋友展示数学问题的趣味性。❓核心挑战在正十二面体的每个顶点代表一座“城市”，要求沿着边寻找一条闭合路线，能够访问图中的每一个顶点恰好一次，并最终返回起点。💡理论起源这个著名的“周游世界问题”成为了图论中重要概念——“汉密尔顿图”的起源，为后续研究图论中的回路问题奠定了基础。6.5.1汉密尔顿图的概念定义6.25：汉密尔顿路与汉密尔顿回路给定图G,若存在一条通路,经过图中每个结点一次且仅一次,称该通路为汉密尔顿路(Hamiltonpaths);若存在一条回路,经过图中每个结点一次且仅一次,称该回路为汉密尔顿回路(Hamiltoncircuits),具有汉密尔顿回路的图称为汉密尔顿图(Hamiltongraph)。汉密尔顿路它是经过图中所有结点的通路中，长度最短的通路。因为图中有n个结点，所以汉密尔顿路的长度为n-1。汉密尔顿回路它是经过图中所有结点的回路中，长度最短的回路。因为图中有n个结点，所以汉密尔顿回路的长度为n。特别规定为了理论上的完整性，在图论中，我们通常规定：平凡图（即仅有一个顶点的图）被定义为汉密尔顿图。图例分析：汉密尔顿图、路与非汉密尔顿图(a)汉密尔顿图存在汉密尔顿回路：

v₁→v₂→v₃→v₄→v₁(b)非汉密尔顿图存在汉密尔顿路v₁→v₂→v₅→v₄→v₃，

但不存在汉密尔顿回路(c)非汉密尔顿图既不存在汉密尔顿回路

也不存在汉密尔顿路。(d)汉密尔顿图结构满足条件，

存在一条包含所有顶点的汉密尔顿回路。(e)非汉密尔顿图图中存在汉密尔顿路，

但无法形成闭合的汉密尔顿回路。(f)非汉密尔顿图图的连通性或顶点分布导致,不存在任何汉密尔顿路。6.5.2汉密尔顿图的判定方法定理6.12：汉密尔顿图的必要条件若图G=<V,E>存在汉密尔顿回路,则对于集合V的每一个非空子集S，均有W(G-S)≤|S|。其中，W(G-S)表示从图G中删除子集S的所有结点及关联边后，所得子图的连通分支数量。定理直观解读从图G中删除任意非空子集S的结点后，剩下的子图被分割成的连通块数量，永远不能超过被“砍掉”的结点数量|S|。这意味着汉密尔顿图的连通性“足够好”。逻辑性质与应用这是一个必要非充分条件。它的主要价值在于：❌判定一个图不是汉密尔顿图，即找出反例S使得

W(G-S)>|S|。✅无法用它来直接证明一个图是汉密尔顿图。例题6.20：利用必要条件判断非汉密尔顿图问题描述试判断图6.43(a)是否为汉密尔顿图？我们利用汉密尔顿图的必要条件（定理6.12）来进行反证。推理与结论1.选取结点子集S={v₁,v₂}，即|S|=2。2.删除S后，子图G-S的连通分支数W(G-S)=33.由于W(G-S)>|S|，不满足必要条件，故结论为该图不是汉密尔顿图。图6.43：图G与删除S后的子图G-S彼得森图（PetersenGraph）：必要条件的局限性关键特性彼得森图满足不等式\(W(G-S)\leq|S|\)对于图中所有非空顶点子集\(S\)，这意味着它满足定理6.12所给出的必要条件。惊人的反例结论尽管满足上述必要条件，但经过严格的图论分析和验证，彼得森图并不是汉密尔顿图（即不存在经过每个顶点恰好一次的回路）。理论启示这有力地证明了：定理6.12的条件不是充分的。汉密尔顿图的判定问题远比欧拉图复杂，至今尚未找到简单的充要条件。定理6.13&6.14：存在汉密尔顿路/回路的充分条件定理6.13·存在汉密尔顿路的充分条件设图G=<V,E>是一个具有n个结点的简单图，若G中每一对不相邻的结点的度数之和大于等于n-1，则在G中存在一条汉密尔顿路。定理6.14·存在汉密尔顿回路的充分条件设图G=<V,E>是一个n阶简单图，若G中每一对不相邻的结点的度数之和大于等于n，则在G中存在一条汉密尔顿回路。关键性质：充分非必要条件

满足上述度数之和条件的图一定存在汉密尔顿路/回路，但反之不成立——即存在汉密尔顿路/回路的图，其结点度数之和未必满足上述要求。充分条件的局限性反例：n边形(n≥3)前提设定：考虑一个普通的n边形（如正六边形）。该图中每个顶点的度数均为2，因此任意两个不相邻顶点的度数之和为2+2=4。条件不满足：当边数n>5时（如n=6），顶点度数之和4<n-1(即5)。这意味着它不满足定理6.13的充分条件。事实结论：n边形显然存在汉密尔顿回路，它本身就是一个汉密尔顿图。逻辑结论与启示1.充分非必要条件：定理6.13和6.14给出的是判断汉密尔顿图的充分条件，而非必要条件。满足条件则“一定是”，但不满足条件并不代表“一定不是”。2.理论边界：这揭示了图论中判定汉密尔顿图的复杂性：目前尚未找到简单的充要条件，我们需要根据具体图的结构特征灵活分析。定义6.26：图的闭包（Closure）定义内容给定图G=<V,E>有n个结点,若将图G中度数之和至少是n的非邻接结点连接起来得图G',对图G'重复上述步骤,直到不再有这样的结点对存在为止,所得到的图,称为是原图G的闭包(Closure),记作C(G)。✦核心特性一个图的闭包是唯一的，与添加边的顺序无关。定理6.15：利用闭包判定汉密尔顿图定理核心表述当且仅当一个简单图G的闭包C(G)是汉密尔顿图时，这个简单图G是汉密尔顿图。判定策略与应用通过反复连接图G中度数之和足够大的非邻接顶点，逐步将G扩展为其闭包C(G)。若最终得到的闭包C(G)是汉密尔顿图（例如，C(G)是完全图），则可直接判定原图G也是汉密尔顿图。汉密尔顿图判定的现状计算复杂性壁垒汉密尔顿图的判定问题是图论与理论计算机科学中公认的NP-困难(NP-hard)问题。这意味着，在现有的经典计算模型下，不存在一个多项式时间的算法能够在所有情况下，快速判定任意一个图是否是汉密尔顿图。理论探索的困境尽管经过多年的研究，数学界已经提出了超过300个相关定理和充分条件，但遗憾的是，至今仍没有发现一个简单、通用的“充分必要”判别准则。寻找这样一个高效、普适的判定方法，依然是图论领域中一个极具挑战性的重大未解决问题。本节总结汉密尔顿图的概念▌定义

包含汉密尔顿回路的图，即在图中存在一条经过每个顶点恰好一次的回路。▌核心特征

在不重复访问顶点的前提下，完成对所有顶点的遍历并最终回到起点。判定方法体系1.必要条件(证伪)

公式:W(G-S)≤|S|。不满足此条件，则必不是汉密尔顿图。2.充分条件(证实)

利用度数和条件(Dirac/Ore定理)，满足即可判定为汉密尔顿图。3.闭包方法(间接判定)

通过逐步构造图的闭包，将复杂判定转化为简单完全图判定。计算复杂性NP-困难问题(NP-hard)

目前数学界尚未找到一个简洁、通用的充要条件来直接判定所有图。这意味着在大规模图数据中，汉密尔顿图的判定是一个计算上的难题，没有已知的高效算法。核心概念与定理汇总表汉密尔顿图具有汉密尔顿回路的图。定义6.25汉密尔顿路经过图中每个结点一次且仅一次的通路。定义6.25汉密尔顿回路经过图中每个结点一次且仅一次的回路。定义6.25必要条件对任意非空子集S，有W(G-S)≤|S|。定理6.12汉密尔顿路充分条件任意两结点度数之和≥n-1。定理6.13汉密尔顿回路充分条件任意两结点度数之和≥n。定理6.14图的闭包通过连接度数和≥n的非邻接顶点直到无法连接为止得到的图。定义6.26闭包判定定理G是汉密尔顿图当且仅当其闭包C(G)是汉密尔顿图。定理6.15THANKYOU感谢观看第六章图论6.6平面图与欧拉公式PlanarGraphsandEuler'sFormula目录CONTENTS01平面图的

基本概念平面图的定义、示例

以及非平面图的

典型反例展示。02面的概念面、边界与次数的

严谨数学定义

及其基础计算方法。03平面图的

性质与定理面的次数之和关系

欧拉公式及其

重要应用场景。04非平面图的判定利用必要条件

证明K₅和K₃,₃

为典型非平面图。05库拉托夫斯基

定理平面图判定的

终极理论方法与

核心准则。引言：为什么要学习平面图？现实世界的需求在工程设计与网络规划等诸多实际场景中，我们面临一个核心挑战：如何避免图的边在非端点处交叉？这直接关系到系统的稳定性与运行效率。印制电路板(PCB)电路板上的导线若发生交叉，极易引发短路故障，严重威胁电路安全与功能实现。建筑电气布线强弱电线缆的不规范交叉会产生电磁干扰(EMI)，导致信号失真或设备运行异常。交通网络设计减少道路的物理交叉点能有效优化路网结构，降低交通事故风险与通行延误。图：复杂的汽车电驱电控PCB电路板

高密度走线需严格遵循“无交叉”的平面性原则定义6.27：平面图(PlaneGraph)▌定义内容设图G=<V,E>是一个无向图，如果能够把G的所有结点和边都画在平面上，且使得任何两条边除了端点外，没有其它的交点，就称G是一个平面图，也称G可嵌入平面。关键在于“画法”一个图是否是平面图，取决于是否存在一种画法，使得边不交叉。即使图的某种画法存在边交叉，只要能找到一种画法避免交叉，它仍是平面图。同构不变性平面图是图的一个拓扑性质。如果一个图与某个平面图同构，那么它本身也是平面图。这意味着，无论图的顶点如何重命名或边如何重新排列，只要结构一致，平面性保持不变。平面图示例有些图的边看似相交，但通过改变画法（同构变换），可以消除所有交叉点，证明其是平面图。示例(a)看似有交叉的图，可以通过将部分边画成弧线，将交叉点“绕过去”。示例(b)方形内的对角线交叉，同样可以通过弧线重绘来避免，使其无交叉地存在于平面上示例(c)三维立方体的结构，也可以在二维平面上通过拓扑变换，画出无交叉的平面图。非平面图示例有些图无论如何改画，都无法消除边的交叉。它们被称为非平面图。完全偶图K3,3这是一个经典的非平面图。它有两组各3个结点，组内无边，组间全连接。完全图K55个结点中，任意两个结点之间都有边相连。这也是一个经典的非平面图，是所有非平面图的“基本构件”之一。定义6.28：面、边界与次数▍定义：设图G=<V,E>是一个无向连通图。由图中的边所围成的区域，区域内既不包含图的结点，也不包含图中的边，称这样的区域为图G的面(Face)。面的概念直观地描述了平面图被边分割后的区域属性。无限面(InfiniteFace)包含图外部的无限大的区域，是所有平面图都具备的外部面。有限面(FiniteFace)完全由图中的边所包围、面积有限的内部区域，是图的内部面。边界(Boundary)包围一个面的所有边构成的回路。对于无限面，其边界通常由图的外部边构成。次数(Degree)边界的长度，即构成边界的边的条数。面r的次数通常记为deg(r)。面的次数计算示例图(a)分析图(a)包含4个面，每个面的边界均由三角形构成，因此每个面的次数均为3。图(b)分析图(b)包含5个面。特别注意计算r₃的次数时，其内部的“桥”被计算了两次，故该面的次数最终为5。关键结论：一条边无论作为两个面的公共边，还是作为一个面边界的“桥”，在计算所有面的次数之和时，都会被计算两次。定理6.16：面的次数之和定理内容一个有限平面图中，面的次数之和，等于其边数的两倍。证明思路任何一条边，在图中存在两种情况：1.作为两个面的公共边：分别计入这两个面的次数。2.作为一个面的边界（即桥）：在这个面的边界中被计算两次。结论：无论哪种情况，每条边都被计算了两次。因此，面的次数之和等于边数的两倍。示例验证•图6.50(a)：边数e=6，面的次数之和为3+3+3+3=12=2×6。•图6.50(b)：边数e=9，面的次数之和为3+3+5+4+3=18=2×9。以上两个例子直观地验证了定理的正确性。定理6.17：欧拉公式(Euler'sFormula)定理内容Statement设有一个连通简单平面图G，共有v个结点，e条边和r个面，则一定有：v-e+r=2起源与背景Origin该公式最初是欧拉在研究凸多面体时发现的。利用球极投影的几何变换，任何凸多面体的表面都可展开为一个连通的平面图，从而使该公式的应用范围得到了极大推广。图：凸多面体与平面展开图的拓扑同胚欧拉公式的证明(数学归纳法)01/基础步骤(BaseCase)•孤立结点：v=1,e=0,r=1→1-0+1=2(成立)•两个结点一条边：v=2,e=1,r=1→2-1+1=2(成立)•一个结点一个环：v=1,e=1,r=2→1-1+2=2(成立)归纳假设(InductiveHypothesis)假设：对于任意一个连通的平面图G，当边数为e=k时，欧拉公式v-e+r=2成立。注：k为任意正整数，图需保持连通性。递推证明(InductiveStep)1.增加一个新结点(保持连通):v+1,e+1,r不变。公式仍成立：(v+1)-(e+1)+r=v-e+r=2。2.连接两个已有结点(增加面):v不变,e+1,r+1。公式仍成立：v-(e+1)+(r+1)=v-e+r=2。定理6.18：平面图的必要条件定理内容：设G是一个有v个结点、e条边的连通简单平面图，若v≥3，则e≤3v-6。01.面次数分析连通简单平面图中，每个面的边数至少为3。由握手定理，所有面的次数之和等于边数的两倍，故2e≥3r，即r≤2e/3。02.代入欧拉公式将面数的上界代入欧拉公式v-e+r=2，可得不等式：

2≤v-e+(2e/3)。03.整理推导将上一步的不等式移项并整理，消去分数项，最终可得到边数e的上界：

e≤3v-6。这是一个必要非充分条件。其逆否命题具有极强的实用价值：

若一个图不满足e≤3v-6，则它一定不是平面图。例题6.21：证明K5

不是平面图待证命题请证明：在图论中，拥有5个顶点的完全图\(K_5\)无法被画在一个平面上，使得任意两条边都不会在非顶点的位置相交。证明逻辑(基于必要条件)1.确定参数：在K5中，顶点数v=5，边数e=102.代入定理：根据平面图必要条件公式，计算得

3v−6=3×5−6=9。3.比较结果：10>9，不满足上述必要条件。4.结论：K5不是平面图。完全图K5

的结构示意每个顶点均与其他4个顶点相连，边的密集程度

导致无法避免在平面上的交叉。例题6.22：证明

K3,3

不是平面图初步分析：必要条件的局限性在完全二部图K3,3

中，顶点数和边数分别为：顶点数v=6，边数e=9根据平面图的必要条件e≤3v−6进行验证：3v−6=3×6−6=12，满足9≤

12。结论：无法仅通过该不等式判定其非平面性，需引入更强的判定方法。严格证明：反证法1.假设：假设K3,3

是平面图。2.面次数推导：K3,3是偶图，不含奇圈，故每个面的次数至少为4。3.推导新不等式：由2e>4r

得r≤e/2，代入欧拉公式v-e+r=2，可推导出新的必要条件：e≤2v−44.验证矛盾：代入数据得2v-4=8，但K3,3

的边数e=9>8，与上述必要条件矛盾。5.结论：假设不成立，故K3,3

不是平面图。定义6.29：2度结点内同构▍定义内容给定两个图G1和G2

，如果它们是同构的，或者通过反复插入或除去度数为2的结点后，使G1

与G2同构，则称该两图是在2度结点内同构的。核心思想：在一条边上插入或删除一个度数为2的结点，不会改变图的平面性。这一性质是判定图的平面性的关键依据之一。定理6.19：库拉托夫斯基定理(Kuratowski'sTheorem)▌定理内容(TheoremStatement)一个图G是平面图，当且仅当G中不包含与

K5

或

K3,3在2度结点内同构的子图。充分必要条件(Criterion)这是判断一个图是否为平面图的“终极判定工具”。它将复杂的几何嵌入问题转化为纯粹的图论结构识别问题。本质(Essence)任何非平面图，其结构中必然“隐藏”着一个可以通过边收缩操作还原为\(K_5\)或\(K_{3,3}\)的子图。本章总结：平面图与欧拉公式平面图(PlanarGraph)定义：若一个图能画在平面上，且除顶点外，任意两边没有交叉点，则称该图为平面图。面(Face)平面图被边分割出的连通区域。它包含一个特殊的、包含无穷远点的“无限面”(OuterFace)，其余被边完全包围的区域为“有限面”。欧拉公式(Euler'sFormula)对于任意连通平面图，恒有v-e+r=2。其中v为顶点数，e为边数，r为面数（包含无限面）。判定方法(PlanarityTest)•必要条件：若G是简单连通平面图，则e≤3v-6(偶图则满足e≤2v-4)，常用以证伪。•充要条件：库拉托夫斯基定理——一个图是平面图当且仅当它不含K₅或K₃,₃的细分图。感谢观看THANKYOUFORWATCHING06图论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)虽未能证明四色猜想，