Graph theory is an area in discrete mathematics which studies configurations (called graphs) involving a set of vertices interconnected by edges. This book is intended as a general introduction to graph theory and, in particular, as a resource book for junior college students and teachers reading and teaching the subject at H3 Level in the new Singapore mathematics curriculum for junior college. The book builds on the verity that graph theory at this level is a subject that lends itself well to the development of mathematical reasoning and proof.
Author(s): K. M. Koh; F. M. Dong; E. G. Tay
Publisher: World Scientific Publishing Company
Year: 2007
Language: English
Pages: 245
Tags: Математика;Дискретная математика;Теория графов;
Contents......Page 12
Preface......Page 6
Notation......Page 10
1.1 The Konigsberg bridge problem......Page 16
1.2 Multigraphs and graphs......Page 17
Exercise 1.2......Page 26
1.3 Vertex degrees......Page 29
Exercise 1.3......Page 38
1.4 Paths, cycles and connectedness......Page 41
Exercise 1.4......Page 49
2.1 Isomorphic graphs and isomorphisms......Page 52
2.2 Testing isomorphic graphs......Page 56
Exercise 2.2......Page 62
2.3 Subgraphs of a graph......Page 64
Exercise 2.3......Page 72
2.4 The complement of a graph......Page 77
Exercise 2.4......Page 81
3.1 Bipartite graphs......Page 84
Exercise 3.1......Page 94
3.2 Trees......Page 97
Exercise 3.2......Page 102
3.3 (*) Spanning trees of a graph......Page 104
Exercise 3.3......Page 109
4.1 The four-colour problem......Page 110
4.2 Vertex-colourings and chromatic number......Page 111
Exercise 4.2......Page 116
4.3 Enumeration of chromatic number......Page 117
Exercise 4.3......Page 122
4.4 Greedy colouring algorithm......Page 128
Exercise 4.4......Page 130
4.5 An upper bound for the chromatic number and Brooks’ theorem......Page 134
Exercise 4.5......Page 136
Exam Timetable......Page 138
Chemical Storage......Page 140
Exercise 4.6......Page 142
5.1 Introduction......Page 144
5.2 Matchings......Page 146
Exercise 5.2......Page 150
5.3 Hall’s theorem......Page 154
Exercise 5.3......Page 158
5.4 System of distinct representatives......Page 162
Exercise 5.4......Page 167
6.1 Eulerian multigraphs......Page 170
Exercise 6.1......Page 173
6.2 Characterization of Eulerian multigraphs......Page 174
Exercise 6.2......Page 182
6.3 Around the world and Hamiltonian graphs......Page 186
6.4 A necessary condition for a graph to be Hamiltonian......Page 192
Exercise 6.4......Page 195
6.5 Two sufficient conditions for a graph to be Hamiltonian......Page 199
Exercise 6.5......Page 203
7.1 Digraphs......Page 206
Exercise 7.1......Page 210
The in-degree and out-degree of a vertex......Page 212
Isomorphic digraphs......Page 214
Connectedness......Page 215
Exercise 7.2......Page 218
7.3 Tournaments......Page 224
Transitive tournaments......Page 225
Exercise 7.3......Page 228
7.4 Two properties of tournaments......Page 231
Exercise 7.4......Page 236
References......Page 238
Books Recommended......Page 240
Index......Page 242
