A shortest path problem

A network or graph consists of a set of points nodes) connected by lines edges or links). These links can be one-way (one can go from point A to B, but not vice versa) or two-way. When the edges are characterized by values, it is called a weighted graph. In the usual economic problems for which one applies networks, these values are cost, time, or distance. 

Graphs have been applied in chemometrics to describe molecules. Indeed, molecules can be represented as nodes (the atoms) connected by bonds (the edges). Because in the present chapter, we want to emphasize the optimization aspect, we refer the reader to the literature e.g. Refs. [20-23]. 

This follows step 2a. Only one ion remains on the column. It is now eluted, so that the terminal node is reached. 

One may question whether the application of graph theory is really necessary as no doubt a separation such as that described above can be investigated easily without it. However, when more ions are to be separated, the number of nodes grows very rapidly. 

The calculation of the number of nodes is rather complicated. It is simpler in the special case where transfers from one column to another are not allowed (all ions eluted from the column must be completely separated from all the other ions). In this instance, and for three elements, the following nodes should be considered ABC//, A//B/C, AB//C, AC//B, BC//A, B//A/C, C//A/B, and //A/B/C. If one considers only the stationary phase (to the left of //), one notes that all the combinations of zero, one, two, and three ions out of three are present. 

---