Topology in Interviews

Topology is not abstraction for its own sake. Every graph connectivity algorithm computes β₀, every planarity test uses χ, every DNA-topology analysis uses knot theory.

• LeetCode Number of Islands and Number of Provinces are β₀ computations under the hood
• PCB and VLSI routing decisions reduce to planarity and minimum-genus tests
• DNA recombination and protein-knot detection rely on Fox colorings and knot polynomials
• Course Schedule and build-graph cycle detection are H₁ tests on directed complexes

Connectivity: Topological Interpretation

"Is the graph connected?" asks for β₀. "Find all connected components" computes H₀. "Does a cycle exist?" probes β₁. Topology gives a unified vocabulary for dozens of graph problems that look unrelated on the surface. Recognizing this under interview pressure separates strong candidates from the rest.

Topological facts about a graph G = (V, E): β₀(G) = number of connected components; β₁(G) = |E| − |V| + β₀ = cyclomatic number (number of independent cycles); χ(G) = |V| − |E| = β₀ − β₁. Union-Find (DSU) computes β₀ in O(α(n)) per operation - essentially constant time.

Interview pattern: hear "connectivity" or "components" → reach for DSU. Hear "cycle in undirected graph" → DSU with extra_edges count. Hear "cycle in directed graph" → topological sort (Kahn's BFS). The answer frames as: β₀ = components, β₁ = independent cycles.

Jordan Curve Theorem and Planar Graphs

The Jordan curve theorem seems simple: a simple closed curve in the plane divides it into exactly two regions. Yet its proof is non-trivial, requiring fundamental groups and homology. In software engineering it underlies the point-in-polygon algorithm and planar graph testing used in routing, map rendering, and VLSI layout.

Algorithmic consequences: 1. Point-in-polygon - count ray-edge crossings; odd count means inside. 2. Planar graphs satisfy Euler's formula V − E + F = 2. 3. K₅ and K₃,₃ are non-planar (Kuratowski's theorem). Non-planarity implies minimum genus ≥ 1 - the graph requires a torus to embed without crossings.

At an interview: "Whether this graph admits a drawing without edge crossings" is a planarity question. Quick test: E > 3V − 6 (or E > 2V − 4 for bipartite graphs) implies non-planar. Full O(V) testing uses the Hopcroft-Tarjan algorithm. Frame it: planarity = embeddable on S² without crossings.

The four-color theorem states every planar graph is 4-colorable. This is a theorem about S² topology. On a torus, up to 7 colors may be needed: the chromatic number bound is χ(g) = ⌊(7 + √(1+48g))/2⌋ (Heawood's formula). For g=1 (torus): χ = 7.

Knot Theory and Bioinformatics

DNA inside a cell nucleus is supercoiled and knotted. Topoisomerase - an enzyme that cuts one DNA strand, passes another through, then re-ligates - literally changes the knot type. Understanding this requires knot theory. In CS, knot invariants appear in program verification, memory model analysis, and network topology proofs.

A knot is an embedding of S¹ into S³. Two knots are equivalent (ambient isotopic) if one deforms into the other without cutting. Knot invariants distinguish non-equivalent knots: Alexander polynomial Δ(t), Jones polynomial V(t), and Fox n-colorability. The unknot (trivial knot) has Δ(t) = 1 and admits only 3 colorings mod 3.

Connections to biology: 1. DNA replication requires unwinding the double helix - topoisomerase I changes the linking number 2. site-specific recombination is knot surgery 3. about 1% of proteins contain genuine knots in their backbone - AlphaFold structures are analyzed for these. The topology of the DNA configuration space determines which enzymes can unknot which configurations.

Fox 3-coloring count > 3 proves a knot is non-trivial, but the converse fails. The figure-eight knot has only 3 colorings (same as the unknot), yet it is genuinely knotted. Stronger invariants - Alexander or Jones polynomials - are needed when 3-coloring gives inconclusive results.

Euler Characteristic and Genus Under Pressure

"On which surface can K₅ be drawn without crossings?" - a genuine FAANG graph embedding question. The answer is the torus (genus 1), derived from the Euler characteristic formula χ = 2 − 2g and edge-count inequalities. Such questions probe depth of understanding rather than memorized algorithms.

For a graph G embedded on an orientable surface of genus g without crossing edges: V − E + F = χ = 2 − 2g. With triangular faces: 2E ≥ 3F, giving E ≤ 3(V + 2g − 2). For bipartite graphs (no triangles): E ≤ 2(V + 2g − 2). The minimum genus for which G embeds is called genus(G).

Interview cheat sheet: 1. E > 3V−6 → non-planar 2. genus(Kₙ) = ⌈(n−3)(n−4)/12⌉ 3. torus admits 7-colorings (Heawood bound) 4. treewidth(G) ≤ 3·genus(G)·Δ+1 - this connects topology to dynamic programming efficiency.

What this lesson unifies

• β₀ and β₁ provide a unified language for connectivity and cycle problems
• The Jordan curve theorem underlies point-in-polygon and planarity tests
• Fox 3-coloring distinguishes many non-trivial knots from the unknot but is incomplete
• Graph genus determines minimum VLSI layers and bounds treewidth-based DP complexity

How the full course assembles here

The final lesson assembles the course: compactness → metric spaces → fundamental group → covering spaces → homology → surface classification → Euler characteristic → manifolds → de Rham cohomology → TDA → ML applications, all appearing in concrete interview problems.

• Topology in ML and Data Science — previous lesson, supplies the Riemannian and TDA tools that resurface here
• Surface classification and Euler characteristic — supplies χ = 2 − 2g used for the genus inequalities
• Homology and Betti numbers — gives β₀ and β₁ that name the connectivity and cycle questions

Вопросы для размышления

• Which interview problem now reads differently through the lens of β₀ or β₁?
• Number of Islands is β₀, Redundant Connection detects β₁ ≥ 1, Course Schedule is cycle detection in a digraph - which production graph problems sit in the same family?
• Where would the genus inequality E ≤ 3(V + 2g − 2) help estimate VLSI layer count or treewidth bounds?

Связанные уроки

• fa-01