Explore BrainMass
Share

# Graphs and their adjacency matrices. Trees

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

Task Background: Graphs and Trees are useful in visualizing data and the relations within and between data sets. Conversely, it is also important to be able to represent graphs as databases or arrays, so that programs for processing the data can be written.

Part I: Adjacency Matrix and Shortest Path

Construct a graph based on the adjacency matrix that appears below. Label all nodes with indices consistent with the placement of numbers within the matrix.

0 6 0 5 0
| 6 0 1 0 3 |
| 0 1 0 4 8 |
| 5 0 4 0 0 |
0 3 8 0 0

1) Describe the graph and why it is consistent with the matrix.
2) How many simple paths are there from vertex 1 to vertex 5? Explain.Which is the shortest of those paths?
Part II: Trees

1) Construct and describe a tree that indicates the following: A college president has 2 employees who answer directly to him or her, namely a vice president and provost. The vice president and provost each have an administrative assistant. Three deans answer to the provost, and the heads of finance and alumni relations answer to the vice president. Each dean oversees three department chairpersons, and each department chair oversees several faculty in each of their respective departments.
2) Suppose that the professional correspondences are the same as above, with the addition that there is also a direct working relationship between the college president and the head of alumni relations (it is not necessary to draw this). Would the graph still be a tree? Why or why not?

#### Solution Summary

The graph with a given adjacency matrix is constructed. The number of simple paths connecting two concrete vertices in this graph is found. The shortest path among such paths is found. The tree that models the structure of a college staff is given.

\$2.19

## Project Management, PERT, Combinations, Venn Diagrams, Equivalence Relations, Trees and Graphs and Algorithms

1 The table below tells the time needed for a number of tasks and which tasks precede them. Make a PERT diagram, and determine the project time and critical path.
______________________________
A 3 NONE
B 5 NONE
C 2 A
D 4 A, B
E 6 A, B
F 6 C, D, E
G 3 D, E
H 3 F, G
I 2 F, G
______________________________

2 Calculate:
a. 8!/5!
b. 9!/(3! 6!)

3 Let A = {1, 2}, B = {2, 3, 4}, C = {2}, D = {x: x is an odd positive integer}, and E = {3, 4}. Are each of the following true or false?
a. C &#61645; A
b. B &#61645; D
c. |B| = 3
d. &#61638; &#61645; C

4 In Cincinnati, chili consists of spaghetti topped by any (or none) of meat sauce, cheese, chopped onions, and beans. In how many ways can chili be ordered?

5 For each of the following expressions, state whether or not it is a polynomial in x, and if so give its degree.
a. 2x + 3x1/2 + 4
b. 2x + 3x

6 Let A = {1, 2, 3, 4}, B = {1, 4, 5}, C = {3, 5, 6}, and the universal set U = {1, 2, 3, 4, 5, 6}.
a. Determine the resulting set:

b. Determine the resulting set:

c. Draw a Venn diagram depicting the set:

7 Determine which of the reflexive, symmetric, and transitive properties are satisfied by the given relation R defined on set S, and state whether R is an equivalence relation on S.
a. S = {1,2,3,4,5,6,7,8} and x R y means that x - y is odd
b. S = {1,2,3,4,5,6,7,8} and x R y means that &#61564;4 - x&#61564; = &#61564;4 - y&#61564;

8 Perform the indicated operation in Zm. Write your answer in the form [r] with 0 &#61603; r &#61603; m
a. [43] + [31] in Z22
b. [11]8 in Z5

9 A hospital heart monitoring device uses two feet of paper per hour. If it is attached to a patient at 8 a.m. with a supply of paper 150 feet long, at what hour of the day will the device run out of paper?

10 For the following, determine a Hasse diagram for the partial order R on set S.
S = {1, 2, 3, 4} and R = {(1, 1), (2, 2), (3, 3), (4, 4), (2, 4), (3, 1)}

11 Identify the minimal and maximal elements of S with respect to the given partial order R.
S = the nonempty subsets of {1, 2, 3} and A R B if B &#61645; A

12 Find the value of f(a).
a.
b.
c.
d.

13 In the following exercise Z denotes the set of integers. Determine if each function g is one-to-one, onto, or both.
a.
b.

14 Suppose that a number xn is computed recursively by
x1 = 2 and xn = 2xn-1 + 3 for n &#61619; 2. Compute x1 through x5.

15 Prove the given statement by mathematical induction.

16 Evaluate the numbers.
a. C(8, 3)
b. C(13, 9)
c. C(n, 1)
d. P(n, r) / C(n, r)

17 What is a graph?

18 List the set of vertices and the set of edges for the graph below.

19 What is a connected graph? Give two examples.

20 What is a weighted graph? What are its applications?

21 List the vertices and directed edges for the directed graph below:

22 Construct the labeled directed graph for the adjacency matrix:

23 Find an Euler path for the following graph:

24 What is a tree? Is a PERT diagram always a tree? Explain.

25 For each of the following graphs, determine if each is a tree and explain your answer.
a. b.

26 What is a spanning tree? Give an example.

27 Explain the breadth-first search spanning tree algorithm, and then apply it to the following graph:

28 Use Prim's algorithm to find the minimal spanning tree for the graph in the previous problem.

29 How do you know if a graph is a binary tree?

30 Explain the preorder traversal algorithm.

31 Explain the binary search tree search algorithm.

32 Evaluate the following:
a. C(7, 2)
b. C(12, 7)
c. (x + y)7
d. the coefficient of x7y2 in the expansion of (2x - y)9

33 How many words must be chosen in order to assure that at least two begin with the same letter?

34 How many different 4-digit numbers can be formed using 5, 6, 7, 8 without repetition?

35 How many distributions of 14 different books are possible if Carlos is to receive 5 books, Jamie, 4 books and Robert, 2 books?

36 Define probability.

37 Determine the probability of the following:
a. If three dice are rolled, that all will be odd
b. If two coins are flipped, that they both will land the same

38 In a particular dormitory there are 350 college freshmen. Of these, 312 are taking an English course and 108 are taking a mathematics course. If 95 of these freshman are taking courses in both English and mathematics, how many are taking neither?

39 In the following sequences determine s5 if s0, s1, ... sn, ... is a sequence satisfying the given recurrence relation and initial condition.
a. sn= -sn-1 - n2 for n >= 1, s0 = 3
b. sn = 5sn-1 - 3sn-2 for n >= 2, s0 = -1, s1 = -2

40 An investor begins to save in 1990 with \$500. Each year, the savings increases 10% over the year before, and then investor contributes another \$100. Write a recurrence relation and initial conditions on the sn, the amount of savings n years after 1990. Use this relation to determine the amount saved by 1994.

41 Explain the method of iteration.

42 Use the method of iteration to find a formula expressing sn as a function of n for the given recurrence relation:
sn= -sn-1 + 10, s0 = -4

43 What are finite state machines? Is a computer a finite state machine? Explain.

44 Draw a transition diagram for the finite state machine with the given state table:
A B C
0 B C A
1 A C B

45 Draw a transition diagram for the finite state machine with the given state table below, with A being both the initial and accepting state.
A B
x B A
y A A
z B B

46 Give the state table for the finite state machine with the given transition diagram:

47 In what state would the machine in the previous question end if it started in the initial state and was given the input string abaabb?

48 Draw the transition diagram for the finite state machine with output whose state and output tables is:
A B A B
0 A A z X
1 B B z Y

keywords: program evaluation and review technique

View Full Posting Details