A * set* is a collection of distinguishable objects, called its

We adopt special notations for frequently encountered sets.

denotes the * empty set*, that is, the set containing no members.

**Z** denotes the set of * integers*, that is, the set {. . . , 2, -1, 0, 1, 2, . . .}.

**R** denotes the set of * real numbers*.

**N** denotes the set of * natural numbers*, that is, the set {0, 1, 2, . . .}.

If all the elements of a set *A* are contained in a set *B*, that is, if *x* *A *implies *x* *B*, then we write *A * *B* and say that *A* is a * subset* of

We sometimes define sets in terms of other sets. Given a set *A*, we can define a set *B* *A* by stating a property that distinguishes the elements of *B*. For example, we can define the set of even integers by {*x* : *x* **Z** and *x*/2 is an integer}. The colon in this notation is read "such that." (Some authors use a vertical bar in place of the colon.)

Given two sets *A* and *B*, we can also define new sets by applying **set operations***:*

The * intersection* of sets

AB= {x:xAandxB} .

The * union* of sets

AB= {x:xAandxB} .

The * difference* between two sets

A-B= {x:xAandxB} .

Set operations obey the following laws.

AA=A,

AA=A.

AB =BA,

AB =BA.

A(BC) = (AB)C,

A(BC) = (AB)C.

A(BC) = (AB) (AC),

A(BC) = (AB) (AC).

A(AB) =A,

A(AB) =A.

A- (BC) = (A-B)(A-C),

A- (BC) = (A-B)(A-C).

The first of DeMorgan's laws is illustrated in Figure 5.1, using a * Venn diagram*, a graphical picture in which sets are represented as regions of the plane.

Often, all the sets under consideration are subsets of some larger set *U *called the **universe****.** For example, if we are considering various sets made up only of integers, the set **Z** of integers is an appropriate universe. Given a universe *U*, we define the * complement* of a set

DeMorgan's laws (5.2) can be rewritten with complements. For any two sets *A, B* *U*, we have

Two sets *A* and *B* are * disjoint* if they have no elements in common, that is, if . A collection

the sets are * pairwise disjoint*, that is,

In other words, *S* forms a partition of *S* if each element of *S* appears in exactly one *S _{i}*

The number of elements in a set is called the * cardinality* (

For any two finite sets *A* and *B*, we have the identity

|AB| = |A| + |B| - |AB|,

from which we can conclude that

|AB| |A| + |B|.

If *A* and *B* are disjoint, then |*A* *B| = 0 and thus |*A* *B| = |*A| + |*B|. If *A * *B*, then |*A| |*B|.

A finite set of *n* elements is sometimes called an * n-set*. A 1-set is called a

The set of all subsets of a set *S*, including the empty set and the set *S *itself, is denoted 2* ^{S}* and is called the

We sometimes care about setlike structures in which the elements are ordered. An * ordered pair* of two elements

The **Cartesian product**** **of two sets *A* and *B*, denoted *A* *B*, is the set of all ordered pairs such that the first element of the pair is an element of *A *and the second is an element of *B*. More formally,

AB= {(a,b) :aAandbB}.

|AB| = |A||B| .

The Cartesian product of *n* sets *A*_{l}, *A*_{2},. . . , *A _{n}* is the set of

A_{1}A_{2}A= {(_{n}a_{1},a_{2},...,a):_{n}a_{i }A,_{i}i= 1, 2,...,n} ,

|A_{1}A_{2}A| = |_{n}A_{1}| |A_{2}| |A|_{n}

if all sets are finite. We denote an *n-*fold Cartesian product over a single set *A* by the set

A=^{n}AAA,

Draw Venn diagrams that illustrate the first of the distributive laws (5.1).

Prove the generalization of DeMorgan's laws to any finite collection of sets:

Prove the generalization of equation (5.3), which is called the** principle of inclusion and exclusion:**

|A_{1 }A_{2 }A|_{n}_{ =}

|A_{1}| + |A_{2}| + + |A_{n}|

-|A_{1}A_{2}| - |A_{1 }A_{3}| - (all pairs)

+|A_{1}A_{2}A_{3}+ (all triples)

+(-1)-1 |^{n}A_{1}A_{2}A|_{n}.

Show that the set of odd natural numbers is countable.

A** binary relation***R* on two sets *A* and *B* is a subset of the Cartesian product *A* *B*. If (*a, b*) *R*, we sometimes write *a* *R* *b*. When we say that *R* is a binary relation on a set *A*, we mean that *R* is a subset of *A* *A*. For example, the "less than" relation on the natural numbers is the set {(*a,b*): *a,b* **N** and *a *< *b*}. An *n*-ary relation on sets *A*_{1}, *A*_{2}, . . . , *A _{n}* is a subset of

A binary relation *R* A* *A *is *

aRa

aRbimpliesbRa

aRbandbRcimplya Rc

A relation that is reflexive, symmetric, and transitive is an **equivalence relation****.** For example, "=" is an equivalence relation on the natural numbers, but "<" is not. If *R* is an equivalence relation on a set *A*, then for *a* *A*, the * equivalence class* of

The equivalence classes of any equivalence relation *R* on a set *A* form a partition of *A*, and any partition of *A* determines an equivalence relation on *A* for which the sets in the partition are the equivalence classes.

A binary relation *R* on a set *A* is * antisymmetric* if

aRbandbRaimplya=b.

For example, the "" relation on the natural numbers is antisymmetric, since *a* *b* and *b* *a* imply *a* = *b*. A relation that is reflexive, antisymmetric, and transitive is a * partial order*, and we call a set on which a partial order is defined a

A partial order *R* on a set *A* is a * total* or

Prove that the subset relation " on all subsets of **Z **is a partial order but not a total order.

Show that for any positive integer *n*, the relation "equivalent modulo *n*" is an equivalence relation on the integers. (We say that *a* *b *(mod *n*) if there exists an integer *q* such that *a* - *b* =*qn*.) Into what equivalence classes does this relation partition the integers?

Give examples of relations that are

**a****.** reflexive and symmetric but not transitive,

* b.* reflexive and transitive but not symmetric,

* c. *symmetric and transitive but not reflexive.

Given two sets *A* and *B*, a **function***f* is a binary relation on *A * *B* such that for all *a* *A*, there exists precisely one *b * *B* such that (*a,b*) . The set *A* is called the **domain**** **of *f*, and the set *B* is called the * codomain *of

f= {(a,b) :aNandb=amod 2 }

g= {(a,b) :aNanda+bis even}

Given a function *f *: *A* *B*, if *b* = *f* (*a*), we say that *a* is the * argument *of

A * finite sequence *of length

If *f *: *A* *B* is a function and *b* = *f *(*a*), then we sometimes say that *b *is the * image* of

f(A' = {bB : b=f(a) for someaA'} .

The * range* of

A function is a * surjection* if its range is its codomain. For example, the function

A function *f *: *A* *B* is an* injection* if distinct arguments to â produce

A function *f *: *A* *B* is a * bijection* if it is injective and surjective. For example, the function

0 0 ,

1 -1 ,

2 1 ,

3 -2 ,

4 2 ,

The function is injective, since no element of **Z** is the image of more than one element of **N**. It is surjective, since every element of **Z** appears as the image of some element of **N**. Hence, the function is bijective. A bijection is sometimes called a * one-to-one correspondence*, since it pairs elements in the domain and codomain. A bijection from a set

When a function â is bijective, its **inverse***â*^{-1} is defined as

f^{-1}(b) =aif and only iff(a) =b.

For example, the inverse of the function *â*(*n*) = (-1)^{n}*n*/2 is

Let *A *and *B* be finite sets, and let *f *: *A* *B* be a function. Show that

* a.* if

* b.* f

Give a bijection from **Z** to **Z** **Z**.

This section presents two kinds of graphs: directed and undirected. The reader should be aware that certain definitions in the literature differ from those given here, but for the most part, the differences are slight. Section 23.1 shows how graphs can be represented in computer memory.

A * directed graph* (or

In an **undirected graph***G* = (*V, E*), the edge set *E* consists of *unordered* pairs of vertices, rather than ordered pairs. That is, an edge is a set {*u, v*}, where *u,v* *V* and *u* *v*. By convention, we use the notation (*u, v*) for an edge, rather than the set notation {*u,v*}, and (*u,v*) and (*v, u*) are considered to be the same edge. In an undirected graph, self-loops are forbidden, and so every edge consists of exactly two distinct vertices. Figure 5.2(b) is a pictorial representation of an undirected graph on the vertex set {1, 2, 3, 4, 5, 6}.

Many definitions for directed and undirected graphs are the same, although certain terms have slightly different meanings in the two contexts. If (*u, v*) is an edge in a directed graph *G* = (*V, E*), we say that (*u, v*) is * incident from* or

If (*u, v*) is an edge in a graph *G* = (*V, E*), we say that vertex *v* is * adjacent* to vertex

The * degree* of a vertex in an undirected graph is the number of edges incident on it. For example, vertex 2 in Figure 5.2(b) has degree 2. In a directed graph, the

A * path* of

A * subpath* of path

In a directed graph, a path *v*_{0, }*v*_{1}, . . . , *v _{k}* forms a

An undirected graph is * connected* if every pair of vertices is connected by a path. The

A directed graph is * strongly connected* if every two vertices are reachable from each other. The

Two graphs *G* = (*V*, *E*) and *G**'* = (*V*'*, *E*'*) are * isomorphic* if there exists a bijection

We say that a graph *G**' = *(*V*', E*'*) is a * subgraph* of

E'= {(u, v)E:u, vV'} .

Given an undirected graph *G* = (*V, E*), the * directed version* of

Several kinds of graphs are given special names. A * complete graph* is an undirected graph in which every pair of vertices is adjacent. A

There are two variants of graphs that you may occasionally encounter. A * multigraph* is like an undirected graph, but it can have both multiple edges between vertices and self-loops. A

Attendees of a faculty party shake hands to greet each other, and each professor remembers how many times he or she shook hands. At the end of the party, the department head sums up the number of times that each professor shook hands. Show that the result is even by proving the* handshaking lemma*: if

Show that in an undirected graph, the length of a cycle must be at least 3.

Show that any connected, undirected graph *G = *(*V*,* E*) satisfies |*E| |*V| -* 1.*

As with graphs, there are many related, but slightly different, notions of trees. This section presents definitions and mathematical properties of several kinds of trees. Sections 11.4 and 23.1 describe how trees can be represented in a computer memory.

As defined in Section 5.4, a * free tree* is a connected, acyclic, undirected graph. We often omit the adjective "free" when we say that a graph is a tree. If an undirected graph is acyclic but possibly disconnected, it is a

The following theorem captures many important facts about free trees.

Let *G = (V, E*) be an undirected graph. The following statements are equivalent.

2. Any two vertices in *G* are connected by a unique simple path.

3. *G* is connected, but if any edge is removed from *E*, the resulting graph is disconnected.

4. *G* is connected, and |*E| = |*V| - 1.

5. *G* is acyclic, and |*E| = |*V| - 1.

6. *G* is acyclic, but if any edge is added to *E*, the resulting graph contains a cycle.

A * rooted tree* is a free tree in which one of the vertices is distinguished from the others. The distinguished vertex is called the

Consider a node *x* in a rooted tree *T* with root *r*. Any node *y* on the unique path from *r* to *x* is called an * ancestor* of

If the last edge on the path from the root *r* of a tree *T* to a node *x* is (*y, x*), then *y* is the * parent* of

The number of children of a node *x* in a rooted tree *T* is called the * degree* of

An * ordered tree* is a rooted tree in which the children of each node are ordered. That is, if a node has

Binary trees are best described recursively. A **binary tree*** T* is a structure defined on a finite set of nodes that either

is comprised of three disjoint sets of nodes: a * root* node, a binary tree called its

A binary tree is not simply an ordered tree in which each node has degree at most 2. For example, in a binary tree, if a node has just one child, the position of the child--whether it is the * left child* or the

The positioning information in a binary tree can be represented by the internal nodes of an ordered tree, as shown in Figure 5.7(c). The idea is to replace each missing child in the binary tree with a node having no children. These leaf nodes are drawn as squares in the figure. The tree that results is a * full binary tree*: each node is either a leaf or has degree exactly 2. There are no degree-1 nodes. Consequently, the order of the children of a node preserves the position information.

The positioning information that distinguishes binary trees from ordered trees can be extended to trees with more than 2 children per node. In a* positional tree*, the children of a node are labeled with distinct positive integers. The

A * complete k-ary tree* is a

by equation (3.3). Thus, a complete binary tree has 2* ^{h}* - 1 internal nodes.

Show by induction that a binary tree with *n* nodes has height at least lg *n*.

The **internal path length*** *of a full binary tree is the sum, taken over all internal nodes of the tree, of the depth of each node. Likewise, the* exernal path length* is the sum, taken over all leaves of the tree, of the depth of each leaf. Consider a full binary tree with

Let us associate a "weight" *w*(*x*) = 2* ^{-d}* with each leaf

A * k-coloring* of an undirected graph

* a.* Show that any tree is 2-colorable.

* b.* Show that the following are equivalent:

3. *G* has no cycles of odd length.

* d.* Show that if

* a.* In any group of

* b.* Every group of six people contains either three mutual friends or three mutual strangers.

Many divide-and-conquer algorithms that operate on graphs require that the graph be bisected into two nearly equal-sized subgraphs by removing a small number of edges. This problem investigates bisections of trees.

A useful compendium of many definitions and results from graph theory is the book by Harary [94].