Discrete Maths CIMT

of 270

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
PDF
270 pages
4 downs
230 views
Share
Description
Discrete mathematics textbook.
Tags
Transcript
  Discrete Mathematics  Preface  PREFACE The latter half of the 20th century has seen rapid advances in thedevelopment of suitable techniques for solving decision-makingproblems. A catalyst for these advances has been the revolutionin computing. Even the smallest business is able to obtain,relatively cheaply, significant computer power. This has led toa rapid increase of research into discrete  or finite  mathematics.The vast majority of mathematical developments over the past300 years since Newton have concentrated on advances in ourunderstanding and application of continuous  mathematics, and itis only recently that parallel advances in discrete  mathematics havebeen sought. Much, although not all, of the mathematics in this textis based on developments this century which are still continuing.The aim of this text is to give a comprehensive treatment of the majortopics in discrete mathematics, emphasising their applicability toproblems in a highly technological world.This text has been produced for students and includes examples,activities and exercises. It should be noted that the activities are not optional but are an important part of the learning philosophy in whichyou are expected to take a very active part. The text integratesã  Exposition in which the concept is explained;ã  Examples which show how the techniques are used;ã  Activities which either introduce new concepts orreinforce techniques;ã  Discussion which are essentially 'stop and think' Points points, where discussion with otherstudents and teachers will be helpful;ã  Exercises at the end of most sections in order toprovide further practice;ã  Miscellaneous at the end of each chapter which provide Exercises opportunities for reinforcement of themain points of the chapter.Note that answers to the exercises are given at the back of thebook. You are expected to have a calculator available throughoutyour study of this text and occasionally to have access to a computer.Some of the sections, exercises and questions are marked with anasterisk (*). This means that they are either not  central to thedevelopment of the topics in this text and can be omitted withoutcausing problems, or they are regarded as particularly challenging.Any enquiries regarding this textshould be addressed toMathematics EnhancementProgrammeCIMT, Faculty of EducationUniversity of PlymouthDouglas AvenueExmouth EX8 2ATTel:01395 255521Fax:01395 255422 Discussion points are writtenin a special typeface asillustrated here.  Contents Discrete Mathematics  CONTENTS PREFACEChapter 1 GRAPHS 1.0 Introduction 11.1 The language of graphs 11.2 Isomorphism 31.3 Walks, trails and paths 71.4 Cycles and Eulerian trails 81.5 Hamiltonian cycles 91.6 Trees 101.7 Coloured cubes 131.8 Miscellaneous Exercises 15 Chapter 2 TRAVEL PROBLEMS 2.0 Introduction 172.1 The shortest path problem 172.2 The minimum connector problem 212.3 Kruskal's algorithm 222.4 Prim's algorithm 252.5 The travelling salesman problem 272.6 The Chinese postman problem 322.7 Local applications 352.8 Miscellaneous Exercises 35 Chapter 3 ENUMERATION 3.0 Introduction 393.1 The multiplicative principle 403.2 Arrangements 423.3 Making choices 463.4 Further arrangements 493.5 Simple probability 523.6 Subsets 533.7 The pigeonhole principle 553.8 Inclusion and exclusion 563.9 Unequal division 583.10Partitions 613.11Derangements 623.12Miscellaneous Exercises 65 Chapter 4 INEQUALITIES 4.0 Introduction 674.1 Fundamentals 684.2 Graphs of inequalities 704.3 Classical inequalities 734.4 Isoperimetric inequalities 774.5 Miscellaneous Exercises 81 Chapter 5 LINEAR PROGRAMMING 5.0 Introduction 835.1 Formation of linear programmingproblems 845.2 Graphical solution 875.3 Simplex method 915.4 Simplex tableau 955.5 Miscellaneous Exercises 98 Chapter 6 PLANAR GRAPHS 6.0 Introduction 1016.1 Plane drawings 1026.2 Bipartite graphs 1036.3 A planarity algorithm 1046.4 Kuratowski's theorem 1086.5 Miscellaneous Exercises 109 Chapter 7 NETWORK FLOWS 7.0 Introduction 1117.1 Di-graphs 1127.2 Max flow - min cut 1137.3 Finding the flow 1147.4 Labelling flows 1157.5 Super sources and sinks 1187.6 Minimum capacities 1197.7 Miscellaneous Exercises 121 Chapter 8 CODES IN EVERYDAY USE 8.0 Introduction 1258.1 Historical perspective 1258.2 Check digits 127  Contents  Discrete Mathematics  8.3 Bar code design 1288.4 Postcodes 1328.5 Telephone numbers 1338.6 Computing codes 1348.7 Miscellaneous Exercises 135 Chapter 9 THEORY OF CODES 9.0 Introduction 1379.1 Noise 1379.2 Error correction 1399.3 Parity check matrix 1439.4 Decoding using parity check matrix1479.5 Cyclic codes 1499.6 Miscellaneous Exercises 151 Chapter 10LOGIC 10.0Introduction 15310.1The nature of logic 15410.2Combining propositions 15610.3Boolean expressions 15910.4Compound propositions 16110.5What are the implications? 16210.6Recognising equivalence 16410.7Tautologies and contradictions 16510.8The validity of an argument 16710.9Miscellaneous Exercises 168 Chapter 11BOOLEAN ALGEBRA 11.0Introduction 17111.1Combinatorial circuits 17111.2When are circuits equivalent? 17411.3Switching circuits 17511.4Boolean algebra 17811.5Boolean functions 18011.6Minimisation with NAND gates 18311.7Full and half adders 18411.8Miscellaneous Exercises 187 Chapter 12CRITICAL PATH ANALYSIS 12.0Introduction 18912.1Activity networks 19012.2Algorithm for constructing activitynetworks 19212.3Critical path 19612.4Miscellaneous Exercises 200 Chapter 13SCHEDULING 13.0Introduction 20313.1Scheduling 20413.2Bin packing 20713.3Knapsack problem 21113.4Miscellaneous Exercises 215 Chapter 14DIFFERENCE EQUATIONS 1 14.0Introduction 21714.1Recursion 21814.2Iteration 22014.3First order difference equations 22214.4Loans 22714.5Non-homogeneous linear equations23014.6A population problem 23114.7Miscellaneous Exercises 234 Chapter 15 DIFFERENCE EQUATIONS 2 15.0Introduction 23715.1General solutions 23815.2Equations with equal roots 24215.3A model of the economy 24515.4Non-homogeneous equations 24615.5Generating functions 25115.6Extending the method 25315.7Miscellaneous Exercises 256 APPENDICES 257 ANSWERS 265 INDEX 281    1 Chapter 1 Graphs  1 GRAPHS Objectives After studying this chapter you shouldãbe able to use the language of graph theory;ãunderstand the concept of isomorphism;ãbe able to search and count systematically;ãbe able to apply graph methods to simple problems. 1.0Introduction This chapter introduces the language and basic theory of graphs.These are not graphs drawn on squared paper, such as you metduring your GCSE course, but merely sets of points joined by lines.You do not need any previous mathematical knowledge to studythis chapter, other than an ability to count and to do very simplearithmetic.Although graph theory was first explored more than two hundredyears ago, it was thought of as little more than a game formathematicians and was not really taken seriously until the latetwentieth century. The growth in computer power, however, ledto the realisation that graph theory can be applied to a widerange of industrial and commercial management problems of considerable economic importance.Some of the applications of graph theory are studied in later chapters of this book. Chapter 2, for example, looks at several different problemsinvolving the planning of 'best' networks or routes, while Chapter 6considers the question of planarity (very important in designingmicrochips and other electronic circuits). Chapter 7 deals withproblems to do with the flow of vehicles through a road system or oilthrough a pipe, and Chapters 12 and 13 show how to analyse acomplex task and determine the most efficient way in which it can bedone. All these applications, however, depend on an understanding of the basic principles of graph theory. 1.1The language of graphs A graph  is defined as consisting of a set of vertices  (points) anda set of edges  (straight or curved lines; alternatively called arcs):each edge joins one vertex to another, or starts and ends at thesame vertex.
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks