Advanced Graph Theory
Autor Santosh Kumar Yadaven Limba Engleză Hardback – 17 iun 2023
Subliniem, încă de la început, că Advanced Graph Theory este construită pe o metodologie riguroasă, menită să servească drept suport principal pentru cursurile universitare de matematică discretă. Structura volumului urmărește o progresie logică: primele secțiuni sunt dedicate fundamentelor — de la definirea grafurilor simple și a gradelor nodurilor, până la explorarea drumurilor, ciclurilor și grafurilor biconexe. Remarcăm atenția deosebită acordată capitolului de operații algebrice, unde Santosh Kumar Yadav detaliază procese precum compoziția, fuziunea sau calculul rangului și nulității, elemente esențiale pentru modelarea matematică avansată.
Din punct de vedere pedagogic, autorul optează pentru o prezentare care îmbină rigoarea demonstrativă cu un context istoric relevant, facilitând astfel înțelegerea evoluției conceptelor. Un aspect distinctiv al acestei ediții din 2023 îl reprezintă setul de exerciții: acestea nu sunt simple aplicații directe, ci probleme complexe, marcate vizual pentru a semnala un nivel ridicat de dificultate. Considerăm că această abordare transformă lectura dintr-una pasivă într-un proces activ de rezolvare de probleme.
Cititorii familiarizați cu Graph Theory and Its Applications de Jonathan L. Gross vor aprecia în acest volum focalizarea mai accentuată pe rigoarea algebrică și pe structura modulară care permite adaptarea conținutului atât pentru cursuri semestriale, cât și pentru sesiuni anuale extinse. În contextul operei autorului, lucrarea de față rafinează conceptele introduse în Discrete Mathematics with Graph Theory, oferind o specializare necesară cercetătorilor și studenților la nivel postuniversitar care doresc să depășească nivelul introductiv al matematicii discrete.
Preț: 569.63 lei
Preț vechi: 670.15 lei
-15%
Carte disponibilă
Livrare economică 28 mai-11 iunie
Specificații
ISBN-10: 3031225619
Pagini: 285
Ilustrații: XIV, 285 p. 152 illus.
Dimensiuni: 168 x 240 mm
Greutate: 0.59 kg
Ediția:2023
Editura: Springer International Publishing
Colecția Springer
Locul publicării:Cham, Switzerland
De ce să citești această carte
Recomandăm acest volum studenților și cadrelor didactice care caută un instrument de studiu structurat după standardele academice internaționale. Advanced Graph Theory oferă nu doar teorie, ci și o metodologie de lucru prin exerciții provocatoare, fiind ideală pentru pregătirea examenelor de masterat sau pentru cercetare în informatică și matematică aplicată.
Despre autor
Santosh Kumar Yadav este un autor prolific de literatură academică, specializat în matematică discretă și etica cercetării. Experiența sa didactică se reflectă în claritatea cu care abordează subiecte complexe în lucrări precum Discrete Mathematics with Graph Theory. Dincolo de matematică, interesele sale academice acoperă integritatea academică, publicând Research and Publication Ethics, dar și domenii interdisciplinare, fapt ce demonstrează o capacitate de analiză riguroasă aplicabilă în diverse ramuri științifice. În prezentul volum, Yadav își folosește expertiza pentru a oferi o resursă fundamentală în studiul grafurilor.
Descriere scurtă
The present book is based on the curriculum of undergraduate and postgraduate courses of universities in India and abroad. Every effort is made to present the various topics in the theory of graphs in a logical manner with adequate historical background and include suitable figures to illustrate concepts and results ideally. The formidable exercises, neither easy nor straightforward, are bold faced and highlighted. The theory portion of each chapter is studied thoroughly as it helps solve many of the problems with comparative ease. Selected material from this book is used for a semester course on graph theory, while the entire book serves for a whole session course.
Cuprins
1. Basics of Graph Theory 1–50
1.1 Introduction 1
1.2 Graph! What is it? 2
1.2.1 Simple Graph 2
1.2.2 Graph 4
1.2.3 Loops 7
1.2.4 Degree of Vertices 7
1.2.5 Equivalence Relation 10
1.2.6 Random Graph Model 13
1.2.7 Isolated Vertex, Pendent Vertex and Null Graph 13
1.3 Digraphs 14
1.4 Path, Trail, Walk and Vertex Sequence 17
1.5 Subgraph 18
1.6 Circuit and Cycle 18
1.7 Cycles and Multiple Paths 19
1.8 Connected Graph 19
1.9 Spanning Subgraph and Induced Subgraph 20
1.10 Eulerian Graph (Eulerian Trail and Circuit) 21
1.11 Hamiltonian Graph 22
1.12 Biconnected Graph 22
1.13 Algebraic Terms and Operations used in Graph Theory 23
1.13.1 Graphs Homomarphism and Graph Isomorphism 23
1.13.2 Union of two Graphs 25
1.13.3 Intersection of two Graphs 25
1.13.4 Addition of two Graphs 25
1.13.5 Direct Sum or Ring Sum of two Graphs 26
1.13.6 Product of two Graphs 26
1.13.7 Composition of two Graphs 27
1.13.8 Complement of a Graph 27
1.13.9 Fusion of a Graph 28
1.13.10 Rank and Nullity 28
1.13.11 Adjacency Matrix 29
1.13.12 Some Important Theorems 29
1.14 Some Popular Problems in Graph Theory 34
1.14.1 Tournament Ranking Problem 34
1.14.2 The Königsberg Bridge Problem 36
1.14.3 Four Colour Problem 36
1.14.4 Three Utilities Problem 37
1.14.5 Traveling - Salesman Problem 37
1.14.6 MTNL’S Networking Problem 38
1.14.7 Electrical Network Problems 38
1.14.8 Satellite Channel Problem 39
1.15 Applications of Graphs 40
1.16 Worked Examples 40
Summary 46
Exercise 48
Suggested Readings 50
2. Trees 51–88
2.1 Introduction 51
2.2 Definitions of Tree 52
2.3 Forest 53
2.4 Rooted Graph 54
2.5 Parent, Child, Sibling and Leaf 55
2.6 Rooted Plane Tree 55
2.7 Binary Trees 61
2.8 Spanning Trees 63
2.9 Breadth – First Search and Depth – First Search 64
2.10 Minimal Spanning Trees 71
2.10.1 Kruskal’s Algorithm (for Finding a Minimal Spanning Tree) 71
2.10.2 Prim’s Algorithm 76
2.10.3 Dijkstra’s Algorithm 78
2.10.4 The Floyd-Warshall Algorithm 79
2.11 Directed Trees 80
2.12 Solved Examples 81
Summary 86
Exercise 87
Suggested Readings 88
xii Advanced Graph Theory
3. Planar Graphs 89–110
3.1 Introduction 89
3.2 Geometrical Representation of Graphs 90
3.3 Bipertite Graph 92
3.4 Homeomorphic Graph 93
3.5 Kuratowski’s Graphs 94
3.6 Dual Graphs 98
3.7 Euler’s Formula 100
3.8 Outerplanar Graphs 102
3.8.1 k-outerplanar Graphs 103
3.9 Solved Examples 103
Summary 108
Exercise 109
Suggested Readings 109
4. Directed Graphs 111–140
4.1 Introduction 111
4.2 Directed Paths 113
4.3 Tournament 114
4.4 Directed Cycles 116
4.5 Acyclic Graph 119
4.6 Di-Orientable Graph 120
4.7 Applications of Directed Graphs 124
4.7.1 Job Sequencing Problem 124
4.7.2 To Design an Efficient Computer Drum 125
4.7.3 Ranking of the Participants in a Tournament 127
4.8 Network Flows 129
4.9 Improvable Flows 130
4.10 Max-Flow Min-Cut Theorem 131
4.11 k-flow 133
4.12 Tutte’s Problem 134
Summary 136
Exercise 137
Suggested Readings 139
5. Matching and Covering 141–170
5.1 Introduction 141
5.2 Matching and Covering in Bipertite Graphs 143
5.2.1 Covering 147
5.3 Perfect Matching 149
Contents xiii
5.4 Factor-critical Graph 153
5.5 Complete Matching 155
5.6 Matrix Method to Find Matching of a Bipertite Graph 157
5.7 Path Covers 160
5.8 Applications 161
5.8.1 The Personnel Assignment Problem 161
5.8.2 The Optimal Assignment Problem 165
5.8.3 Covering to Switching Functions 166
Summary 168
Exercise 168
Suggested Readings 170
6. Colouring of Graphs 171–200
6.1 Introduction 171
6.2 Vertex Colouring 173
6.3 Chromatic Polynomial 174
6.3.1 Bounds of the Chromatic Number 175
6.3.2 Clique 175
6.4 Exams Scheduling Problem 179
6.5 Edge Colouring 186
6.6 List Colouring 190
6.7 Greedy Colouring 192
6.8 Applications 196
6.8.1 The Time Table Problem 196
6.8.2 Scheduling of Jobs 196
6.8.3 Ramsey Theory 197
6.8.4 Storage Problem 197
Summary 198
Exercise 198
Suggested Readings 199
7. Colouring of Graphs 201–220
7.1 Introduction 201
7.2 Independent Sets and Cliques 203
7.3 Original Ramsey’s Theorems 204
7.4 Induced Ramsey Theorems 208
7.5 Applications 213
7.5.1 Schur’s Theorem 213
7.5.2 Geometry Problem 214
Summary 218
Exercise 218
Suggested Readings 219
xiv Advanced Graph Theory
8. Enumeration and Pölya’s Theorem 221–242
8.1 Introduction 221
8.2 Labelled Counting 222
8.3 Unlabelled Counting 223
8.4 Generating Function 225
8.5 Partitions of a Finite Set 228
8.6 The Labelled counting Lemma 230
8.7 Permutations 231
8.7.1 Cycle Index 232
8.8 Pölya’s Enumeration Theorem 232
8.9 Burnside’s Lemma 235
Summary 240
Exercise 241
Suggested Readings 242
9. Spectral Properties of Graphs 243–252
9.1 Introduction 243
9.2 Spectrum of the Complete Graph Kn 245
9.3 Spectrum of the Cycle Cn 246
9.4 Spectra of Regular Graphs Theorem 246
9.5 Theorem of the Spectrum of the Complement of a Regular Graph 247
9.6 Sachs’ Theorem 248
9.7 Cayley Graphs and Spectrum 250
Summary 251
Exercise 252
Suggested Readings 252
10. Emerging Trends in Graph Theory 253–280
10.1 Introduction 253
10.2 Perfect Graphs 253
10.3 Chordal Graphs Revisited 257
10.4 Intersection Representation 257
10.5 Tarjan’s Theorem (1976) 258
10.6 Perfectly Orderable Graph 261
10.7 Minimal Imperfect Graph 261
10.7.1 Star-cutset Lemma 261
10.8 Imperfect Graphs 262
10.9 Strong Perfect Graph Coryecture 266
10.10 Hereditary Family 267
10.11 Matroids 267
Contents xv
10.11.1 Hereditary Systems 268
10.11.2 Rank Function in Cycle Matroids 269
10.12 Basic Properties of Matroids 270
10.13 Span Function 271
10.14 Encodings of Graphs 275
10.15 Ramanujan Graphs 276
Exercise 278
Suggested Readings 279
References 281–282
Index 283–286
Notă biografică
Dr.Santosh Kumar Yadav has been associated with academic and research activities for more than 25 years. He has been an active and dynamic administrator as the director (Academic and Research) at J.J.T. University, Rajasthan. As an academician, he has taught undergraduates and postgraduate classes in different premier institutions including various colleges of Delhi University in different capacities.
Caracteristici
Contains formidable exercises which are neither easy nor straight forward
Includes suitable figures to illustrate concepts and results ideally