Combinatorics and graph theory

About the Book: This text has been carefully designed for flexible use for First Semester M.C.A. course of Uttar Pradesh Technical University (U.P.T.U.), and it contains the following features: Precise mathematical language is used without excessive formalism and abstraction. Over 900 exercises (problem sets) in the text with many different types of questions posed. Care has been taken to balance the mix of notation and words in mathematical statements. Problem sets (exercises) are stated clearly and unambiguously and all are carefully graded for various levels of difficulty. Contents. Cover......Page 1 Preface ......Page 8 Contents......Page 12 1.1 The Rules of Sum and Product......Page 16 1.2 Permutations......Page 27 1.3 Combinations......Page 40 1.4 Permutations and Combinations with Repetitions......Page 51 1.5 Probability......Page 67 1.6 Ramsey Number......Page 76 1.7 The Catalan Numbers......Page 80 1.8 Group......Page 82 1.9 Generating Function......Page 101 Problem Set 1.1......Page 153 Problem Set 1.2......Page 155 Problem Set 1.3......Page 158 Problem Set 1.4......Page 160 Answers......Page 162 2.1 The First-Order Linear Recurrence Relation......Page 167 2.2 The Second-Order Linear Homogeneous Recurrence Relation with Constant Coefficients ......Page 177 2.3 The Non Homogeneous Recurrence Relations......Page 178 2.4 the Method of Generating Functions......Page 203 Problem Set 2.1......Page 227 Problem Set 2.2......Page 230 Answers......Page 233 3.1 What is a Graph? Definition......Page 235 3.2 Directed and Undirected Graphs......Page 236 3.3 Basic Terminologies ......Page 237 3.4 Degree of a Vertex......Page 238 3.5 Isolated and Pendent Vertices......Page 239 3.6 Types of Graphs......Page 255 3.7 Subgraphs......Page 260 3.8 Graphs Isomorphism ......Page 262 3.9 Operations of Graphs......Page 279 3.10 Connected and Disconnected Graphs ......Page 286 3.11 Walks, Paths and Circuits......Page 293 3.12 Eulerian Graphs......Page 299 3.13 Fleury's Algorithm......Page 309 3.14 Hamiltonian Graphs......Page 313 3.15 Tree......Page 325 3.17 Rooted Tree......Page 326 3.18 Binary Trees......Page 327 3.19 Counting Trees......Page 348 3.20 Minimal Spanning Trees......Page 356 Problem Set 3.1......Page 369 Problem Set 3.2......Page 375 Answers......Page 379 4.3 Unilaterally Connected......Page 381 4.7 Vertex Connectivity......Page 382 4.8 Transport Networks......Page 389 4.9 Max-Flow Min-Cut Theorem......Page 395 4.10 Combinatorial and Geometric Graphs (Representation) ......Page 402 4.11 Planar Graphs......Page 403 4.13 Homeomorphic Graphs......Page 404 4.14 Region......Page 405 4.17 Inner Vertex Set......Page 406 4.19 Crossing Number......Page 407 4.20 Bipartite Graph......Page 408 4.21 Euler's Formula ......Page 410 4.22 Three Utility Problem......Page 420 4.23 Kuratowski's Theorem ......Page 431 4.24 Detection of Planarity of a Graph......Page 432 4.25 Dual of a Planar Graph......Page 438 4.27 Representation of Graphs......Page 447 Problem Set 4.1......Page 456 Problem Set 4.2......Page 461 Answers......Page 465 5.1 Graph Coloring......Page 468 5.2 Chromatic Polynomial......Page 470 5.3 Decomposition Theorem......Page 472 5.4 Color Problem......Page 497 5.5 Matching Theory......Page 501 5.7 Independence......Page 514 5.9 Edge Covering......Page 515 5.11 Line-core and Point-Core......Page 516 5.12 Digraph Definition......Page 517 5.13 Types of Digraphs......Page 519 5.14 Connected Digraphs......Page 522 5.16 Reachability......Page 523 5.19 Arborescence......Page 524 5.20 Hand Shaking Dilemma ......Page 525 5.23 Adjacency Matrix of a Digraph......Page 526 5.24 Nullity of a Matrix......Page 543 5.25 Types of Enumeration......Page 548 5.26 Labeled Graphs ......Page 549 5.28 Generating Functions......Page 552 5.30 Rooted Unlabeled Trees ......Page 553 5.32 Trees Unlabeled Trees ......Page 554 5.34 Permutation......Page 555 5.35 Equivalence Classes of Functions......Page 558 Problem Set 5.1......Page 566 Problem Set 5.2......Page 571 Answers......Page 574 Index......Page 575