非平凡树可以 1-因子分解 ❌，可以 1-因子分解的图一定是偶数阶数的正则图。D. 若图 G 是 2k 正则连通图，则可以分解为 k 个二因子的并。哈密尔顿图一定没有割点 ❌ 存在自环的哈密尔顿图有割点；回路是边不重圈的并；当n为奇数时，Kn有(n-1)/2条没有公共边的哈密尔顿圈。图的割点也是子图的割点 ❌ 八字形的图去掉一个块就没有割点。图 G 的一个 2-因子实际上就是它的一个哈密尔顿圈 ❌

一、图的连通性刻画(⼀)、割边及其性质定义1 边eee为图GGG的⼀条割边，如果 ω(G−e)>ω(G)ω(G − e) > ω(G)ω(G−e)>ω(G)。（ω(G)ω(G)ω(G) 表示图 GGG 连通分支的数量，G−eG − eG−e 表示只去掉 eee 这条边，边两边的点不动）e2e_2e2​ 为割边，是因为去掉 e2e_2e2​ 这条边后只剩下右边一个点，与其他部分不连

** 数据 **//** 相对高度 **//** 父节点 **//** 左子树 **//** 右子树 **/

第一章 图的基本概念基本概念名词概念有限图顶点集和边集都有限的图称为有限图；平凡图只有一个顶点而无边的图称为平凡图；其他所有的图都称为非平凡图空图边集为空的图称为空图；n阶图顶点数为n的图称为n阶图；(n, m) 图顶点数为n,边数为m的图称为(n, m) 图；边的重数连接两个相同顶点的边的条数称为边的重数；重数大于1的边称为重边；环端点重合为一点的边称为环；简单图无环无重边的图称为简单图；其余的

（1）至少有 n-1 条边。（2）如果边数大于 n-1，则至少有一条闭迹。（3）如恰有 n-1 条边，则至少有一个奇度点。若对∀v∈VG, 有dv≥22m∑dv≥2n⇒m≥nn−1;若G中有1度顶点，对顶点数n作数学归纳。当 n=2 时，G显然至少有一条边，结论成立。设当n = k时，结论成立，即至少有 k - 1条边当 n=k+1 时，设去掉任一一个一度顶点vdV−1，则剩下的图G−v满足 n

(一)、重点概念1、图、简单图、图的同构与自同构、度序列与图序列、补图与自补图、两个图的联图、两个图的积图、偶图；(1)图：一个图是一个序偶<V,E><V,E><V,E>，记为G=(V,E)G=(V,E)G=(V,E),其中：1)VVV是一个有限的非空集合，称为顶点集合,其元素称为顶点或点。用∣V∣|V|∣V∣表示顶点数；2)EEE是由VVV中的点组成的无序对构

一、图的边着色(一)、相关概念定义1 给定图 G=(V,E)G=(V,E)G=(V,E)，称映射 π:E→{1,2,3,...,k}\pi : E \to \{1, 2, 3, ..., k\}π:E→{1,2,3,...,k} 为 GGG 的一个 kkk 边着色，简称边着色，称 {1,2,3,...,k}\{1, 2, 3, ..., k\}{1,2,3,...,k} 为色集。若 π\piπ 为

一、欧拉图与中国邮路问题(一)、欧拉图及其性质1、欧拉图的概念(1)、问题背景—欧拉与哥尼斯堡七桥问题注：一笔画----中国古老的民间游戏要求：对于一个图G, 笔不离纸, 一笔画成.(2)、欧拉图概念经过连通图 GGG 的每条边的迹被称为 Euler 迹（欧拉迹）（欧拉迹不要求回到原点，经过所有的点与边）定义1 对于连通图GGG，如果GGG中存在经过每条边的 闭迹（即 Euler 闭迹），则称GG

一、偶图的匹配问题偶图回顾kkk 正则偶图：两个顶点子集包含顶点个数相等对称差运算：保留不同的，去掉相同的(一)、图的匹配与贝尔热定理1、图的匹配相关概念(1)、匹配 MMM — 如果 MMM 是图 GGG 的边子集(不含环），且 MMM 中的任意两条边没有共同顶点（即不相邻），则称 MMM 是 GGG 的一个匹配或对集或边独立集。如果 GGG 中顶点 vvv 是 GGG 的匹配 MMM 中某条边

一、树的概念与性质(一)、树的概念与应用1、树的概念定义1 不含圈的图称为无圈图，树是连通的无圈图。（T3T_3T3​ 是平凡图，即度为 0）定义2称无圈图GGG为森林。注：(1) 树与森林都是单图; (单图即简单图，无重边无环的图)(2) 树与森林都是偶图。2、树的应用树是图论中应用最为广泛的一类图。在理论上，由于树的简单结构，常常是图论理论研究的“试验田”。在实际问题中，许多实际问题的图论模型