离散数学
真值表、幂集格、关系矩阵、等价类、哈斯图、归纳法、鸽巢、二分图、着色、最小生成树、欧拉与哈密顿回路、汉诺塔递推。
本页 12 条示例。代码引自 corpus/examples/math-discrete/，截图为真机渲染的终态。
真值表：p → q 和 ¬p ∨ q 逐行等价
五列的表格里，p、q、¬p、p→q、¬p∨q 四行取值全部填满；最后两列被绿框一起圈住——上下四行逐格相同，右侧标出「恒等」。
py
"""真值表：p → q 和 ¬p ∨ q 逐行等价
@expect 五列的表格里，p、q、¬p、p→q、¬p∨q 四行取值全部填满；最后两列被绿框一起圈住——上下四行逐格相同，右侧标出「恒等」。
@note 讲解要点：蕴含 p→q 只在「p 真而 q 假」时为假，这正好等于 ¬p∨q 的真值。逻辑等价的判据不是「意思像」，而是真值表逐行一致——两张表相同，两个公式就可以互相替换。
"""
from manim import *
class TruthTableScene(Scene):
def construct(self):
headers = ["p", "q", "¬p", "p → q", "¬p ∨ q"]
rows = [
["真", "真", "假", "真", "真"],
["真", "假", "假", "假", "假"],
["假", "真", "真", "真", "真"],
["假", "假", "真", "真", "真"],
]
ncol = len(headers)
nrow = len(rows) + 1
cell = 0.95
width = ncol * cell
height = nrow * cell
center = [0, -0.3, 0]
left = center[0] - width / 2
top = center[1] + height / 2
def pos(row, col):
return [left + cell * (col + 0.5), top - cell * (row + 0.5), 0]
cells = VGroup()
for r in range(nrow):
for c in range(ncol):
box = Square(side_length=cell, color=GRAY_B, stroke_width=1.5).move_to(pos(r, c))
cells.add(box)
head_texts = VGroup(
*[Text(name, font_size=26, color=YELLOW).move_to(pos(0, c)) for c, name in enumerate(headers)]
)
body = VGroup()
for r, values in enumerate(rows):
for c, value in enumerate(values):
color = GRAY_A
if c == 3 and value == "假":
color = RED
if c == 4 and value == "假":
color = RED
body.add(Text(value, font_size=26, color=color).move_to(pos(r + 1, c)))
# 高亮框按坐标手算，不圈组：SurroundingRectangle(组) 会让被量的组之后不再渲染，
# 而且这些格子已经在外面的 cells 组里了——同一个物体进两个组本身就致病
box = Rectangle(
width=cell * 2 + 0.16,
height=height + 0.16,
color=GREEN,
stroke_width=3,
).move_to([left + cell * 4, center[1], 0])
equal_note = Text("两列逐行相同 → 逻辑等价", font_size=24, color=GREEN).move_to([0, 2.6, 0])
# 绿框右缘 x≈2.93，右侧标出「恒等」
ident_note = Text("恒等", font_size=24, color=GREEN).move_to([3.6, -0.3, 0])
# 公式用绝对坐标定位（to_edge 要读包围盒，长公式会读出 NaN 而整条消失）
formula = MathTex(r"p \to q \equiv \neg p \lor q", font_size=44).move_to([0, 3.3, 0])
caption = Text("「p 真且 q 假」是唯一让蕴含为假的一行——红字就是它", font_size=24, color=GRAY_A)
caption.move_to([0, -3.35, 0])
self.play(Write(formula), Write(equal_note), run_time=0.8)
self.play(Create(cells), Write(head_texts), run_time=0.9)
self.play(LaggedStart(*[FadeIn(t) for t in body], lag_ratio=0.03), run_time=1.5)
self.play(Create(box), Write(ident_note), run_time=0.7)
self.play(Write(caption), run_time=0.7)
self.wait(0.4)幂集格：{1,2,3} 的 8 个子集按包含关系排成一个立方体
八个节点按子集大小分成四层：最上 ∅、中间两层各三个、最下 {1,2,3}；连线只在「差一个元素」的节点之间。整体形状就是一个三维立方体的平面投影。
py
"""幂集格：{1,2,3} 的 8 个子集按包含关系排成一个立方体
@expect 八个节点按子集大小分成四层：最上 ∅、中间两层各三个、最下 {1,2,3}；连线只在「差一个元素」的节点之间。整体形状就是一个三维立方体的平面投影。
@note 讲解要点：每往上一层就往子集里加一个元素，所以图的宽度是二项式系数 1-3-3-1；节点总数是 2³ = 8。幂集永远可以这样分层画成一格，这就是它叫布尔格的原因。
"""
from manim import *
class PowerSetLatticeScene(Scene):
def construct(self):
nodes = {
"empty": [0, 2.4, "∅"],
"a": [-3.4, 1.2, "{1}"],
"b": [0, 1.2, "{2}"],
"c": [3.4, 1.2, "{3}"],
"ab": [-3.4, 0.0, "{1,2}"],
"ac": [0, 0.0, "{1,3}"],
"bc": [3.4, 0.0, "{2,3}"],
"abc": [0, -1.2, "{1,2,3}"],
}
edges = [
("empty", "a"),
("empty", "b"),
("empty", "c"),
("a", "ab"),
("a", "ac"),
("b", "ab"),
("b", "bc"),
("c", "ac"),
("c", "bc"),
("ab", "abc"),
("ac", "abc"),
("bc", "abc"),
]
circles = VGroup()
labels = VGroup()
for key, (x, y, name) in nodes.items():
circle = Circle(radius=0.44, color=GRAY_B)
circle.set_fill(GRAY_E, opacity=0.45)
circle.move_to([x, y, 0])
circles.add(circle)
labels.add(Text(name, font_size=21, color=WHITE).move_to([x, y, 0]))
links = VGroup(
*[
Line(nodes[a][:2] + [0], nodes[b][:2] + [0], color=GRAY_C, stroke_width=2.5)
for a, b in edges
]
)
head = Text("幂集格：8 个子集，按包含关系分层", font_size=27, color=YELLOW).move_to([0, 3.3, 0])
level_note = Text("层 = 子集大小：0 → 1 → 2 → 3", font_size=24, color=GREEN).move_to([0, -2.3, 0])
count_note = MathTex(r"|P(\{1,2,3\})| = 2^3 = 8", font_size=40).move_to([0, -3.1, 0])
self.play(Write(head), run_time=0.6)
self.play(Create(links), run_time=0.9)
self.play(LaggedStart(*[FadeIn(c) for c in circles], lag_ratio=0.1), run_time=1.2)
self.play(Write(labels), run_time=0.8)
self.play(Write(level_note), run_time=0.7)
self.play(Write(count_note), run_time=0.8)
self.wait(0.4)关系矩阵：把「自反」和「对称」读成矩阵的样子
4×4 的方格对应 {1,2,3,4} 上的有序对，填实代表「有这条关系」。绿色小框圈出主对角线（自反），黄色小框圈出一对关于对角线镜像的格子（对称）——图案翻过去完全不变。
py
"""关系矩阵：把「自反」和「对称」读成矩阵的样子
@expect 4×4 的方格对应 {1,2,3,4} 上的有序对，填实代表「有这条关系」。绿色小框圈出主对角线（自反），黄色小框圈出一对关于对角线镜像的格子（对称）——图案翻过去完全不变。
@note 讲解要点：关系就是有序对集合，也就是 0/1 矩阵，也就是有向图——同一件事的三种画法。自反 = 主对角线全 1；对称 = 关于主对角线镜像相同；传递 = R∘R ⊆ R，即「沿箭头走两步也仍是箭头」。
"""
from manim import *
class RelationMatrixScene(Scene):
def construct(self):
n = 4
cell = 0.86
span = n * cell
origin = [-3.3, -0.2, 0]
members = [(i, j) for i in range(1, n + 1) for j in range(1, n + 1) if (i - j) % 2 == 0]
boxes = {}
centers = {}
for i in range(1, n + 1):
for j in range(1, n + 1):
cx = origin[0] - span / 2 + cell * (j - 0.5)
cy = origin[1] + span / 2 - cell * (i - 0.5)
box = Square(side_length=cell, color=GRAY_B, stroke_width=1.5).move_to([cx, cy, 0])
if (i, j) in members:
box.set_fill(BLUE, opacity=0.75)
boxes[(i, j)] = box
centers[(i, j)] = (cx, cy)
# 逐个 add 进唯一的组；不要把已有物体再装进第二个 VGroup
cells = VGroup()
for key in sorted(boxes):
cells.add(boxes[key])
heads = VGroup()
for j in range(1, n + 1):
heads.add(
Text(str(j), font_size=22, color=YELLOW).move_to(
[origin[0] - span / 2 + cell * (j - 0.5), origin[1] + span / 2 + 0.35, 0]
)
)
for i in range(1, n + 1):
heads.add(
Text(str(i), font_size=22, color=YELLOW).move_to(
[origin[0] - span / 2 - 0.35, origin[1] + span / 2 - cell * (i - 0.5), 0]
)
)
# 高亮框用原始坐标手算：Indicate 会把已填充物体的填充剥掉，不能用在这里
diag_marks = VGroup(
*[
Rectangle(width=cell * 0.9, height=cell * 0.9, color=GREEN, stroke_width=3.5).move_to(
[centers[(i, i)][0], centers[(i, i)][1], 0]
)
for i in range(1, n + 1)
]
)
mirror_marks = VGroup(
*[
Rectangle(width=cell * 0.9, height=cell * 0.9, color=YELLOW, stroke_width=3.5).move_to(
[centers[key][0], centers[key][1], 0]
)
for key in [(1, 3), (3, 1)]
]
)
right_x = 2.7
r1 = Text("自反：主对角线全为 1", font_size=25, color=GREEN).move_to([right_x, 1.5, 0])
r2 = Text("对称：关于对角线镜像相同", font_size=25, color=YELLOW).move_to([right_x, 0.7, 0])
# 「传递」两个字必须走 Text（MathTex 里写中文 = 什么都不显示），公式部分单独一块
r3_label = Text("传递：", font_size=25).move_to([right_x - 1.5, -0.2, 0])
r3_math = MathTex(r"R \circ R \subseteq R", font_size=38).move_to([right_x + 0.75, -0.2, 0])
r4 = Text("i ≡ j (mod 2) 的同余关系", font_size=24, color=BLUE).move_to([right_x, -1.2, 0])
r5 = Text("三条性质全中 → 等价关系", font_size=25, color=GREEN).move_to([right_x, -2.0, 0])
caption = Text("关系 = 有序对集合 = 0/1 矩阵 = 有向图，同一件事的三种画法", font_size=24, color=GRAY_A)
caption.move_to([0, 3.25, 0])
self.play(Write(caption), run_time=0.7)
self.play(Create(cells), Write(heads), run_time=1.0)
self.play(Create(diag_marks), Write(r1), run_time=1.0)
self.play(Create(mirror_marks), Write(r2), run_time=1.0)
self.play(Write(r3_label), Write(r3_math), run_time=0.7)
self.play(Write(r4), Write(r5), run_time=0.8)
self.wait(0.4)等价类：模 3 同余把 0~8 切成三堆
上方 0~8 九个数字排成一条线；下方被重新排成三行，每行三个数字——同余的那三个凑成一组并被绿框圈住，三组互不重叠、合起来正好是全部九个数。
py
"""等价类：模 3 同余把 0~8 切成三堆
@expect 上方 0~8 九个数字排成一条线；下方被重新排成三行，每行三个数字——同余的那三个凑成一组并被绿框圈住，三组互不重叠、合起来正好是全部九个数。
@note 讲解要点：等价关系会把集合「切」成若干个互不相交的等价类，每个等价类内部的元素彼此等价、跨类元素绝不等价。三堆合起来还是 9 个、两两无交集——这就是「划分」的定义，也是商集 A/R 的由来。
"""
from manim import *
class EquivalenceClassesScene(Scene):
def construct(self):
values = list(range(9))
line_y = 2.0
line_x = [-5.6 + i * 1.4 for i in range(9)]
line_dots = VGroup(*[Dot([line_x[i], line_y, 0], radius=0.13, color=WHITE) for i in range(9)])
line_labels = VGroup(
*[Text(str(i), font_size=24, color=YELLOW).move_to([line_x[i], line_y + 0.42, 0]) for i in range(9)]
)
line_head = Text("全集 A = {0,1,2,…,8}", font_size=25, color=GRAY_A).move_to([0, 3.1, 0])
colors = [GREEN, YELLOW, BLUE]
rows_y = [0.5, -0.95, -2.4]
row_x = [-3.6, -1.2, 1.2]
groups = VGroup()
groups_content = VGroup()
group_labels = VGroup()
for mod in range(3):
members = [v for v in values if v % 3 == mod]
vgroup = VGroup()
for idx, v in enumerate(members):
dot = Dot([row_x[idx], rows_y[mod], 0], radius=0.15, color=colors[mod])
num = Text(str(v), font_size=24, color=colors[mod]).move_to([row_x[idx], rows_y[mod] + 0.42, 0])
vgroup.add(dot, num)
# SurroundingRectangle 会「吃掉」被量的那组——量副本；同时 vgroup 本身要上屏
frame = SurroundingRectangle(vgroup.copy())
frame.set_color(colors[mod])
frame.set_stroke(width=3)
groups.add(frame)
groups_content.add(vgroup)
group_labels.add(
Text(f"[{mod}] = {{{', '.join(str(m) for m in members)}}}", font_size=24, color=colors[mod])
.move_to([4.3, rows_y[mod], 0])
)
caption = Text("三个等价类：两两不交，并起来还是全集", font_size=25, color=GREEN).move_to([0, -3.5, 0])
self.play(Write(line_head), run_time=0.6)
self.play(FadeIn(line_dots), Write(line_labels), run_time=0.9)
self.play(
LaggedStart(*[FadeIn(g) for g in groups_content], lag_ratio=0.35),
LaggedStart(*[Create(f) for f in groups], lag_ratio=0.35),
run_time=1.6,
)
self.play(Write(group_labels), run_time=0.8)
self.play(Write(caption), run_time=0.7)
self.wait(0.4)哈斯图：只画「覆盖关系」，不可比的两个元素一眼看出
{1,2,3,6} 按整除关系排成菱形——1 在最下、6 在最上，而 2 和 3 并排站在中间；2 与 3 之间没有连线，被标上「不可比」。从 1 到 6 的传递关系也没有画线。
py
"""哈斯图：只画「覆盖关系」，不可比的两个元素一眼看出
@expect {1,2,3,6} 按整除关系排成菱形——1 在最下、6 在最上，而 2 和 3 并排站在中间；2 与 3 之间没有连线，被标上「不可比」。从 1 到 6 的传递关系也没有画线。
@note 讲解要点：哈斯图省掉两类边：传递得到的不画（1|6 就不画），自反的环也不画。所以图中「没有边」只说明两者不可比或能被传递推出，不能读成「没关系」。菱形里 2∥3 这种「既不左也不右」的元素，偏序才会有、全序不会有。
"""
from manim import *
class HasseDiagramScene(Scene):
def construct(self):
nodes = {
"one": [0, -1.9, "1"],
"two": [-2.3, -0.1, "2"],
"three": [2.3, -0.1, "3"],
"six": [0, 1.5, "6"],
}
edges = [("one", "two"), ("one", "three"), ("two", "six"), ("three", "six")]
circles = VGroup()
labels = VGroup()
for key, (x, y, name) in nodes.items():
circle = Circle(radius=0.45, color=GRAY_B)
circle.set_fill(GRAY_E, opacity=0.5)
circle.move_to([x, y, 0])
circles.add(circle)
labels.add(Text(name, font_size=30, color=YELLOW).move_to([x, y, 0]))
links = VGroup(
*[
Line(nodes[a][:2] + [0], nodes[b][:2] + [0], color=GRAY_C, stroke_width=3)
for a, b in edges
]
)
incomparable = DashedLine([-2.3, -0.1, 0], [2.3, -0.1, 0], color=RED)
incomparable_label = Text("2 与 3 不可比（互不整除）", font_size=24, color=RED)
incomparable_label.move_to([0, -0.62, 0])
# 被省略的传递边 1→6：沿真实方向画虚线示意，两端各离开圆边 0.15，不穿过任何节点
skipped = DashedLine([0, -1.3, 0], [0, 0.9, 0], color=GRAY_D)
skipped_label = Text("1 整除 6 由传递得到，不画", font_size=23, color=GRAY_A)
skipped_label.move_to([4.4, 1.0, 0])
caption = Text("哈斯图 = 去掉传递边、去掉自反环之后的整除关系", font_size=25, color=GREEN)
caption.move_to([0, -3.2, 0])
head = Text("整除偏序 ({1,2,3,6}, |) 的哈斯图", font_size=27, color=YELLOW).move_to([0, 3.0, 0])
self.play(Write(head), run_time=0.6)
self.play(Create(links), run_time=0.8)
self.play(LaggedStart(*[FadeIn(c) for c in circles], lag_ratio=0.15), run_time=1.0)
self.play(Write(labels), run_time=0.7)
self.play(Create(incomparable), Write(incomparable_label), run_time=0.8)
self.play(Create(skipped), Write(skipped_label), run_time=0.8)
self.play(Write(caption), run_time=0.7)
self.wait(0.4)数学归纳法的经典图示：两段阶梯拼成一个矩形
左边蓝色阶梯的柱高依次是 1、2、3、4，右边黄色阶梯柱高 4、3、2、1；两块交错拼合后正好填满一个宽 4、高 5 的矩形——所以阶梯的总格子数是 4×5 的一半。
py
"""数学归纳法的经典图示：两段阶梯拼成一个矩形
@expect 左边蓝色阶梯的柱高依次是 1、2、3、4，右边黄色阶梯柱高 4、3、2、1；两块交错拼合后正好填满一个宽 4、高 5 的矩形——所以阶梯的总格子数是 4×5 的一半。
@note 讲解要点：归纳法的两块拼图缺一不可——「基例」保证第一块砖立在原地（n=1 成立），「归纳步」保证倒下一块就带倒下一块（n 成立则 n+1 成立）。而这张图给出的是结论的闭式：1+2+…+n = n(n+1)/2。
"""
from manim import *
class MathematicalInductionScene(Scene):
def construct(self):
n = 4
unit = 0.72
x_left = -5.0
y_bottom = -2.2
def cell(j, k):
return [
x_left + unit * (j + 0.5),
y_bottom + unit * (k + 0.5),
0,
]
lower = VGroup()
upper = VGroup()
for j in range(n):
for k in range(j + 1):
box = Square(side_length=unit * 0.97, color=BLUE)
box.set_fill(BLUE, opacity=0.75)
box.move_to(cell(j, k))
lower.add(box)
for k in range(j + 1, n + 1):
box = Square(side_length=unit * 0.97, color=YELLOW)
box.set_fill(YELLOW, opacity=0.75)
box.move_to(cell(j, k))
upper.add(box)
outline = Rectangle(width=unit * n, height=unit * (n + 1), color=WHITE)
outline.move_to([x_left + unit * n / 2, y_bottom + unit * (n + 1) / 2, 0])
leg_lower = Text("1 + 2 + 3 + 4", font_size=24, color=BLUE).move_to([x_left + unit * n / 2, y_bottom - 0.42, 0])
leg_upper = Text("4 + 3 + 2 + 1", font_size=24, color=YELLOW).move_to([x_left + unit * n / 2 + 2.4, y_bottom - 0.42, 0])
right_x = 2.4
formula = MathTex(r"1 + 2 + \cdots + n = \frac{n(n+1)}{2}", font_size=46)
formula.move_to([right_x, 1.5, 0])
step1 = Text("两块阶梯拼成 4 × 5 的矩形", font_size=24, color=WHITE).move_to([right_x, 0.35, 0])
step2 = MathTex(r"1+2+3+4 = \frac{4 \times 5}{2} = 10", font_size=42, color=GREEN)
step2.move_to([right_x, -0.8, 0])
note = Text("基例管「第一块砖」，归纳步管「倒下一块带倒下一块」", font_size=23, color=GRAY_A)
note.move_to([right_x, -2.1, 0])
caption = Text("两条腿都成立，整条链就都成立", font_size=25, color=YELLOW).move_to([right_x, -2.9, 0])
self.play(LaggedStart(*[FadeIn(b) for b in lower], lag_ratio=0.08), run_time=1.4)
self.play(Write(leg_lower), run_time=0.5)
self.play(LaggedStart(*[FadeIn(b) for b in upper], lag_ratio=0.08), run_time=1.4)
self.play(Write(leg_upper), Create(outline), run_time=0.7)
self.play(Write(formula), run_time=0.8)
self.play(Write(step1), run_time=0.6)
self.play(Write(step2), run_time=0.8)
self.play(Write(note), run_time=0.7)
self.play(Write(caption), run_time=0.7)
self.wait(0.4)鸽巢原理：13 只鸽子放进 12 个巢
12 个巢先各落一只鸽子，还剩一只无处可放；它落进第一个巢时被红圈标出——巢数已经用完，必然有一只和别的挤在一起。
py
"""鸽巢原理：13 只鸽子放进 12 个巢
@expect 12 个巢先各落一只鸽子，还剩一只无处可放；它落进第一个巢时被红圈标出——巢数已经用完，必然有一只和别的挤在一起。
@note 讲解要点：m 个巢装 n 只鸽子，必有某个巢至少装 ⌈n/m⌉ 只，靠的是「平均」而不是「构造」——假如每个巢都不到 ⌈n/m⌉ 只，总数就凑不到 n。这是抽屉原理、也是「哈希必冲突」的同一句话。
"""
from manim import *
class PigeonholeScene(Scene):
def construct(self):
holes = 12
xs = [-5.5 + i * 1.0 for i in range(holes)]
nests = VGroup()
for x in xs:
box = Square(side_length=0.82, color=GRAY_B, stroke_width=2).move_to([x, 0, 0])
nests.add(box)
hole_numbers = VGroup(
*[Text(str(i + 1), font_size=20, color=GRAY_A).move_to([xs[i], -0.66, 0]) for i in range(holes)]
)
pigeons = VGroup()
for x in xs:
dot = Dot([x, 0, 0], radius=0.14, color=TEAL)
pigeons.add(dot)
extra = Dot([xs[0], 0, 0], radius=0.15, color=RED)
ring = Circle(radius=0.34, color=RED, stroke_width=3)
ring.move_to([xs[0], 0, 0])
head = Text("12 个巢，先各放一只：正好用完", font_size=25, color=GREEN).move_to([0, 1.3, 0])
tail = Text("第 13 只无论放进哪个巢，都会和已有的挤在一起", font_size=25, color=RED)
tail.move_to([0, -2.0, 0])
formula = MathTex(r"\left\lceil \frac{n}{m} \right\rceil = \left\lceil \frac{13}{12} \right\rceil = 2", font_size=46)
formula.move_to([0, -2.9, 0])
self.play(FadeIn(nests), Write(hole_numbers), run_time=0.9)
self.play(LaggedStart(*[FadeIn(d) for d in pigeons], lag_ratio=0.08), run_time=1.4)
self.play(Write(head), run_time=0.6)
self.play(FadeIn(extra, shift=DOWN * 0.6), run_time=0.7)
self.play(Create(ring), Write(tail), run_time=0.8)
self.play(Write(formula), run_time=0.8)
self.wait(0.4)二分图：顶点能分成两组、边只在组间出现
左边六个顶点分成蓝、黄两列，六条边全部从蓝列跨到黄列，同列内部一条边都没有；右侧对照画着一个三角形——三条边首尾相接构成的奇环。
py
"""二分图：顶点能分成两组、边只在组间出现
@expect 左边六个顶点分成蓝、黄两列，六条边全部从蓝列跨到黄列，同列内部一条边都没有；右侧对照画着一个三角形——三条边首尾相接构成的奇环。
@note 讲解要点：二分图的定义就是「顶点能二分类，使每条边的两端分属不同类」，等价于「图中没有奇环」。所以一个三角形就足以否决整个二分性；这也是判断二分图的染色算法能一行写完的原因。
"""
from manim import *
import math
class BipartiteGraphScene(Scene):
def construct(self):
left_x = -4.7
right_x = -1.5
ys = [1.5, 0.0, -1.5]
def disc_at(x, y, color):
disc = Circle(radius=0.27, color=WHITE, stroke_width=2)
disc.set_fill(color, opacity=0.92)
disc.move_to([x, y, 0])
return disc
left_discs = VGroup()
left_nums = VGroup()
right_discs = VGroup()
right_nums = VGroup()
for idx, y in enumerate(ys):
left_discs.add(disc_at(left_x, y, BLUE))
left_nums.add(Text(str(idx + 1), font_size=20, color=WHITE).move_to([left_x, y, 0]))
right_discs.add(disc_at(right_x, y, YELLOW))
right_nums.add(Text(str(idx + 4), font_size=20, color=WHITE).move_to([right_x, y, 0]))
links = [
(0, 0),
(0, 1),
(1, 1),
(1, 2),
(2, 0),
(2, 2),
]
edges = VGroup()
for a, b in links:
edges.add(
Line(
[left_x, ys[a], 0],
[right_x, ys[b], 0],
color=GRAY_B,
stroke_width=3,
)
)
# SurroundingRectangle 会「吃掉」被量的那组（之后不再渲染）——必须量副本
left_box = SurroundingRectangle(left_discs.copy())
left_box.set_color(BLUE)
left_box.set_stroke(width=2)
right_box = SurroundingRectangle(right_discs.copy())
right_box.set_color(YELLOW)
right_box.set_stroke(width=2)
side_labels = VGroup(
Text("一组 U", font_size=24, color=BLUE).move_to([left_x, 2.45, 0]),
Text("另一组 V", font_size=24, color=YELLOW).move_to([right_x, 2.45, 0]),
)
ok_note = Text("同组内部没有边 → 是二分图", font_size=24, color=GREEN).move_to([-3.1, -2.5, 0])
tri_center = [3.5, 0.3]
tri_radius = 1.25
tri_points = []
for i in range(3):
ang = math.pi / 2 + i * 2 * math.pi / 3
tri_points.append(
[tri_center[0] + tri_radius * math.cos(ang), tri_center[1] + tri_radius * math.sin(ang), 0]
)
tri_edges = VGroup(
*[Line(tri_points[i], tri_points[(i + 1) % 3], color=RED, stroke_width=3) for i in range(3)]
)
tri_dots = VGroup(*[Dot(p, radius=0.14, color=WHITE) for p in tri_points])
tri_note = Text("奇环（三角形）→ 不是二分图", font_size=24, color=RED).move_to([3.5, -2.5, 0])
head = Text("二分图：顶点分两组，边只跨组", font_size=27, color=YELLOW).move_to([0, 3.2, 0])
caption = Text("二分图 ⇔ 不含奇环：找到奇环就能立刻否决", font_size=24, color=GRAY_A)
caption.move_to([0, -3.3, 0])
self.play(Write(head), run_time=0.6)
self.play(Create(edges), run_time=0.9)
self.play(LaggedStart(*[FadeIn(d) for d in left_discs], lag_ratio=0.15), run_time=0.9)
self.play(LaggedStart(*[FadeIn(d) for d in right_discs], lag_ratio=0.15), run_time=0.9)
self.play(Write(left_nums), Write(right_nums), run_time=0.7)
self.play(Create(left_box), Create(right_box), Write(side_labels), run_time=0.8)
self.play(Write(ok_note), run_time=0.6)
self.play(Create(tri_edges), FadeIn(tri_dots), run_time=0.9)
self.play(Write(tri_note), run_time=0.6)
self.play(Write(caption), run_time=0.7)
self.wait(0.4)图着色：相邻顶点不能同色，最少要几种
左边 5 个顶点连成一个奇数环，只用红蓝两色会在闭合处撞色，于是必须动用第三种颜色（绿）；右边 4 个顶点两两相连，无论怎么排都得用满四种颜色。
py
"""图着色：相邻顶点不能同色，最少要几种
@expect 左边 5 个顶点连成一个奇数环，只用红蓝两色会在闭合处撞色，于是必须动用第三种颜色（绿）；右边 4 个顶点两两相连，无论怎么排都得用满四种颜色。
@note 讲解要点：色数 χ(G) 是「最少几种颜色」。奇数环 χ=3、偶数环 χ=2——差一个顶点就差一种颜色。两两相邻的完全图 Kn 必须 n 色，这是下界；四色定理则保证平面图 4 色永远够用。
"""
from manim import *
import math
class GraphColoringScene(Scene):
def construct(self):
# 左：5 环（奇环）——两色不够，需要 3 色
c5_center = [-3.8, 0.1]
c5_radius = 1.7
c5_points = []
for i in range(5):
ang = math.pi / 2 + i * 2 * math.pi / 5
c5_points.append([c5_center[0] + c5_radius * math.cos(ang), c5_center[1] + c5_radius * math.sin(ang), 0])
c5_colors = [RED, BLUE, RED, BLUE, GREEN]
c5_edges = VGroup(
*[
Line(c5_points[i], c5_points[(i + 1) % 5], color=GRAY_B, stroke_width=3)
for i in range(5)
]
)
c5_vertices = VGroup()
for point, color in zip(c5_points, c5_colors):
disc = Circle(radius=0.3, color=WHITE, stroke_width=2)
disc.set_fill(color, opacity=0.9)
disc.move_to(point)
c5_vertices.add(disc)
c5_note = Text("C5：奇环 → 至少 3 色", font_size=24, color=GREEN).move_to([-3.8, -2.35, 0])
# 右：K4——两两相邻，必须 4 色
k4_center = [3.5, 0.1]
k4_points = [[k4_center[0], k4_center[1], 0]]
for i in range(3):
ang = math.pi / 2 + i * 2 * math.pi / 3
k4_points.append(
[k4_center[0] + 1.5 * math.cos(ang), k4_center[1] + 1.5 * math.sin(ang), 0]
)
k4_colors = [YELLOW, RED, BLUE, GREEN]
k4_edges = VGroup()
for i in range(4):
for j in range(i + 1, 4):
k4_edges.add(Line(k4_points[i], k4_points[j], color=GRAY_B, stroke_width=3))
k4_vertices = VGroup()
for point, color in zip(k4_points, k4_colors):
disc = Circle(radius=0.3, color=WHITE, stroke_width=2)
disc.set_fill(color, opacity=0.9)
disc.move_to(point)
k4_vertices.add(disc)
k4_note = Text("K4：两两相邻 → 必须 4 色", font_size=24, color=YELLOW).move_to([3.5, -2.35, 0])
head = Text("图着色：相邻顶点不能同色，最少要几种", font_size=27, color=YELLOW).move_to([0, 3.2, 0])
caption = Text("χ(C5) = 3，χ(K4) = 4；四色定理保证平面图 χ ≤ 4", font_size=24, color=GRAY_A)
caption.move_to([0, -3.25, 0])
self.play(Write(head), run_time=0.6)
self.play(Create(c5_edges), Create(k4_edges), run_time=1.0)
self.play(LaggedStart(*[FadeIn(v) for v in c5_vertices], lag_ratio=0.18), run_time=1.2)
self.play(Write(c5_note), run_time=0.6)
self.play(LaggedStart(*[FadeIn(v) for v in k4_vertices], lag_ratio=0.18), run_time=1.2)
self.play(Write(k4_note), run_time=0.6)
self.play(Write(caption), run_time=0.7)
self.wait(0.4)最小生成树：按权重从小到大加边，成环的边就丢掉
六个顶点上先淡淡铺开全部 8 条带权边；随后按权重 1→8 依次判定——能被采纳的边亮成绿色（共 5 条，刚好把 6 个点连成一棵），会成环的边被判红并画成虚线。最终 5 条绿边总权重 19。
py
"""最小生成树：按权重从小到大加边，成环的边就丢掉
@expect 六个顶点上先淡淡铺开全部 8 条带权边；随后按权重 1→8 依次判定——能被采纳的边亮成绿色（共 5 条，刚好把 6 个点连成一棵），会成环的边被判红并画成虚线。最终 5 条绿边总权重 19。
@note 讲解要点：Kruskal 的核心只有一句——「只要不成环就加」。n 个顶点的生成树恰好 n-1 条边，所以加够 5 条就停。贪心之所以最优，是因为最轻的那条边必定属于某棵最小生成树（割性质）。
"""
from manim import *
class SpanningTreeScene(Scene):
def construct(self):
coords = {
1: [-4.8, 0.5],
2: [-3.0, 1.9],
3: [-3.0, -0.8],
4: [-0.9, 1.3],
5: [-0.9, -1.0],
6: [1.0, 0.2],
}
# (端点, 端点, 权重, 是否被采纳)
specs = [
(1, 2, 1, True),
(1, 3, 2, True),
(2, 3, 3, False),
(2, 4, 4, True),
(3, 5, 5, True),
(4, 5, 6, False),
(4, 6, 7, True),
(5, 6, 8, False),
]
def point(v):
return [coords[v][0], coords[v][1], 0]
ghost_edges = VGroup(
*[Line(point(a), point(b), color=GRAY_D, stroke_width=2) for a, b, _, _ in specs]
)
background = VGroup()
for v, (x, y) in coords.items():
disc = Circle(radius=0.26, color=BLUE)
disc.set_fill(BLUE, opacity=0.8)
disc.move_to([x, y, 0])
background.add(disc)
background.add(Text(str(v), font_size=22, color=WHITE).move_to([x, y, 0]))
weight_labels = VGroup()
for a, b, w, _ in specs:
mid = [(coords[a][0] + coords[b][0]) / 2, (coords[a][1] + coords[b][1]) / 2, 0]
weight_labels.add(Text(str(w), font_size=20, color=GRAY_A).move_to([mid[0], mid[1] + 0.22, 0]))
accepted = VGroup()
rejected = VGroup()
step_notes = VGroup()
for idx, (a, b, w, ok) in enumerate(specs):
if ok:
accepted.add(Line(point(a), point(b), color=GREEN, stroke_width=4))
else:
rejected.add(DashedLine(point(a), point(b), color=RED, stroke_width=3))
step_notes.add(
Text(
f"{w}：{a}-{b} " + ("采纳" if ok else "成环，丢弃"),
font_size=22,
color=GREEN if ok else RED,
).move_to([4.7, 2.2 - idx * 0.52, 0])
)
head = Text("最小生成树 = n−1 条边 · 总权重 1+2+4+5+7 = 19", font_size=25, color=GREEN)
head.move_to([0, 3.1, 0])
caption = Text("Kruskal：按权重升序扫，不成环就加；加满 n−1 条即停", font_size=24, color=GRAY_A)
caption.move_to([0, -3.2, 0])
self.play(Write(head), run_time=0.6)
self.play(Create(ghost_edges), FadeIn(background), Write(weight_labels), run_time=1.0)
self.play(LaggedStart(*[Create(e) for e in accepted], lag_ratio=0.35), run_time=2.0)
self.play(LaggedStart(*[Create(e) for e in rejected], lag_ratio=0.3), run_time=1.0)
self.play(Write(step_notes), run_time=1.2)
self.play(Write(caption), run_time=0.7)
self.wait(0.4)欧拉回路与哈密顿回路：一个数「边」，一个数「点」
左边是共用一个顶点的两个三角形：中心顶点度数为 4、其余都是 2，全为偶数，所以能一笔走遍每条边恰好一次（欧拉回路）；但走遍每个顶点恰好一次做不到。右边是带一条斜线的四边形：沿外圈可以走遍四个顶点（哈密顿回路），但有两个度为 3 的顶点，欧拉回路不存在。
py
"""欧拉回路与哈密顿回路：一个数「边」，一个数「点」
@expect 左边是共用一个顶点的两个三角形：中心顶点度数为 4、其余都是 2，全为偶数，所以能一笔走遍每条边恰好一次（欧拉回路）；但走遍每个顶点恰好一次做不到。右边是带一条斜线的四边形：沿外圈可以走遍四个顶点（哈密顿回路），但有两个度为 3 的顶点，欧拉回路不存在。
@note 讲解要点：欧拉回路只看度数——连通且全是偶度就存在（一笔画问题）；哈密顿回路要看整体结构，至今没有简单的充要条件（属于 NP-完全）。同样是一笔画，问法差一个字，难度天差地别。
"""
from manim import *
class EulerHamiltonScene(Scene):
def construct(self):
# 左：蝴蝶结——有欧拉回路，无哈密顿回路
center = [-3.7, -0.3]
s = [center[0], center[1], 0]
l1 = [center[0] - 1.35, center[1] + 1.0, 0]
l2 = [center[0] - 1.35, center[1] - 1.0, 0]
r1 = [center[0] + 1.35, center[1] + 1.0, 0]
r2 = [center[0] + 1.35, center[1] - 1.0, 0]
left_edges = VGroup(
Line(s, l1, color=GRAY_B, stroke_width=3),
Line(s, l2, color=GRAY_B, stroke_width=3),
Line(l1, l2, color=GRAY_B, stroke_width=3),
Line(s, r1, color=GRAY_B, stroke_width=3),
Line(s, r2, color=GRAY_B, stroke_width=3),
Line(r1, r2, color=GRAY_B, stroke_width=3),
)
left_nodes = VGroup(
Dot(s, radius=0.16, color=YELLOW),
Dot(l1, radius=0.14, color=WHITE),
Dot(l2, radius=0.14, color=WHITE),
Dot(r1, radius=0.14, color=WHITE),
Dot(r2, radius=0.14, color=WHITE),
)
left_degree = Text("中心顶点度数 4，其余全为 2 —— 全偶", font_size=23, color=GREEN)
left_degree.move_to([-3.7, -2.0, 0])
left_yes = Text("有欧拉回路：一笔走遍每条边各一次", font_size=23, color=GREEN)
left_yes.move_to([-3.7, -2.6, 0])
left_no = Text("无哈密顿回路：过中心顶点只能一次，跨不过两半", font_size=23, color=RED)
left_no.move_to([-3.7, -3.2, 0])
# 右：四边形加斜线——有哈密顿回路，无欧拉回路
a = [2.2, 0.9, 0]
b = [4.6, 0.9, 0]
c = [4.6, -1.5, 0]
d = [2.2, -1.5, 0]
right_edges = VGroup(
Line(a, b, color=GRAY_B, stroke_width=3),
Line(b, c, color=GRAY_B, stroke_width=3),
Line(c, d, color=GRAY_B, stroke_width=3),
Line(d, a, color=GRAY_B, stroke_width=3),
Line(a, c, color=GRAY_B, stroke_width=3),
)
right_nodes = VGroup(
Dot(a, radius=0.14, color=RED),
Dot(b, radius=0.14, color=WHITE),
Dot(c, radius=0.14, color=RED),
Dot(d, radius=0.14, color=WHITE),
)
right_yes = Text("有哈密顿回路：沿外圈走遍四个顶点", font_size=23, color=GREEN)
right_yes.move_to([3.4, -2.0, 0])
right_no = Text("无欧拉回路：两个红点度数为 3（奇）", font_size=23, color=RED)
right_no.move_to([3.4, -2.6, 0])
right_extra = Text("欧拉看度数，哈密顿看结构", font_size=23, color=GRAY_A)
right_extra.move_to([3.4, -3.2, 0])
head = Text("同样是「一笔画」，问法差一个字，难度差一个量级", font_size=26, color=YELLOW)
head.move_to([0, 3.2, 0])
self.play(Write(head), run_time=0.7)
self.play(Create(left_edges), FadeIn(left_nodes), run_time=1.0)
self.play(Write(left_degree), run_time=0.6)
self.play(Write(left_yes), Write(left_no), run_time=0.8)
self.play(Create(right_edges), FadeIn(right_nodes), run_time=1.0)
self.play(Write(right_yes), Write(right_no), run_time=0.8)
self.play(Write(right_extra), run_time=0.6)
self.wait(0.4)汉诺塔的递推：T(n) = 2T(n−1) + 1，所以是 2ⁿ − 1
左下画着三根柱子，最左边那根垒着从小到大的三个盘子；右边的柱状图给出 n=1 到 8 的步数。柱子高度是按 log₂(T+1) 等比缩放的，所以画面上的高度恰好等距上升——一条完美的直线，代表的是货真价实的指数增长。
py
"""汉诺塔的递推：T(n) = 2T(n−1) + 1，所以是 2ⁿ − 1
@expect 左下画着三根柱子，最左边那根垒着从小到大的三个盘子；右边的柱状图给出 n=1 到 8 的步数。柱子高度是按 log₂(T+1) 等比缩放的，所以画面上的高度恰好等距上升——一条完美的直线，代表的是货真价实的指数增长。
@note 讲解要点：把上面 n−1 个盘子搬走要 T(n−1) 步，搬最大的那个 1 步，再把 n−1 个搬回来又 T(n−1) 步，于是 T(n) = 2T(n−1)+1，展开就是 2ⁿ−1。64 个盘子的经典题目需要 1.8×10¹⁹ 步——按每秒一步要五百多亿年。
"""
from manim import *
class HanoiRecurrenceScene(Scene):
def construct(self):
# 左下：三根柱子与三个盘子
base = Line([-6.6, -2.5, 0], [-1.4, -2.5, 0], color=GRAY_B, stroke_width=4)
pegs = VGroup()
peg_names = VGroup()
for idx, x in enumerate([-5.9, -4.2, -2.5]):
pegs.add(Line([x, -2.5, 0], [x, -0.5, 0], color=GRAY_B, stroke_width=3))
peg_names.add(Text(["A", "B", "C"][idx], font_size=22, color=GRAY_A).move_to([x, -2.85, 0]))
widths = [2.2, 1.6, 1.0]
colors = [BLUE, GREEN, RED]
disks = VGroup()
for idx, (w, color) in enumerate(zip(widths, colors)):
disk = Rectangle(width=w, height=0.42, color=WHITE)
disk.set_fill(color, opacity=0.85)
disk.move_to([-5.9, -2.29 + idx * 0.46, 0])
disks.add(disk)
peg_note = Text("n 个盘子：2ⁿ − 1 步", font_size=23, color=YELLOW).move_to([-4.0, 0.0, 0])
# 右侧：按 log2 缩放的柱状图
ns = list(range(1, 9))
moves = [2 ** n - 1 for n in ns]
base_y = -2.4
max_h = 4.3
peak = float(max(ns))
bars = VGroup()
tops = VGroup()
bottoms = VGroup()
for idx, (n, mv) in enumerate(zip(ns, moves)):
x = -0.3 + idx * 0.95
height = n / peak * max_h
bar = Rectangle(width=0.62, height=height, color=BLUE)
bar.set_fill(BLUE, opacity=0.75)
bar.move_to([x, base_y + height / 2, 0])
bars.add(bar)
tops.add(Text(str(mv), font_size=17, color=YELLOW).move_to([x, base_y + height + 0.3, 0]))
bottoms.add(Text(f"n={n}", font_size=15, color=GREEN).move_to([x, base_y - 0.34, 0]))
bar_axis = Line([-0.9, base_y, 0], [6.9, base_y, 0], color=GRAY_B, stroke_width=3)
log_note = Text("高度按 log₂(T+1) 画 → 看起来是直线", font_size=22, color=GRAY_A)
log_note.move_to([3.0, 2.6, 0])
formula = MathTex(r"T(n) = 2\,T(n-1) + 1 \;\Longrightarrow\; T(n) = 2^n - 1", font_size=40)
formula.move_to([0, 3.3, 0])
caption = Text("指数增长的「直线」——因为它本来就画在对数尺上", font_size=23, color=GRAY_A)
caption.move_to([0, -3.3, 0])
self.play(Write(formula), run_time=0.9)
self.play(Create(base), Create(pegs), Write(peg_names), run_time=0.8)
self.play(LaggedStart(*[FadeIn(d) for d in disks], lag_ratio=0.25), run_time=1.0)
self.play(Write(peg_note), run_time=0.6)
self.play(Create(bar_axis), Write(log_note), run_time=0.7)
self.play(LaggedStart(*[FadeIn(b) for b in bars], lag_ratio=0.12), run_time=1.6)
self.play(Write(bottoms), run_time=0.5)
self.play(Write(tops), run_time=0.8)
self.play(Write(caption), run_time=0.7)
self.wait(0.4)