prev

next

out of 577

View

600Download

80

Tags:

Embed Size (px)

DESCRIPTION

Book on CombinatoricsMath

This pageintentionally left

blank

Copyright 2007, New Age International (P) Ltd., PublishersPublished by New Age International (P) Ltd., Publishers

All rights reserved.No part of this ebook may be reproduced in any form, by photostat, microfilm,xerography, or any other means, or incorporated into any information retrievalsystem, electronic or mechanical, without the written permission of the publisher.All inquiries should be emailed to rights@newagepublishers.com

PUBLISHING FOR ONE WORLD

NEW AGE INTERNATIONAL (P) LIMITED, PUBLISHERS4835/24, Ansari Road, Daryaganj, New Delhi - 110002Visit us at www.newagepublishers.com

ISBN (13) : 978-81-224-2890-2

IIIIIDedicated this bookDedicated this bookDedicated this bookDedicated this bookDedicated this book

tototototoOMOMOMOMOM

Maha Kaali MaataMaha Kaali MaataMaha Kaali MaataMaha Kaali MaataMaha Kaali Maata&&&&&mymymymymy

PPPPParentsarentsarentsarentsarents

(v)

This pageintentionally left

blank

PREFACE

This text has been carefully designed for flexible use. It is primarily designed to provide anintroduction to some fundamental concepts in COMBINATORICS AND GRAPH THEORY for post-graduate (Master of Computer Applications M.C.A.) students.

Each topic is divided into sections of approximately the same length, and each section is dividedinto subsections that form natural blocks of material for teaching. Instructors can easily pace theirlectures using these blocks.

All definitions and theorems in this text are stated extremely carefully so that students will ap-preciate the precision of language and rigor needed in mathematical sciences. Proofs are motivated anddeveloped slowly, their steps are all carefully justified. Recursive definitions are explained and usedextensively.

The writing style in this book is direct and pragmatic. Precise mathematical language is usedwithout excessive formalism and abstraction. Care has been taken to balance the mix of notation andwords in mathematical statements.

Over 1000 problems are used to illustrate concept, related to different topics, and introduceapplications. In most examples, a question is first posed, then its solution is presented with appropriatedetails. The applications included in this text demonstrate the utility of combinatorics and Graph Theoryin the solution of real world problem. This text includes applications to wide-variety of areas, includingcomputer science and engineering.

There are over 900 exercises in the text with many different types of questions posed. There is anample supply of straight forward exercises that develop basic skills, a large number of intermediateexercises and many challenging (problem sets) exercise sets. Problem sets are stated clearly andunambiguously, and all are carefully graded for various levels of difficulty. It will be honest on my partto accept that it is not possible to include every thing in one book.

Many people contributed directly or indirectly to the completion of this book. Thanks are due tomy friends who were able to convince me that I should write this book.

I am grateful to my students, who always encouraged me and many times thanked me for writingthis book.

Special thanks to my teachers, who made me realize that I can indeed write a book onCombinatorial Mathematics. Some pulled me down, some encouraged me and some gave meconstructive suggestions. I am grateful to all of them.

(vii)

I specially thank to Mr. K. Krishna (president); Mr. R. Rajagopal (secretary); Mr. Lokanath(Treasurer); Dr. Rukhmangada (Chairman); Mr. Kuppaswamy (Convener); Mr. Subramanyam(Manager); K.S. Institute of Technology, Bangalore; who always encouraged me and gave me constructivesuggestions. I am grateful to all of them.

I an greateful to my parents; Grandmother; maternal uncle; elder sister, elder brothers; whotolerated me all along while I devoted my time to completing this book.

I express my sincere thanks to the chairman Mr. R.K. Gupta, the Managing Director Mr. SaumyaGupta, the Marketing Manager Mr. V.R. Babu and Mr. R. Srinath and Lucknow Branch ManagerMr. L.N. Mishra of M/s New Age International (P) Limited, publishers, New Delhi, for their responsiblework-done at every level in the publication of the book with high production standards.

Healthy criticism and suggestions to improve the quality and standards of the text are mostwelcome.

Bangalore, March 2007

C. Vasudev

(viii)

This pageintentionally left

blank

This pageintentionally left

blank

CONTENTS

Preface (vii)

Unit 1. Counting Principles and Generating Functions 1151

1.1 The Rules of Sum and Product 1

1.2 Permutations 12

1.3 Combinations 25

1.4 Permutations and Combinations with Repetitions 36

1.5 Probability 52

1.6 Ramsey Number 61

1.7 The Catalan Numbers 65

1.8 Group 67

1.9 Generating Function 86

Problem set 1.1 138

Problem set 1.2 140

Problem set 1.3 146

Problem set 1.4 150

Answers 151

Unit 2. Recurrence Relations 152219

2.1 The First-order Linear Recurrence Relation 157

2.2 The Second-order Linear Homogeneous Recurrence relation with

Constant coefficients 162

2.3 The Non-Homogeneous Recurrence relations 163

2.4 The method of Generating Functions 188

Problem set 2.1 212

Problem set 2.2 215

Answers 218

Unit 3. Graphs and Trees 220365

3.1 What is a graph ? 220

3.2 Directed and Undirected graphs 221

3.3 Basic Terminologies 222(xi)

(xii)

3.4 Degree of a vertex 223

3.5 Isolated and Pendent vertices 224

3.6 Types of Graphs 240

3.7 Subgraphs 245

3.8 Graphs Isomophism 247

3.9 Operations of graphs 267

3.10 Connected and Disconnected graphs 271

3.11 Walks, paths and circuits 278

3.12 Eulerian graphs 284

3.13 Fleurys Algorithm 294

3.14 Hamiltonian graphs 298

3.15 Tree 310

3.16 Spanning tree 311

3.17 Rooted tree 311

3.18 Binary Trees 312

3.19 Counting trees 333

3.20 Minimal spanning trees 341

Problem set 3.1 354

Problem set 3.2 360

Answers 364

Unit 4. Cutsets, Network flows and Planar Graphs 366452

4.1 Cut vertex, cut set and bridge 366

4.2 Connected or weakly connected 366

4.3 Unilaterally connected 366

4.4 Strongly connected 367

4.5 Connectivity 367

4.6 Edge connectivity 367

4.7 Vertex connectivity 374

4.8 Transport networks 382

4.9 Max-flow min-cut theorem 386

4.10 Combinatorial and Geometric graphs 387

4.11 Planar graphs 388

4.12 Kuratowskis Graphs 389

4.13 Homeomorphic Graphs 389

4.14 Region 390

4.15 Maximal planar graphs 391

4.16 Subdivision graphs 391

4.17 Inner vertex set 391

4.18 Outer planar graphs 392

4.19 Crossing Number 392

4.20 Bipartite graph 393

4.21 Eulers Formula 395

4.22 Three utility problem 405

4.23 Kuratowskis theorem 416

4.24 Detection of planarity of a graph 417

4.25 Dual of a planar graph 423

4.26 Knigsbergs Brideg problem 432

4.27 Representation of graphs 432

Problem set 4.1 441

Problem set 4.2 447

Answers 450

Unit 5. Coloring, Digraphs and Enumeration 453559

5.1 Graph coloring 453

5.2 Chromatic polynomial 455

5.3 Decomposition theorem 457

5.4 Colour problem 482

5.5 Matching theory 486

5.6 Coverings 499

5.7 Independence 499

5.8 Vertex covering 500

5.9 Edge covering 500

5.10 Critical points and critical lines 501

5.11 Line-core and point-core 501

5.12 Digraph Definition 502

5.13 Types of Digraphs 504

5.14 Connected digraphs 507

5.15 Condensation 508

5.16 Reachability 508

5.17 Orientable graph 509

5.18 Accessibility 509

5.19 Arborescence 509

5.20 Hand shaking dilemma 510

(xiii)

5.21 Incidence matrix of a digraph 511

5.22 Circuit matrix of a digraph 511

5.23 Adjacency matrix of a digraph 511

5.24 Nullity of a matrix 528

5.25 Types of Enumeration 533

5.26 Labeled graphs 534

5.27 Partitions 537

5.28 Generating functions 537

5.29 Counting unlabeled trees 538

5.30 Rooted unlabeled trees 538

5.31 Counting series for un 539

5.32 Free unlabeled trees 539

5.33 Centroid 540

5.34 Permutation 540

5.35 Equivalence classes of functions 543

Problem set 5.1 551

Problem set 5.2 556

Answers 563

Index 568570

(xiv)

1.1 THE RULES OF SUM AND PRODUCT

1.1.1 Sum Rule. (The Principle of disjunctive Counting)

If a first task can be done in n1 ways and a second task in n2 ways, and if these tasks cannot bedone at the same time, then there are n1 + n2 ways to do one of these tasks.

In other words. If a set X is the union of disjoint non empty subsets S1, S2, ......, Sn, then

| X | = | S1 | + | S2 | + ...... + | Sn |.

1.1.2 Product Rule. (The principle of Sequential Counting)

Suppose that a procedure can be broken down into a sequence of two tasks. If there are n1 waysto do the first task and n2 ways to do the second task after the first task has been done, then there are n1n2ways to do the procedure.

In other words, If S1, S2, ......, Sn are non empty sets, then the number of elements in the cartesian

product S1 S2 ...... Sn is the product 1

| S |=

n ii

. That is, | S1 S2 ...... Sn | = 1

| S |=

n ii

.

Problem 1.1. A student can choose a computer project from one of three lists. The