Problems for Chapter 1

Problems for section 1.1

filler
filler
filler
Return to main text: top / section 1.1 !======================


Problems for section 1.2

Problem 1


In Fig 1.2a some of the graphs are ugraphs and others are digraphs. For each ugraph write down the full adjacency array and the short adjacency array. For each digraph write down the adjacency array. (Answers are given below.)










Problem 2

The basic structure of a ugraph is shown in Fig 1.2b. In Fig 1.2c, Fig 1.2d, Fig 1.2e the basic structure has received three different labelings. Write down the short adjacency arrays for each of the three labeled ugraphs.

This shows that labeling a ugraph in two different ways may produce the same adjacency array or it may produce two different adjacency arrays.



Return to main text: top / section 1.2

Problems for section 1.3

Problem 1.3a

In the drawing Fig 1.3a six pairs of ugraphs are shown. Which pairs are equivalent?


Problem 1.3b

In the drawing Fig 1.3b the first (A) is a labeled ugraph. Some of the nodes in drawings (B) and (C) are labeled. Finish labeling (B) and (C) so that all three ugraphs have the same adjacency arrays.

Problem 1.3c

In the drawing Fig 1.3c the first (A) is a labeled ugraph. Label all the nodes in (B) and (C) so that all three ugraphs have the same adjacency arrays.




Problem 1.3d

The following letters form ten ugraphs. On each the five small solid black circles are thenodes.
(a) Copy A and R to paper, replacing the black circles by ordinary circles big enough to contain integers. Label the vertices in A with integers 1,2,3,4,5. Then find a labeling of R with the same five integers so that A and R have the same short adjacency arrays. (This shows that A and R are equivalent ugraphs).
(b) To what ugraph F equivalent?
(c) To what is the letter ugraph K equivalent?
(d) In the same way show that the remaining four letters form two pairs of equivalent ugraphs

Problem 1.3e True or False ?
(A) All ugraphs with exactly 3 nodes and exactly 2 edges are equivalent?
(B) The ugraph in Fig 1.3e is NOT equivalent to any ugraph in figure Prob1.3f.
(C) Any ugraph with exactly 4 nodes and exactly 3 edges is equivalent to one of the ugraphs shown in Fig 1.3f.
(D) If two labeled ugraphs have the same (short) adjacency arrays then they are equivalent.
(E) All complete ugraphs with exactly 5 nodes are equivalent May the number 5 be replaced by any positive integer to get a true statement?




(F) The pair of ugraphs in Fig 1.3g are equivalent. Prove it by assigning integer labels and comparing adjacency arrays.





(G) The pair of digraphs in Fig 1.3h are equivalent. Prove it by assigning integer labels and comparing adjacency arrays.





Problem 1.3f Draw two non-equivalent ugraphs with exactly 4 nodes and 2 edges each.


Answers to problem 1.2a (S=short adj array for a ugraph, F=full adj array for a ugraph, D=adj array for a digraph)
(A) D, 1,3,5,  2,1,  3,4,  4,1,  5,2//
(B) S,  1,2,3,  2,3,  3,4,  4,  5,0//       F,  1,2,3,  2,1,3,  3,1,2,4,  4,3,  5,0//
(C) D,  1,2,5,  2,3,4,  3,  4,3,5,  5//
(D) S,  1,2,4,  2,3,4,  3,  4,5,  5//       F,  1,2,4,  2,1,3,4,  3,2,  4,1,2,5,  5,4//
(E) D,  1,2,3,4,5,  2,  3,  4,  5,2,  6,1,   0,0
(F) S,  1,0,  2,3,7,  3,4,  4,5,  5,7,  6,0,  7//     F,  1,0,  2,3,7,  3,2,4,  4,3,5,  5,4,7,  6,0,  7,2,5//
(G) D,  1,2,4,6,  2,1,3,  3,  4,3,6,  5,0,  6,4,7,  7//
(H) S,  1,0,  2,6,  3,4,5,6,  4,5,  5,  6,7,  7//       F,  1,0,  2,6,  3,4,5,6,  4,3,5,  5,3,4,  6,2,3,7,  7,6//
(I) D  1,2,  2,3,4,5,  3,  4,1,2,3,  5,3//

Answers to problem 1.3a
The pairs of ugraphs in B,D,E,F are equivalent. The pairs in A,C are not equivalent.

Answers to problem 1.3b


Notice that every node has degree three.


Answers to problem 1.3c


There are more than one completed labeled graph for (B) and (C). One solution is given to the right. Notice that every node must have degree three.

Answers to problem 1.3d
The following pairs of letters form equivalent ugraphs:
A,R  F,T  K,X  M,V  S,Z

Return to main text: top / section 1.3