Discrete Mathematics for Computer Science

160 CHAPTER 3 Relations

Other familiar examples of relations arise when we consider family trees. Tradition-

ally, a special notation is used, which goes roughly as follows: Marriages are shown with

= signs. The first-generation couple sits at the top of the tree. Only their direct descendents

officially belong to the tree. Marriages of descendents are indicated by an = sign and the

name of the partner. With the exception of the top couple, the children of a person in the

tree are drawn off a horizontal line that is joined to that person by a short vertical segment.

(No horizontal line is needed for an "only" child). The horizontal line for the children of

the top couple is joined to the = sign at the top, since both parents belong to the tree.

The children of the first-generation couple form the second generation, the children of the

second-generation couples form the third generation, and so on.

In Figure 3. 1, George is the only child of Peter and Elaine. Peter is in the picture only

because of his marriage to Elaine. Elaine, not Peter, is a child of Mary and John. Elaine is

in the second generation, and George is in the third generation.

Mary = John

Peter = Elaine

George

Figure 3.1 Examples of family tree entries.

Although the marriage of a descendent is indicated by an = sign and the name of the

partner, no further information is given about these partners. For example, in the family tree

of Mary and John shown in Figure 3.2, even if Peter and Harold were brothers, this would

not be shown. A family tree is a rich source of information about a number of relations.

In Example 2 you will list the elements of three relations that can be formed from the

relationships shown in Figure 3.2.

Mary = John

Peter = Elaine Maude = Harold

George Elizabeth

Figure 3.2 Family tree.

Example 2. For the family tree shown in Figure 3.2, identify the elements of the relations

(a) IsMarriedTo, (b) IsParentOf and (c) IsSameGeneration.

Solution.

(a) IsMarriedTo = {(Mary, John), (John, Mary), (Peter, Elaine),

(Elaine, Peter), (Maude, Harold), (Harold, Maude)}

A representation for the specific relation IsMarriedTo is shown in Table 3.5.