# Untitled

unknown
plain_text
2 years ago
3.9 kB
1
Indexable
Never
class OnePointSeven(Scene):
def construct(self):
# Part 1
s1 = Tex(r"Show that $\Delta({v}) = 0$ for a single vertex $v \notin {s, t}$", font_size=tex_font_size).to_edge(LEFT).to_edge(UP)
s2 = Tex(r"$\Delta({v}) = \phi_{out}({v}) - \phi_{in}({v})$", font_size=tex_font_size).next_to(s1, DOWN).to_edge(LEFT)
s3 = Tex(r"$= \Sigma_{u \in {v}} \Sigma_{w \in V \textbackslash {v}}f_{uw} - \Sigma_{u \in V \textbackslash {v}} \Sigma{w \in {v}}f_{uw}$", font_size=tex_font_size).next_to(s2, DOWN).to_edge(LEFT)
s4 = Tex(r"$= \Sigma_{w \in V \textbackslash {v}}f_{vw} - \Sigma_{u \in V \textbackslash {v}}f_{uv}$", font_size=tex_font_size).next_to(s3, DOWN).to_edge(LEFT)
s5 = Tex(r"$= \Sigma_{w \in V}f_{vw} - \Sigma_{u \in V}f_{uv}$", font_size=tex_font_size).next_to(s4, DOWN).to_edge(LEFT)
s6 = Tex(r"Therefore $\Delta({v}) = 0$", font_size=tex_font_size).next_to(s5, DOWN).to_edge(LEFT)

# Part 2
s7 = Tex(r"Let $W \subset V$ and $y \in V \textbackslash W$", font_size=tex_font_size).next_to(s6, DOWN, LARGE_BUFF).to_edge(LEFT)
s7_ = Tex(r"Show that $\Delta_{W \cup {y}} = \Delta(W) + \Sigma_{v \in V}f_{yv} - \Sigma_{u \in V}f_{uy}$", font_size=tex_font_size).next_to(s7, DOWN).to_edge(LEFT)
s8 = Tex(r"$\Delta_{W \cup {y}} = \phi_{out}(W \cup {y}) - \phi_{in}(W \cup {y})$", font_size=tex_font_size).next_to(s7_, DOWN).to_edge(LEFT)
s9 = Tex(r"$= (\phi_out(W) + \Sigma_{v \in V \textbackslash W}f_{yv} - \Sigma_{u \in W}f_{uy}) - (\phi_{in}(W) + \Sigma_{u \in V \textbackslash W}f_{uy} - \Sigma_{v \in W}f_{yv})$", font_size=tex_font_size).next_to(s8, DOWN).to_edge(LEFT)
s10 = Tex(r"$= (\phi_{out}(W) - \phi_{in}(W)) + (\Sigma_{v \in V \textbackslash W}f_{yv} + \Sigma_{v \in W}f_{yv}) - (\Sigma_{u \in V \textbackslash W}f_{uy} + \Sigma_{u \in W}f_{uy})$", font_size=tex_font_size).next_to(s9, DOWN).to_edge(LEFT)
s11 = Tex(r"$= \Delta(W) + \Sigma_{v \in V}f_{yv} - \Sigma_{u \in V}f_{uy}$", font_size=tex_font_size).next_to(s10, DOWN).to_edge(LEFT)

# Part 3, induction to prove that Delta(W) = 0 if s, t \notin W
s12 = Tex(r"Proving by induction that $\Delta(W) = 0$, given that $s, t \notin W$", font_size=tex_font_size).to_edge(RIGHT).to_edge(UP)
s13 = Tex(r"Let n be the number of vertices in W", font_size=tex_font_size).next_to(s12, DOWN).to_edge(RIGHT)
s14 = Tex(r"Base case, $n=1$:", font_size=tex_font_size).next_to(s13, DOWN).to_edge(RIGHT)
s15 = Tex(r"$\Delta(W) = \Delta({v}) = 0$ from part i)", font_size=tex_font_size).next_to(s14, DOWN).to_edge(RIGHT)
s16 = Tex(r"Inductive step, adding a vertex y where $y \notin {s, t}$", font_size=tex_font_size).next_to(s15, DOWN).to_edge(RIGHT)
s17 = Tex(r"$\Delta(W \cup {y}) = \Delta(W) + \Sigma_{v \in V}f_{yv} - \Sigma_{u \in V}f_{uy}$", font_size=tex_font_size).next_to(s16, DOWN).to_edge(RIGHT)
s18 = Tex(r"$\Delta(W \cup {y}) = \Delta(W) + 0$", font_size=tex_font_size).next_to(s17, DOWN).to_edge(RIGHT)

# Conclusion
s19 = Tex(r"Thus adding a vertex $y \notin {s, t}$ to W doesn't increase $\Delta(W)$.", font_size=tex_font_size).next_to(s18, DOWN).to_edge(RIGHT)
s20 = Tex(r"Thus $\Delta(W) = 0$.", font_size=tex_font_size).next_to(s19, DOWN).to_edge(RIGHT)

animations = [
Write(s1),
Write(s2),
Write(s3),
Write(s4),
Write(s5),
Write(s6),
Write(s7),
Write(s7_),
Write(s8),
Write(s9),
Write(s10),
Write(s11),
Write(s12),
Write(s13),
Write(s14),
Write(s15),
Write(s16),
Write(s17),
Write(s18),
Write(s19),
Write(s20)
]

self.play(AnimationGroup(*animations, lag_ratio=2))