连通图和强连通图

1. 公式
   观察依据

   考点文字中出现“N个顶点的无向图G”、“n-1条边”、“$n*(n-1)/2$”等表达式。

n

图中顶点的数量

正整数

1. 公式
   观察依据

   考点文字中出现“对于N个顶点的无向图G”、“在N个顶点的有向图G中”。

G

被讨论的图

无向图或有向图

1. 图示
   观察依据

   左侧无向图和右侧有向图中的顶点均标注为 A、B、C、D、E。

A, B, C, D, E

示例图中的顶点标签

顶点集合

1. 字幕依据
   观察依据

   画面左下考点文字中出现“N个顶点的无向图G”“n-1条边”“$n*(n-1)/2$”等表述。

n

图中顶点个数；画面正文有时写作 N，有时写作 n。

正整数

1. 字幕依据
   观察依据

   画面左下考点文字写有“对于N个顶点的无向图G”“在N个顶点的有向图G中”。

G

被讨论的图，既可用于无向图也可用于有向图。

图

1. 图示
   观察依据

   上方两个示例图和下方图1、图2中都使用 A、B、C、D、E 标注顶点。

A, B, C, D, E

示例图中的顶点标签。

顶点集合元素

1. 字幕依据
   观察依据

   幻灯片文字多次出现“N个顶点”“n-1条边”“$n*(n-1)/2$”等表达式。

2. 声音
   观察依据

   讲解者说“五个顶点”“n等于五嘛，五个顶点就是五乘四”。

n

图中顶点的个数

正整数

1. 字幕依据
   观察依据

   幻灯片文字写有“对于N个顶点的无向图G”“在N个顶点的有向图G中”。

G

被讨论的图，片段中既指无向图也指有向图

图结构

1. 图示
   观察依据

   左侧无向图示例中顶点标注为 A、B、C、D、E。

2. 声音
   观察依据

   讲解者说“字母A B C D E”。

A,B,C,D,E

用于举例的五个顶点名称

顶点标签

1. 声音
   观察依据

   讲解者说“比方说下面有五个顶点A B C D E，还有一个F”。

2. 图示
   观察依据

   讲解者在空白处手写 A、B、C、D、E、F 六个顶点。

A,B,C,D,E,F

用于构造非连通图极值例子的六个顶点名称

顶点标签

1. 字幕依据
   观察依据

   幻灯片文字：“如果G是连通图则最少有n-1条边”。

n-1

n个顶点的连通无向图的最少边数

非负整数表达式

1. 字幕依据
   观察依据

   幻灯片文字：“最多为 $n*(n-1)/2$”。

2. 声音
   观察依据

   讲解者说“最多会有二分之n乘n减一条边”。

$n(n-1)/2$

n个顶点的无向图的最大边数，也是完全图的边数

非负整数表达式

1. 声音
   观察依据

   讲师说：“好，我们接着来看一下连通图的定义。图中任意两个顶点都是连通的，则称为连通图，否则是非连通图。”

2. 字幕依据
   观察依据

   画面左侧文字为“图中任意两个顶点都是连通的，则称为连通图，否则是非连通图”。

连通图是无向图中的概念。若图中任意两个顶点之间都存在路径，则称该图为连通图；只要存在某两个顶点之间没有路径，就称为非连通图。

1. 适用于无向图

2. 要求任意两个顶点之间都存在路径

1. 声音
   观察依据

   讲师说：“在强连通图当中，图中任意一对顶点都是强连通的，则称此图为强连通图。”

2. 字幕依据
   观察依据

   画面右侧文字为“图中任意一对顶点都是强连通的，则称此图为强连通图”。

强连通图是有向图中的概念。若图中任意一对顶点都满足双向可达，即从一个顶点到另一个顶点有路径，反向也有路径，则称该图为强连通图。

1. 适用于有向图

2. 要求任意一对顶点之间都存在双向路径

1. 连通图的定义

1. 声音
   观察依据

   讲师说：“在讲连通图之前，我们要先明确，连通图主要是在无向图当中才有这个概念……强连通图是在有向图当中才有这个概念。”

2. 动画
   观察依据

   讲师在“连通图”旁手写“无向图”，在“强连通图”旁手写“有向图”。

视频明确区分两类概念的适用对象：连通图用于无向图，强连通图用于有向图。这一区分决定了后续判断时要看单向路径还是双向路径。

1. 连通图针对无向图

2. 强连通图针对有向图

1. 字幕依据
   观察依据

   画面下方考点文字写出无向图和有向图在 n 个顶点时的最少边数与最多边数公式。

1. 视频画面中这些公式一直存在，但本片段音频未逐条讲解其推导。

视频给出关于 n 个顶点图的基本计数结论：无向连通图最少需要 n-1 条边，最多有 $n(n-1)/2$ 条边；无向非连通图最多可能有 (n-1)(n-2)/2 条边；有向强连通图最少有 n 条边，最多有 $n(n-1)$ 条边。

1. n 表示顶点数

2. 前两条针对无向图

3. 最后两条针对有向图

1. 连通图的定义
2. 强连通图的定义

1. 字幕依据
   观察依据

   左侧定义文字写明“图中任意两个顶点都是联通的，则称为连通图，否则是非连通图”。

2. 图示
   观察依据

   左侧示例为无向图，顶点 A、B、C、D、E 之间以无向边相连。

视频把“连通图”定义为：在一个图中，如果任意两个顶点之间都是连通的，则该图称为连通图；否则称为非连通图。画面同时强调这一概念对应“无向图”。

1. 适用于无向图

2. 要求任意两个顶点之间都存在连通路径

1. 字幕依据
   观察依据

   右侧定义文字写明“图中任意一对顶点都是强联通的，则称此图为强连通图”。

2. 图示
   观察依据

   右侧示例为有向图，顶点 A、B、C、D、E 之间以有向边相连。

3. 声音
   观察依据

   讲解者逐一验证 A 与 C、A 与 E、A 与 D、B 与 C、B 与 E、B 与 D、C 与 E、C 与 D、E 与 D 都强连通，并总结“任意一对顶点都是强连通的，所以该图就是一个强连通图”。

视频把“强连通图”定义为：在一个有向图中，如果任意一对顶点之间都是强连通的，则称该图为强连通图。讲解中还通过逐对检查顶点之间的双向可达性来演示这一定义。

1. 适用于有向图

2. 要求任意一对顶点之间都互相可达

1. 字幕依据
   观察依据

   左下考点文字写有“如果G是连通图则最少有n-1条边，最多为 $n*(n-1)/2$”“若为非连通图，则最多可能有 (n-1)*(n-2)/2 条边”。

2. 声音
   观察依据

   讲解者读到“在无向图当中，如果G是连通图的话，则最少有n减一条边”，并追问“什么时候情况是最小的呢？就是类似于一棵树的时候”。

视频给出关于 N 个顶点无向图 G 的常见考点：若 G 是连通图，则边数最少为 n-1，最多为 $n(n-1)/2$；若 G 是非连通图，则边数最多为 (n-1)(n-2)/2。讲解进一步指出，连通图取到最少边数的情形“类似于一棵树”。

1. 针对 N 个顶点的无向图 G

2. n 为顶点数

1. 连通图

1. 字幕依据
   观察依据

   左下考点文字写有“在N个顶点的有向图G中，若G是强连通图，则最少有n条边（回路），最多$n*(n-1)$”。

视频给出关于 N 个顶点有向图 G 的常见考点：若 G 是强连通图，则边数最少为 n 条，并且画面把这种最少情形标注为“回路”；边数最多为 $n(n-1)$。

1. 针对 N 个顶点的有向图 G

2. n 为顶点数

1. 强连通图

1. 字幕依据
   观察依据

   幻灯片文字：“图中任意两个顶点都是联通的，则称为连通图，否则是非连通图”。

2. 图示
   观察依据

   左侧标题为“连通图”，配有无向图示例，顶点 A、B、C、D、E 之间有若干无向边。

片段给出无向图语境下的定义：若图中任意两个顶点之间都存在通路，则称该图为连通图；否则称为非连通图。这里的“任意两个顶点都联通”不是要求两两直接相邻，而是要求两两可达。

1. 讨论对象是无向图

2. 判断标准是任意两顶点之间是否存在通路

1. 字幕依据
   观察依据

   幻灯片文字：“图中任意一对顶点都是强联通的，则称此图为强连通图”。

2. 图示
   观察依据

   右侧标题为“强连通图”，配有有向图示例，顶点 A、B、C、D、E 之间有带方向的边。

片段给出有向图语境下的定义：若图中任意一对顶点都是强连通的，则称此图为强连通图。结合右侧有向图示例，强连通强调的是沿有向边方向也能互相到达。

1. 讨论对象是有向图

2. 任意一对顶点都要满足强连通

1. 字幕依据
   观察依据

   幻灯片文字：“如果G是连通图则最少有n-1条边”。

2. 声音
   观察依据

   讲解者画出一个以 C 为中心连接 A、B、D、E 的星形图，并说“五个顶点用到了四条边”。

对于 n 个顶点的无向图 G，若 G 是连通图，则其边数至少为 n-1。讲解者用 5 个顶点的星形例子说明：5 个顶点只需 4 条边即可保持连通。

1. G 为无向图

2. G 有 n 个顶点

3. G 连通

1. 连通图与非连通图

1. 字幕依据
   观察依据

   幻灯片文字：“最多为 $n*(n-1)/2$”。

2. 声音
   观察依据

   讲解者说“最多会有二分之n乘n减一条边”，并联系“完全图”。

3. 图示
   观察依据

   讲解者在空白处写出 $4+3+2+1$，再写成 $5*4/2$。

n 个顶点的无向图最多有 $n(n-1)/2$ 条边，这个上界在完全图中达到。讲解者把最大边数与“完全图”联系起来，并用 5 个顶点的具体例子计算为 $5\times 4/2$。

1. G 为无向图

2. G 有 n 个顶点

3. 求的是可能的最大边数

1. 连通图与非连通图

1. 字幕依据
   观察依据

   幻灯片文字：“如果G是连通图则最少有n-1条边”。

2. 声音
   观察依据

   讲解者用 5 个顶点、4 条边的星形图演示最少连通情形。

对于 n 个顶点的无向图 G，如果 G 是连通图，则 G 至少有 n-1 条边。

1. G 是无向图

2. G 有 n 个顶点

3. G 是连通图

对所有满足前提的 n 和 G 成立

1. 字幕依据
   观察依据

   幻灯片文字：“最多为 $n*(n-1)/2$”。

2. 声音
   观察依据

   讲解者说“最多会有二分之n乘n减一条边”，并问“大家有没有想到这个完全图”。

对于 n 个顶点的无向图，其边数最多为 $n(n-1)/2$，且该上界对应完全图。

1. G 是无向图

2. G 有 n 个顶点

对所有 n 个顶点的无向图成立

1. 字幕依据
   观察依据

   幻灯片文字：“若为非连通图，则最多可能有 (n-1)*(n-2)/2 条边”。

2. 图示
   观察依据

   讲解者构造 6 个顶点例子，其中 5 个顶点圈成一组，第 6 个顶点孤立。

1. 讲解者口述公式与屏幕公式不一致，屏幕公式更清晰。

对于 n 个顶点的无向图，如果它不是连通图，则其边数最多为 (n-1)(n-2)/2。

1. G 是无向图

2. G 有 n 个顶点

3. G 非连通

对所有满足前提的 n 和 G 成立

1. 字幕依据
   观察依据

   幻灯片文字：“在N个顶点的有向图G中，若G是强连通图，则最少有n条边（回路）”。

2. 图示
   观察依据

   右下方“图1”为 4 个顶点的有向环。

对于 n 个顶点的有向图 G，如果 G 是强连通图，则 G 至少有 n 条边。

1. G 是有向图

2. G 有 n 个顶点

3. G 是强连通图

对所有满足前提的 n 和 G 成立

1. 字幕依据
   观察依据

   幻灯片文字：“最多$n*(n-1)$”。

对于 n 个顶点的有向图，其边数最多为 $n(n-1)$。

1. G 是有向图

2. G 有 n 个顶点

对所有 n 个顶点的有向图成立

1. 公式
   观察依据

   幻灯片文字：“如果G是连通图则最少有n-1条边”。

对于 n 个顶点的无向图 G，如果 G 是连通图，则 G 最少有 n-1 条边。

1. G 是无向图

2. G 有 n 个顶点

3. G 是连通图

对所有满足条件的无向图 G 成立

1. 公式
   观察依据

   幻灯片文字：“最多为 $n*(n-1)/2$”。

对于 n 个顶点的无向图 G，如果 G 是连通图，则 G 最多有 $n(n-1)/2$ 条边。

1. G 是无向图

2. G 有 n 个顶点

3. G 是连通图

对所有满足条件的无向图 G 成立

1. 公式
   观察依据

   幻灯片文字：“若为非连通图，则最多可能有 (n-1)*(n-2)/2 条边”。

对于 n 个顶点的无向图 G，如果 G 是非连通图，则 G 最多有 (n-1)(n-2)/2 条边。

1. G 是无向图

2. G 有 n 个顶点

3. G 是非连通图

对所有满足条件的无向图 G 成立

1. 公式
   观察依据

   幻灯片文字：“若G是强连通图，则最少有n条边（回路）”。

2. 声音
   观察依据

   教师说“让它成为一个环形嘛……这种情况下就是有的最少的边数，n个顶点对应n条边”。

对于 n 个顶点的有向图 G，如果 G 是强连通图，则 G 最少有 n 条边。

1. G 是有向图

2. G 有 n 个顶点

3. G 是强连通图

对所有满足条件的有向图 G 成立

1. 公式
   观察依据

   幻灯片文字：“最多$n*(n-1)$”。

2. 声音
   观察依据

   教师说“最多有n乘n减一……因为在有向图当中它有两条边嘛，它一个指过去一个指过来，所以说在它基础上它要乘个二”。

对于 n 个顶点的有向图 G，如果 G 是强连通图，则 G 最多有 $n(n-1)$ 条边。

1. G 是有向图

2. G 有 n 个顶点

3. G 是强连通图

对所有满足条件的有向图 G 成立

1. 声音
   观察依据

   讲师说：“连通的意思就是任意两个顶点之间存在路径。比方说这个A和D……A与D的话，它可以通过A走到C，C再走到D，有这么一条路径，所以说可以认为A与D之间是连通的。”

2. 动画
   观察依据

   讲师在左侧无向图上沿 A-C-D 描出路径。

1. 公式

   $$A \to C \to D$$
   解释

   从顶点 A 出发，经过 C，再到 D，形成一条可达路径。

   步骤依据

   依据视频中“连通”的解释：两顶点之间存在路径即为连通。

   视频直接表达

即使 A 与 D 没有直接相连，只要存在 A-C-D 这样的路径，A 与 D 仍然是连通的。

1. 声音
   观察依据

   讲师说：“并且A与B、C、E，B与C、E、D，C与E、D，E与D之间都是存在路径的。所以这幅图就是一个连通图。”

1. 讲师口头列举了多组顶点对，但未逐一画出所有路径。

1. 公式

   $$\forall u,v \in V,\ u \neq v,\ \text{there exists} u \leadsto v \text{a path}$$
   解释

   视频通过列举若干顶点对之间存在路径，说明左侧无向图满足任意两点连通。

   步骤依据

   依据连通图定义：任意两个顶点都连通则为连通图。

   依据视频推导

左侧示例图满足任意两顶点间都有路径，因此是连通图。

1. 声音
   观察依据

   讲师说：“强连通的意思就是说，比方说现在有两个顶点A与B，A到B有路径，B到A也有路径，这种情况下才叫强连通的。”

2. 动画
   观察依据

   讲师在空白处写出 $A\to B$ 和 $B\to A$。

1. 公式

   $$A \leadsto B$$
   解释

   先从 A 到 B 存在一条有向路径。

   步骤依据

   这是强连通定义的一半条件。

   视频直接表达
2. 公式

   $$B \leadsto A$$
   解释

   再从 B 回到 A 也存在一条有向路径。

   步骤依据

   这是强连通定义的另一半条件。

   视频直接表达

只有当两个顶点之间正反方向都可达时，才能称为强连通。

1. 声音
   观察依据

   讲师说：“好，我们来看一下A和B之间，A可以到B，B可以到A，所以AB是强连通的，没问题。”

2. 图示
   观察依据

   右侧有向图中 A 与 B 之间有双向箭头。

1. 公式

   $$A \to B$$
   解释

   图中存在从 A 指向 B 的有向边。

   步骤依据

   直接读取右侧有向图。

   视频直接表达
2. 公式

   $$B \to A$$
   解释

   图中存在从 B 指向 A 的有向边。

   步骤依据

   直接读取右侧有向图。

   视频直接表达

因为 A 到 B 和 B 到 A 都存在路径，所以 A 与 B 是强连通的。

1. 声音
   观察依据

   讲解者依次说明“A可以走B再走到C”“C走D再走到A”“A与C之间也是强连通”，随后继续列举 A 与 E、A 与 D、B 与 C、B 与 E、B 与 D、C 与 E、C 与 D、E 与 D 都强连通。

2. 图示
   观察依据

   右上有向示例图中，顶点 A、B、C、D、E 之间存在多条有向边，支持这些双向可达路径。

1. 公式

   $$A \to B \to C,\quad C \to D \to A$$
   解释

   先检查 A 与 C 这一对顶点：从 A 可以经 B 到达 C，从 C 可以经 D 回到 A。

   步骤依据

   依据有向图中“强连通”需要双向可达的定义。

   视频直接表达
2. 公式

   $$A \leftrightarrow C$$
   解释

   因此 A 与 C 之间是强连通的。

   步骤依据

   由上一步得到的双向路径推出。

   视频直接表达
3. 公式

   $$A \leftrightarrow E,\ A \leftrightarrow D,\ B \leftrightarrow C,\ B \leftrightarrow E,\ B \leftrightarrow D,\ C \leftrightarrow E,\ C \leftrightarrow D,\ E \leftrightarrow D$$
   解释

   讲解者继续对剩余顶点对作同样的双向可达检查，并逐对给出肯定结论。

   步骤依据

   依据强连通图定义，需要对任意一对顶点都验证双向可达。

   视频直接表达
4. 公式

   $$\forall u,v\in V(G),\ u \leftrightarrow v$$
   解释

   由于任意一对顶点都强连通，所以该有向图是强连通图。

   步骤依据

   直接套用视频中给出的强连通图定义。

   视频直接表达

右上示例有向图满足“任意一对顶点都强连通”，因此是强连通图。

1. 声音
   观察依据

   讲解者说“很明显图一不是吧。A可以到D，但D不能反过去到A。所以说它就不是一个强连通图。”

2. 图示
   观察依据

   下方图1为有向图，顶点 A、B、C、D、E 之间有单向边，其中存在 A 到 D 的方向但缺少从 D 返回 A 的路径。

1. 公式

   $$A \to D$$
   解释

   在图1中，可以从 A 沿有向边到达 D。

   步骤依据

   由图中可见的有向路径得出。

   视频直接表达
2. 公式

   $$D \not\to A$$
   解释

   但从 D 出发无法沿有向边返回 A。

   步骤依据

   讲解者明确指出“D不能反过去到A”。

   视频直接表达
3. 公式

   $$\neg(A \leftrightarrow D)$$
   解释

   因此 A 与 D 这一对顶点不是强连通的。

   步骤依据

   强连通要求双向可达，单向可达不满足定义。

   视频直接表达
4. 公式

   $$\text{graph one is not strongly connected}$$
   解释

   只要存在一对顶点不满足双向可达，整个有向图就不是强连通图。

   步骤依据

   依据强连通图定义。

   视频直接表达

图1不是强连通图。

1. 声音
   观察依据

   讲解者先说“图二肯定也不是了”，接着解释“B可以到A，B也可以到C，C能到A，但A没有办法到B吧……所以说图二也不是一个强连通图。”

2. 图示
   观察依据

   下方图2为有向图，顶点 A、B、C、D、E 之间的箭头方向使某些顶点只能单向到达其他顶点。

1. 公式

   $$B \to A,\quad B \to C,\quad C \to A$$
   解释

   在图2中，B 可以到达 A，B 也可以到达 C，且 C 可以到达 A。

   步骤依据

   由图中可见的有向边和讲解者的口头列举得出。

   视频直接表达
2. 公式

   $$A \not\to B$$
   解释

   但 A 无法沿有向边到达 B。

   步骤依据

   讲解者明确说“A没有办法到B”。

   视频直接表达
3. 公式

   $$\neg(A \leftrightarrow B)$$
   解释

   因此 A 与 B 这一对顶点不是强连通的。

   步骤依据

   强连通要求双向可达。

   视频直接表达
4. 公式

   $$\text{graph two is not strongly connected}$$
   解释

   存在一对顶点不满足双向可达，故图2不是强连通图。

   步骤依据

   依据强连通图定义。

   视频直接表达

图2不是强连通图。

1. 声音
   观察依据

   讲解者说“除非他要把这个箭头改一下……这样它就是一个连通图了。看到没？B可以到C，C可以到A，A可以到B。这样形成一个环，它就是强连通图，并且这种情况下它的边数是最小的。”

2. 动画
   观察依据

   讲解者在图2附近手绘修改箭头，形成 A、B、C 之间的环形有向结构。

1. 讲解者口头一度说“这样它就是一个连通图了”，随后又明确说“它就是强连通图”；结合上下文和画面，这里实际讨论的是有向图的强连通性。

1. 公式

   $$B \to C,\quad C \to A,\quad A \to B$$
   解释

   讲解者把箭头改成三条首尾相接的有向边，形成一个环。

   步骤依据

   由手绘修改和口头描述共同给出。

   视频直接表达
2. 公式

   $$A \leftrightarrow B \leftrightarrow C \leftrightarrow A$$
   解释

   在这个环中，任意两个顶点都可以沿环双向到达，因此它们彼此强连通。

   步骤依据

   依据强连通定义。

   依据视频推导
3. 公式

   $$\text{number of edges}=3$$
   解释

   该构造只用三条有向边就使三个顶点构成强连通图。

   步骤依据

   讲解者明确说“这种情况下它的边数是最小的”。

   视频直接表达

把图2中的箭头改成 $A\to B\to C\to A$ 这样的环后，图成为强连通图，并且这是边数最小的情形之一。

1. 声音
   观察依据

   讲解者说“A与另外四个顶点都有相连，那么就用了四条边。然后接着是B与另外三个边相连，三条边。四加三加二加一。”

2. 图示
   观察依据

   讲解者在空白处依次写出 4、$4+3$、$4+3+2$、$4+3+2+1$，再写成 $5*4/2$。

1. 公式

   $$4+3+2+1$$
   解释

   对 5 个顶点的完全图，先数与第一个顶点相连的 4 条边，再数与第二个顶点新相连的 3 条边，依次类推。

   步骤依据

   按顶点顺序逐次加入新边，避免重复计数同一条无向边。

   视频直接表达
2. 公式

   $$\frac{5\times 4}{2}$$
   解释

   把 $4+3+2+1$ 改写为 $5\times 4/2$。

   步骤依据

   这是等差数列求和的结果，讲解者口头提到“首项加末项”。

   视频直接表达
3. 公式

   $$\frac{n(n-1)}{2}$$
   解释

   将具体例子推广到一般 n 个顶点。

   步骤依据

   讲解者明确说“n在这个地方就是n等于五嘛，五个顶点就是五乘四”，把 5 替换为一般的 n。

   视频直接表达

n 个顶点的完全图有 $n(n-1)/2$ 条边，因此 n 个顶点的无向图最多也有这么多条边。

1. 声音
   观察依据

   讲解者说“我们要让这幅图是一个非连通图且有最多的边，那么就让下面这五个顶点成为一个完全图，并且让F与A B C D E都不相连”。

2. 图示
   观察依据

   讲解者画出 A、B、C、D、E、F 六个顶点，把 A-E 圈在一起，F 单独在外。

1. 片段在 120 秒结束时尚未完成最终数值计算，只完成了构造思路。

1. 公式

   $$A,B,C,D,E$$
   解释

   先把其中 5 个顶点放在一起，令它们两两相连，形成一个完全子图。

   步骤依据

   这样可以在不引入第 6 个顶点的连边时尽量多地增加边数。

   视频直接表达
2. 公式

   $$F$$
   解释

   让第 6 个顶点 F 与 A、B、C、D、E 都不相连。

   步骤依据

   只要 F 与其余顶点没有任何边，整图就必然非连通。

   视频直接表达
3. 公式

   $$\frac{(n-1)(n-2)}{2}$$
   解释

   把上述构造推广到 n 个顶点：取 n-1 个顶点构成完全图，剩 1 个孤立顶点。

   步骤依据

   屏幕文字给出该极值公式；讲解者的构造正是这一公式的直观来源。

   依据视频推导

要使非连通无向图的边数最多，应让 n-1 个顶点形成完全图，另 1 个顶点孤立，从而得到最大边数 (n-1)(n-2)/2。

1. 声音
   观察依据

   教师说“因为总总的顶点数为六个，最终答案是二分之五乘四……因为它是根据顶点为n减一个顶点嘛，本来是n个减去这一个为，然后剩余的剩余的顶点数就为n减一个顶点，n减一个顶点对应的完全图的数量不就是二分之n乘n减一嘛”。

2. 图示
   观察依据

   教师在幻灯片下方画出包含 A、B、C、D、E 五个顶点的圈，并在旁边写出 $5*4/2$，随后又写出 (n-1)*(n-2)/2。

1. 公式

   $$$$
   解释

   考虑 n 个顶点的无向非连通图，为了使边数尽可能多，应让其中一个连通分量包含 n-1 个顶点，另一个连通分量只包含 1 个孤立顶点。

   步骤依据

   视频通过“本来是n个减去这一个”说明把 1 个顶点单独分离出去。

   视频直接表达
2. 公式

   $$\frac{(n-1)(n-2)}{2}$$
   解释

   n-1 个顶点的完全图边数为 $\frac{(n-1)((n-1)-1)}{2}=\frac{(n-1)(n-2)}{2}$。

   步骤依据

   教师口述“n减一个顶点对应的完全图的数量”，并写出相应表达式。

   视频直接表达
3. 公式

   $$$$
   解释

   若这个孤立顶点再与下面 n-1 个顶点中的任意一个相连，则整张图就不再是非连通图。

   步骤依据

   教师说“如果这个单独出来的一个顶点与下面的这五个顶点当中任意一颗顶点之间都有连线的话，那么它就不能成为非连通图了”。

   视频直接表达

因此，n 个顶点的无向非连通图最多有 $\frac{(n-1)(n-2)}{2}$ 条边。

1. 声音
   观察依据

   教师说“让它成为一个环形嘛，ABCD，A指C，C指D，D指B，B指A。好，这种情况下就是有的最少的边数，n个顶点对应n条边，比方说这个四条顶点对应四条边”。

2. 图示
   观察依据

   教师手写 A、B、C、D 四个顶点，并用箭头连成一个有向环。

1. 教师口述“A指C，C指D，D指B，B指A”，但画面中更像是在画一个相邻连接的有向环；具体箭头方向以画面为准存在轻微不一致。

1. 公式

   $$$$
   解释

   取 n 个顶点，把它们连成一个有向环。

   步骤依据

   教师说“让它成为一个环形嘛”。

   视频直接表达
2. 公式

   $$$$
   解释

   在有向环中，每个顶点都有一条出边指向下一个顶点，因此共有 n 条边。

   步骤依据

   教师举例“四条顶点对应四条边”。

   视频直接表达
3. 公式

   $$$$
   解释

   有向环中任意两点沿环方向可达，因此该图是强连通图。

   步骤依据

   这是“强连通图”定义下对环形构造的直接应用。

   依据视频推导

所以 n 个顶点的有向强连通图最少需要 n 条边。

1. 图示
   观察依据

   左侧展示一个含顶点 A、B、C、D、E 的无向图。

2. 声音
   观察依据

   讲师围绕该图解释“任意两个顶点都是连通的”并以 A、D 为例说明路径存在。

判断左侧无向图是否为连通图。

1. 图为无向图

2. 顶点为 A、B、C、D、E

3. 讲师指出 A 与 D 可通过 A-C-D 路径相连

4. 讲师指出其他顶点对之间也存在路径

说明该图满足连通图定义。

1. 公式

   $$A \leadsto D \text{ via } A \to C \to D$$
   解释

   先验证没有直接边的两个顶点 A、D 之间仍有路径。

   步骤依据

   连通性看的是路径存在，而不是是否有直接边。

   视频直接表达
2. 公式

   $$\text{\text{且} paths exist between all other pairs of vertices}$$
   解释

   再推广到任意两顶点都连通。

   步骤依据

   依据连通图定义。

   视频直接表达

左侧无向图是连通图。

与画面定义“图中任意两个顶点都是连通的，则称为连通图”一致。

1. 图示
   观察依据

   右侧展示一个含顶点 A、B、C、D、E 的有向图。

2. 声音
   观察依据

   讲师解释强连通定义，并举例验证 A 与 B 之间双向可达。

1. 片段在讲师刚要开始检查 A 与 C 时结束，未给出完整的全图判定过程。

理解右侧有向图中“强连通”的含义，并检查部分顶点对是否强连通。

1. 图为有向图

2. 顶点为 A、B、C、D、E

3. A 与 B 之间存在双向路径

说明何为强连通，并验证 A 与 B 是否强连通。

1. 公式

   $$A \leadsto B \text{且} B \leadsto A$$
   解释

   对顶点对 A、B 检查两个方向是否都可达。

   步骤依据

   强连通要求双向路径同时存在。

   视频直接表达
2. 公式

   $$\text{therefore} A,B \text{strongly connected}$$
   解释

   由双向可达得出结论。

   步骤依据

   依据强连通图定义。

   视频直接表达

在该示例中，A 与 B 是强连通的。

与讲师口头结论“A和B之间，A可以到B，B可以到A，所以AB是强连通的”一致。

1. 图示
   观察依据

   右上有向示例图展示顶点 A、B、C、D、E 及其有向边。

2. 声音
   观察依据

   讲解者逐对验证顶点之间的强连通性并得出结论。

判断右上示例有向图是否为强连通图。

1. 图为有向图

2. 顶点为 A、B、C、D、E

3. 图中存在若干有向边，使讲解者可逐对验证双向可达

验证是否任意一对顶点都强连通。

1. 公式

   $$A \to B \to C,\quad C \to D \to A$$
   解释

   先验证 A 与 C 的双向可达。

   步骤依据

   强连通图要求任意一对顶点双向可达。

   视频直接表达
2. 公式

   $$A \leftrightarrow E,\ A \leftrightarrow D,\ B \leftrightarrow C,\ B \leftrightarrow E,\ B \leftrightarrow D,\ C \leftrightarrow E,\ C \leftrightarrow D,\ E \leftrightarrow D$$
   解释

   继续验证其余顶点对。

   步骤依据

   逐对检查定义条件。

   视频直接表达
3. 公式

   $$\text{every pair of vertices is strongly connected}$$
   解释

   所有顶点对均满足双向可达。

   步骤依据

   由前面逐对验证得到。

   视频直接表达

该有向图是强连通图。

依据视频给出的定义：图中任意一对顶点都是强连通的，则称此图为强连通图。

1. 图示
   观察依据

   下方图1为有向图，标注为“图1”。

2. 声音
   观察依据

   讲解者判断“图一不是”，理由是 A 可以到 D，但 D 不能反过去到 A。

判断图1是不是强连通图。

1. 图1是有向图

2. 存在从 A 到 D 的有向路径

3. 不存在从 D 返回 A 的有向路径

判断图1是否满足强连通图定义。

1. 公式

   $$A \to D$$
   解释

   A 可以到达 D。

   步骤依据

   图中可见路径。

   视频直接表达
2. 公式

   $$D \not\to A$$
   解释

   D 不能到达 A。

   步骤依据

   讲解者明确指出。

   视频直接表达
3. 公式

   $$\neg(A \leftrightarrow D)$$
   解释

   A 与 D 不满足双向可达。

   步骤依据

   由上两步推出。

   依据视频推导

图1不是强连通图。

只要存在一对顶点不是强连通的，就不满足强连通图定义。

1. 图示
   观察依据

   下方图2为有向图，标注为“图2”。

2. 声音
   观察依据

   讲解者判断“图二肯定也不是了”，并举出 A 无法到 B 的例子。

判断图2是不是强连通图。

1. 图2是有向图

2. B 可以到 A，B 也可以到 C，C 能到 A

3. A 没有办法到 B

判断图2是否满足强连通图定义。

1. 公式

   $$B \to A,\quad B \to C,\quad C \to A$$
   解释

   先列出图中可见的若干有向路径。

   步骤依据

   由图和讲解者描述得出。

   视频直接表达
2. 公式

   $$A \not\to B$$
   解释

   但 A 不能到达 B。

   步骤依据

   讲解者明确指出。

   视频直接表达
3. 公式

   $$\neg(A \leftrightarrow B)$$
   解释

   因此 A 与 B 不是强连通的。

   步骤依据

   强连通要求双向可达。

   依据视频推导

图2不是强连通图。

存在一对顶点不满足双向可达，即不符合强连通图定义。

1. 动画
   观察依据

   讲解者在图2旁手绘修改箭头，形成环状有向结构。

2. 声音
   观察依据

   讲解者说“B可以到C，C可以到A，A可以到B。这样形成一个环，它就是强连通图，并且这种情况下它的边数是最小的。”

1. 该例子是在原图2基础上临时改写得到的示意构造，不是原图2本身。

如何通过修改箭头使图2变成强连通图，并观察其边数特点。

1. 原图2不是强连通图

2. 讲解者手动把箭头改成 $B\to C$、$C\to A$、$A\to B$ 的环形结构

说明修改后的图为何是强连通图，并指出其边数最小。

1. 公式

   $$B \to C,\quad C \to A,\quad A \to B$$
   解释

   修改后三条有向边首尾相接形成环。

   步骤依据

   由手绘动画和讲解者描述得出。

   视频直接表达
2. 公式

   $$A \leftrightarrow B \leftrightarrow C \leftrightarrow A$$
   解释

   环上任意两点都可沿两个方向到达对方。

   步骤依据

   依据有向环的可达性。

   依据视频推导
3. 公式

   $$\text{minimum number of edges}$$
   解释

   讲解者指出这种环形构造的边数是最小的。

   步骤依据

   视频口头结论。

   视频直接表达

修改后的图是强连通图，并且这种环形构造对应边数最小的情形。

与后面给出的有向强连通图最少 n 条边的考点一致。

1. 声音
   观察依据

   讲解者说“我们让C连A，C连B，C连D，C连E。看到没？五个顶点用到了四条边。”

2. 图示
   观察依据

   讲解者在空白处画出中心点 C 分别连接 A、B、D、E 的星形无向图。

用 5 个顶点构造一个连通的无向图，并观察最少需要多少条边。

1. 顶点为 A、B、C、D、E

2. 要求图连通

给出一个边数较少的连通构造，并说明其边数。

1. 公式

   $$C-A,\ C-B,\ C-D,\ C-E$$
   解释

   让中心顶点 C 分别与其他四个顶点相连。

   步骤依据

   这样任意两个顶点都可以通过 C 相互到达，因此图连通。

   视频直接表达
2. 公式

   $$4=5-1$$
   解释

   该例子共用了 4 条边。

   步骤依据

   讲解者明确说“五个顶点用到了四条边”，对应一般公式 n-1。

   视频直接表达

5 个顶点的连通无向图最少可用 4 条边，即 n-1。

检查任意两点是否都能经过中心点 C 相连通；本例中所有点都邻接 C，因此连通。

1. 声音
   观察依据

   讲解者说“A与另外四个顶点都有相连……B与另外三个……四加三加二加一……就等于二分之五乘四。”

2. 图示
   观察依据

   讲解者写出 $4+3+2+1$，再写成 $5*4/2$。

计算 5 个顶点的完全图有多少条边，并由此理解无向图最大边数公式。

1. 顶点数为 5

2. 图为完全图，即任意两顶点都直接相连

求出总边数，并对应到一般公式 $n(n-1)/2$。

1. 公式

   $$4+3+2+1$$
   解释

   依次统计每个新顶点带来的新边数。

   步骤依据

   第一个顶点贡献 4 条边，第二个在未重复计数的前提下再贡献 3 条，依此类推。

   视频直接表达
2. 公式

   $$\frac{5\times 4}{2}$$
   解释

   把 $4+3+2+1$ 化为 $5\times 4/2$。

   步骤依据

   这是等差求和的写法，讲解者口头提到“首项加末项”。

   视频直接表达
3. 公式

   $$\frac{n(n-1)}{2},\ n=5$$
   解释

   将 5 代入一般公式。

   步骤依据

   讲解者明确把例子中的 5 对应到公式里的 n。

   视频直接表达

5 个顶点的完全图有 10 条边，一般公式为 $n(n-1)/2$。

用组合计数也可得到 $C(5,2)=10$，与 $5\times 4/2$ 一致。

1. 声音
   观察依据

   讲解者说“比方说下面有五个顶点A B C D E，还有一个F。我们要让这幅图是一个非连通图且有最多的边，那么就让下面这五个顶点成为一个完全图，并且让F与A B C D E都不相连。”

2. 图示
   观察依据

   讲解者画出 A、B、C、D、E、F 六个顶点，把 A-E 圈在一起，F 单独在外。

1. 片段结束时只完成构造，未把 6 个顶点情形的最终数值算完。

构造一个 6 个顶点的非连通无向图，使它的边数尽可能多。

1. 顶点为 A、B、C、D、E、F

2. 要求整图非连通

给出边数最多的非连通构造。

1. 公式

   $$K_5 \text{ on } A,B,C,D,E$$
   解释

   让 A、B、C、D、E 五个顶点两两相连，形成一个 5 个顶点的完全子图。

   步骤依据

   在固定这 5 个顶点内部时，完全图能给出最多内部边数。

   视频直接表达
2. 公式

   $$F \text{ isolated}$$
   解释

   让 F 与 A、B、C、D、E 都不相连。

   步骤依据

   只要存在孤立顶点，整图就一定非连通。

   视频直接表达
3. 公式

   $$\frac{5\times 4}{2}=10$$
   解释

   该构造中边全部来自 A-E 形成的完全子图。

   步骤依据

   沿用前面完全图计数公式，5 个顶点的完全图有 10 条边。

   依据视频推导

6 个顶点的非连通图若要边数最多，可让其中 5 个顶点构成完全图，第 6 个顶点孤立；本例边数为 10。

若再给 F 添加任意一条边，虽然边数增加，但图可能仍非连通与否取决于具体连接；而屏幕给出的极值公式对应的是“一个孤立点 + 其余点完全图”的极端构造。

1. 声音
   观察依据

   教师说“它有五个顶点的话，那么就是二分之五乘四嘛”。

2. 图示
   观察依据

   教师在幻灯片下方写出 $5*4/2$。

计算 5 个顶点的无向完全图有多少条边。

1. 顶点数为 5

求完全图边数

1. 公式

   $$\frac{5\times 4}{2}$$
   解释

   代入无向完全图边数公式 $\frac{n(n-1)}{2}$。

   步骤依据

   教师口述“二分之五乘四”。

   视频直接表达
2. 公式

   $$10$$
   解释

   计算得到 10 条边。

   步骤依据

   算术化简。

   依据视频推导

10

与公式 $\frac{n(n-1)}{2}$ 在 $n=5$ 时的取值一致。

1. 声音
   观察依据

   教师说“因为总总的顶点数为六个，最终答案是二分之五乘四”。

2. 图示
   观察依据

   教师写出 6，随后写出 (n-1)*(n-2)/2，并画出 5 个顶点的圈。

计算 6 个顶点的无向非连通图最多可以有多少条边。

1. 顶点数为 6

2. 图是非连通图

求最大边数

1. 公式

   $$\frac{(6-1)(6-2)}{2}$$
   解释

   代入非连通图最大边数公式 $\frac{(n-1)(n-2)}{2}$。

   步骤依据

   教师说“总的顶点数为六个，最终答案是二分之五乘四”。

   视频直接表达
2. 公式

   $$\frac{5\times 4}{2}$$
   解释

   化简为 $\frac{5\times 4}{2}$。

   步骤依据

   算术代入。

   视频直接表达
3. 公式

   $$10$$
   解释

   计算得到 10 条边。

   步骤依据

   算术化简。

   依据视频推导

10

对应构造是一个 5 个顶点的完全图加 1 个孤立顶点。

1. 动画
   观察依据

   讲师用红笔在“连通图”旁写“无向图”，在“强连通图”旁写“有向图”。

1. 标题“连通图和强连通图”

2. 左侧“连通图”

3. 右侧“强连通图”

4. 红色手写批注

1. 在连通图旁补充“无向图”

2. 在强连通图旁补充“有向图”

1. 两张示例图本身未改变

2. 页面整体版式未改变

视觉上强调两类概念分别属于无向图和有向图，避免混淆。

1. 动画
   观察依据

   讲师在左侧无向图上沿 A-C-D 描线，展示一条路径。

1. 左侧无向图

2. 顶点 A、C、D

3. 红色描线

1. A 到 C 的边被强调

2. C 到 D 的边被强调

1. 图的结构未改变

2. 顶点位置未改变

说明即使 A 与 D 没有直接边，也可以通过中间顶点形成路径，从而满足连通性。

1. 动画
   观察依据

   讲师在空白处写出 $A\to B$ 与 $B\to A$ 的双向示意。

1. 手写 A

2. 手写 B

3. 两个方向箭头

1. 先写出 A 到 B 的方向

2. 再补出 B 到 A 的方向

1. 这是对定义的抽象示意，不是原示例图的一部分

用极简图示说明强连通的核心是双向可达。

1. 图示
   观察依据

   整页标题为“连通图和强连通图”；左上为“连通图 无向图”示例，右上为“强连通图 有向图”示例，左下为“考点”文字，右下为“图1”“图2”两个有向图。

1. 标题“连通图和强连通图”

2. 左上无向示例图

3. 右上有向示例图

4. 左下考点文字

5. 右下图1和图2

1. 讲解过程中在图1、图2附近添加红色圈划、叉号和箭头修改痕迹。

1. 页面主标题和四个主要区域的位置保持不变。

2. 左下考点文字始终可见。

页面用左右对照方式区分无向图的连通图与有向图的强连通图，并用下方两个小图做判断题示例。

1. 动画
   观察依据

   讲解者在图1周围做圈划和否定标记，配合口头判断其不是强连通图。

1. 图1

2. 红色圈划与否定标记

1. 图1被重点圈出并加上表示“不是”的标记。

1. 图1原有顶点和边不变。

视觉标注用于强调图1不满足强连通图定义。

1. 动画
   观察依据

   讲解者在图2附近手绘新的箭头方向，形成环状结构。

1. 图2

2. 新绘制的有向箭头

1. 箭头方向被改成 $B\to C$、$C\to A$、$A\to B$ 的环形连接。

1. 顶点标签 A、B、C 不变。

通过改变边的方向而不是增加顶点，演示如何得到强连通且边数最小的结构。

1. 图示
   观察依据

   整页分为左右两部分：左侧标题“连通图”，右侧标题“强连通图”；下方有“考点”文字和两个小型有向图“图1”“图2”。

1. 左侧连通图示例

2. 右侧强连通图示例

3. 下方考点文字

4. 右下图1和图2

1. 讲解者在空白处不断添加红色手写顶点、边和算式

1. 页面主标题和印刷文字保持不变

2. 左右两栏的主题划分保持不变

版面把无向图的连通性与有向图的强连通性并列呈现，便于对比两类图的定义和边数极值。

1. 动画
   观察依据

   讲解者先写 A、B、C、D、E，再把 C 放在中心并向四周连线。

2. 声音
   观察依据

   讲解者同步说“C连A，C连B，C连D，C连E”。

1. 五个顶点 A,B,C,D,E

2. 中心点 C

3. 四条无向边

1. 先出现顶点标签，再出现中心点 C，最后逐条画出 C 到其他四点的边

1. 顶点总数始终为 5

2. 最终边数为 4

该动画展示了一个 5 顶点连通图的最小边构造，用来说明连通图最少需要 n-1 条边。

1. 动画
   观察依据

   讲解者依次写出 4、$4+3$、$4+3+2$、$4+3+2+1$，再改写成 $5*4/2$，并在旁边标注 $n=5$。

1. 算式 $4+3+2+1$

2. 算式 $5*4/2$

3. 标注 $n=5$

1. 算式从逐项累加变为乘积除以 2 的闭式表达

2. 随后把具体数字 5 对应到一般符号 n

1. 表达的对象始终是 5 个顶点完全图的边数

视觉过程把“逐个数边”的直观计数转化为一般公式 $n(n-1)/2$ 的推导。

1. 动画
   观察依据

   讲解者画出 A、B、C、D、E、F 六个顶点，把 A-E 圈在一起，F 单独放在外面。

2. 声音
   观察依据

   讲解者说让五个顶点成为完全图，F 与其他点都不相连。

1. 六个顶点 A,B,C,D,E,F

2. 圈住的 A-E 子集

3. 孤立的 F

1. 先列出六个顶点，再把其中五个归为一组，最后强调第六个点孤立

1. 总顶点数为 6

2. 目标是构造非连通且边数最多的图

该画面把抽象公式 (n-1)(n-2)/2 具体化为“n-1 个点成完全图，1 个点孤立”的极值构造。

1. 图示
   观察依据

   整页幻灯片上方左侧为“连通图”示例，右侧为“强连通图”示例；下方左侧为无向图考点文字，右侧为有向图考点文字和图1、图2。

1. 连通图示例

2. 强连通图示例

3. 无向图考点文字

4. 有向图考点文字

5. 图1

6. 图2

1. 无动态变化，整段保持同一页面

1. 页面主题始终是“连通图和强连通图”

2. 左右两栏分别对应无向图与有向图

视觉上把无向连通图与有向强连通图并列对照，便于比较二者边数极值公式。

1. 图示
   观察依据

   教师在左下区域用红笔圈出“非连通图”相关文字，写出 6、(n-1)*(n-2)/2，并画出包含 A、B、C、D、E 的圈。

1. 红色圈注

2. 数字 6

3. 表达式 (n-1)*(n-2)/2

4. 五个顶点 A、B、C、D、E 的圈

1. 先圈出非连通图文字

2. 再写出 6 和公式

3. 最后画出 5 个顶点的圈并标注 $5*4/2$

1. 始终围绕“非连通图最多边数”这一结论

板书把“孤立 1 个顶点 + 其余 n-1 个顶点构成完全图”的极值构造可视化。

1. 声音
   观察依据

   讲师说：“有些同学会认为A与D之间没有直接相连的这条红线，所以说他认为A与D之间不是连通的。这种理解很明显是错误的。”

把“连通”误解为两个顶点之间必须存在直接相连的边。

连通只要求两个顶点之间存在路径，允许经过其他中间顶点。

1. 字幕依据
   观察依据

   页面把“连通图”与“无向图”并列，把“强连通图”与“有向图”并列。

以为“连通图”和“强连通图”是同一类概念，或者都可以在同一种图上不加区分地使用。

视频明确把“连通图”放在无向图一侧，把“强连通图”放在有向图一侧；后者要求任意一对顶点双向可达。

1. 声音
   观察依据

   讲解者在图1和图2中都因为某一对顶点只能单向到达而判定其不是强连通图。

只要从一个顶点能走到另一个顶点，就认为这两个顶点强连通。

视频反复强调必须双向可达；图1中 A 可到 D 但 D 不能回 A，图2中 A 不能到 B，因此都不算强连通。

1. 声音
   观察依据

   讲解者先用星形图说明“五个顶点用到了四条边”就能连通，后面又把最大边数与“完全图”联系起来。

2. 字幕依据
   观察依据

   幻灯片同时给出最少 n-1 条边和最多 $n(n-1)/2$ 条边两个不同极值。

看到“任意两个顶点都是联通的”时，容易误解为任意两点之间必须有一条直接边。

连通只要求任意两点之间存在一条路径，不要求直接相邻。片段中的星形图就是反例：5 个点只有 4 条边仍然连通。

1. 字幕依据
   观察依据

   幻灯片对无向图给出“最多为 $n*(n-1)/2$”，对有向图给出“最多$n*(n-1)$”。

把无向图的最大边数 $n(n-1)/2$ 直接套用到有向图上。

有向图中一对顶点之间可以有两条方向相反的边，因此最大边数是 $n(n-1)$，不是 $n(n-1)/2$。

1. 声音
   观察依据

   讲解者把非连通图最多边数读成“n减一乘二分之n乘n减一乘n减二条边”。

2. 字幕依据
   观察依据

   屏幕文字清楚写着“(n-1)*(n-2)/2”。

仅凭口述容易记错非连通图最大边数公式。

应以屏幕显示的 (n-1)(n-2)/2 为准；讲解者此处口述出现了明显偏差。

1. 声音
   观察依据

   教师说“如果这个单独出来的一个顶点与下面的这五个顶点当中任意一颗顶点之间都有连线的话，那么它就不能成为非连通图了”。

在求非连通图最大边数时，误以为可以把那个单独分出来的顶点再与其他顶点相连而不影响“非连通”。

一旦这个孤立顶点与其余连通分量中的任一顶点相连，整张图就会变成连通图，不再属于非连通图。

1. 声音
   观察依据

   教师说“因为在有向图当中它有两条边嘛，它一个指过去一个指过来，所以说在它基础上它要乘个二”。

误以为有向图最多边数仍是 $\frac{n(n-1)}{2}$。

有向图中同一对顶点之间可以有方向相反的两条边，所以最多边数是无向完全图的两倍，即 $n(n-1)$。

1. 声音
   观察依据

   讲师明确说连通图在无向图中，强连通图在有向图中。

“适用范围”这一知识点直接规定了连通图定义只用于无向图。

1. 声音
   观察依据

   讲师明确说强连通图在有向图中才有这个概念。

“适用范围”这一知识点直接规定了强连通图定义只用于有向图。

1. 声音
   观察依据

   讲师先讲无向图中的“连通”是存在路径，再讲有向图中的“强连通”是正反方向都有路径。

1. 这是基于视频内容的分析员归纳，视频未直接使用“推广”一词。

在有向图语境下，强连通比单纯“存在一条路径”更严格，要求任意一对顶点双向可达。

1. 字幕依据
   观察依据

   画面下方边数公式分别针对“连通图”“非连通图”“强连通图”给出。

1. 本片段未展开证明这些公式，只是展示结论。

边数范围公式建立在连通图与强连通图定义之上，用于刻画不同结构下的极值情况。

1. 图示
   观察依据

   页面左右并列展示“连通图 无向图”和“强连通图 有向图”。

视频通过左右对照区分两类概念：前者面向无向图，只要求任意两顶点连通；后者面向有向图，要求任意一对顶点强连通。

1. 声音
   观察依据

   讲解者在环形示例中说“这种情况下它的边数是最小的”。

2. 字幕依据
   观察依据

   左下考点随后写出“若G是强连通图，则最少有n条边（回路）”。

前面用环形有向图演示最小强连通结构，后面把它归纳为有向强连通图最少需要 n 条边的考点。

1. 字幕依据
   观察依据

   左下考点先定义无向图 G 的连通情形，再给出最少 n-1 条边。

2. 声音
   观察依据

   讲解者把最少边情形解释为“类似于一棵树的时候”。

连通图定义直接用于推出无向连通图的最少边数和最多边数范围。

1. 字幕依据
   观察依据

   幻灯片先定义连通图，紧接着给出“如果G是连通图则最少有n-1条边”。

2. 声音
   观察依据

   讲解者用星形图解释最少边数。

连通图的定义直接引出其最少边数结论：要达到任意两点可达，至少需要 n-1 条边。

1. 声音
   观察依据

   讲解者问“大家有没有想到这个完全图”，随后说“完全图当中不就是二分之n乘n减一条边吗”。

最大边数对应的是完全图这种“两两直接相连”的极端情形，而连通图只要求可达，不要求两两直接相连。

1. 字幕依据
   观察依据

   幻灯片把“如果G是连通图……”与“若为非连通图……”并列书写。

2. 图示
   观察依据

   讲解者用 6 个顶点的孤立点构造说明非连通极值。

非连通图的最大边数是相对于连通图定义的补面情形：一旦要求图不连通，就必须至少留下一个与其他部分断开的顶点。

1. 字幕依据
   观察依据

   右侧先定义“强连通图”，下方又写“在N个顶点的有向图G中，若G是强连通图，则最少有n条边（回路）”。

2. 图示
   观察依据

   右下图1是有向环。

强连通图的定义直接推出有向情形下的最少边数：要让任意两点双向可达，至少需要一个覆盖全图的有向回路。

1. 字幕依据
   观察依据

   同一页并列给出无向图最多 $n(n-1)/2$ 条边和有向图最多 $n(n-1)$ 条边。

两者差别来自边的方向性：无向边一对顶点只算一条，有向边一对顶点可算两条方向相反的边。

1. 声音
   观察依据

   讲师朗读连通图定义。

1. 连通图的定义

1. 声音
   观察依据

   讲师以 A 和 D 为例解释路径存在即可认为连通。

1. 连通图的定义
2. 误以为必须有直接边才算连通

1. 声音
   观察依据

   讲师朗读强连通图定义并解释双向路径。

1. 强连通图的定义

1. 声音
   观察依据

   讲师区分连通图用于无向图，强连通图用于有向图。

1. 连通图与强连通图的适用范围
2. 连通图的定义
3. 强连通图的定义

1. 字幕依据
   观察依据

   画面下方给出 n 个顶点时各类图的最少边数和最多边数。

1. n 个顶点图的边数范围

1. 字幕依据
   观察依据

   左侧定义文字直接给出连通图定义。

1. 连通图

1. 字幕依据
   观察依据

   右侧定义文字直接给出强连通图定义。

2. 声音
   观察依据

   讲解者逐对验证任意顶点对都强连通。

1. 强连通图
2. 右上示例图是强连通图的判定过程

1. 声音
   观察依据

   讲解者分别判断图1和图2都不是强连通图，并给出反例路径。

1. 图1不是强连通图的反例判定
2. 图2不是强连通图的反例判定
3. 图1是否为强连通图
4. 图2是否为强连通图

1. 声音
   观察依据

   讲解者说环形构造“边数是最小的”。

2. 字幕依据
   观察依据

   考点文字给出无向连通图最少 n-1 条边、有向强连通图最少 n 条边。

1. 无向连通图与非连通图的边数范围
2. 有向强连通图的边数范围
3. 修改图2箭头后形成最小强连通结构

1. 字幕依据
   观察依据

   幻灯片文字：“图中任意两个顶点都是联通的，则称为连通图，否则是非连通图”。

1. 连通图与非连通图

1. 声音
   观察依据

   讲解者用 5 个顶点、4 条边的星形图说明最少连通边数。

1. 连通无向图的最少边数
2. 5个顶点连通图的最少边例子

1. 声音
   观察依据

   讲解者把最大边数与完全图联系起来，并写出 $4+3+2+1=5*4/2$。

1. 无向图的最大边数与完全图
2. 完全图边数的逐步计数
3. 5个顶点完全图的边数例子