Discrete Algorithmic Mathematics, Third Edition
Written in a lively, clear style that talks to the reader, this book is unique for its emphasis on algorithmics and the inductive and recursive paradigms as central mathematical themes.
TABLE OF CONTENTS Discrete Algorithmic Mathematics, Third Edition
Chapter 3: Graphs and Trees
3.1 Examples and Terminology
One way to judge the importance of a branch of mathematics is by the variety of unrelated problems to which it can be applied. By this measure, the subject of this chapter is surely one of the most important in discrete mathematics. To illustrate, we begin by presenting three quite different problems to which graph theory can be applied. One of these is a children s puzzle; one is a problem on the properties of sequences; and the last is a common problem in computer science. (By the way, the first example in this book (in the Prologue) also was an example of graph theory.)
In presenting these three problems we ll introduce informally some of the terminology of graph theory. We think you will understand these examples without much elaboration of the terminology. Later in this section we ll formalize the terminology used in the examples as well as some of the other terminology of graph theory.
First we ll state the three problems and then consider their solutions.
Example 1
The Wolf, Cabbage, Goat and Farmer Problem
A farmer is bringing a wolf, a cabbage and a goat to market. The farmer arrives with all three at one side of a river that they need to cross. The farmer has a boat which can accommodate only one of the three. (It s a big cabbage.) But if the wolf is left alone with the goat, the wolf will eat the goat. And if the goat is left alone with...
Copyright A K Peters, Ltd. 2004 under license agreement with Books24x7
