跳转至

408 高频考点精讲:图的概念(Graph Fundamental Concepts and Theorems)

模块归属:数据结构 · 图结构
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生


一、 考情档案

  • 近十年考查频次:3 次(2016~2025 年:2017#7、2022#6、2025#6)
  • 历年总考查频次:6 次(历年统考考查还包含 2009#5、2010#7、2014#6 等)
  • 出题形式:单项选择题为主,分值均为 2 分。常考查握手定理代数方程求解、图连通性充要判定、有向图强连通性质、度数约束下的拓扑回路存在性推导等。
  • 命题特点:
  • 抽象逻辑推导要求高:题目频繁出现“必有”、“必定”、“充分条件”等逻辑量词,考查反例构造能力与严格的数学反证法。
  • 极值与边界模型集中:重点考查维持图非连通的最大边数、保证图必定连通的最小边数、强连通图的最小弧数等极值边界。
  • 概念交叉融合:命题常将图的基本度数定理、遍历算法(BFS/DFS)适用范围、拓扑排序存在性与唯一性、带权路径性质交叉综合命制。
近十年考查年份分布:
2016   2017   2018   2019   2020   2021   2022   2023   2024   2025
 -      √      -      -      -      -      √      -      -      √
       (#7)                               (#6)                 (#6)

二、 具体考察内容

1. 图的形式化定义与分类基准

(1)图的代数定义

图由顶点集合与边集合共同构成,形式化记为二元组: $\(G = (V, E)\)$ * 顶点集 \(V(G)\):图的所有顶点的非空有限集合。 - 核心公理限制:图的顶点集绝不能为空(\(V \neq \varnothing\)$ \text{),即} $\(|V| \ge 1\)。线性表、栈、队列以及树均允许为空结构,但数据结构中不存在“空图”。 * 边集 \(E(G)\)$ \text{:连接图中顶点的边的有限集合。边集可以为空(} $\(E = \varnothing\)$ \text{),当} $\(E = \varnothing\) 时,图中所有顶点互不连通,该图退化为由孤立顶点构成的零图(Null Graph)。

(2)有向图与无向图

  • 无向图(Undirected Graph): 若图中的边均无方向,则称该图为无向图。边由无序对表示,记作 \((u, v)\)$ \text{或} $\((v, u)\)$ \text{,满足} $\((u, v) = (v, u)\)$ \text{。此时称顶点} $\(u\)$ \text{与顶点} $\(v\)$ \text{互为邻接点,边} $\((u, v)\)$ \text{依附于顶点} $\(u\)$ \text{和} $\(v\)。
  • 有向图(Directed Graph / Digraph): 若图中的边具有确定方向,则称该边为有向边(弧,Arc),该图为有向图。弧由有序对表示,记作 \(\langle u, v \rangle\),其中:
  • \(u\) 称为弧尾(Tail),亦称始点;
  • \(v\) 称为弧头(Head),亦称终点。
  • 必须严格区分 \(\langle u, v \rangle \neq \langle v, u \rangle\)。\(\langle u, v \rangle\)$ \text{表示一条从} $\(u\)$ \text{指向} $\(v\) 的单向关联。

(3)简单图、多重图与完全图

  • 自环(Self-loop):起点与终点为同一个顶点的边,即 \((u, u)\)$ \text{或} $\(\langle u, u \rangle\)。
  • 多重边(Multiple Edges):连接相同顶点对的多条同方向有向边或无向边。
  • 简单图(Simple Graph):不存在自环且不存在多重边的图。在 408 统考考纲范围内,若无特别说明,所讨论的图均为简单图。
  • 完全图(Complete Graph):
  • 无向完全图 \(K_n\)$ \text{:含} $\(n\) 个顶点的无向图中,任意两个不同顶点之间都恰好存在一条边。其边数达到无向简单图的理论极大值: $\(|E| = \binom{n}{2} = \frac{n(n-1)}{2}\)$
  • 有向完全图:含 \(n\) 个顶点的有向图中,任意两个不同顶点之间都存在方向相反的两条有向边。其弧数达到有向简单图的理论极大值: $\(|E| = 2 \times \binom{n}{2} = n(n-1)\)$

2. 顶点的度与握手定理(Handshaking Lemma)

(1)度的形式化定义

  • 无向图顶点的度(Degree): 顶点 \(v\)$ \text{的度} $\(\deg(v)\) 定义为与该顶点相关联的边数。
  • 有向图顶点的度:
  • 入度(In-degree, \(ID(v)\)$ \text{):以顶点} $\(v\) 为弧头的弧的数目;
  • 出度(Out-degree, \(OD(v)\)$ \text{):以顶点} $\(v\) 为弧尾的弧的数目;
  • 总度(Total Degree, \(TD(v)\)$ \text{):顶点} $\(v\) 的入度与出度之和,即: $\(TD(v) = ID(v) + OD(v)\)$

(2)握手定理推导与数学证明

  • 欧拉握手定理(无向图): 设无向图 \(G = (V, E)\),则所有顶点的度数之和等于边数的 2 倍: $\(\sum_{v \in V} \deg(v) = 2|E|\)$ 证明:考虑图的关联结构。每一条边 \(e = (u, v)\)$ \text{连接两个端点} $\(u\)$ \text{和} $\(v\)$ \text{。在遍历所有顶点并累加其度数} $\(\sum_{v \in V} \deg(v)\)$ \text{时,每条边} $\(e\)$ \text{恰好在端点} $\(u\)$ \text{处被计数一次,在端点} $\(v\) 处被计数一次,合计被严格计算了 2 次。因此度数总和恒等于边数的 2 倍。
  • 有向图的握手恒等式: 在有向图 \(G = (V, E)\)$ \text{中,每条弧} $\(\langle u, v \rangle\)$ \text{从弧尾} $\(u\)$ \text{出发,向弧头} $\(v\) 进入。每条弧贡献 1 个出度与 1 个入度: $\(\sum_{v \in V} OD(v) = \sum_{v \in V} ID(v) = |E|\)$ $\(\sum_{v \in V} TD(v) = \sum_{v \in V} (OD(v) + ID(v)) = 2|E|\)$

(3)核心推论与代数性质

  • 推论 1(奇度顶点定理):在任何无向图中,度数为奇数的顶点个数必为偶数。 证明:将顶点集 \(V\)$ \text{划分为奇度顶点集} $\(V_{odd}\)$ \text{与偶度顶点集} $\(V_{even}\)。由握手定理: $\(\sum_{v \in V_{odd}} \deg(v) + \sum_{v \in V_{even}} \deg(v) = 2|E|\)$ 由于 \(2|E|\)$ \text{为偶数,且} $\(\sum_{v \in V_{even}} \deg(v)\) 为偶数累加必为偶数,可得: $\(\sum_{v \in V_{odd}} \deg(v) = 2|E| - \sum_{v \in V_{even}} \deg(v) \equiv 0 \pmod 2\)$ 集合 \(V_{odd}\)$ \text{中每个顶点的度数均为奇数。若干个奇数相加的和为偶数,充要条件是项数必须为偶数。因此} $\(|V_{odd}|\) 必须为偶数。
  • 推论 2(平均度数原理):无向图的平均度数为 \(\bar{d} = \frac{2|E|}{|V|}\)$ \text{。图中必定存在顶点} $\(u\)$ \text{使得} $\(\deg(u) \ge \lceil \bar{d} \rceil\)$ \text{,同时存在顶点} $\(w\)$ \text{使得} $\(\deg(w) \le \lfloor \bar{d} \rfloor\)。

3. 路径、回路与子图结构

(1)路径与回路

  • 路径(Path): 从顶点 \(v_p\)$ \text{到顶点} $\(v_q\)$ \text{的顶点序列} $\((v_0, v_1, v_2, \dots, v_k)\)$ \text{,满足} $\(v_0 = v_p, v_k = v_q\)$ \text{,且对任意} $\(0 \le i \le k - 1\)$ \text{,均有} $\((v_i, v_{i+1}) \in E\)$ \text{(有向图中为} $\(\langle v_i, v_{i+1} \rangle \in E\))。
  • 路径长度(Path Length):路径序列中所包含的边的数目 \(k\)。在带权图中,路径长度为路径上各边权值的代数和。
  • 回路 / 环(Cycle):起点与终点相同的路径,即 \(v_0 = v_k\)(\(k \ge 1\))。
  • 简单路径(Simple Path):序列中顶点互不重复出现的路径。
  • 简单回路(Simple Cycle):除起点与终点相同(\(v_0 = v_k\))外,其余中间顶点互不重复出现的回路。

(2)子图与生成子图辨析

  • 子图(Subgraph): 设图 \(G = (V, E)\)$ \text{与} $\(G' = (V', E')\)$ \text{。若} $\(V' \subseteq V\)$ \text{且} $\(E' \subseteq E\)$ \text{,则称} $\(G'\)$ \text{为} $\(G\) 的子图。 结构合法性约束:子图的边集 \(E'\)$ \text{中所包含的任何一条边,其两个端点必须完全包含在顶点子集} $\(V'\) 中,不允许出现悬空边。
  • 生成子图(Spanning Subgraph): 若子图 \(G'\)$ \text{包含原图} $\(G\)$ \text{的全部顶点(即} $\(V' = V\)$ \text{),且边集满足} $\(E' \subseteq E\)$ \text{,则称} $\(G'\)$ \text{为} $\(G\) 的生成子图。生成子图仅对边进行删减,保留了全部顶点。

4. 连通性、强连通性与分量理论

(1)无向图连通性与连通分量

  • 连通(Connected):若从顶点 \(u\)$ \text{到顶点} $\(v\)$ \text{存在路径,则称顶点} $\(u\)$ \text{与顶点} $\(v\) 连通。
  • 连通图(Connected Graph):若无向图中任意两个不同顶点之间都是连通的,则称该图为连通图。
  • 连通分量(Connected Component):无向图中的极大连通子图。
  • “极大”的数学内涵:该子图自身保持连通,且必须包含该连通区域内所有可达顶点以及这些顶点在原图中依附的所有边。若向该子图中再加入原图任意一个外部顶点或外部边,必将破坏连通性或脱离原图范围。
  • 非连通图的分解:任何非连通无向图都可以唯一分解为 \(c\)(\(c \ge 2\))个互不相交的连通分量的并集。连通图的连通分量有且仅有 1 个(即其自身)。

(2)生成树与生成森林

  • 生成树(Spanning Tree):连通无向图的极小连通子图。
  • “极小”的数学内涵:包含图中全部 \(n\)$ \text{个顶点,且边数最少(恰好为} $\(n - 1\) 条)。
  • 动态边界性质:
    1. 在生成树中删去任意一条边,该子图必然分裂为两个连通分量,不再连通;
    2. 在生成树中添加任意一条属于原图但不属于生成树的边,必然导致图中产生唯一的一个简单回路。
  • 生成森林(Spanning Forest):非连通无向图中各个连通分量的生成树汇集的集合。
  • 若无向图包含 \(n\)$ \text{个顶点,划分为} $\(c\) 个连通分量,则其生成森林包含的边数严格满足: $\(|E_{forest}| = n - c\)$

(3)有向图强连通性与强连通分量

  • 强连通(Strongly Connected):在有向图中,若任意两个不同顶点 \(u\)$ \text{和} $\(v\)$ \text{,既存在从} $\(u\)$ \text{到} $\(v\)$ \text{的有向路径,又存在从} $\(v\)$ \text{到} $\(u\) 的有向路径(即双向互达),则称该图为强连通图。
  • 强连通分量(Strongly Connected Component, SCC):有向图中的极大强连通子图。
  • 弱连通图(Weakly Connected Graph):忽略有向图中所有弧的方向将其视为无向图后,若该无向图是连通的,则称原图为弱连通图。

5. 核心极值定理与模型推导

(1)定理 1:无向连通图的边数下界

含 \(n\) 个顶点的无向图若是连通的,其边数满足: $\(|E| \ge n - 1\)$ * 逆否命题定理:若含 \(n\)$ \text{个顶点的无向图边数满足} $\(|E| < n - 1\)$ \text{(即} $\(n > |E| + 1\)),则该图必定是不连通的。 * 注意陷阱:该定理是必要条件而非充分条件。若 \(|E| \ge n - 1\),图不一定连通(边可以集中分布在局部顶点之间形成环,而剩余顶点孤立)。

(2)定理 2:保证无向图必定连通的最小边数阈值

对于含 \(n\) 个顶点的无向简单图,若要保证无论边如何连接,该图必定是连通图,边数必须满足的充要条件为: $\(|E| > \binom{n-1}{2} = \frac{(n-1)(n-2)}{2}\)$ 即必定连通的最小边数下界为: $\(|E|_{\min\_guaranteed} = \frac{(n-1)(n-2)}{2} + 1\)$ * 极值反例构造模型: 考虑最极端的非连通构造:取 \(n-1\)$ \text{个顶点构造一个无向完全子图} $\(K_{n-1}\)$ \text{,将剩余 1 个顶点设为孤立点。此时非连通图能够容纳的边数达到理论极大值} $\(\frac{(n-1)(n-2)}{2}\)。在此基础上任意再添加 1 条边,该边必将孤立顶点与完全子图相连,使整图变为连通图。

极端非连通模型示意图 (n = 5):
完全子图 K_4 (边数 = 6)           孤立点
   v1 ----- v2
   | \   / |
   |   X   |                   v5 (孤立)
   | /   \ |
   v3 ----- v4
总边数 = 6,图不连通。再加任意 1 条边连接 v5,图必连通。

(3)定理 3:强连通有向图的弧数下界

含 \(n\) 个顶点的有向图若是强连通的,其弧数满足: $\(|E| \ge n\)$ * 极值模型:含 \(n\)$ \text{个顶点的简单有向环路} $\(v_1 \to v_2 \to \dots \to v_n \to v_1\)$ \text{。此时弧数恰好为} $\(n\)$ \text{,每个顶点的入度和出度均为 1,任意两顶点相互可达。若弧数} $\(< n\),根据握手定理必存在入度为 0 或出度为 0 的顶点,破坏强连通性。

(4)定理 4:各顶点度数 \(\ge 2\) 的无向图回路存在性

设 \(G = (V, E)\)$ \text{为有限简单无向图。若对任意} $\(v \in V\)$ \text{,均满足} $\(\deg(v) \ge 2\)$ \text{,则图} $\(G\) 中必存在简单回路。 * 严格数学证明(最长路径法): 1. 由于图 \(G\)$ \text{的顶点集} $\(V\) 有限,图中所含简单路径的长度必存在最大值。 2. 设 \(P = (v_1, v_2, \dots, v_k)\)$ \text{为图} $\(G\)$ \text{中一条最长简单路径,其长度为} $\(k-1\)。 3. 考察端点 \(v_k\)$ \text{。由题设} $\(\deg(v_k) \ge 2\),\(v_k\)$ \text{至少与 2 个不同顶点相邻。在路径} $\(P\)$ \text{中,} $\(v_k\)$ \text{与其前驱} $\(v_{k-1}\) 相邻。 4. 若 \(v_k\)$ \text{存在相邻顶点} $\(w \notin \{v_1, v_2, \dots, v_k\}\)$ \text{,则可以将路径扩展为} $\((v_1, \dots, v_k, w)\)$ \text{,形成长度为} $\(k\)$ \text{的更长简单路径,与} $\(P\) 是最长简单路径矛盾。 5. 因此,\(v_k\)$ \text{的所有邻接点必须全部落在路径} $\(P\)$ \text{内部。除} $\(v_{k-1}\)$ \text{外,} $\(v_k\)$ \text{必然还与路径上前置的某个顶点} $\(v_i\)(\(1 \le i \le k - 2\))相邻。 6. 顶点序列 \((v_i, v_{i+1}, \dots, v_{k-1}, v_k, v_i)\) 构成了一条长度大于等于 3 的简单回路。证毕。 * 基于树与森林性质的反证法: 若图 \(G\)$ \text{无回路,则图} $\(G\)$ \text{为无向森林。无向森林的每个连通分量均为树。根据树的性质,任何含至少 2 个顶点的树必至少存在 2 个度为 1 的叶子节点(或孤立点度为 0)。这与题设“所有顶点度数均} $\(\ge 2\)$ \text{”产生矛盾。因此图} $\(G\) 必包含回路。

(5)定理 5:有向无环图(DAG)与零入度顶点

  • DAG 的零入度性质:任何有限有向无环图必至少存在一个入度为 0 的顶点,且必至少存在一个出度为 0 的顶点。
  • 一般有向图的反例:若有向图中包含环路,则可以完全不存在入度为 0 的顶点。例如单个有向回路中所有顶点的入度与出度均严格等于 1。

三、 近十年真题精讲(2016~2025)


【真题 1】2025 年 408 统考第 6 题 · 图结构综合性质辨析

题目
下列关于图的叙述中,正确的是( )。
A. 有向图必定存在入度为 0 的顶点
B. 有向无环图的拓扑排序有序序列存在且唯一
C. 各顶点的度均大于等于 2 的无向图必有回路
D. 可用 BFS 算法求出带权图中的每一对顶点的最短路径

【解析】

  • 选项 A 深度辨析(错误): 对于一般有向图,若图内包含有向环路,则各顶点的入度完全可以均大于 0。 反例构造:构造包含 3 个顶点的有向环 \(v_1 \to v_2 \to v_3 \to v_1\)。该图中每个顶点的入度均为 1,出度均为 1,不存在任何入度为 0 的顶点。 理论延伸:只有在限定图为“有向无环图(DAG)”时,才必定存在入度为 0 的顶点(拓扑排序的起始顶点)。全称命题未加 DAG 约束,结论不成立。
  • 选项 B 深度辨析(错误): 有向无环图(DAG)必定存在拓扑序列,但拓扑序列不一定唯一。 拓扑排序序列唯一的充要条件是:在拓扑排序算法执行的每一个步骤中,当前图中入度为 0 的顶点有且仅有 1 个(此时该 DAG 存在唯一的哈密顿路径)。 反例构造:设顶点集 \(V = \{1, 2, 3\}\)$ \text{,弧集} $\(E = \{\langle 1, 2 \rangle, \langle 1, 3 \rangle\}\)$ \text{。合法拓扑序列可以是} $\((1, 2, 3)\)$ \text{,也可以是} $\((1, 3, 2)\)。由于序列不唯一,B 项错误。
  • 选项 C 深度辨析(正确): 反证推导:假设满足“每个顶点度数均 \(\ge 2\)”的无向图无回路,则该图必为无向森林。无向森林由若干棵树(或孤立点)组成。 设某连通分量包含 \(k\) 个顶点:
  • 若 \(k = 1\),孤立顶点的度数为 0,与题设矛盾;
  • 若 \(k \ge 2\)$ \text{,该连通分量为一棵树,其边数恰好为} $\(k - 1\) 条。 根据握手定理,该树所有顶点的度数之和为 \(2(k - 1) = 2k - 2\)。 若每个顶点的度数均大于等于 2,则该分量的度数总和必满足: $\(\sum \deg(v) \ge 2k\)$ 产生 \(2k \le 2k - 2\)$ \text{(即} $\(0 \le -2\))的代数矛盾! 因此,假设不成立,图中必定存在简单回路。C 项正确。
  • 选项 D 深度辨析(错误): 广度优先搜索(BFS)算法求解最短路径的充要前提是:图为无权图,或所有边的权值均严格相等。 在边权非负的一般带权图中,路径长度取决于边权之和而非边的数目,较多边数的路径其权值总和可能小于较少边数的路径,BFS 的贪心最优子结构失效。求解一般带权图的单源最短路径必须使用 Dijkstra 算法;求解每一对顶点之间的最短路径应使用 Floyd-Warshall 算法。D 项错误。

正确答案:C


【真题 2】2022 年 408 统考第 6 题 · 无向图连通性与边数判定

题目
对于无向图 \(G=(V,E)\),下列选项中,正确的是( )。
A. 当 \(|V| > |E|\)$ \text{时,} $\(G\) 一定是连通的
B. 当 \(|V| < |E|\)$ \text{时,} $\(G\) 一定是连通的
C. 当 \(|V| = |E| - 1\)$ \text{时,} $\(G\) 一定是不连通的
D. 当 \(|V| > |E| + 1\)$ \text{时,} $\(G\) 一定是不连通的

【解析】

  • 理论基石(无向连通图边数下界定理): 若无向图 \(G=(V, E)\)$ \text{是连通图,则包含} $\(|V|\)$ \text{个顶点的极小连通子图为生成树,树的边数恰为} $\(|V| - 1\)。 向树中添加边可形成环,但图依然连通,故连通图的边数必须满足: $\(|E| \ge |V| - 1\)$
  • 选项 D 严格证明(正确): 将连通性命题转化为逆否命题: 原命题:“\(G\)$ \text{是连通图} $\(\implies |E| \ge |V| - 1\)”。 其等价的逆否命题为:“\(|E| < |V| - 1 \implies G\) 是非连通图”。 将不等式进行代数移项变换: $\(|E| < |V| - 1 \iff |V| > |E| + 1\)$ 因此,当 \(|V| > |E| + 1\)$ \text{时,边数甚至不足以支撑连通所需的最小骨架(树),图} $\(G\) 必定不连通!D 项正确。
  • 选项 A 辨析(错误): 当 \(|V| > |E|\) 时,图可能是连通的,也可能是非连通的。 反例构造:设 \(|V|=4, |E|=1\)$ \text{。此时满足} $\(|V| > |E|\),但 4 个顶点仅有 1 条边,图被分割为 3 个连通分量,并不连通。
  • 选项 B 辨析(错误): 当 \(|V| < |E|\) 时,边数虽然较多,但边可以完全集中在某几个顶点之间构成完全子图,导致其余顶点孤立。 反例构造:设 4 个顶点构成完全子图 \(K_4\)$ \text{(含 6 条边),额外加入 1 个孤立顶点。此时顶点数} $\(|V|=5\)$ \text{,边数} $\(|E|=6\)$ \text{,满足} $\(|V| < |E|\),但该图包含 2 个连通分量,是不连通图。
  • 选项 C 辨析(错误): 当 \(|V| = |E| - 1\)$ \text{即} $\(|E| = |V| + 1\) 时,边数多于生成树的边数,完全可以构成连通图。 反例构造:在包含 4 个顶点的简单回路(4 个顶点、4 条边)中增加一条对角线,形成含有 4 个顶点、5 条边的连通图。此时 \(|V| = 4, |E| = 5\)$ \text{,满足} $\(|V| = |E| - 1\),但图是连通的,“一定不连通”结论错误。

正确答案:D


【真题 3】2017 年 408 统考第 7 题 · 握手定理与极值代数求解

题目
已知无向图 \(G\)$ \text{含有 16 条边,其中度为 4 的顶点个数为 3,度为 3 的顶点个数为 4,其他顶点的度均小于 3。图} $\(G\) 所含的顶点个数至少是( )。
A. 10          B. 11          C. 13          D. 15

【解析】

  1. 根据握手定理建立总度数恒等式: 无向图中所有顶点的度数之和等于边数的 2 倍。已知边数 \(|E| = 16\): $\(\sum_{v \in V} \deg(v) = 2 \times |E| = 2 \times 16 = 32\)$
  2. 分解已知顶点的度数贡献:
  3. 3 个顶点的度数为 4,度数贡献为:\(3 \times 4 = 12\);
  4. 4 个顶点的度数为 3,度数贡献为:\(4 \times 3 = 12\);
  5. 已确定的这 \(3 + 4 = 7\) 个顶点累积的度数和为: $\(\text{Sum}_{known} = 12 + 12 = 24\)$
  6. 计算剩余顶点的度数总和需求: 设其余顶点的集合为 \(V_{rest}\),其度数总和为: $\(\sum_{u \in V_{rest}} \deg(u) = 32 - 24 = 8\)$
  7. 极值优化求解: 题目要求图 \(G\)$ \text{所含的顶点总数至少是多少,等价于求解剩余顶点集合的基数} $\(|V_{rest}|\) 的最小值。 由题设,“其他顶点的度均小于 3”,即: $\(\forall u \in V_{rest}, \quad \deg(u) \le 2\)$ 设剩余顶点个数为 \(k = |V_{rest}|\)。根据不等式放缩: $\(8 = \sum_{u \in V_{rest}} \deg(u) \le \sum_{u \in V_{rest}} 2 = 2k\)$ $\(2k \ge 8 \implies k \ge 4\)$
  8. 合法性与奇度顶点校验:
  9. 当 \(k = 4\) 时,剩余 4 个顶点的度数均取最大值 2。
  10. 此时整张图中各顶点的度数分布为:3 个度为 4,4 个度为 3,4 个度为 2。
  11. 检验奇度顶点:度为 3 的顶点个数为 4,4 是偶数,完全满足“无向图中度数为奇数的顶点个数必须为偶数”的充要条件,拓扑结构合法。
  12. 此时图所含顶点总数达到最小值: $\(|V|_{\min} = 3 + 4 + k_{\min} = 3 + 4 + 4 = 11\)$

正确答案:B


四、 核心解题套路与易错陷阱

1. 核心解题套路

套路一:握手定理极值代数三步法

  1. 列总和方程:直接计算 \(2|E|\) 作为整个方程的右端项;
  2. 拆分已知度数:将已知顶点的度数加权求和,计算剩余度数缺口 \(\Delta D = 2|E| - \sum \deg(v_{known})\);
  3. 极值放缩与奇偶校验:
  4. 若求顶点数最少,使剩余顶点的度数尽可能取最大值;
  5. 若求顶点数最多,使剩余顶点的度数尽可能取最小值(简单图无自环多重边时注意孤立点度数为 0,但需结合连通性约束);
  6. 最后必须检查奇度顶点总数是否为偶数,若为奇数则需调整 1 个顶点的度数以满足合法性。

套路二:连通性判定双界限模型

处理无向图顶点数 \(n\)$ \text{与边数} $\(e\) 的连通性题目时,立即调用两个绝对界限: 1. 下界门槛(树):\(e < n - 1 \iff n > e + 1 \implies\) 必定不连通。 2. 充分上界(极端团):\(e > \frac{(n-1)(n-2)}{2} \implies\) 必定连通。 3. 不确定中间带:当 \(n - 1 \le e \le \frac{(n-1)(n-2)}{2}\) 时,图可能连通也可能不连通,断言“一定连通”或“一定不连通”的选项均可直接排除。

套路三:拓扑与回路快速甄别法

  1. 判断回路存在:若所有顶点度数 \(\ge 2\),必有回路;若有向图中无入度为 0 的顶点,必有有向回路。
  2. 判断拓扑序列唯一性:不仅图必须是有向无环图,而且每次入度减为 0 压入暂存结构的顶点数必须始终恒等于 1。

2. 易错陷阱清单

  • 陷阱 1:混淆“极大连通子图”与“极小连通子图”
  • 连通分量是极大连通子图:要求顶点和边包含完整,不可再向外扩张;
  • 生成树是极小连通子图:要求边数最少(\(n - 1\) 条),不可再删边。两者修饰语绝对不可对调。
  • 陷阱 2:误以为“边数足够多图就一定连通” 在没有达到必定连通阈值 \(\frac{(n-1)(n-2)}{2} + 1\)$ \text{之前,即便边数多达上百条,只要所有边全部连接在} $\(n-1\)$ \text{个顶点内部,剩下的第} $\(n\) 个顶点依然是孤立点,图依然不连通。
  • 陷阱 3:误将无向图连通性质套用到有向图 无向图连通最少需 \(n-1\)$ \text{条边;有向图强连通最少需} $\(n\)$ \text{条边(构成单向闭环)。若有向图只有} $\(n-1\) 条边,绝不可能是强连通图。
  • 陷阱 4:忽略图的非空性约束 在选择题辨析“是否存在空图”时,必须牢记:根据图的定义,图的顶点集合 \(V\)$ \text{必须非空(} $\(V \neq \varnothing\)$ \text{)。不存在} $\(V = \varnothing\) 的图!

五、 考点速记清单

1. 核心公式与代数极值速查

概念名称 代数关系式 / 极值公式 关键限制条件
无向图握手定理 \(\sum \deg(v) = 2\|E\|\) 奇度顶点个数必为偶数
有向图握手定理 \(\sum ID(v) = \sum OD(v) = \|E\|\)$ \text{ 总度数之和为} $\(2\|E\|\)
无向完全图边数 \(\|E\| = \frac{n(n-1)}{2}\) 简单无向图边数上限
有向完全图弧数 \(\|E\| = n(n-1)\) 简单有向图弧数上限
连通图边数下界 \(\|E\| \ge n - 1\) 达到下界时为生成树
保证必然连通最小边数 \(\|E\| = \frac{(n-1)(n-2)}{2} + 1\)$ \text{ 击穿} $\(K_{n-1}\) 孤立点模型
强连通图边数下界 \(\|E\| \ge n\) 达到下界时为单向有向环
生成森林边数公式 \(\|E\| = n - c\) \(n\)$ \text{为顶点数,} $\(c\) 为连通分量数

2. 关键概念对立辨析速记表

辨析维度 概念 A 概念 B 核心区别准则
子图极值性 连通分量(极大连通子图) 生成树(极小连通子图) 连通分量包含全部可达边;生成树仅含 \(n-1\) 条边
连通性强弱 无向图连通 有向图强连通 强连通要求任意两点双向互达;最少边数无向需 \(n-1\)$ \text{,有向需} $\(n\)
路径约束 简单路径 简单回路 简单路径顶点不重复;简单回路仅起点与终点重合
结构前提 DAG 必有零入度点 有向图不一定有零入度点 只要图中存在有向回路,所有顶点的入度均可 \(\ge 1\)