考研笔记

图的基本概念

图论的直觉你有，这一节要补的是教材那一套精确到字的术语。

第 6 章的选择题有相当比例落在术语上：极大连通子图、生成子图、简单路径、强连通分量——这些词在算法竞赛里要么不用，要么用得很随意。这一页只做一件事：把每个词的边界钉死。

机制

图不能是空图

教材开篇的注意框，是第 6 章第一个考点：

线性表可以是空表，树可以是空树，但图不可以是空图。 也就是说，图中不能一个顶点也没有，图的顶点集 一定非空，但边集 可以为空，此时图中只有顶点而没有边。

「 非空、 可空」这一句要能立刻答出来。

有向图与无向图

边的记法术语
有向图有向边（也称弧），顶点的有序对 称为弧尾， 称为弧头； 称为从 到 的弧，也称 邻接到
无向图无向边（简称边），顶点的无序对 或 和 互为邻接点；边 依附于 和 ，或称边 和 相关联

边界辨析：

「弧尾」是起点，「弧头」是终点。 记法上 里 在前是尾、 在后是头—— 和箭头的方向一致，但和「头在前」的日常直觉相反。 十字链表的 tailvex/headvex 两个域名就是从这里来的（6.2.3）。

简单图与多重图

一个图 若满足：① 不存在重复边；② 不存在顶点到自身的边，则称图 为简单图。若图 中某两个顶点之间的边数大于 1 条，又允许顶点通过一条边和自身关联，则称图 为多重图。

教材原话：「本书中仅讨论简单图。」

度、入度、出度

  • 无向图中，顶点 的度是指依附于顶点 的边的条数，记为 。无向图的全部顶点的度之和等于边数的 2 倍，因为每条边和两个顶点相关联。
  • 有向图中，顶点 的度分为入度和出度：入度是以顶点 为终点的有向边的数目，记为 ；出度是以顶点 为起点的有向边的数目，记为 。顶点 的度等于其入度与出度之和，即 。
  • 有向图的全部顶点的入度之和与出度之和相等，并且等于边数，这是因为每条有向边都有一个起点和终点。
无向有向

关联对照：

「度数之和 边数」与 5.1.3 的「结点数 度数之和 」不是同一条。 树里的「度」只算孩子数（出度），所以每条边只被数一次； 图里无向边的两端都要计度，所以要乘 2。同一个字，两章的定义不同。

路径、回路与环

  • 顶点 到顶点 之间的一条路径是指顶点序列 。
  • 路径上的边的数目称为路径长度。
  • 第一个顶点和最后一个顶点相同的路径称为回路或环。
  • 若一个图有 个顶点，且有大于 条边，则此图一定有环。
  • 简单路径：在路径序列中，顶点不重复出现的路径。
  • 简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。
  • 距离：从顶点 出发到顶点 的最短路径若存在，则此路径的长度称为从 到 的距离。若从 到 根本不存在路径，则记该距离为无穷（）。

子图与生成子图

设有两个图 和 ，若 是 的子集，且 是 的子集，则称 是 的子图。若有满足 的子图 ，则称其为 的生成子图。

边界辨析：

教材注意框：「并非 和 的任何子集都能构成 的子图，因为这样的子集可能不是图，即 的子集中的某些边关联的顶点可能不在这个 的子集中。」 取了边就必须把它的两个端点一起取上——这一条几乎年年以判断题出现。

「生成子图」的判据只有一个：顶点集完全相同。 边可以随便删，顶点一个都不能少。

连通性

概念定义
连通（无向图）若从顶点 到顶点 有路径存在，则称 和 是连通的
连通图图 中任意两个顶点都是连通的
连通分量无向图中的极大连通子图
强连通（有向图）若有一对顶点 和 ，从 到 和从 到 之间都有路径，则称这两个顶点是强连通的
强连通图 / 强连通分量任意一对顶点都强连通 / 有向图中的极大强连通子图

边数与连通性的两条界：

  • 假设一个图有 个顶点，若边数小于 ，则此图必是非连通图。
  • 教材脚注给了反向的界：非连通情况下边最多的情况是「由 个顶点构成一个完全图，此时再加入一个孤立顶点」，即最多 条边。

边界辨析：

「边数 非连通」是单向的。 边数 不能推出连通—— 上面那个反例正好有 条边（远多于 ）却不连通。 同样，「边数 一定有环」也是单向的，有环不代表边多。

口径差异：

算法竞赛里这些词用得很松：「连通块」就是连通分量，「子图」常指任意点边集合， 「简单路径」和「路径」经常混用，n 个点 n-1 条边直接叫树。 408 每个词都有精确定义，而且专考这些精确性：

  • 极大连通子图（不能再加顶点仍连通），不是「最大」；
  • 生成子图要求顶点集完全相同；
  • 简单回路允许首尾顶点重复，简单路径不允许；
  • 图不能为空图。

另外算竞几乎不区分「弧头/弧尾」，而十字链表的两个域名直接用了它们。

手算模板

数度与边：无向图 ；有向图 。给一半的度数求边数，套这两式。

判连通分量个数：从任一未访问顶点出发做一次遍历（6.3），能到达的所有顶点构成一个连通分量；重复直到所有顶点被访问，遍历发起的次数就是连通分量数。

极值题的三个界：

问题答案
个顶点的无向连通图至少几条边
个顶点的无向图至少几条边才一定连通
个顶点的无向图最多几条边仍可能非连通

边界

说法判断说明
「图可以是空图」❌ 一定非空； 可以为空
「 中 是弧头」❌ 是弧尾（起点）， 是弧头
「本书讨论多重图」❌仅讨论简单图
「无向图度数之和等于边数」❌等于边数的 2 倍
「有向图度数之和等于边数」❌入度之和 = 出度之和 = 边数；度数之和是
「路径长度是顶点数」❌是边的数目
「简单回路的顶点都不重复」❌首尾两个顶点相同，其余不重复
「 和 的任意子集构成子图」❌边的端点必须在顶点子集中
「生成子图的边集与原图相同」❌顶点集相同，边可以少
「连通分量是最大连通子图」⚠️教材用词是极大连通子图
「边数 则连通」❌单向：边数 才必非连通
「有 个顶点 条边一定是树」❌还要连通；否则可能是「一个环 + 一个孤立点」
「强连通分量只对有向图有意义」✅无向图讲连通分量

对照速查

量无向图有向图
边的记法，无序对，有序对
度
度数之和（入度之和 = 出度之和 = ）
连通性连通图 / 连通分量强连通图 / 强连通分量
极大子图极大连通子图极大强连通子图
结论内容
图非空 必非空， 可空
一定有环边数
必非连通边数
非连通的最多边数

考点

  • 图不可以是空图——第 6 章第一个考点。
  • 无向图中顶点和边的关系（2009、2017 命题追踪）：。
  • 路径、回路、简单路径、简单回路的定义（2011 命题追踪）。
  • 图的连通性与边和顶点的关系（2010、2022 命题追踪），三个极值界。
  • 子图必须包含边的两个端点（教材注意框）。
  • 生成子图的判据是顶点集相同。
  • 极大连通子图的措辞。

链接

反向链接