6.1 图的基本概念

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/度数与握手定理顶点的度数是指与该顶点相关联的边的数量。握手定