Graph theory with applications / J. A. Bondy and U. S. R. Murty.
Editor: New York : American Elsevier, 1976Descripción: x, 264 p. : il. ; 24 cmISBN: 0444194517Otra clasificación: 05Cxx (94A20)Contents Preface vi [1] GRAPHS AND SUBGRAPHS 1.1 Graphs and Simple Graphs [1] 1.2 Graph Isomorphism [4] 1.3 The Incidence and Adjacency Matrices [7] 1.4 Subgraphs [8] 1.5 Vertex Degrees [10] 1.6 Paths and Connection [12] 1.7 Cycles [14] Applications 1.8 The Shortest Path Problem [15] 1.9 Spemer’s Lemma [21] 2 TREES 2.1 Trees [25] 2.2 Cut Edges and Bonds [27] 2.3 Cut Vertices [31] 2.4 Cayley’s Formula [32] Applications 2.5 The Connector Problem [36] 3 CONNECTIVITY 3.1 Connectivity [42] 3.2 Blocks [44] Applications 3.3 Construction of Reliable Communication Networks [47] 4 EULER TOURS AND HAMILTON CYCLES 4.1 Euler Tours [51] 4.2 Hamilton Cycles [53] Applications 4.3 The Chinese Postman Problem [62] 4.4 The Travelling Salesman Problem [65] 5 MATCHINGS 5.1 Matchings [70] 5.2 Matchings and Coverings in Bipartite Graphs [72] 5.3 Perfect Matchings [76] Applications 5.4 The Personnel Assignment Problem [80] 5.5 The Optimal Assignment Problem [86] 6 EDGE COLOURINGS 6.1 Edge Chromatic Number [91] 6.2 Vizing’s Theorem [93] Applications 6.3 The Timetabling Problem [96] 7 INDEPENDENT SETS AND CLIQUES 7.1 Independent Sets [101] 7.2 Ramsey’s Theorem [103] 7.3 Turan’s Theorem [109] Applications 7.4 Schur’s Theorem [112] 7.5 A Geometry Problem [113] 8 VERTEX COLOURINGS 8.1 Chromatic Number [117] 8.2 Brooks’ Theorem [122] 8.3 Hajós’ Conjecture [123] 8.4 Chromatic Polynomials [125] 8.5 Girth and Chromatic Number [129] Applications 8.6 A Storage Problem [131] 9 PLANAR GRAPHS 9.1 Plane and Planar Graphs [135] 9.2 Dual Graphs [139] 9.3 Euler’s Formula [143] 9.4 Bridges [145] 9.5 Kuratowski’s Theorem [151] 9.6 The Five-Colour Theorem and the Four-Colour Conjecture [156] 9.7 Nonhamiltonian Planar Graphs [160] Applications 9.8 A Planarity Algorithm [163] Contents 10 DIRECTED GRAPHS 10.1 Directed Graphs [171] 10.2 Directed Paths [173] 10.3 Directed Cycles Applications [176] 10.4 A Job Sequencing Problem [179] 10.5 Designing an Efficient Computer Drum [181] 10.6 Making a Road System One-Way [182] 10.7 Ranking the Participants in a Tournament [185] NETWORKS 11.1 Flows [191] 11.2 Cuts [194] 11.3 The Max-Flow Min-Cut Theorem Applications [196] 11.4 Menger’s Theorems [203] 11.5 Feasible Flows [206] 12 THE CYCLE SPACE AND BOND SPACE 12.1 Circulations and Potential Differences [212] 12.2 The Number of Spanning Trees [218] Applications 12.3 Perfect Squares [220] Appendix I Hints to Starred Exercises [227] Appendix II Four Graphs and a Table of their Properties [232] Appendix III Some Interesting Graphs [234] Appendix IV Unsolved Problems [246] Appendix V Suggestions for Further Reading [254] Glossary of Symbols [257] Index [261]
| Item type | Home library | Shelving location | Call number | Materials specified | Status | Date due | Barcode | Course reserves |
|---|---|---|---|---|---|---|---|---|
Libros
|
Instituto de Matemática, CONICET-UNS | Libros ordenados por tema | 05 B711 (Browse shelf) | Available | A-4683 |
Publicado originalmente: London : Macmillan, 1976.
Bibliografía: p. [254]-255.
Contents --
Preface vi [1] --
GRAPHS AND SUBGRAPHS --
1.1 Graphs and Simple Graphs [1] --
1.2 Graph Isomorphism [4] --
1.3 The Incidence and Adjacency Matrices [7] --
1.4 Subgraphs [8] --
1.5 Vertex Degrees [10] --
1.6 Paths and Connection [12] --
1.7 Cycles [14] --
Applications --
1.8 The Shortest Path Problem [15] --
1.9 Spemer’s Lemma [21] --
2 TREES --
2.1 Trees [25] --
2.2 Cut Edges and Bonds [27] --
2.3 Cut Vertices [31] --
2.4 Cayley’s Formula [32] --
Applications --
2.5 The Connector Problem [36] --
3 CONNECTIVITY --
3.1 Connectivity [42] --
3.2 Blocks [44] --
Applications --
3.3 Construction of Reliable Communication Networks [47] --
4 EULER TOURS AND HAMILTON CYCLES --
4.1 Euler Tours [51] --
4.2 Hamilton Cycles [53] --
Applications --
4.3 The Chinese Postman Problem [62] --
4.4 The Travelling Salesman Problem [65] --
5 MATCHINGS --
5.1 Matchings [70] --
5.2 Matchings and Coverings in Bipartite Graphs [72] --
5.3 Perfect Matchings [76] --
Applications --
5.4 The Personnel Assignment Problem [80] --
5.5 The Optimal Assignment Problem [86] --
6 EDGE COLOURINGS --
6.1 Edge Chromatic Number [91] --
6.2 Vizing’s Theorem [93] --
Applications --
6.3 The Timetabling Problem [96] --
7 INDEPENDENT SETS AND CLIQUES --
7.1 Independent Sets [101] --
7.2 Ramsey’s Theorem [103] --
7.3 Turan’s Theorem [109] --
Applications --
7.4 Schur’s Theorem [112] --
7.5 A Geometry Problem [113] --
8 VERTEX COLOURINGS --
8.1 Chromatic Number [117] --
8.2 Brooks’ Theorem [122] --
8.3 Hajós’ Conjecture [123] --
8.4 Chromatic Polynomials [125] --
8.5 Girth and Chromatic Number [129] --
Applications --
8.6 A Storage Problem [131] --
9 PLANAR GRAPHS --
9.1 Plane and Planar Graphs [135] --
9.2 Dual Graphs [139] --
9.3 Euler’s Formula [143] --
9.4 Bridges [145] --
9.5 Kuratowski’s Theorem [151] --
9.6 The Five-Colour Theorem and the Four-Colour Conjecture [156] --
9.7 Nonhamiltonian Planar Graphs [160] --
Applications --
9.8 A Planarity Algorithm [163] --
Contents --
10 DIRECTED GRAPHS --
10.1 Directed Graphs [171] --
10.2 Directed Paths [173] --
10.3 Directed Cycles Applications [176] --
10.4 A Job Sequencing Problem [179] --
10.5 Designing an Efficient Computer Drum [181] --
10.6 Making a Road System One-Way [182] --
10.7 Ranking the Participants in a Tournament [185] --
NETWORKS --
11.1 Flows [191] --
11.2 Cuts [194] --
11.3 The Max-Flow Min-Cut Theorem Applications [196] --
11.4 Menger’s Theorems [203] --
11.5 Feasible Flows [206] --
12 THE CYCLE SPACE AND BOND SPACE --
12.1 Circulations and Potential Differences [212] --
12.2 The Number of Spanning Trees [218] --
Applications --
12.3 Perfect Squares [220] --
Appendix I --
Hints to Starred Exercises [227] --
Appendix II --
Four Graphs and a Table of their Properties [232] --
Appendix III --
Some Interesting Graphs [234] --
Appendix IV --
Unsolved Problems [246] --
Appendix V --
Suggestions for Further Reading [254] --
Glossary of Symbols [257] --
Index [261] --
MR, 54 #117
Click on an image to view it in the image viewer
There are no comments on this title.