Discrete mathematics
Truth tables, power-set lattices, relation matrices, equivalence classes, Hasse diagrams, induction, pigeonhole, bipartite graphs, colouring, minimum spanning trees, Euler and Hamilton cycles, and the Hanoi recurrence.
This page lists 12 examples. The code is imported from corpus/examples/math-discrete/; the screenshots are end states rendered on real machines.
Truth table: p → q and ¬p ∨ q equivalent row by row
A five-column table with all values of p, q, ¬p, p→q and ¬p∨q filled in; the last two columns are circled together in green — identical cell by cell across all four rows, labelled equivalent on the right.
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)Power-set lattice: the 8 subsets of {1,2,3} as a cube
Eight nodes in four layers by subset size: ∅ on top, three each in the two middle layers, {1,2,3} at the bottom; edges only between nodes differing by one element. The whole shape is a planar projection of a 3-cube.
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)Relation matrix: reading reflexivity and symmetry off a matrix
A 4×4 grid of ordered pairs on {1,2,3,4}, filled cells meaning the relation holds. A green box circles the main diagonal (reflexive) and a yellow box a pair mirrored across it (symmetric) — the pattern is unchanged when flipped.
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)Equivalence classes: congruence mod 3 cuts 0–8 into three piles
The nine digits 0–8 in a line on top; below they are rearranged into three rows of three — each congruent triple grouped and circled in green, the three groups disjoint and together covering all nine digits.
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)Hasse diagram: only cover relations; incomparable elements at a glance
{1,2,3,6} ordered by divisibility into a diamond — 1 at the bottom, 6 at the top, 2 and 3 side by side in the middle; no edge between 2 and 3, labelled incomparable. The transitive relation from 1 to 6 is also left undrawn.
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)The classic picture of induction: two staircases making one rectangle
The blue staircase on the left has column heights 1, 2, 3, 4 and the yellow one on the right 4, 3, 2, 1; interleaved they exactly fill a rectangle 4 wide and 5 high — so the staircase's total cell count is half of 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)Pigeonhole principle: 13 pigeons into 12 holes
Twelve holes each take one pigeon first, leaving one with nowhere to go; when it lands in the first hole a red circle marks it — the holes are used up, so some hole must hold two.
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)Bipartite graphs: vertices split in two, edges only across
Six vertices in a blue and a yellow column on the left with all six edges crossing from blue to yellow and none inside a column; a triangle on the right as the counterexample — an odd cycle of three edges head to tail.
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)Graph colouring: adjacent vertices differ; how few colours suffice
On the left a 5-cycle where red and blue alone collide at the closure, forcing a third colour (green); on the right four mutually adjacent vertices that need all four colours however arranged.
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)Minimum spanning tree: add edges by weight, drop those that close a cycle
All 8 weighted edges first laid faintly over six vertices, then judged in weight order 1→8 — adopted edges light up green (5 of them, exactly connecting the 6 points into a tree), cycle-forming edges turn red and dashed. The 5 green edges total weight 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)Euler vs Hamilton cycles: one counts edges, the other counts vertices
On the left two triangles sharing a vertex: the centre vertex has degree 4 and the rest 2, all even, so every edge can be traversed exactly once in one stroke (Euler cycle), but visiting every vertex exactly once is impossible. On the right a quadrilateral with one diagonal: the outer ring visits all four vertices (Hamilton cycle), but two vertices have degree 3, so no Euler cycle exists.
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)The Hanoi recurrence: T(n) = 2T(n−1) + 1, hence 2ⁿ − 1
Three pegs at the bottom left with three discs stacked small-to-large on the first; the bar chart on the right gives the move counts for n=1 to 8. Bar heights scale by log₂(T+1), so the picture rises in perfectly even steps — a straight line standing for genuine exponential growth.
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)