Author | Walther, Hansjoachim. author |
---|---|
Title | Ten Applications of Graph Theory [electronic resource] / by Hansjoachim Walther |
Imprint | Dordrecht : Springer Netherlands, 1984 |
Connect to | http://dx.doi.org/10.1007/978-94-009-7154-7 |
Descript | 264 p. online resource |
0. Introduction -- 1. Flows and tensions on networks -- 1.1. Basic concepts -- 1.2. Properties of flows and tensions -- 1.3. The maximum flow problem -- 1.4. The maximum tension problem -- 1.5. The conception of network analysis -- 1.6. Bibliography -- 2. The linear transportation problem -- 2.1. Formulation of the problem -- 2.2. The solution according to Busacker and Gowen -- 2.3. The solution according to Klein -- 2.4. Proof of minimality -- 2.5. Conclusions -- 2.6. Bibliography -- 3. The cascade algorithm -- 3.1. Formulation of the problem -- 3.2. The standard method -- 3.3. The revised matrix algorithm -- 3.4. The cascade algorithm -- 3.5. Bibliography -- 4. Nonlinear transportation problems -- 4.1. Formulation of the problem -- 4.2. A convex transportation problem -- 4.3. A multi-flow problem -- 4.4. Bibliography -- 5. Communication and supply networks -- 5.1. Formulation of the problem -- 5.2. Networks without Steinerโs points -- 5.3. Networks containing Steinerโs points -- 5.4. Influence exerted by the cost function on the structure of the optimal network -- 5.5. Bibliography -- 6. The assignment and the travelling salesman problems -- 6.1. The assignment problem -- 6.2. The travelling salesman problem -- 6.3. Final observations -- 6.4. Bibliography -- 7. Coding and decision graphs -- 7.1. Formulation of the problem -- 7.2. Algorithm for the generation of a cycle-free questionnaire -- 7.3. Optimal questionnaires -- 7.4. An example from coding -- 7.5. Bibliography -- 8. Signal flow graphs -- 8.1. Formulation of the problem -- 8.2. The algorithm of Mason for solving linear systems of equations -- 8.3. Bibliography -- 9. Minimum sets of feedback arcs -- 9.1. Formulation of the problem -- 9.2. The algorithm of Lempel and Cederbaum -- 9.3. The idea of Younger -- 9.4. Bibliography -- 10. Embedding of planar graphs in the plane -- 10.1. Formulation of the problem -- 10.2. Theorems of Kuratowski, MacLane and Whitney -- 10.3. The planarity algorithm of Dambitis -- 10.4. Planarity studies made by decomposing graphs -- 10.5. The embedding algorithm of Demoucron, Malgrange and Pertuiset -- 10.6. The planarity algorithm of Tutte -- 10.7. Bibliography -- Algorithms -- Author Index