连通图和强连通图

1. 字幕依据
   观察依据

   考点文字中出现“N个顶点”

N

图中顶点的数量

正整数

1. 字幕依据
   观察依据

   考点文字中出现“e条边”

e

图中边的数量

非负整数

1. 图示
   观察依据

   图中顶点标有字母 A, B, C, D, E

A, B, C, D, E

示例图中的顶点标识

离散集合

1. 公式
   观察依据

   板书考点中出现“对于N个顶点的无向图G”“最少有n-1条边”“最多为 $n*(n-1)/2$”等表述。

1. 画面同时使用大写 N 和小写 n 指代顶点数，视频未解释二者是否严格同义。

n

图中顶点个数

正整数

1. 公式
   观察依据

   板书写作“如果G是连通图”“若G是强连通图”。

G

被讨论的图

无向图或有向图

1. 图示
   观察依据

   上方示例图与下方图1、图2中的顶点均用 A、B、C、D、E 标注。

2. 声音
   观察依据

   讲解者反复说“A可以走B再走到C”“B可以到A”等。

A, B, C, D, E

示例图中的顶点标签

顶点集合中的元素

1. 字幕依据
   观察依据

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

2. 声音
   观察依据

   讲解中把具体例子中的顶点数代入 $n=5$，说明“n在这个地方就是n等于5嘛，五个顶点”。

n

图中顶点的个数

正整数；在本片段的具体示例中取 $n=5$

1. 字幕依据
   观察依据

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

G

被讨论的图；在本片段中既指无向图也指有向图，需结合上下文判断

1. 字幕依据
   观察依据

   “如果G是连通图则最少有n-1条边”。

2. 声音
   观察依据

   讲解者画出5个顶点并用4条边把它们连起来，说“五个顶点用到了四条边”。

n-1

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

1. 字幕依据
   观察依据

   “最多为 $n*(n-1)/2$”。

2. 公式
   观察依据

   板书写出 $4+3+2+1 = (5\cdot 4)/2$，并口头联系到完全图。

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

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

1. 字幕依据
   观察依据

   “若为非连通图，则z最多可能有 (n-1)*(n-2)/2 条边”。

2. 声音
   观察依据

   讲解者举例构造：让其中5个顶点形成完全图，另一个顶点与前5个都不相连。

1. 字幕中该处写作“z最多可能有”，但 z 未在片段内另行定义，疑似排版占位或笔误。

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

n 个顶点的无向非连通图可能达到的最大边数

1. 字幕依据
   观察依据

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

2. 图示
   观察依据

   右侧“强连通图”示例为5个顶点的有向环。

n

n 个顶点的有向强连通图最少边数；片段中以“回路”形式给出

1. 声音
   观察依据

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

2. 字幕依据
   观察依据

   图中任意两个顶点都是连通的，则称为连通图，否则是非连通图

在无向图中，如果任意两个顶点之间都存在路径，则该图被称为连通图；否则为非连通图。

1. 适用于无向图

1. 声音
   观察依据

   在强连通图当中，图中任意一对顶点都是强连通的，则称此图为强连通图。

2. 字幕依据
   观察依据

   图中任意一对顶点都是强连通的，则称此图为强连通图

在有向图中，如果任意一对顶点之间都存在双向路径（即从 u 到 v 和从 v 到 u 都有路径），则该图被称为强连通图。

1. 适用于有向图

1. 字幕依据
   观察依据

   如果G是连通图则最少有n-1条边，最多为 $n * (n-1) / 2$

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

1. G 是无向连通图

1. 连通图的定义

1. 字幕依据
   观察依据

   若为非连通图，则e最多可能有(n-1) * (n-2) / 2条边

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

1. G 是无向非连通图

1. 连通图的定义

1. 字幕依据
   观察依据

   在N个顶点的有向图G中，若G是强连通图，则最少有n条边（回路），最多n*（n-1）

对于 N 个顶点的有向图 G，如果是强连通图，则最少有 N 条边（构成一个回路），最多有 $N*(N-1)$ 条边。

1. G 是有向强连通图

1. 强连通图的定义

1. 公式
   观察依据

   左侧板书写明：“图中任意两个顶点都是连通的，则称为连通图，否则是非连通图。”

2. 图示
   观察依据

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

视频将连通图定义为无向图中任意两个顶点之间都存在通路的情形；只要存在某一对顶点不连通，就称为非连通图。

1. 适用于无向图

2. 要求任意两个顶点都连通

1. 公式
   观察依据

   右侧板书写明：“图中任意一对顶点都是强连通的，则称此图为强连通图。”

2. 图示
   观察依据

   右侧示例为有向图，顶点 A、B、C、D、E 之间带有方向箭头。

3. 声音
   观察依据

   讲解者说“A可以走B再走到C……C走D再走到A……A与C之间也是强连通”，并总结“任意一对顶点都是强连通的，所以该图就是一个强连通图”。

视频把强连通图定义为有向图中任意一对顶点之间都能沿有向路径互相到达的图。判断方法是逐对检查是否存在双向可达路径。

1. 适用于有向图

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

1. 连通图

1. 公式
   观察依据

   板书考点写出：“对于N个顶点的无向图G，如果G是连通图则最少有n-1条边，最多为 $n*(n-1)/2$；若为非连通图，则最多可能有 (n-1)*(n-2)/2 条边。”

2. 声音
   观察依据

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

1. 视频只口头解释最小边数对应“类似于一棵树”，未给出正式证明。

视频给出 n 个顶点无向图在连通与非连通两种情形下的边数极值：连通时最少 n-1 条边、最多完全图边数 $n(n-1)/2$；非连通时最多 (n-1)(n-2)/2 条边。

1. G 为含 n 个顶点的无向图

2. 分别针对 G 连通与 G 非连通两种情形

1. 连通图

1. 公式
   观察依据

   板书最后一行写出：“在N个顶点的有向图G中，若G是强连通图，则最少有n条边（回路），最多$n*(n-1)$。”

1. 视频在本片段内未展开解释“最少有n条边（回路）”的完整证明，只在前面用三顶点环作直观说明。

视频给出 n 个顶点有向图在强连通时的边数极值：最少 n 条边，并以“回路”提示最小结构；最多 $n(n-1)$ 条边，即任意两不同顶点间都可存在一对相反方向的有向边。

1. G 为含 n 个顶点的有向图

2. G 是强连通图

1. 强连通图

1. 字幕依据
   观察依据

   “图中任意两个顶点都是联通的，则称为连通图，否则是非连通图”。

2. 图示
   观察依据

   左侧标题为“连通图”，配有一个5顶点无向图示例。

片段对无向图给出定义：若图中任意两个顶点之间都存在通路，则称为连通图；只要存在某两个顶点不连通，就称为非连通图。左侧示例用绿色无向图直观表示这一概念。

1. 对象是无向图

2. 判定依据是“任意两个顶点”是否都连通

1. 字幕依据
   观察依据

   “图中任意一对顶点都是强联通的，则称此图为强连通图”。

2. 图示
   观察依据

   右侧标题为“强连通图”，配有一个5顶点有向环示例。

片段对有向图给出定义：若图中任意一对顶点之间都是强连通的，则称此图为强连通图。右侧示例用橙色有向环表示每个顶点都能沿有向边到达其他顶点。

1. 对象是有向图

2. 要求任意一对顶点双向可达

1. 字幕依据
   观察依据

   “如果G是连通图则最少有n-1条边”。

2. 声音
   观察依据

   讲解者画5个点并用4条边连接，说“五个顶点用到了四条边”。

3. 图示
   观察依据

   红笔在空白处画出 A、B、C、D、E 五个点，并以 C 为中心连出4条边。

对于 n 个顶点的无向图 G，若 G 是连通图，则其边数至少为 n-1。片段通过 $n=5$ 的例子说明：5 个顶点最少需要 4 条边才能保持连通。

1. G 为无向图

2. G 有 n 个顶点

3. G 连通

1. 连通图与非连通图

1. 声音
   观察依据

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

2. 图示
   观察依据

   图1中 A 到 D 有单向箭头，D 没有回到 A 的路径。

图1不是强连通图，因为存在顶点 A 与 D，使得 A 可到 D，但 D 不可到 A。

1. 图1为有向图

2. 图中存在从 A 到 D 的有向边

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

存在一对顶点 (A,D) 不满足双向可达

1. 声音
   观察依据

   讲解者说：“图二肯定也不是了……B可以到A，A怎么跑到B呢？不行，所以说图二也不是一个强连通图。”

2. 图示
   观察依据

   图2中 $B\to A$、$B\to C$、$C\to A$ 均为单向边，A 没有回到 B 的路径。

图2不是强连通图，因为存在顶点 A 与 B，使得 B 可到 A，但 A 不可到 B。

1. 图2为有向图

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

3. 不存在从 A 到 B 的有向路径

存在一对顶点 (A,B) 不满足双向可达

1. 声音
   观察依据

   讲解者说：“除非他要把这个箭头改一下……这样形成一个环，它就是强连通图，并且这种情况下它的边数是最小的。”

2. 图示
   观察依据

   讲解者在图2上补画反向箭头，使 A、B、C 形成有向环。

1. 视频未给出一般性证明，只以三顶点环作直观例子。

将图2中的边方向调整为形成有向环后，该图成为强连通图；在该例子中这种结构的边数是最小的。

1. 修改后的图中 A、B、C 形成有向环

2. 环上每个顶点都可沿方向到达其余顶点

针对该示例图的具体修改

1. 字幕依据
   观察依据

   “如果G是连通图则最少有n-1条边”。

2. 声音
   观察依据

   讲解者用5个顶点、4条边的例子支持该结论。

若 G 是 n 个顶点的无向连通图，则 |$E(G)$| ≥ n-1。

1. G 是无向图

2. G 有 n 个顶点

3. G 连通

对所有满足前提的无向连通图 G 成立

1. 字幕依据
   观察依据

   “最多为 $n*(n-1)/2$”。

2. 声音
   观察依据

   讲解者把它解释为完全图的边数。

若 G 是 n 个顶点的无向简单图，则 |$E(G)$| ≤ $n(n-1)/2$。

1. G 是无向简单图

2. G 有 n 个顶点

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

1. 字幕依据
   观察依据

   “若为非连通图，则z最多可能有 (n-1)*(n-2)/2 条边”。

2. 声音
   观察依据

   讲解者用“5个顶点组成完全图，第6个顶点孤立”的构造说明该上界可达。

1. 字幕中的 z 未定义，疑似笔误。

若 G 是 n 个顶点的无向非连通简单图，则 |$E(G)$| ≤ (n-1)(n-2)/2。

1. G 是无向简单图

2. G 有 n 个顶点

3. G 非连通

对所有满足前提的无向非连通图成立

1. 字幕依据
   观察依据

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

2. 图示
   观察依据

   右侧有向环示例显示 n 个顶点用 n 条边实现强连通。

若 G 是 n 个顶点的有向强连通图，则 |$E(G)$| ≥ n。

1. G 是有向图

2. G 有 n 个顶点

3. G 强连通

对所有满足前提的有向强连通图成立

1. 字幕依据
   观察依据

   “最多$n*(n-1)$”。

1. 片段未给出证明，只给出结论性文字。

若 G 是 n 个顶点的有向强连通简单图，则 |$E(G)$| ≤ $n(n-1)$。

1. G 是有向简单图

2. G 有 n 个顶点

3. G 强连通

对所有满足前提的有向强连通图成立

1. 公式
   观察依据

   幻灯片文字明确写出该结论。

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

1. G 是无向图

2. G 有 n 个顶点

3. G 连通

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

1. 公式
   观察依据

   幻灯片文字明确写出该结论。

对于 n 个顶点的无向图 G，如果 G 是非连通图，则最多可能有 $\frac{(n-1)(n-2)}{2}$ 条边。

1. G 是无向图

2. G 有 n 个顶点

3. G 非连通

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

1. 公式
   观察依据

   幻灯片文字明确写出该结论。

在 n 个顶点的有向图 G 中，若 G 是强连通图，则最少有 n 条边，最多有 $n(n-1)$ 条边。

1. G 是有向图

2. G 有 n 个顶点

3. G 强连通

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

1. 声音
   观察依据

   比方说这个A和D...它可以通过A走到C，C再走到D...所以说可以认为A与D之间是连通的。并且A与B、C、E...都是存在路径的。所以这幅图就是一个连通图。

2. 动画
   观察依据

   讲师在左侧无向图上用红线描出 A-C-D 的路径

1. 公式

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

   寻找顶点 A 和 D 之间的路径

   步骤依据

   连通意味着存在路径，不要求直接相连

   视频直接表达
2. 公式

   $$\forall u, v \in V, \exists P(u, v)$$
   解释

   图中任意两点间均存在路径

   步骤依据

   满足连通图的定义

   依据视频推导

该无向图是连通图

1. 声音
   观察依据

   讲解者逐对检查上方有向图：“A可以走B再走到C……C走D再走到A……同样的A与E也是强连通，A与D也是强连通，还有B与C，B与E，B与D，C与E，C与D，E与D，都是强连通的。”

2. 图示
   观察依据

   上方右侧有向图中各顶点之间存在可沿箭头行走的路径。

1. 公式

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

   先说明从 A 到 C 可沿有向路径到达。

   步骤依据

   依据图中箭头方向和讲解者口述路径。

   视频直接表达
2. 公式

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

   再说明从 C 回到 A 也存在有向路径，因此 A 与 C 双向可达。

   步骤依据

   依据图中箭头方向和讲解者口述路径。

   视频直接表达
3. 公式

   $$\forall u,v \in V,\ u \leftrightarrow v$$
   解释

   随后讲解者继续列举 A 与 E、A 与 D、B 与 C、B 与 E、B 与 D、C 与 E、C 与 D、E 与 D 等顶点对，说明它们都强连通。

   步骤依据

   依据强连通图定义：任意一对顶点都强连通。

   视频直接表达
4. 公式

   $$\text{this directed graph is strongly connected}$$
   解释

   由所有顶点对均双向可达，得出结论。

   步骤依据

   直接套用强连通图定义。

   视频直接表达

上方右侧有向图满足任意一对顶点都强连通，因此是强连通图。

1. 声音
   观察依据

   讲解者指出“A可以到D，但D不能反过去到A”。

2. 图示
   观察依据

   图1中 D 为只有入边的终点，没有离开 D 的箭头。

1. 公式

   $$A \to D$$
   解释

   图中存在从 A 到 D 的有向路径。

   步骤依据

   直接读图。

   视频直接表达
2. 公式

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

   但图中不存在从 D 回到 A 的有向路径。

   步骤依据

   直接读图，D 没有出边。

   视频直接表达
3. 公式

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

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

   步骤依据

   强连通要求双向可达。

   视频直接表达
4. 公式

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

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

   步骤依据

   强连通图定义的否定。

   视频直接表达

图1不是强连通图。

1. 声音
   观察依据

   讲解者说“B可以到A，A怎么跑到B呢？不行”。

2. 图示
   观察依据

   图2中 $B\to A$、$B\to C$、$C\to A$，A 没有指向其他顶点的出边。

1. 公式

   $$B \to A$$
   解释

   图中存在从 B 到 A 的有向路径。

   步骤依据

   直接读图。

   视频直接表达
2. 公式

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

   但 A 没有出边，无法沿箭头回到 B。

   步骤依据

   直接读图。

   视频直接表达
3. 公式

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

   所以 B 与 A 不满足强连通。

   步骤依据

   强连通要求双向可达。

   视频直接表达
4. 公式

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

   存在一对顶点不可互达，故整体不是强连通图。

   步骤依据

   强连通图定义的否定。

   视频直接表达

图2不是强连通图。

1. 声音
   观察依据

   讲解者说“把这个箭头改一下……B可以到C，C可以到A，A可以到B，这样形成一个环，它就是强连通图”。

2. 图示
   观察依据

   讲解者在图2上补画反向箭头，形成 A、B、C 的有向环。

1. 公式

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

   修改后三个顶点沿同一方向构成闭合有向环。

   步骤依据

   依据讲解者补画箭头后的图形。

   视频直接表达
2. 公式

   $$\forall u,v \in \{A,B,C\},\ u \leftrightarrow v$$
   解释

   在有向环中，任取两点都可沿环方向到达对方。

   步骤依据

   环的可达性直观说明。

   依据视频推导
3. 公式

   $$\text{the modified graph is strongly connected}$$
   解释

   由于三对顶点均双向可达，满足强连通图定义。

   步骤依据

   套用强连通图定义。

   视频直接表达

把图2改成有向环后，它成为强连通图；视频进一步称这种结构边数最小。

1. 声音
   观察依据

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

2. 公式
   观察依据

   板书写出 $4+3+2+1 = (5\cdot 4)/2$。

3. 图示
   观察依据

   左侧绿色完全图被红笔圈注，用来辅助计数。

1. 公式

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

   对5个顶点的完全图，从第一个顶点出发可连4条边；去掉已计过的边后，第二个顶点再新增3条，第三个新增2条，第四个新增1条。

   步骤依据

   按顶点顺序逐层计数，避免重复统计同一条无向边。

   视频直接表达
2. 公式

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

   把 $4+3+2+1$ 看成首项为4、末项为1、项数为4的等差数列，也可写成 ($5\cdot 4$)/2。

   步骤依据

   讲解者口头使用“首项加末项”的等差求和思路，并在板书写出该结果。

   视频直接表达
3. 公式

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

   将具体例子中的 5 替换为一般顶点数 n，得到 n 个顶点完全图的边数公式。

   步骤依据

   由特例推广到一般公式；片段文字已直接给出该通式。

   视频直接表达

n 个顶点的无向完全图有 $n(n-1)/2$ 条边，因此这也是无向简单图的最大边数。

1. 声音
   观察依据

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

2. 图示
   观察依据

   红笔画出 A、B、C、D、E 被圈在一起，F 单独在外。

1. 片段只讲到构造思路，未继续写出最终数值计算。

1. 公式

   $$K_{n-1}$$
   解释

   为了让图边数尽可能多但仍不连通，先把其中 n-1 个顶点两两相连，形成一个完全子图。

   步骤依据

   完全子图在给定顶点数下边数最多。

   视频直接表达
2. 公式

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

   这 n-1 个顶点内部的边数就是 (n-1)(n-2)/2。

   步骤依据

   套用前面得到的完全图边数公式。

   依据视频推导
3. 公式

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

   剩下的第 n 个顶点不与任何顶点相连，因此整个图仍然非连通。

   步骤依据

   孤立点保证不存在跨分量的通路。

   视频直接表达

由此可得：n 个顶点的无向非连通图最多有 (n-1)(n-2)/2 条边。

1. 声音
   观察依据

   讲解者说“因为总总的顶点数为六个”“最终答案是二分之五乘四”“就是二分之n减一乘上n减二”“因为它是根据顶点为n减一个顶点嘛”“本来是n个减去这一个位，然后剩余的剩余的顶点数就为n减一个顶点”“n减一个顶点对应的完全图的数量不就是二分之n乘n减一嘛”“如果这个单独出来的一个顶点与下面的这五个顶点当中任意一个顶点之间都有连线的话，那么它就不能成为非连通图了”。

2. 动画
   观察依据

   讲解者在空白处圈出 6，并写出 n、n-1、n-2 等提示，配合口头解释。

1. 讲解者口述中“二分之n乘n减一”与最终公式“二分之n减一乘n减二”之间的过渡略快，但整体指向剩余 n-1 个顶点构成完全图。

1. 公式

   $$$$
   解释

   先把一个顶点视为孤立点，使图保持非连通。

   步骤依据

   讲解者说“本来是n个减去这一个位”，即从 n 个顶点中拿出一个单独顶点。

   视频直接表达
2. 公式

   $$$$
   解释

   剩下的顶点数为 n-1。

   步骤依据

   讲解者明确说“剩余的顶点数就为n减一个顶点”。

   视频直接表达
3. 公式

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

   为了让总边数最多，让这 n-1 个剩余顶点之间两两相连，形成完全图。

   步骤依据

   讲解者说“n减一个顶点对应的完全图的数量不就是……”，并把答案落到“二分之n减一乘上n减二”。

   视频直接表达
4. 公式

   $$$$
   解释

   若把这个孤立顶点再与其余任一顶点相连，图就不再是非连通图。

   步骤依据

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

   视频直接表达

因此，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 条边。

   步骤依据

   讲解者总结“n个顶点对应n条边”。

   视频直接表达
3. 公式

   $$$$
   解释

   在这个有向环中，任意两个顶点都可沿环互相到达，因此图是强连通的。

   步骤依据

   这是“环形”构造用于说明强连通最少边数的直接含义。

   依据视频推导

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

1. 声音
   观察依据

   讲解者说“最多有n乘n减一”“这个最多的情况与之前我们讲的这个性质是一样的，最多有二分之n乘n减一嘛”“因为在有向图当中它有两条边嘛，它一个指过去一个指过来，所以说在它基础上它要乘个二”。

1. 公式

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

   先回忆 n 个顶点无向完全图的边数。

   步骤依据

   讲解者明确引用“最多有二分之n乘n减一”。

   视频直接表达
2. 公式

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

   在有向图中，每一对顶点之间可以有两条方向相反的边。

   步骤依据

   讲解者说“它一个指过去一个指过来，所以说在它基础上它要乘个二”。

   视频直接表达

因此 n 个顶点有向图的最大边数为 $n(n-1)$。

1. 图示
   观察依据

   左侧展示了一个包含 A, B, C, D, E 五个顶点的无向图

2. 声音
   观察依据

   讲师以 A 和 D 为例，说明它们之间虽然没有直接边，但存在 A-C-D 的路径，因此是连通的。

判断给定的无向图是否为连通图

1. 无向图包含顶点 A, B, C, D, E

2. 边包括 (A,B), (A,C), (B,C), (C,D), (C,E), (D,E) 等

验证任意两点间是否存在路径

1. 公式

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

   验证 A 和 D 之间是否存在路径

   步骤依据

   通过中间节点 C 可以找到路径

   视频直接表达
2. 公式

   $$\text{The same reasoning applies to other pairs of points}$$
   解释

   验证其他任意两点间是否存在路径

   步骤依据

   观察图形可知所有点都在同一个连通分量中

   视频直接表达

该图是连通图

任意两点间均可找到路径

1. 图示
   观察依据

   上方右侧有向图，顶点为 A、B、C、D、E。

2. 声音
   观察依据

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

判断上方右侧有向图是否为强连通图。

1. 图为有向图

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

3. 图中存在若干有向边，可沿箭头行走

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

1. 公式

   $$A \to B \to C,\ 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”为有向图，顶点 A、B、C、D，其中 $A\to D$ 为单向边。

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”为有向图，顶点 A、B、C，边方向为 $B\to A$、$B\to C$、$C\to A$。

2. 声音
   观察依据

   讲解者说“B可以到A，A怎么跑到B呢？不行”。

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

1. 图2是有向图

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

3. A 没有回到 B 的出边路径

判断图2是否满足任意一对顶点都强连通。

1. 公式

   $$B \to A$$
   解释

   B 可以到达 A。

   步骤依据

   直接读图。

   视频直接表达
2. 公式

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

   A 不能到达 B。

   步骤依据

   直接读图。

   视频直接表达
3. 公式

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

   所以 B 与 A 不满足强连通。

   步骤依据

   强连通要求双向可达。

   视频直接表达

图2不是强连通图。

通过找出一对不可互达顶点完成否定。

1. 图示
   观察依据

   讲解者在图2上补画反向箭头，使 A、B、C 形成有向环。

2. 声音
   观察依据

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

如何改动图2的边方向，使它成为强连通图，并观察其边数特点。

1. 原图2为有向图

2. 顶点为 A、B、C

3. 讲解者可手工补画箭头

构造一个强连通版本，并说明其边数最小。

1. 公式

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

   把边改成沿同一方向闭合的有向环。

   步骤依据

   依据讲解者补画后的图形。

   视频直接表达
2. 公式

   $$\forall u,v \in \{A,B,C\},\ u \leftrightarrow v$$
   解释

   环上任意两点都可沿环到达彼此。

   步骤依据

   有向环的可达性。

   依据视频推导
3. 公式

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

   三顶点环恰用三条边实现强连通。

   步骤依据

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

   视频直接表达

修改后的图2是强连通图，且在该例子中边数最小。

检查任意两顶点是否都能沿环互相到达。

1. 声音
   观察依据

   “我画一下吧，字母A B C D E。我们让C连A，C连B，C连D，C连E。”“看到没？五个顶点用到了四条边。”

2. 图示
   观察依据

   红笔在空白处画出5个点，并以 C 为中心连出4条边。

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

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

2. 要求图连通

给出一个边数最少的连通构造

1. 公式

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

   把 C 作为中心点，分别连到其余4个顶点。

   步骤依据

   这样任意两点都可经过 C 相通，图连通。

   视频直接表达
2. 公式

   $$4=5-1$$
   解释

   该构造一共使用了4条边。

   步骤依据

   与“n 个顶点连通图最少 n-1 条边”的结论一致。

   视频直接表达

5个顶点的连通无向图最少需要4条边。

讲解者直接数出所画边数为4，并与 n-1 对应。

1. 声音
   观察依据

   “完全图当中不就是二分之n乘n减一条边吗？”“A与另外四个顶点都有相连……四加三加二加一……就等于二分之五乘四。”

2. 公式
   观察依据

   板书写出 $4+3+2+1 = (5\cdot 4)/2$。

3. 图示
   观察依据

   左侧绿色5顶点完全图被圈出并用于计数。

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

1. 顶点数 $n=5$

2. 图为完全图

求边数并联系通式 $n(n-1)/2$

1. 公式

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

   按顶点顺序逐次新增边：第一个点连4条，第二个再连3条，第三个再连2条，第四个再连1条。

   步骤依据

   避免重复计数同一条无向边。

   视频直接表达
2. 公式

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

   把上述求和写成等差求和结果。

   步骤依据

   讲解者口头使用“首项加末项”的求和说法。

   视频直接表达
3. 公式

   $$\frac{n(n-1)}{2}\bigg|_{n=5}=\frac{5\cdot 4}{2}$$
   解释

   将一般公式代入 $n=5$，得到同样结果。

   步骤依据

   与板书和口述一致。

   视频直接表达

5个顶点的完全图有10条边，即 ($5\cdot 4$)/2。

特例计算与通式代入结果一致。

1. 声音
   观察依据

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

2. 图示
   观察依据

   红笔画出 A、B、C、D、E 被圈在一起，F 单独在外。

1. 片段未继续算出该例子的具体边数，只停留在构造说明。

构造一个边数尽可能多但仍然非连通的无向图。

1. 示例中共有6个顶点：A、B、C、D、E、F

2. 要求图非连通

说明如何使边数最大化同时保持非连通

1. 公式

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

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

   步骤依据

   在5个顶点内部，完全图边数最多。

   视频直接表达
2. 公式

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

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

   步骤依据

   这样 F 自成一个孤立分量，整体图仍非连通。

   视频直接表达

该构造说明：非连通但边数最多的图，可取一个 n-1 个顶点的完全图再加一个孤立点。

讲解者通过“完全子图 + 孤立点”的构造直接支持上界思路。

1. 声音
   观察依据

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

2. 动画
   观察依据

   讲解者在空白处圈出数字 6，并写出与 5、4 相关的计算提示。

若总顶点数为 6，求无向非连通图最多可能有多少条边。

1. 顶点总数 $n=6$

2. 图为无向图

3. 图非连通

求最大边数。

1. 公式

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

   代入非连通无向图最大边数公式。

   步骤依据

   来自幻灯片公式 |E| $\le \frac{(n-1)(n-2)}{2}$。

   视频直接表达
2. 公式

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

   化简括号内的差值。

   步骤依据

   讲解者口述“二分之五乘四”。

   视频直接表达
3. 公式

   $$10$$
   解释

   计算得到最大边数。

   步骤依据

   算术化简。

   依据视频推导

10 条边。

与幻灯片给出的通式在 $n=6$ 时一致。

1. 动画
   观察依据

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

2. 动画
   观察依据

   讲师在左侧无向图上画出 A 到 D 的路径 A-C-D

3. 动画
   观察依据

   讲师在右侧有向图上画出 A 到 B 的双向箭头，并在下方写出 A -> B 和 B -> A

1. 无向图

2. 有向图

3. 红色手写笔迹

1. 添加文字标注区分无向和有向

2. 绘制路径以解释连通性

3. 绘制双向箭头以解释强连通性

1. 图的基本拓扑结构不变

通过动态标注强调连通图针对无向图，强连通图针对有向图，并直观展示路径和双向可达的概念。

1. 图示
   观察依据

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

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

2. 左侧无向图示例

3. 右侧有向图示例

4. 左下考点文字

5. 右下“图1”“图2”

1. 讲解过程中在右侧有向图和下方图1、图2上陆续添加红色箭头、圈注和叉号。

1. 页面主标题和左右两大定义区始终可见。

版面对比了无向图的“连通”与有向图的“强连通”，并用下方例题检验概念。

1. 动画
   观察依据

   讲解者在右上有向图上沿边描画路径，并圈出若干顶点。

2. 声音
   观察依据

   同步口述“A可以走B再走到C”“C走D再走到A”等。

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

2. 有向边

3. 红色描画轨迹

1. 沿箭头依次描出若干可达路径

2. 用圈注强调正在检查的顶点对

1. 图本身结构不变

2. 箭头方向不变

视觉动作用于说明“任意一对顶点都强连通”的逐对验证过程。

1. 动画
   观察依据

   讲解者在图1上描出 A 到 D 的方向，并在 D 附近做否定标记。

2. 声音
   观察依据

   同步说“D不能反过去到A”。

1. 图1

2. 顶点 A、D

3. 红色标记

1. 强调 $A\to D$ 可达

2. 强调 $D\to A$ 不可达

1. 图1原有边方向不变

用一对不可互达顶点说明图1不是强连通图。

1. 动画
   观察依据

   先在图2上指出 $B\to A$ 可达而 $A\to B$ 不可达，随后补画反向箭头形成环。

2. 声音
   观察依据

   讲解者先说“图二也不是一个强连通图”，后说“把这个箭头改一下……形成一个环，它就是强连通图”。

1. 图2

2. 顶点 A、B、C

3. 新增红色箭头

1. 先标出 A 无法回到 B

2. 后补画箭头使 A、B、C 构成有向环

1. 顶点集合不变

2. 讨论对象仍是同一三顶点有向图

同一图形先作为非强连通反例，再通过改变边方向展示最小强连通结构。

1. 图示
   观察依据

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

1. 左侧绿色无向图

2. 右侧橙色有向图

3. 下方考点文字

4. 右下角图1和图2

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 为中心的边

1. 先写顶点标签

2. 再从中心点 C 向外逐条画边

1. 顶点总数保持为5

2. 边数最终为4

该动画演示 n 个顶点的连通图最少可用 n-1 条边实现。

1. 动画
   观察依据

   红笔圈住左侧绿色完全图，并在上方写出 4、$4+3$、$4+3+2$、$4+3+2+1$，最后写成 ($5\cdot 4$)/2。

2. 公式
   观察依据

   板书逐步累加并转化为乘积除以2。

1. 左侧5顶点完全图

2. 红色累加式 $4+3+2+1$

3. 结果 ($5\cdot 4$)/2

1. 先圈出完全图

2. 再逐项写出累加过程

3. 最后改写为乘积形式

1. 示例顶点数始终为5

2. 讨论对象始终是无向完全图

视觉过程把“逐点新增边”的计数方法转成等差求和，再过渡到一般公式 $n(n-1)/2$。

1. 动画
   观察依据

   红笔写出 A、B、C、D、E、F，把 A 到 E 圈在一起，F 单独留在外面。

2. 声音
   观察依据

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

1. 六个顶点标签 A、B、C、D、E、F

2. 圈住的五个顶点

3. 孤立的 F

1. 先列出6个顶点

2. 再把前5个顶点圈成一组

3. 最后把 F 留在组外

1. 总顶点数为6

2. 图始终保持非连通

该动画直观展示“一个完全分量加一个孤立点”的极值构造思想。

1. 图示
   观察依据

   整段画面为同一张幻灯片：上方左右分别是“连通图”和“强连通图”示例，下方是“考点”文字与公式，右下还有“图1”“图2”两个小型有向图示例。

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

2. 左侧“连通图”示例

3. 右侧“强连通图”示例

4. 下方“考点”文字与公式

5. 右下“图1”“图2”

1. 讲解过程中红笔在空白处不断添加圈注、字母和箭头

1. 幻灯片主文字和示例图始终可见

2. 主题一直围绕连通图与强连通图的边数极值

画面以静态讲义为主，动态红笔批注用于补充推导和构造示例。

1. 动画
   观察依据

   讲解者在空白处圈出“6”，并陆续写出 n、n-1、n-2 等提示，围绕非连通图最大边数进行标注。

1. 个别手写符号较潦草，但结合音频可确认其在说明 n、n-1、n-2 的关系。

1. 圈出的数字 6

2. 手写的 n、n-1、n-2

3. 原有幻灯片公式

1. 从具体数值 6 过渡到一般表达式 n-1、n-2

2. 通过圈画强调“剩余顶点构成完全图”的思想

1. 幻灯片原公式保持不变

这些批注把抽象公式 $\frac{(n-1)(n-2)}{2}$ 与“拿出一个孤立点，其余点尽量连满”的构造联系起来。

1. 动画
   观察依据

   讲解者在空白处画出 A、B、C、D 四个顶点及有向箭头，形成环状结构。

2. 声音
   观察依据

   讲解者同步说“让它成为一个环形嘛”“n个顶点对应n条边”。

1. 口述箭头顺序与画面局部笔顺不完全一致，但都指向同一个有向环构造。

1. 手写顶点 A、B、C、D

2. 有向箭头

3. 空白批注区

1. 先写顶点字母，再补有向边，最后围成环

1. 顶点数为 4 时边数也为 4

2. 构造目的是说明最少边情形

该动画直观展示了强连通有向图最少边数 n 的取得方式：把所有顶点串成一个有向环。

1. 声音
   观察依据

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

认为两个顶点之间必须有直接的边相连才是连通的。

连通是指两个顶点之间存在路径，路径可以经过其他中间顶点，不要求直接相连。

1. 声音
   观察依据

   讲解者反复强调“D不能反过去到A”“A怎么跑到B呢？不行”。

2. 图示
   观察依据

   图1、图2都依靠箭头方向判断可达性。

看到两点之间有一条路径就以为它们强连通。

强连通要求双向可达；只满足一个方向不足以判定为强连通。

1. 声音
   观察依据

   讲解者问“什么时候情况是最小的呢？就是类似于一棵树的时候”。

2. 公式
   观察依据

   板书给出连通无向图最少 n-1 条边。

认为只要连通就需要接近完全图的边数。

n 个顶点的无向连通图最少只需要 n-1 条边，典型情形就是树状结构。

1. 字幕依据
   观察依据

   “若为非连通图，则z最多可能有 (n-1)*(n-2)/2 条边”。

1. 无法确认 z 是笔误还是排版占位符，但片段内未给出其定义。

读者可能误以为 z 是另一个新引入的量。

在本片段语境中，该句实际是在说非连通图最多可能有 (n-1)(n-2)/2 条边；z 未被另行定义，应视为可疑排版或笔误，而不是新的数学对象。

1. 图示
   观察依据

   左栏“连通图”配无向图，右栏“强连通图”配有向图。

2. 字幕依据
   观察依据

   两侧定义分别强调“任意两个顶点都是联通的”和“任意一对顶点都是强联通的”。

可能把“连通图”和“强连通图”当成同一种条件。

片段通过左右分栏明确区分：连通图针对无向图，只要求任意两点相通；强连通图针对有向图，要求任意一对顶点双向可达。

1. 字幕依据
   观察依据

   无向连通图“最少有n-1条边”；有向强连通图“最少有n条边（回路）”。

2. 图示
   观察依据

   右侧示例是有向环。

可能误以为无向连通图和有向强连通图的最少边数相同。

片段明确给出不同下界：无向连通图最少 n-1 条边，而有向强连通图最少 n 条边，原因是有向图中需要用有向回路保证双向可达。

1. 图示
   观察依据

   左侧“连通图”示例并不是每两点都有直接边，而是通过路径相连。

2. 公式
   观察依据

   幻灯片同时给出连通图最少 n-1 条边、最多 $\frac{n(n-1)}{2}$ 条边。

容易把连通图误解为任意两点都必须有直接边。

视频中的定义是“任意两个顶点都是连通的”，即存在路径即可；只有达到最多边数 $\frac{n(n-1)}{2}$ 时才是无向完全图。

1. 声音
   观察依据

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

在求非连通图最大边数时，容易想再把孤立点与其余点相连以增加边数。

视频说明一旦这个单独顶点与其余任一顶点相连，图就不再是非连通图，因此最大边数只能来自剩余 n-1 个点内部的完全连接。

1. 声音
   观察依据

   讲解者用“环形”说明最少边数，并说“n个顶点对应n条边”。

容易把“强连通”与“边很多”直接挂钩。

视频给出的最少情形只是一个有向环，n 个顶点只需 n 条边即可强连通。

1. 声音
   观察依据

   这个定义与其实与连通图当中都比较像吧

连通图针对无向图，要求任意两点有路径；强连通图针对有向图，要求任意两点有双向路径。两者定义形式相似但适用对象和条件不同。

1. 公式
   观察依据

   左右两侧分别给出“连通图”和“强连通图”的定义。

2. 图示
   观察依据

   左侧配无向图，右侧配有向图。

连通图针对无向图的任意两点可达，强连通图针对有向图的任意两点双向可达。

1. 声音
   观察依据

   讲解者先说改成环后“边数是最小的”，后面板书又给出有向强连通图最少 n 条边。

前面用三顶点环直观说明最小强连通结构，后面把它推广为 n 顶点有向强连通图最少 n 条边。

1. 公式
   观察依据

   板书在“考点”中直接对“G是连通图”给出最少 n-1 条边、最多 $n(n-1)/2$ 条边。

连通图定义被用于推出无向图在连通与非连通情形下的边数极值。

1. 字幕依据
   观察依据

   先给出“连通图”定义，随后在“考点”中给出“如果G是连通图则最少有n-1条边”。

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

1. 声音
   观察依据

   讲解者把最大边数解释为“完全图当中不就是二分之n乘n减一条边吗”。

无向图最大边数对应完全图；而非连通图的最大边数则来自“去掉一个孤立点后，其余 n-1 个点仍尽量稠密”的对比构造。

1. 字幕依据
   观察依据

   右栏先定义“强连通图”，后文给出“若G是强连通图，则最少有n条边（回路）”。

强连通性的双向可达要求，直接对应有向环这种最少 n 条边的实现方式。

1. 图示
   观察依据

   左栏为无向图示例，右栏为有向图示例；标题分别为“连通图”和“强连通图”。

片段把无向图的连通性与有向图的强连通性并列对照，强调二者适用对象和判定条件不同。

1. 公式
   观察依据

   幻灯片先定义连通图，再给出“如果G是连通图则最少有n-1条边，最多为 $n*(n-1)/2$”。

无向连通图的边数范围直接建立在“连通图”定义之上。

1. 公式
   观察依据

   幻灯片先定义强连通图，再给出“在n个顶点的有向图G中，若G是强连通图，则最少有n条边……最多$n*(n-1)$”。

有向强连通图的边数极值命题以强连通图定义为前提。

1. 声音
   观察依据

   讲解者说“这个最多的情况与之前我们讲的这个性质是一样的，最多有二分之n乘n减一嘛”“因为在有向图当中它有两条边嘛……所以说在它基础上它要乘个二”。

视频把有向图最大边数 $n(n-1)$ 与无向完全图最大边数 $\frac{n(n-1)}{2}$ 对比，说明有向情形每对顶点可有两条反向边。

1. 公式
   观察依据

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

同一类无向图按是否连通分成两种边数极值情形。

1. 声音
   观察依据

   好，我们接着来看一下连通图的定义。

1. 连通图的定义

1. 声音
   观察依据

   在强连通图当中，图中任意一对顶点都是强连通的，则称此图为强连通图。

1. 强连通图的定义

1. 字幕依据
   观察依据

   考点：对于N个顶点的无向图G...

1. 连通图的边数范围
2. 非连通图的最大边数

1. 公式
   观察依据

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

1. 强连通图

1. 声音
   观察依据

   讲解者用 A 到 D、D 不能回 A 判断图1。

1. 强连通图
2. 图1是否为强连通图

1. 声音
   观察依据

   讲解者说改成环后“边数是最小的”。

2. 公式
   观察依据

   板书给出有向强连通图最少 n 条边。

1. 有向强连通图的边数范围
2. 修改图2使其成为强连通图

1. 公式
   观察依据

   板书列出无向连通图与非连通图的边数公式。

1. 无向连通图与非连通图的边数范围

1. 字幕依据
   观察依据

   “图中任意两个顶点都是联通的，则称为连通图，否则是非连通图”。

1. 连通图与非连通图

1. 字幕依据
   观察依据

   “图中任意一对顶点都是强联通的，则称此图为强连通图”。

1. 强连通图

1. 声音
   观察依据

   “五个顶点用到了四条边”。

2. 字幕依据
   观察依据

   “如果G是连通图则最少有n-1条边”。

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

1. 公式
   观察依据

   4加3加2加1等于5乘以4再除以2。

2. 声音
   观察依据

   讲解者把它联系到完全图。

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

1. 声音
   观察依据

   “要让这幅图是一个非连通图且有最多的边……让下面这五个顶点成为一颗完全图……让F与A、B、C、D、E都不相连”。

1. 无向非连通图最大边数
2. 非连通图最大边数的构造推导
3. 非连通图最大边数构造示例