Discrete Math Notes
Trees: Examples and Basic Properties
A graph is said to be circuit-free if, and only if, it has no circuits. The graph is
called
a tree if, and only if, it is circuit-free and connected. A trivial tree is a graph
that
consists of a single vertex. A graph is called a forest if, and only if, it is
circuit-free
and not connected.
Tree Binary
Tree Tree
Trivial
Tree
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. 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.
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.
Parse Tree
5 + 3 => inorder
+ 5 3 => preorder
5 3 + => post order
(5 + 3) * 6
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. As is discussed briefly in Chapter 12, this work has proved useful in
constructing compilers for high-level computer languages. 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 syntac tic
derivation trees or parse trees. 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;
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 grammar are called productions. It is customary to express
them using the shorthand notation illustrated below. 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 u represents the word or, and
angle brackets K L are used to enclose terms to be defined (such as a
sentence or noun phrase).
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 above. Or a sentence can contain
syntactic errors but not semantic ones, as, for instance, when a two-year-old
child says, “Me hungry!”
Terminal Vertices and Leaves
Leaves and internal Vertices in Trees Find all leaves (or terminal vertices) and
all internal (or branch) vertices in the following tree:
The leaves (or terminal vertices) are v0, v2, v4, v5, v7, and v8. The internal
(or branch) vertices are v6, v1, and v3.
Example:
B A C
A D F
C E
D G H
A rooted tree is a tree in which there is one vertex that is distinguished
from the others and is called the root. The level of a vertex is the number of
edges along the unique path between it and the root. The height of a rooted
tree is the maximum level of any vertex of the tree. Given the root or any
internal vertex v of a rooted tree, the children of v are all those vertices that
are adjacent to v and are one level farther away from the root than v. If w is
a child of v, then v is called the parent of w, and two distinct vertices that
are both children of the same parent are called siblings. Given two distinct
vertices v and w, if v lies on the unique path between w and the root, then v
is an ancestor of w and w is a descendant of v
Binary Search Tree
L<P<R
15,10,19,25,12,4,18
A*b-(c/(d+e))
Spanning Tree and a Shortest Path Algorithm
Iteration Number Edge Considered Weight Action Taken
1 v3 – v4 2 added
2 V0-v5 4 added
3 V1-v3 5 added
4 V1-v4 7 Not added
5 V0-v5 8 added
6 V4-v5 10 Added
7 V0-v1 12 Not added
8 V6-v7 13 added
9 V4-v7 15 added
10 V3-v7 18 Not added
11 V2-v7 19 added
12 V2-v1 20 Not added
Total weight: 61
Total weight: 28