最小生成树 - 理论计算机科学导论

1. 声音
   观察依据

   主讲人指出，最小生成树仍然是图上的一棵生成树，且该图的每条边上都必须标有数字。

2. 图示
   观察依据

   一只手绘制了一个顶点为紫色、边为蓝色的图，然后在各条边旁用红色写上数字。

weighted graph

每条边都被赋予一个指定数值的图。

图论；带边权的有限无向图。

1. 声音
   观察依据

   “所有边都被赋予了某个特定数字”以及“每条边都必须附有一个特定数值”。

2. 图示
   观察依据

   红色数字被写在所绘制图的各条边上。

1. 视频未说明是否允许负权重或零权重。

edge number / edge value

赋予某条边的数值量；本片段中的示例使用正整数，例如1、2、3、4和6。

所展示的带权图的边标签。

1. 声音
   观察依据

   “对每一棵生成树，你可以将这些数字加总起来”以及“此处这棵生成树的权值为20”。

2. 公式
   观察依据

   黑板上显示了一棵被高亮的生成树，其权值计算式为$2+4+3+2+3+6=20$。

weight of a spanning tree

属于该生成树的所有边上的数值之和。

适用于任意选定的加权图的生成树。

1. 声音
   观察依据

   主讲人引入了“最小生成树”的概念，并随后将其定义为所有生成树中边权总和最小的那个生成树。

2. 字幕依据
   观察依据

   黑板上写的标题是“最小生成树”。

在本片段中，最小生成树被呈现为加权图的一棵生成树，其总权重（即其各条边上数字之和）在该图的所有生成树中尽可能小。

1. 基础对象必须是一张图。

2. 每条边都必须附有一个数值。

3. 比较是在同一张图的所有生成树之间进行的。

1. 生成树（先前已学概念）
2. 用于最小生成树问题的加权图输入

1. 声音
   观察依据

   “既然大家已经了解了生成树的概念，接下来我想向大家介绍最小生成树的概念。”

2. 字幕依据
   观察依据

   先写出短语“生成树”，再扩展为“最小生成树”。

1. 本片段假定观众已掌握先前材料中给出的生成树定义，因此未完整复述该定义。

本视频将“生成树”视为已知概念，并以此为基础概念，通过引入边权和最小化要求，进一步精确定义“最小生成树”。

1. 默认学习者已掌握生成树的相关知识。

1. 声音
   观察依据

   要寻找最小生成树，需要一种特殊类型的图，其中每条边都被赋予了一个确定的数值。

2. 图示
   观察依据

   先画出顶点和边，再在边上添加红色数字。

1. 该片段并未对加权图这一更广泛的图类给出形式化定义，仅说明每条边都附有一个数值。

主讲人指出，最小生成树定义在边带有数值标签的图上；在最短路径问题中这些标签代表距离，但此处它们也可以表示其他类型的数值。

1. 每条边都必须附有一个数值。

1. 生成树（先前已学概念）

1. 声音
   观察依据

   “对每一棵生成树，你可以将这些数值相加”，接着说“这棵生成树的权重为20”。

2. 公式
   观察依据

   屏幕上显示的求和式为$2+4+3+2+3+6=20$。

3. 动画
   观察依据

   图中被选中的边以绿色描出，同时标出其对应的数值标签。

给定一个带权图，任选一棵生成树，并将该树中所包含的边上的数值相加。所得的和称为该生成树的权。

1. 图的每条边上必须标有数值。

2. 仅对所选生成树中包含的边求和。

1. 生成树（先前已学概念）
2. 用于最小生成树问题的加权图输入

1. 声音
   观察依据

   一个图可能拥有不止一棵最小生成树，但每一棵最小生成树都必须满足：其所有边的权值之和尽可能小。

视频明确指出，一个图可能具有多棵最小生成树。所要求的并非生成树本身唯一，而是每一棵最小生成树都必须达到可能的最小总边权和。

1. 适用于本片段中讨论的带权图。

1. 最小生成树

1. 声音
   观察依据

   最小生成树是指该图的所有生成树中，总权值（即所有边上的数值之和）最小的那一棵生成树。

对于一个带权图，一棵生成树是该图的最小生成树，当且仅当它的总边权和是该图所有生成树中可能的最小值。

1. 图的每条边上都附有数值。

2. 当前讨论的对象是该图的一棵生成树。

对于给定的带权图，其所有生成树中，最小生成树是那些总边权和达到最小值的生成树。

1. 声音
   观察依据

   一个图可能拥有多个最小生成树，但每个最小生成树都必须满足：其所有边的权值之和尽可能小。

一个图可能拥有多个最小生成树，且每个这样的生成树都必须具有最低可能的总边权和。

1. 该图是视频片段中所描述类型的带权图。

存在拥有多个最小生成树的带权图；对于这类图的任意一个最小生成树，其边权和均为最小值。

1. 声音
   观察依据

   主讲人首先选取一棵生成树，计算其权重为20；接着再选取另一棵生成树，计算其权重为21；最后通过比较这两个权重，引出最小生成树的定义。

2. 公式
   观察依据

   展示了两个求和式：$2+4+3+2+3+6=20$ 和 $3+4+3+2+3+6=21$。

3. 动画
   观察依据

   用绿色高亮不同的边集，以表示不同的生成树。

1. 该片段并未证明不存在权重低于20的其他生成树；它仅演示了如何比较权重，并由此引出最小生成树的定义。

1. 公式

   $$$$
   解释

   从一个带权图出发，从中任选一棵生成树。

   步骤依据

   主讲人说：“我们为这个图任取一棵生成树。”

   视频直接表达
2. 公式

   $$2+4+3+2+3+6=20$$
   解释

   将所选生成树各条边上的数字标签相加，得到它的总权重。

   步骤依据

   根据前述方法，生成树的权重等于其各条边上数字的总和。

   视频直接表达
3. 公式

   $$$$
   解释

   为同一张图另选一棵生成树。

   步骤依据

   主讲人明确说道：“现在，如果你另选一棵生成树，例如这里这一棵。”

   视频直接表达
4. 公式

   $$3+4+3+2+3+6=21$$
   解释

   将第二棵生成树各条边上的标签数值相加，得到它的总权重。

   步骤依据

   对第二棵选定的生成树同样应用该求和规则。

   视频直接表达
5. 公式

   $$20 < 21$$
   解释

   比较这两个总和，可观察到第一棵生成树的权重小于第二棵。

   步骤依据

   对屏幕上显示的两个和式进行直接的算术比较。

   依据视频推导
6. 公式

   $$$$
   解释

   利用这一比较引出定义：最小生成树是指总权重尽可能小的生成树。

   步骤依据

   主讲人在完成比较后立即从该例子过渡到一般性定义。

   视频直接表达

该例子展示了如何计算并比较生成树的权重，从而引出最小生成树的定义——即总权重最小的生成树。

1. 声音
   观察依据

   主讲人选择了一棵生成树，并称其权重为20。

2. 公式
   观察依据

   黑板上显示$2+4+3+2+3+6=20$。

3. 动画
   观察依据

   用绿色描出一组边，以标示所选的生成树。

1. 顶点的具体名称未作标注，因此所选边仅能通过其显示的权重及相对位置来识别。

已知所画出的带权图，请从中选择一棵生成树，并计算其总权重。

1. 画出一幅带权图，其各条边上标有数字标签。

2. 从该图中选出一棵生成树。

求出所选生成树的权重。

1. 公式

   $$$$
   解释

   找出所选生成树中包含的各条边。

   步骤依据

   主讲人用绿色描出一组边，以指示所选的树。

   视频直接表达
2. 公式

   $$2+4+3+2+3+6$$
   解释

   读出这些被选边上的数字标签，并将它们列出以便相加。

   步骤依据

   生成树的权重是其所有边所附数字之和。

   视频直接表达
3. 公式

   $$2+4+3+2+3+6=20$$
   解释

   进行加法运算，得到总权重。

   步骤依据

   对屏幕上显示的求和式进行算术计算。

   视频直接表达

所选生成树的权重为20。

黑板上显示的等式与口述结果一致：该和等于20。

1. 声音
   观察依据

   说话者选择了另一棵生成树，并指出其总权重为21。

2. 公式
   观察依据

   黑板上显示$3+4+3+2+3+6=21$。

3. 动画
   观察依据

   另一组边被用绿色高亮标出。

1. 与前一个例子相同，顶点未标注标签，因此所选边仅通过视觉方式及其权重来确定。

在同一个带权图中选择另一棵生成树，并计算其总权重。

1. 使用的是同一张带权图。

2. 选取第二棵生成树。

求第二棵生成树的权值。

1. 公式

   $$$$
   解释

   再选取该图的另一棵生成树。

   步骤依据

   主讲人明确引入了第二棵示例生成树。

   视频直接表达
2. 公式

   $$3+4+3+2+3+6$$
   解释

   收集属于这棵第二棵生成树的各条边的标签。

   步骤依据

   应用与生成树权值计算相同的求和规则。

   视频直接表达
3. 公式

   $$3+4+3+2+3+6=21$$
   解释

   将所收集的数字相加，得到总权值。

   步骤依据

   对屏幕上显示的和式进行算术运算。

   视频直接表达

第二棵生成树的权值为21。

黑板上的等式与主讲人口头得出的结论一致，总和均为21。

1. 动画
   观察依据

   用紫色圆点表示顶点，用蓝色线条表示边，并在各条边旁标出红色数字。

2. 声音
   观察依据

   主讲人解释说，该图的所有边都必须附有数字。

1. 精确的图布局为手绘而成，部分边的端点在视觉上仅为近似位置，并未进行形式化标注。

1. 紫色顶点

2. 蓝色边

3. 红色数字边标签

1. 顶点首先出现。

2. 随后在顶点之间绘制边。

3. 最后为边添加数字标签。

1. 一旦绘制完成，该图在整个视频片段中始终代表同一个数学对象。

2. 每条边始终关联一个数字。

该绘图确立了最小生成树问题所需的场景：一张边带有权重的图。

1. 动画
   观察依据

   用绿色描出某组边的子集，同时写出公式$2+4+3+2+3+6=20$。

2. 声音
   观察依据

   主讲人称这是一棵生成树，并计算了它的权重。

1. 原始带权图

2. 以绿色描出的所选边

3. 公式 $2+4+3+2+3+6=20$

1. 所选边被重新着色或以绿色覆盖绘制。

2. 它们的标签在黑板右侧相加求和。

1. 底层图结构及所有边的权重均保持不变。

2. 仅对所选的边子集加以强调。

视觉上的强调区分了一棵生成树与整个图，并展示了其权重的计算方式。

1. 动画
   观察依据

   另一组边子集以绿色描出，同时写出公式 $3+4+3+2+3+6=21$。

2. 声音
   观察依据

   主讲人引入了另一棵生成树，并计算了它的权重。

1. 同一张带权图

2. 另一组以绿色描出的边子集

3. 公式 $3+4+3+2+3+6=21$

1. 一组新的边被高亮显示。

2. 图旁写出了第二个总权重。

1. 图的结构与边的标签均未改变。

2. 该比较针对同一张图的不同生成树。

第二次高亮说明，不同的生成树可能具有不同的总权重。

1. 声音
   观察依据

   “一张图可能拥有不止一棵最小生成树……”

人们可能认为一张图仅有一棵最小生成树。

视频明确指出，一张图可以拥有不止一棵最小生成树；要求是每棵的边权总和都达到可能的最低值。

1. 声音
   观察依据

   “在最短环游的情形下，这些数值代表距离，但它们也可以是其他类型的数值。这其实并不重要。”

由于该主题是在‘最短环游’标题下引入的，人们可能误以为边上的数字必须始终表示距离。

主讲人指出，在最短环游的情境中，这些数字可以是距离，但也可能是其他数值；关键要求仅仅是每条边都附有一个数值。

1. 声音
   观察依据

   主讲人首先提及此前已知的生成树概念，再引出最小生成树。

理解生成树被视为定义最小生成树之前所需具备的先备知识。

1. 声音
   观察依据

   要找出一棵最小生成树，需要一张所有边都附有数值的图。

只有当图的边具有数值时，‘最小化生成树总权重’这一概念才有意义。

1. 声音
   观察依据

   “最小生成树仍是一张图上的生成树”，随后又将其定义为总权重最小的生成树。

最小生成树是一种特殊的生成树，即其所有边的权重之和达到最小。

1. 声音
   观察依据

   主讲人首先解释如何对一棵生成树的各边数值求和，再基于该总权重来定义最小生成树。

最小生成树的定义依赖于一种方法：通过将生成树中所有边的权值相加，来度量任意生成树的总权值。

1. 声音
   观察依据

   主讲人将当前所需的图与最短环游问题中的输入进行比较，指出在后者中那些数字表示距离，而此处它们可以是其他数值。

2. 字幕依据
   观察依据

   标题“最短环游”仍保留在新主题上方可见。

该片段对比了最短环游问题的设定（其中边上的数字表示距离）与最小生成树所用的更一般的带权图设定。

1. 声音
   观察依据

   主讲人用自然语言给出了最小生成树的定义。

1. 最小生成树
2. 最小生成树的刻画

1. 公式
   观察依据

   黑板上显示了一个选定生成树的权值计算式：$2+4+3+2+3+6=20$。

2. 声音
   观察依据

   主讲人解释说，需将该生成树各条边上所标的数字相加。

1. 生成树的权重
2. 计算一棵生成树的权重

1. 声音
   观察依据

   主讲人指出，一个图可能拥有不止一棵最小生成树。

1. 最小生成树的非唯一性
2. 多个最小生成树的存在性

1. 公式
   观察依据

   计算了两棵生成树的权值：20和21。

2. 声音
   观察依据

   比较之后，主讲人将最小生成树定义为总权重最小的那棵生成树。

1. 通过比较两棵生成树来引出最小生成树的概念
2. 最小生成树

1. 声音
   观察依据

   主讲人指出，这些数字在最短环游问题中代表距离，但也可以是其他数值。

1. 用于最小生成树问题的加权图输入
2. 误以为边上的数字必须表示距离