graph theory

Graph theory studies systems by separating the things that exist from the relationships that connect them. A graph can represent nets joined by components, process steps constrained by precedence, layout features that conflict on one mask, wafers moving through tools, or failures propagating through dependencies. The abstraction is powerful because the same definitions support proofs, algorithms, and engineering decisions, but a useful model must still state exactly what vertices, edges, directions, weights, multiplicities, and time mean. ```svg ``` **A graph is defined by its vertices and edges, not by its drawing.** A simple undirected graph is an ordered pair $G=(V,E)$ in which each edge is a two-element subset of the vertex set. A directed graph instead uses ordered pairs, while a multigraph can retain parallel edges and a pseudograph can permit loops. Coordinates in a picture are metadata unless geometry is explicitly part of the model. Redrawing a graph without changing incidence preserves the graph, whereas adding an apparently harmless crossing does not create a vertex unless the model declares one. This distinction prevents layout sketches from silently changing connectivity. **The modeling contract should precede every algorithm.** Identify the entity represented by each vertex, the relation represented by each edge, whether an absent edge means false or merely unknown, and whether direction, weight, capacity, sign, label, or timestamp is essential. A circuit netlist, a timing graph, a wafer genealogy graph, and a road network can share the same topology while requiring incompatible semantics. State whether parallel physical routes are aggregated and whether self-dependence becomes a loop. Many incorrect graph analyses are correct computations on the wrong abstraction. **Degree is a local count with global consequences.** In an undirected graph the degree $deg(v)$ counts incident edge ends, with a loop contributing twice, and the handshaking identity $sum_{v\in V}\deg(v)=2|E|$ follows by counting every edge end. Therefore the number of odd-degree vertices is even. Directed graphs separate indegree and outdegree, with both totals equal to $|E|$. Weighted degree or strength sums weights rather than incidences. Degree can flag fanout, congestion, vulnerability, or workload, but high degree alone does not imply global importance. **Walks, trails, paths, and cycles encode different reuse rules.** A walk may repeat vertices and edges; a trail repeats no edge; a simple path repeats no vertex; and a cycle returns to its starting vertex without repeating internal vertices. These distinctions matter when a manufacturing route may revisit tools, a packet must avoid links already used, or a proof requires vertex-simple alternatives. Path length usually counts edges in an unweighted graph and sums costs in a weighted graph. Zero-length paths make each vertex reachable from itself and simplify connectivity definitions. **Subgraphs expose structure without changing the universe of discourse.** A subgraph selects subsets of vertices and edges, while an induced subgraph on $S\subseteq V$ contains every original edge with both endpoints in $S$. A spanning subgraph retains every vertex. Deleting vertices and deleting edges answer different failure questions. Graph minors additionally allow edge contraction, capturing whether a coarse connectivity pattern survives simplification. Confusing an arbitrary subgraph with an induced one can invalidate claims about cliques, coloring, chordality, and forbidden configurations. **Isomorphism separates names from structure.** Graphs $G$ and $H$ are isomorphic when a bijection between their vertex sets preserves adjacency. Degree sequences, component sizes, cycle counts, and spectra can disprove isomorphism but are not generally complete invariants. Canonical labeling seeks a representation independent of input names; automorphisms reveal symmetries within one graph. In layout, chemistry, and netlist comparison, labels and attributes may need preservation in addition to adjacency. Hash equality is only evidence when the hashing scheme is known to be canonical for the relevant graph class. **Sparse representations usually match real engineering graphs.** An adjacency matrix uses $O(|V|^2)$ storage and gives constant-time edge queries, while adjacency lists use $O(|V|+|E|)$ space and enumerate neighbors efficiently. An incidence matrix records vertex-edge participation and naturally represents flows, circuits, and hypergraph extensions. Compressed sparse row formats improve locality for static graphs but make insertion expensive. The representation must preserve edge identity when parallel edges, capacities, provenance, or timestamps matter. Complexity claims should include both the abstract operation count and memory traffic. **Graph traversal turns local adjacency into global knowledge.** Breadth-first search explores an unweighted graph in nondecreasing hop distance using a queue, while depth-first search follows a branch using recursion or an explicit stack. Both run in $O(|V|+|E|)$ time with adjacency lists. The resulting parent edges form a search forest, not a unique property of the graph, because neighbor order changes it. BFS establishes shortest hop distances; DFS exposes discovery and finishing relationships useful for cycles, articulation structure, and topological reasoning. **Breadth-first search proves more than reachability.** When BFS first discovers a vertex, its level is the minimum number of edges from the source. Every undirected edge joins vertices whose levels differ by at most one. The layer structure supports bipartite testing, eccentricity estimates, routing, and wavefront simulations. Multi-source BFS begins with several zero-distance sources and finds the nearest source regions. A queue implementation that marks vertices only when removed can enqueue duplicates and destroy the linear bound; marking on insertion preserves the invariant. **Depth-first search supplies a structural clock.** Discovery and finishing times nest for ancestor-descendant pairs, enabling edge classification in directed graphs. A back edge to an active ancestor certifies a directed cycle; absence of such an edge yields a directed acyclic graph. Low-link values derived from DFS identify articulation vertices, bridges, and biconnected components in undirected graphs. Recursive implementations can overflow on large graphs, so production systems often use explicit frames that preserve iterator state and deterministic neighbor ordering. ```svg ``` **Connected components partition an undirected graph.** Reachability is an equivalence relation, so every vertex belongs to exactly one maximal connected component. A single BFS, DFS, or disjoint-set scan can label all components. In directed graphs, weak components ignore direction, while strongly connected components require mutual directed reachability. Condensing each strongly connected component into one vertex produces a directed acyclic graph, revealing the irreversible ordering hidden inside a cyclic system. **Cuts measure how a graph can come apart.** An edge cut crosses a partition $(S,V\setminus S)$, and a vertex cut removes vertices instead. Edge connectivity $lambda(G)$ and vertex connectivity $kappa(G)$ are the minimum respective cut sizes needed to disconnect a nontrivial graph, bounded by minimum degree through $kappa(G)\leq\lambda(G)\leq\delta(G)$. A bridge is a one-edge cut and an articulation vertex is a one-vertex cut. Reliability claims need the correct failure unit: duplicated links do not protect against a shared endpoint failure. **Menger’s theorem converts robustness into alternative routes.** For distinct vertices, the minimum size of a separating vertex set equals the maximum number of internally vertex-disjoint paths, with an analogous statement for edge-disjoint paths and edge cuts. This min-max equality connects structural redundancy to certificates. In interconnect or supply networks, counting superficially different routes overstates resilience when they share vias, tools, controllers, or physical regions. Model shared-risk groups explicitly before invoking disjointness. **Trees are minimally connected and maximally acyclic.** For a finite undirected graph, being connected with $|V|-1$ edges, being acyclic with $|V|-1$ edges, having a unique simple path between every vertex pair, and losing connectivity after any edge deletion are equivalent tree characterizations. Rooting a tree induces parent, child, depth, ancestor, and subtree relations without changing the underlying undirected graph. Trees support hierarchical decomposition and linear-time dynamic programming because removing an edge separates independent subproblems. **Spanning trees preserve reachability while discarding cycles.** Every connected graph contains a spanning tree, and each non-tree edge creates one fundamental cycle when added. Kirchhoff’s matrix-tree theorem counts spanning trees using a cofactor of the graph Laplacian. Many spanning trees can represent the same network, so a traversal tree is not automatically optimal or robust. In clock distribution, routing, and dependency extraction, one must state whether the objective is length, delay, congestion, balance, fault tolerance, or interpretability. **Minimum spanning trees optimize total edge weight under a precise model.** Kruskal’s algorithm adds safe edges in nondecreasing weight order using disjoint sets; Prim’s algorithm grows one tree through the cheapest frontier edge. The cut property says a lightest edge crossing a cut is safe, while the cycle property rejects a uniquely heaviest cycle edge. Negative weights do not invalidate the problem, but directed arborescences require different algorithms. An MST minimizes total weight, not pairwise distances, maximum delay, degree, or resilience. **Disjoint-set union maintains components under edge additions.** The structure stores a forest of representatives and supports `find` and `union`. Union by rank or size plus path compression gives amortized cost $O(\alpha(n))$, effectively constant for practical sizes, while retaining a rigorous inverse-Ackermann bound. It powers Kruskal’s algorithm and incremental connectivity. It does not support arbitrary deletions or recover actual paths without extra state. Deterministic representative choices can matter for reproducible output even when partitions are identical. **Eulerian traversal consumes edges exactly once.** An undirected connected graph has an Euler circuit precisely when every vertex has even degree, and an Euler trail with distinct endpoints precisely when exactly two vertices have odd degree. Directed versions balance indegree and outdegree with appropriate connectivity. Hierholzer’s algorithm splices cycles and runs in linear time. The problem differs fundamentally from finding a Hamiltonian path, which visits vertices exactly once and is computationally much harder. Confusing the two leads to false complexity claims. **Hamiltonian structure lacks a simple local certificate.** A Hamiltonian cycle visits every vertex once before returning, but degree conditions that are necessary are rarely sufficient. Dirac’s and Ore’s theorems provide strong sufficient conditions for simple graphs, not complete tests. The traveling salesperson problem adds weights and asks for a minimum Hamiltonian tour, making the optimization and feasibility questions distinct. In inspection routing, a route that must traverse every connection is Eulerian; one that must visit every site is Hamiltonian. **Directed acyclic graphs encode precedence without circular obligation.** A topological ordering lists every edge from earlier to later and exists exactly when the directed graph has no cycle. Kahn’s algorithm repeatedly removes zero-indegree vertices, while DFS reverse finishing order gives another construction. Multiple valid orders represent real scheduling freedom. Critical-path calculations on a DAG use longest paths even though longest paths in general graphs are hard. A remaining nonzero-indegree subgraph after Kahn’s algorithm is a concrete cycle witness region. **Shortest paths depend on what edge weight means.** In an unweighted graph BFS minimizes hop count. Dijkstra’s algorithm settles vertices greedily when every edge weight is nonnegative, commonly in $O((|V|+|E|)\log |V|)$ time with a binary heap. Bellman–Ford permits negative edges and detects reachable negative cycles; Floyd–Warshall solves dense all-pairs problems by dynamic programming in $O(|V|^3)$. A negative cycle makes an unrestricted shortest walk undefined, but not necessarily a shortest simple path. Delay, risk, energy, and geometric length are not interchangeable weights, and multi-objective routing cannot usually be collapsed into one scalar without a declared tradeoff. **Dijkstra’s invariant fails as soon as a negative edge matters.** The settled vertex must already have its final shortest distance because any later route would add only nonnegative cost. A negative edge can invalidate that conclusion after extraction. Priority queues may contain stale entries unless decrease-key is implemented, so a practical version checks the extracted key against the current distance. Floating-point comparisons can also change predecessor choices near ties. Verification should confirm path validity, recomputed weight, and the triangle inequalities $d(v)\leq d(u)+w(u,v)$ for every reachable edge. **Potential functions can transform weights without changing optimal paths.** Johnson’s algorithm obtains vertex potentials from Bellman–Ford and reweights each edge to $w'(u,v)=w(u,v)+h(u)-h(v)\geq0$, allowing repeated Dijkstra searches while preserving relative path costs after correction. The same reduced-cost idea appears in min-cost flow and optimization. A heuristic $h$ in A* plays a related but different role: admissibility prevents overestimation, and consistency supports monotone extraction. An aggressive heuristic may be fast yet lose optimality unless that approximation is explicitly accepted. ```svg ``` **Maximum flow is constrained by conservation and capacity.** In a directed capacitated network with source $s$ and sink $t$, a feasible flow satisfies $0\leq f(e)\leq c(e)$ and conserves net flow at every other vertex. Residual edges encode both unused capacity and the ability to undo earlier choices. Ford–Fulkerson augments along residual paths; Edmonds–Karp chooses a shortest-hop augmenting path for polynomial time; Dinic builds level graphs; push–relabel maintains preflows. Integral capacities admit an integral maximum flow, a fact that turns many assignment and routing questions into discrete solutions. **The max-flow min-cut theorem provides matching primal and dual certificates.** The value of any feasible flow cannot exceed the capacity of any $s$-$t$ cut because conservation cancels internal contributions. When no residual path reaches the sink, the vertices reachable from the source define a cut whose capacity equals the current flow. Equality proves both optimality statements at once. Reporting only a flow value wastes this certificate. In physical networks, nominal edge capacities may share bottlenecks or violate independence, so the graph must represent common resources before the theorem answers the intended engineering question. **Minimum-cost flow combines routing with economics.** Each unit sent along an edge incurs cost, and supplies and demands replace or supplement a single source-sink pair. Residual networks carry negative reverse costs, so reduced costs and potentials maintain optimality conditions. Transportation, assignment, reticle movement, and lot dispatch can fit the model when flows are divisible or integrality follows from network structure. Setup times, batch coupling, queueing, and nonlinear congestion break the simple linear model. A solver’s optimum is conditional on capacities, costs, and time aggregation being faithful. ```svg ``` **Bipartite graphs separate two kinds of vertices.** A graph is bipartite exactly when it contains no odd cycle, equivalently when BFS levels provide a valid two-coloring in every component. Incidence relations between jobs and tools, cells and pins, wafers and tests, or clauses and variables naturally form bipartite graphs. Projecting both sides into a one-mode graph can manufacture dense cliques and lose the identity of shared intermediates. Retain the two-part structure when algorithms or interpretations depend on it. **Matching pairs vertices without reuse.** A matching is a set of edges with no shared endpoint; it is maximal if no edge can be added and maximum if its cardinality is largest. These are not synonyms, and a greedy maximal matching can be far from a desired weighted optimum. Berge’s lemma states that a matching is maximum exactly when no augmenting path exists. Alternating paths expose how a locally committed pair can be replaced to gain one matched edge, which is the central mechanism behind matching algorithms. **Hall’s theorem characterizes complete assignment on one side.** A bipartite graph with parts $X$ and $Y$ has a matching saturating $X$ exactly when every subset $S\subseteq X$ has at least $|S|$ distinct neighbors. The condition quantifies collective scarcity that individual degree checks miss. Maximum bipartite matching can be reduced to unit-capacity flow, and the Hopcroft–Karp algorithm accelerates augmentation in phases. Qualification matrices for tools and recipes need time windows, capacities, and maintenance states before a static matching corresponds to an executable schedule. **Vertex covers and matchings reveal a bipartite duality.** A vertex cover touches every edge, while an independent set contains no internal edge. In any graph, the complement of a vertex cover is independent. Kőnig’s theorem says that in bipartite graphs the minimum vertex-cover size equals the maximum matching size. Outside bipartite graphs this equality can fail. The theorem gives a compact certificate and underlies line-covering forms of assignment algorithms. It also warns against transporting a special-class result into arbitrary conflict graphs. **Coloring models conflicts through inequality.** A proper vertex coloring assigns colors so adjacent vertices differ, and the chromatic number $chi(G)$ is the smallest number required. Greedy coloring depends on vertex order and provides an upper bound, while clique size gives a lower bound. Two-colorability is easy, but deciding three-colorability is NP-complete. Edge coloring assigns resources to relations that meet at vertices. In scheduling and mask decomposition, a color must map to a real mutually compatible resource, not merely an integer label. **Lithography decomposition makes coloring physically consequential.** Construct a conflict graph whose vertices are layout features and whose edges join features too close for the same exposure. Double patterning asks whether the graph is bipartite; an odd cycle demands a stitch, feature modification, or additional color. Triple and quadruple patterning introduce harder coloring and balance objectives. The graph changes with spacing rules, process window, stitch eligibility, overlay sensitivity, and precolored features. A mathematically valid coloring is not manufacturable until those physical constraints and density requirements are checked. ```svg ``` **Planarity asks whether crossings are avoidable topologically.** A graph is planar if it can be embedded in the plane with edges meeting only at shared endpoints. A particular drawing with crossings does not prove nonplanarity. For a connected planar embedding, Euler’s relation $|V|-|E|+|F|=2$ counts faces including the exterior. Consequently a simple planar graph with at least three vertices has $|E|\leq3|V|-6$, and a bipartite planar graph has the sharper $|E|\leq2|V|-4$. These are necessary density bounds, not sufficient planarity tests. **Kuratowski’s theorem identifies the two fundamental planar obstructions.** A finite graph is planar exactly when it contains no subdivision of $K_5$ or $K_{3,3}$; Wagner’s equivalent formulation uses minors. Planarity algorithms can produce an embedding or an obstruction certificate in linear time. Physical routing adds layer changes, widths, spacing, obstacles, and terminal geometry, so topological planarity is only the first feasibility screen. A nonplanar net interaction graph may become routable through multiple metal layers and vias, at costs absent from the abstract graph. **The adjacency matrix turns combinatorics into linear algebra.** For a simple graph, $A_{ij}=1$ when vertices $i$ and $j$ are adjacent and zero otherwise. The entry $(A^k)_{ij}$ counts length-$k$ walks, revealing how matrix multiplication aggregates intermediate vertices. Undirected adjacency matrices are symmetric and have real eigenvalues, while directed matrices need not. Vertex relabeling conjugates $A$ by a permutation matrix and preserves its spectrum. Cospectral nonisomorphic graphs show that eigenvalues are informative invariants rather than complete structural fingerprints. **The graph Laplacian encodes variation across edges.** For an undirected weighted graph, $L=D-A$ satisfies $x^TLx=\frac12\sum_{i,j}w_{ij}(x_i-x_j)^2\geq0$. Its nullspace consists of vectors constant on connected components, so the multiplicity of eigenvalue zero equals the number of components. The second-smallest eigenvalue, algebraic connectivity, measures a form of connectedness, and its eigenvector supports spectral partitioning. Normalized Laplacians compensate for degree variation but answer a different objective. Negative or directed weights require care because symmetry and positive semidefiniteness can disappear. **Electrical networks give graph quantities physical meaning.** Treat each edge as a conductance and the weighted Laplacian as the nodal conductance matrix. Solving a grounded Laplacian system gives voltages under injected currents; effective resistance between two vertices equals the voltage difference for unit injection and relates to random-walk commute time and spanning-tree probabilities. Kirchhoff’s current law is the incidence-matrix equation of flow conservation. This analogy informs power-grid analysis, interconnect extraction, and preconditioning, but distributed capacitance and inductance require richer frequency-dependent models than a resistive graph. **Spectral partitioning relaxes a discrete cut problem.** Minimizing cut size alone favors isolating small sets, so ratio cut and normalized cut balance separation against part size or volume. Replacing discrete indicator constraints with continuous vectors yields an eigenproblem whose Fiedler vector can be rounded into a partition. The relaxation gives a tractable bound, not an automatic optimum. Degenerate eigenvalues, weak spectral gaps, disconnected inputs, and rounding choices can make partitions unstable. Always evaluate the original discrete objective and engineering constraints after spectral computation. ```svg ``` **Random graphs distinguish typical structure from worst cases.** In the Erdős–Rényi model $G(n,p)$, each possible edge appears independently with probability $p$, giving expected degree $(n-1)p$. Threshold phenomena cause properties such as isolated-vertex disappearance and connectivity to emerge sharply as density grows. Configuration models preserve a degree sequence more closely, while stochastic block models encode community tendencies. Real semiconductor, biological, and social networks include geometry, hierarchy, direction, and dependence that independent-edge models omit. A null model should preserve the features that would otherwise create a misleading signal. **Probability turns deterministic algorithms into estimators and tests.** Random sampling can estimate triangle counts, reachability, centrality, or cut quality when exhaustive computation is too costly. Randomized contraction finds minimum cuts with analyzable success probability; repeated independent trials amplify confidence. Bloom-like sketches and streaming summaries trade exactness for memory. Report the sampling distribution, failure probability, seed policy, and bias rather than presenting one realization as ground truth. Randomization in tie-breaking can also expose instability that a deterministic vertex order hides. **Centrality measures formalize different notions of importance.** Degree centrality rewards local adjacency, closeness rewards short distances to others, betweenness counts participation in shortest paths, eigenvector centrality rewards connection to important vertices, and PageRank adds a directed random-surfer model with teleportation. Disconnected graphs, direction, weight semantics, and normalization alter every measure. A high-centrality tool may be a bottleneck, but if edges represent similarity instead of material flow the same interpretation is wrong. Compare rankings under plausible models and perturbations before acting on them. **Cliques and independent sets represent complete compatibility opposites.** A clique is a vertex set with every possible internal edge; an independent set has none and is a clique in the complement graph. Maximum clique, maximum independent set, and minimum vertex cover are tightly related and generally NP-hard. Maximal solutions can be found greedily but need not be maximum. In qualification graphs, the meaning flips depending on whether edges encode compatibility or conflict. State the polarity before interpreting a clique as a jointly feasible group. **Graph complexity separates easy verification from hard discovery.** A proposed coloring, path, matching, or tour can often be checked quickly even when finding the optimum is difficult. Polynomial-time algorithms solve traversal, connectivity, shortest nonnegative paths, bipartite matching, maximum flow, planarity, and minimum spanning trees. General graph coloring, Hamiltonian cycle, clique, independent set, and traveling salesperson are NP-complete or NP-hard in their decision or optimization forms. Restricted graph classes, parameters, approximation, integer programming, and heuristics can still make practical instances tractable. “NP-hard” describes scaling, not impossibility. **Approximation guarantees and heuristics answer different promises.** An approximation algorithm provides a worst-case ratio under specified assumptions, while a heuristic offers observed performance without that universal bound. Branch-and-bound can prove optimality by closing a gap; local search may find strong solutions quickly; fixed-parameter algorithms isolate exponential growth in a parameter such as treewidth or solution size. Production reports should separate incumbent objective, valid lower or upper bound, optimality gap, runtime limit, and feasibility. A visually good partition is not an auditable certificate. **Treewidth measures how close a graph is to a tree.** A tree decomposition places vertices into overlapping bags arranged as a tree, covers each edge in some bag, and requires bags containing any vertex to form a connected subtree. Width is largest bag size minus one. Many otherwise hard problems become tractable on bounded-treewidth graphs through dynamic programming, but finding minimum treewidth is itself hard. Elimination order, fill edges, chordal completion, and sparse matrix factorization connect the concept directly to numerical simulation and circuit analysis. **Hypergraphs represent relations involving more than two entities.** A hyperedge can join an arbitrary vertex subset, naturally modeling a multi-terminal electrical net, one recipe requiring several resources, or a defect signature shared by many measurements. Replacing a hyperedge with a clique exaggerates pairwise interactions and can inflate density; replacing it with an auxiliary incidence vertex preserves membership but changes distances. Hypergraph partitioning targets cut nets and balance rather than ordinary edge cuts. The representation choice must follow the cost actually paid when a multiway relation spans partitions. **Temporal and multilayer graphs preserve context that aggregation destroys.** A temporal edge has an availability interval or event time, so a time-respecting path must follow chronological order. A multilayer graph separates relation types such as electrical connectivity, physical proximity, thermal coupling, and shared equipment. Collapsing time can invent paths that never existed; collapsing layers can equate correlation with causation. Algorithms must define waiting, duration, persistence, interlayer transitions, and missing observations. Dynamic connectivity and streaming updates require data structures different from static batch analysis. ```svg ``` **Circuit netlists are often hypergraphs before they are ordinary graphs.** Devices have terminals and nets may connect many terminals, so a bipartite incidence graph or hypergraph preserves semantics better than connecting every device pair. Connectivity extraction uses disjoint sets, while simulation matrices arise from stamped component relations. Signal-flow and timing graphs introduce direction that raw electrical connectivity lacks. Hierarchical modules, buses, power domains, and parasitics must be expanded or summarized consistently before equivalence checking or partitioning. **Static timing analysis is a weighted DAG computation under mode assumptions.** Vertices represent timing events and directed edges carry cell or interconnect delays and constraints. Arrival times propagate by maximum operations, required times backward by minimum operations, and slack measures margin. Sequential elements break combinational cycles in the abstract timing graph, while latches and generated clocks require richer treatment. Process, voltage, temperature, crosstalk, and statistical correlation mean one scalar edge weight is only one analysis corner, not a universal delay. **Placement and routing combine graphs with geometry.** Netlists express connectivity, but objective functions depend on coordinates, congestion grids, obstacles, layer rules, via costs, timing criticality, and power integrity. Steiner trees can reduce estimated wirelength compared with spanning trees because new junction points are allowed. Global routing resembles multicommodity flow but integrality and capacity coupling are difficult; detailed routing enforces exact design rules. Graph abstractions guide decomposition, yet geometric legalization decides manufacturability. **Fault diagnosis uses graphs only after causal semantics are justified.** Vertices may represent tests, symptoms, tools, lots, chambers, or candidate causes; edges may encode genealogy, shared exposure, conditional dependence, or expert rules. Connected clusters identify common history but do not prove a causal source. Directed acyclic graphical models add probabilistic factorization assumptions, while factor graphs represent variables and constraints. Confounding maintenance events, sampling bias, and missing trace data can create persuasive but false communities. Preserve timestamps and intervention evidence. **Graph algorithms require property-based verification, not only example outputs.** Traversal must visit exactly reachable vertices; a spanning tree must be connected, acyclic, and have $|V|-1$ edges; a coloring must separate every edge; a matching must share no endpoints; a flow must meet conservation and capacity; and a shortest-path tree must satisfy edge inequalities. Compare small random cases with brute force, use metamorphic transformations such as vertex relabeling, and test empty, disconnected, parallel-edge, loop, overflow, and adversarial-order cases. **Reproducibility requires deterministic contracts around ties.** Hash-map iteration, parallel reductions, equal edge weights, and arbitrary vertex identifiers can change equally optimal outputs. If downstream systems compare exact structures, sort adjacency, define tie keys, normalize labels, and record software versions. If any optimum is acceptable, tests should validate objective and feasibility rather than one serialized answer. Floating-point weights demand explicit tolerance or integer scaling, because tiny representation differences can change ordering while remaining numerically insignificant. Consider a five-operation process recipe with precedence edges from clean to deposition, deposition to lithography, lithography to etch, and both deposition and etch to metrology. A topological order proves only logical feasibility. To predict completion time, attach duration to operations or edges and compute a longest path through the resulting DAG; to schedule two chambers, add resource constraints that the precedence graph alone cannot express. If metrology feeds a decision that may repeat etch, the operational state model contains a cycle even though one planned pass remains acyclic. The correct graph depends on whether the question is recipe validation, nominal lead time, resource scheduling, or rework behavior. Consider a double-patterning conflict graph formed from seven polygons. A BFS two-coloring either assigns the two masks or discovers an edge whose endpoints have the same parity level. Combining their parent paths with that edge produces an odd-cycle certificate. Engineers can then inspect the corresponding geometric cycle and evaluate a legal stitch, spacing change, or third exposure. Merely returning “not bipartite” hides the actionable structure. Conversely, a two-coloring must be checked against precolored anchors, stitch exclusions, density balance, and overlay-sensitive relations that may not have been included in the first graph construction. Consider a tool-qualification bipartite graph with lots on one side and chambers on the other. A maximum matching answers how many lots can start simultaneously when each chamber handles one lot and every lot needs one chamber. If two chambers share a load lock, or lots require batches, recipes consume different durations, and maintenance begins at different times, plain matching overstates feasibility. A time-expanded network, capacitated flow, integer schedule, or constraint program may be required. Hall-deficient subsets still provide valuable diagnostics by identifying groups of lots whose combined eligible chamber set is too small. Consider an interconnect graph in which edge resistance weights are nonnegative. A minimum-resistance path is not necessarily the path of minimum Elmore delay, because downstream capacitance and branching change the objective. A minimum spanning tree minimizes total selected edge resistance or length, not source-to-sink latency. A Steiner tree may reduce wirelength by adding junctions, but design rules determine permitted junction geometry. These differences demonstrate why an algorithm name should never substitute for an objective function. Define the physical loss, show how graph weights compose, and validate the resulting topology in the electrical model used for signoff. Consider a fab genealogy graph linking wafers to lots, tools, chambers, recipes, consumable batches, and measurement events. A cluster of failing wafers connected to one chamber is a hypothesis generator, not proof of chamber causality, because route selection and sampling may be confounded by product, time, or upstream material. Temporal edges prevent future events from explaining earlier failures, and typed layers stop “processed by” from being treated like “measured with.” Compare affected and unaffected neighbors, seek interventions or maintenance boundaries, and reserve independent runs for confirmation. Graph structure organizes evidence; it does not repeal experimental design. Consider a package or supply network evaluated for resilience. Two paths that appear edge-disjoint in a supplier graph may still depend on the same geographic corridor, utility, sub-tier chemical producer, firmware service, or qualification lab. Introduce vertices or shared-risk labels for those common causes before computing connectivity. Then a minimum cut becomes an interpretable stress scenario and disjoint paths become defensible alternatives. Weighting edges only by procurement price would miss recovery time and substitution delay, while multiplying uncertain probabilities assumes independence that the shared-risk expansion was meant to correct. The certificate is useful because engineers can inspect its members, challenge omissions, and design a targeted redundancy or inventory response. | Engineering question | Graph model | Core method | Required certificate or check | |---|---|---|---| | Are all terminals connected? | Undirected or incidence graph | BFS, DFS, disjoint set | Reachability partition | | Which dependency order is legal? | Directed acyclic graph | Topological sorting | Every edge respects order | | What route has minimum additive cost? | Weighted directed graph | Dijkstra, Bellman–Ford, A* | Path plus recomputed cost | | What single failure disconnects service? | Connectivity graph | Bridges, articulation, min cut | Separating set and components | | How should jobs pair with resources? | Bipartite graph | Matching or min-cost flow | Feasible pairs and augmenting-path absence | | Can features share two masks? | Conflict graph | Bipartite test and coloring | Color of every vertex and odd-cycle witness | | How can nets be partitioned? | Hypergraph | Multilevel partitioning | Balance and cut-net objective | | Where is the critical timing chain? | Weighted DAG | Longest-path dynamic program | Predecessor chain and slack recomputation | | How robust is a shared network? | Capacitated multilayer graph | Disjoint paths and cuts | Shared-risk-aware cut certificate | | Does an implementation preserve theory? | Labeled test graphs | Invariants and brute-force oracle | Property checks under relabeling | ```flowchart start: State the engineering decision and quantity of interest entities: Define vertices edges direction labels weights and missing data class: Identify graph class and exploitable structure invariant: Write feasibility invariants and an independently checkable certificate method: Choose exact approximation parameterized or heuristic method represent: Select adjacency incidence sparse temporal or hypergraph representation compute: Run with deterministic tie and numeric policies verify: Recompute feasibility objective conservation and structural properties stress: Test relabeling edge cases perturbations and brute force small instances meaning: Translate the result back to physical system constraints valid: Does withheld or operational evidence support the interpretation? deploy: Record model scope algorithm version certificate and uncertainty revise: Change the abstraction or assumptions that failed start->entities->class->invariant->method->represent->compute->verify->stress->meaning->valid valid->deploy valid->revise revise->entities ``` **A graph result is trustworthy only when its certificate survives translation back to the system.** The best route must obey real direction and capacity, the valid coloring must satisfy process rules, the matched assignment must fit time and qualification, and the identified cut must represent independent failures rather than shared infrastructure. Preserve the input graph, modeling assumptions, algorithm, tie policy, certificate, and physical checks together. Read graph theory through a structure-and-certificate lens rather than a node-link-picture lens.