| KEY WORDS |
| Graphs and Digraphs |
Dominance Digraphs |
Communication Digraphs |
Networks |
- graph theory
- graph
- vertex
- edge
- directed edge
- directed graph
- digraph
- adjacency matrix
|
- dominance
- asymmetric matrix
|
- communication digraph
- symmetric matrix
- organizational communication
digraph
- path
- connected digraph
|
- network
- cycle
- tree
- spanning tree
- minimum spanning tree
|
Review Exercises
|
| Write a matrix for each graph that is a digraph. Identify
any adjacency matrices. |
| 1. |
 |
2. |
 |
3. |
 |
4. |
 |
| Sketch a digraph for each of the following matrices. |
| 5. |
|
A |
B |
C |
| A |
 |
| B |
| C |
|
6. |
|
M |
N |
P |
| M |
 |
| N |
| P |
|
7. |
|
R |
S |
T |
V |
| R |
 |
| S |
| T |
| V |
|
8. |
|
X |
Y |
Z |
W |
| X |
 |
| Y |
| Z |
| W |
|
| For each matrix n Exercise 9-14 that is the matrix of a dominance
digraph, find the matrix representing two-stage dominance. Find the total
umber of vertices dominated by each vertex in one or two stages. |
| 9. |
|
A |
B |
C |
| A |
 |
| B |
| C |
|
10. |
|
M |
N |
P |
| M |
 |
| N |
| P |
|
11. |
|
X |
Y |
Z |
| X |
 |
| Y |
| Z |
|
| 12. |
|
R |
S |
T |
| R |
 |
| S |
| T |
|
13. |
|
P |
Q |
R |
S |
| P |
 |
| Q |
| R |
| S |
|
14. |
|
A |
B |
C |
D |
| A |
 |
| B |
| C |
| D |
|
| Write the corresponding matrix for each digraph. Find
the number of two-stage dominances for A, B, C, and D. |
| 15. |
 |
16. |
 |
| Decide on the winner of each of the following tournaments,
using one- or two-stage dominances. Here AB means a game between
teams A and B. |
| 17. |
| Game |
AB |
AC |
AD |
AE |
BC |
BD |
BE |
CD |
CE |
DE |
| Winner |
A |
C |
D |
A |
B |
B |
B |
D |
C |
D |
|
|
| 18. |
| Game |
AB |
AC |
AD |
AE |
BC |
BD |
BE |
CD |
CE |
DE |
| Winner |
A |
A |
D |
A |
B |
B |
B |
D |
C |
E |
|
|
| Write the associated matrix for each digraph. Identify
any communication digraph or organizational communication digraphs. |
| 19. |
 |
20. |
 |
21. |
 |
22. |
 |
| Sketch a digraph for each matrix of a communication digraph.
Find all two-stage paths of communication. |
| 23. |
 |
24. |
 |
25. |
 |
26. |
 |
| Identify all paths from A to D in following
digraphs. |
| 27. |
 |
28. |
 |
| Show that each of the following digraphs is connected. |
| 29. |
 |
30. |
 |
| Identify all cycles in the following networks. |
| 31. |
 |
32. |
 |
| Find all spanning trees for each network |
| 33. |
 |
34. |
 |
| Find a minimum spanning tree for each network. |
| 35. |
 |
36. |
 |
