EppDM5eMetric 10 04

CHAPTER 10
THEORY OF GRAPHS AND

TREES
Copyright © Cengage Learning. All rights reserved.

Trees: Examples and Basic
10.4
Properties
Copyright © Cengage Learning. All rights reserved.

Trees: Examples and Basic Properties
In mathematics, a tree is a connected graph that does not
contain any circuits. Mathematical trees are similar in
certain ways to their botanical namesakes.
3
Example 10.4.1 – Trees and Non-trees
All the graphs shown in Figure 10.4.1 are trees, whereas
those in Figure 10.4.2 are not.
Trees. All the graphs in (a)–(d) are connected and circuit-free.

Figure 10.4.1
4
Example 10.4.1 – Trees and Non-trees continued
Non-trees. The graphs in (a), (b), and (c) all have circuits, and the graph in (d) is not connected.
Figure 10.4.2
5
Examples of Trees
6
Example 10.4.2 – A Decision Tree
During orientation week, a college administers a
mathematics placement exam to all entering students. The
exam consists of two parts, and placement
recommendations are made as indicated by the tree shown
in Figure 10.4.3.
Figure 10.4.3
7
Example 10.4.2 – A Decision Tree continued
Read the tree from left to right to decide what course
should be recommended for a student who scored 9 on
part I and 7 on part II.
8
Example 10.4.2 – Solution
Since the student scored 9 on part I, the score on part II is
checked.
Since it is greater than 6, the student should be advised to

take Math 110.
9
Example 10.4.3 – A Parse Tree
In the last 30 years, Noam Chomsky and others have
developed new ways to describe the syntax (or
grammatical structure) of natural languages such as
English.
In the study of grammars, trees are often used to show the

derivation of grammatically correct sentences from certain
basic rules. Such trees are called syntactic derivation
trees or parse trees.
10
Example 10.4.3 – A Parse Tree continued
A very small subset of English grammar, for example,

specifies that
1. a sentence can be produced by writing first a noun
phrase and then a verb phrase;
2. a noun phrase can be produced by writing an article and
then a noun;
3. a noun phrase can also be produced by writing an
article, then an adjective, and then a noun;
4. a verb phrase can be produced by writing a verb and
then a noun phrase;
11
5. one article is “the”;

6. one adjective is “young”;
7. one verb is “caught”;
8. one noun is “man”;
9. one (other) noun is “ball.”
The rules of a grammar are called productions. It is

customary to express them using the shorthand notation
illustrated on the next slide.
12
This notation, introduced by John Backus in 1959 and

modified by Peter Naur in 1960, was used to describe the
computer language Algol and is called the Backus–Naur
notation.
In the notation, the symbol represents the word or, and

angle brackets 〈〉 are used to enclose terms to be defined
(such as a sentence or noun phrase).
1. 〈sentence〉 → 〈noun phrase〉 〈verb phrase〉
2., 3. 〈noun phrase〉 → 〈article〉 〈noun〉 〈article〉 〈adjective〉
〈noun〉
13
4. 〈verb phrase〉 → 〈verb〉 〈noun phrase〉
5. 〈article〉 → the
6. 〈adjective〉 → young
7. 〈verb〉 → caught
8., 9. 〈noun〉 → man ball
14
The derivation of the sentence “The young man caught the

ball” from the above rules is described by the tree shown
below.
15
In the study of linguistics, syntax refers to the grammatical

structure of sentences, and semantics refers to the
meanings of words and their interrelations.
A sentence can be syntactically correct but semantically
incorrect, as in the nonsensical sentence “The young ball
caught the man,” which can be derived from the rules given
on the previous slides.
Or a sentence can contain syntactic errors but not semantic
ones, as, for instance, when a two-year-old child says, “Me
hungry!”
16
Characterizing Trees
17
There is a somewhat surprising relation between the
number of vertices and the number of edges of a tree.
It turns out that if n is a positive integer, then any tree with

n vertices (no matter what its shape) has n − 1 edges.
Perhaps even more surprisingly, a partial converse to this

fact is also true—namely, any connected graph with n
vertices and n − 1 edges is a tree.
18
It follows from these facts that if even one new edge (but
no new vertex) is added to a tree, the resulting graph must
contain a circuit.
Also, from the fact that removing an edge from a circuit

does not disconnect a graph, it can be shown that every
connected graph has a subgraph that is a tree.
It follows that if n is a positive integer, any graph with n

vertices and fewer than n − 1 edges is not connected.
19
A small but very important fact necessary to derive the first
main theorem about trees is that any nontrivial tree must
have at least one vertex of degree 1.
20
Example 10.4.5 – Leaves and Internal Vertices in Trees
Find all leaves (or terminal vertices) and all internal (or
branch) vertices in the following tree:
21
The leaves (or terminal vertices) are v0, v2, v4, v5, v7, and
v8. The internal (or branch) vertices are v6, v1, and v3.
22
23
Example 10.4.6 – Determining Whether a Graph Is a Tree
A graph G has ten vertices and twelve edges. Is it a tree?
24
No. By Theorem 10.4.2, any tree with ten vertices has nine
edges, not twelve.
25
Example 10.4.7 – Finding Trees Satisfying Given Conditions
Find all nonisomorphic trees with four vertices.
26
By Theorem 10.4.2, any tree with four vertices has three
edges. Thus the total degree of a tree with four vertices
must be 6. Also, every tree with more than one vertex has
at least two vertices of degree 1.
Thus the following combinations of degrees for the vertices
are the only ones possible: 1, 1, 1, 3 and 1, 1, 2, 2. There
are two nonisomorphic trees corresponding to both of these
possibilities, as shown below.
27
28
Example 10.4.8 – A Graph with n Vertices and n − 1 Edges That Is Not a Tree
Give an example of a graph with five vertices and four

edges that is not a tree.
29
By Theorem 10.4.4, such a graph cannot be connected.
One example of such an unconnected graph is shown
below.
30
31

EppDM5eMetric 10 04

Uploaded by

Copyright:

Available Formats

EppDM5eMetric 10 04

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

EppDM5eMetric 10 04

Uploaded by

Copyright:

Available Formats

CHAPTER 10

THEORY OF GRAPHS AND

Copyright © Cengage Learning. All rights reserved.

Copyright © Cengage Learning. All rights reserved.

Trees. All the graphs in (a)–(d) are connected and circuit-free.

Since it is greater than 6, the student should be advised to

In the study of grammars, trees are often used to show the

A very small subset of English grammar, for example,

5. one article is “the”;

The rules of a grammar are called productions. It is

This notation, introduced by John Backus in 1959 and

In the notation, the symbol represents the word or, and

4. 〈verb phrase〉 → 〈verb〉 〈noun phrase〉

8., 9. 〈noun〉 → man ball

The derivation of the sentence “The young man caught the

In the study of linguistics, syntax refers to the grammatical

It turns out that if n is a positive integer, then any tree with

Perhaps even more surprisingly, a partial converse to this

Also, from the fact that removing an edge from a circuit

It follows that if n is a positive integer, any graph with n

A graph G has ten vertices and twelve edges. Is it a tree?

Find all nonisomorphic trees with four vertices.

Give an example of a graph with five vertices and four

You might also like