Representing Reactions with Two Vertex Classes
A reaction pathway involves two different kinds of objects: chemical species and reactions. A directed bipartite graph keeps them separate. Species vertices describe what is available; reaction vertices record which inputs are required and which outputs can be produced. This representation is useful for qualitative reachability questions: starting from specified initial species, which other species can become available, and which reactions remain unable to proceed?
We use a simplified, qualitative model. All species and reactions are finite in number. A reaction fires when every species listed as an input is available, and firing makes every listed output available. Species are not consumed, and quantities, reaction rates, and stoichiometric coefficients are ignored. Thus the model describes possible production, not how much material is present or how quickly a reaction occurs. Reversible chemistry can be represented by separate directed reaction vertices for the two directions.
In particular, all inputs are required: having only some of the species in \(I(r)\) does not enable the reaction. If \(I(r)=\varnothing\), then \(I(r)\subseteq S\) for every \(S\), so the reaction is enabled even when no species are initially available. An output arc records possible production; it does not by itself assert that the reaction can occur.
Reachability by Repeated Closure
Let \(S_0\subseteq X\) be the initial set of available species. Define the successive sets \(S_k\) by adding the outputs of every reaction enabled by the current set:
The sets only grow: \(S_k\subseteq S_{k+1}\). Since there are finitely many species, this process eventually reaches a set \(S^*\) for which \(S_{k+1}=S_k\). Such a set is closed: every reaction whose inputs are all in \(S^*\) has all its outputs in \(S^*\). The reactions enabled at this final set are exactly those \(r\) with \(I(r)\subseteq S^*\). A reaction not meeting this condition has at least one required input outside \(S^*\).
Proof. First, every species in \(S_k\) is reachable. This holds for \(S_0\) by definition. If it holds for \(S_k\), then each reaction with \(I(r)\subseteq S_k\) can be fired after making its input species available; firing it adds every species in \(O(r)\). Thus all species in \(S_{k+1}\) are reachable. Induction gives the claim for \(S^*\).
Conversely, consider any finite sequence of firings starting from \(S_0\). We show, in order through that sequence, that every species available after each firing belongs to \(S^*\). Initially this holds because \(S_0\subseteq S^*\). If the next fired reaction is \(r\), all its inputs are already available and hence belong to \(S^*\). Since \(S^*\) is closed, \(O(r)\subseteq S^*\); the firing therefore adds no species outside \(S^*\). So every reachable species is in \(S^*\). Finally, any closed set containing \(S_0\) contains \(S_1\), then \(S_2\), and inductively every \(S_k\); it therefore contains \(S^*\). This proves both assertions. \(\square\)
The procedure terminates after finitely many stages: whenever a stage changes the set, it adds at least one species, and there are only \(|X|\) species. At termination, a reaction with a missing input cannot become enabled at a later stage, because no later stage adds any species. This is why the final set gives a lasting reachability test rather than just a snapshot.
Worked Example: Tracing a Reaction Pathway
Let the species set be \(X=\{A,B,C,D,E,F,G\}\), the reaction set be \(R=\{r_1,r_2,r_3,r_4,r_5\}\), and the directed arcs be \(A\to r_1,\ r_1\to B,\ r_1\to C,\ B\to r_2,\ r_2\to D,\ C\to r_3,\ D\to r_3,\ r_3\to E,\ E\to r_4,\ r_4\to F,\ G\to r_5,\ r_5\to F\). Thus \(r_1\) requires \(A\); \(r_2\) requires \(B\); \(r_3\) requires both \(C\) and \(D\); \(r_4\) requires \(E\); and \(r_5\) requires \(G\). Start with \(S_0=\{A\}\).
| Stage | Available set \(S_k\) | Newly available species | Reactions enabled at this stage that add new species |
|---|---|---|---|
| 0 | \(\{A\}\) | \(\{B,C\}\) | \(r_1\) |
| 1 | \(\{A,B,C\}\) | \(\{D\}\) | \(r_2\) |
| 2 | \(\{A,B,C,D\}\) | \(\{E\}\) | \(r_3\) |
| 3 | \(\{A,B,C,D,E\}\) | \(\{F\}\) | \(r_4\) |
| 4 | \(\{A,B,C,D,E,F\}\) | \(\varnothing\) | None |
For example, at stage 1, \(B\in S_1\), so \(I(r_2)=\{B\}\subseteq S_1\) and \(D\) is added. At stage 2, both \(C\) and \(D\) are available, so \(I(r_3)=\{C,D\}\subseteq S_2\) and \(E\) is added. At the final stage, \(r_5\) is not enabled because \(G\notin S_4\). Hence \(S^*=\{A,B,C,D,E,F\}\). In particular, \(F\) is reachable by either producing route that becomes enabled, while \(G\) is not produced in this network.
Check: The final set is closed: \(r_1,r_2,r_3,r_4\) have all their inputs in \(S^*\), and their outputs \(B,C,D,E,F\) are in \(S^*\); \(r_5\) has input \(G\notin S^*\). The stage table also shows that each of \(B,C,D,E,F\) is added from an enabled reaction.
Why a Directed Path Is Not Enough
A directed path from an initial species to a product follows arcs one at a time, but it does not check whether every input of each reaction on the route is available. A reaction vertex may have several incoming arcs. A path can enter that vertex through one input even though another required input is missing. Reachability must therefore be tested by the closure rule, not by ordinary directed-path reachability in the bipartite graph.
Worked Example: A Product Blocked by Missing Inputs
Take \(X=\{A,B,C,D,E,P\}\), \(R=\{r_1,r_2,r_3,r_4\}\), and the arcs \(A\to r_1,\ r_1\to B,\ C\to r_2,\ r_2\to D,\ B\to r_3,\ D\to r_3,\ r_3\to P,\ E\to r_4,\ r_4\to P\). The reactions are \(A\to B\), \(C\to D\), the two-input reaction \(\{B,D\}\to P\), and \(E\to P\). Let \(S_0=\{A\}\).
At stage 0, only \(r_1\) is enabled, since \(I(r_1)=\{A\}\subseteq S_0\). Its output is \(B\), so \(S_1=\{A,B\}\). At stage 1, \(r_1\) remains enabled, but \(r_2\) is not enabled because \(C\notin S_1\); \(r_3\) is not enabled because \(D\notin S_1\); and \(r_4\) is not enabled because \(E\notin S_1\). No new species are added, so \(S^*=\{A,B\}\).
There is a directed path \(A\to r_1\to B\to r_3\to P\), but it does not represent a feasible firing sequence: \(r_3\) also requires \(D\), which is unavailable. The other producer \(r_4\) requires \(E\), also unavailable. Since \(P\notin S_0\) and every reaction producing \(P\) has a required input outside \(S^*\), \(P\) is unreachable in this model.
Check: Reapplying the rule to \(\{A,B\}\) adds no species: \(C,D,E\notin\{A,B\}\), so \(r_2,r_3,r_4\) remain disabled. Thus \(S_2=S_1=\{A,B\}\), confirming the stopping set.
Proof. Suppose \(P\notin S_0\) and every reaction producing \(P\) has a required input outside \(S^*\). If \(P\) were reachable, the theorem would give \(P\in S^*\). Because \(P\notin S_0\), it must have been added at some stage by a reaction \(r\) with \(P\in O(r)\) and \(I(r)\subseteq S_k\) for that stage \(k\). Since \(S_k\subseteq S^*\), this would give \(I(r)\subseteq S^*\), contradicting the hypothesis that this producer has an input outside \(S^*\). Therefore \(P\) is unreachable. If there is no reaction producing \(P\), the condition over producers holds vacuously, and the same conclusion follows: \(P\), not initially present, cannot be added by any firing. \(\square\)
Worked Example: An Initial Product and a Source Reaction
Let \(X=\{B,C,Q,P\}\), \(R=\{r_0,r_1,r_2\}\), and take the arcs \(r_0\to B,\ B\to r_1,\ C\to r_1,\ r_1\to P,\ Q\to r_2,\ r_2\to P\). Here \(r_0\) has no inputs and produces \(B\); \(r_1\) requires both \(B\) and \(C\) to produce \(P\); \(r_2\) requires \(Q\) to produce \(P\). Start with \(S_0=\{P\}\).
Since \(I(r_0)=\varnothing\), we have \(I(r_0)\subseteq S_0\), so \(r_0\) is enabled and adds \(B\). Thus \(S_1=\{P,B\}\). Reaction \(r_1\) is still disabled because \(C\notin S_1\), and \(r_2\) is disabled because \(Q\notin S_1\). No further species are added, so \(S^*=\{P,B\}\). The species \(P\) is reachable because it was in \(S_0\), even though both reactions that produce it are blocked.
Check: The source reaction adds exactly its output \(B\); \(P\) remains available from the initial set; and neither \(C\) nor \(Q\) is produced by any enabled reaction. The final set is closed, as required.
Common Pitfall and Scope of the Model
Common mistake: following a path as if it checks every input. In the second example, a mistaken path-based calculation might read \(A\to r_1\to B\to r_3\to P\) and conclude that \(P\) is reachable. The correction is to test the entire input set of each reaction: \(I(r_3)=\{B,D\}\), and \(D\notin S^*\). Therefore \(r_3\) cannot fire, and \(P\) is not reached by that route. The separate producer \(r_4\) must also be checked, since products can have more than one producing reaction.
The model answers a specific qualitative question. It treats a species as available once it has appeared and never removes it. A real chemical system may require quantities, conservation laws, catalysts, or rate information; those are not encoded by this graph. Within the stated assumptions, however, the procedure is exact: compute the closure, inspect which reactions have all their inputs there, and distinguish species already in \(S_0\) from species that would need a producing reaction.
Check Your Understanding
For each question, use the input-set rule rather than directed paths alone.
- Suppose \(I(r)=\{A,B\}\) and the current available set is \(\{A,C\}\). Is \(r\) enabled? State the missing input.
- In the pathway example, what is the first stage at which \(r_3\) is enabled, and which two inputs make it enabled?
- Give a reason why a directed path from an initial species to a product may fail to establish that the product is reachable.
- A species \(P\) is absent from \(S_0\), and every reaction producing \(P\) has an input outside \(S^*\). What can you conclude? Why would the same conclusion not follow if \(P\in S_0\)?
- What does an empty input set \(I(r)=\varnothing\) imply about when reaction \(r\) is enabled?