Introduction to Graph Theory 337Example 1. Find the union and intersection of G and H as shown:
1 152 5 2(^4) G (^3 4) H 3
Solution.
5 1 2 5 1 2
4 3 4 3
GuH GnH
Example 2. Let G and H be graphs as shown:2f (^3 5 2)
1 4 4 3
G H
Find G and H.
Solution.
1
2 3
x\ / 5../ 5 \ "u2 2
1 4 4 3
G H1
Distributed Network Architecture
A computer architecture for a set of processors (often called a topology) can be designed
so that each processor has its own memory and only certain pairs of processors are directly
linked to each other. For parallel processing of sorting algorithms, the topology chosen can
affect the efficiency of the algorithm. One widely studied topology is the hypercube. A
hypercube of size n, or an n-cube, denoted as Q, consists of 2' processors indexed by the
integers {0, 1, 2,..., 2n - 1). Processors A and B are directly connected if and only if the
binary representations for A and B differ in exactly one position. For example, if n = 3
and the two processors are 110 and 101, then the processors are not directly connected,
because they differ in both the second (1 and 0) and the third (0 and 1) positions. If the
two processors are 110 and 100, then the two processors are directly connected, since the