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.

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