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. |
|