DIGRAPHS AND NETWORKS

DOMINANCE DIGRAPHS

   The study of dominance is an important aspect of sociology and political science. In the study of dominance, it is assumed that given a pair A and B (A and B might represent people, or teams, for example) then either A dominates B or B dominates A, but not both. Dominance would be of interest when studying gang violence or attending a tournament in which each team in a league must play every other team exactly once, with no ties allowed.

   As an example, the following chart shows the results of a tournament among five teams A, B, C, D, and E, where, for example, AB indicates a game between teams A and B.

A digraph for this tournament is shown in Figure 6.

   Notice that there is no transitive property for dominance. (Recall the transitive property for “less than,” for example: if a < b and b < c, then a < c.) As shown previously, A dominates (won the game with) B, and B dominated D, but D dominates A.

   The matrix corresponding to the digraph in Figure 6 is as follows.

   As mentioned at the end of the previous section, this matrix is an adjacency matrix. A matrix obtained from a dominance situation will always be an adjacency matrix, since either A dominates B, or B dominates A, but not both. Also, if the entry in row i and column j is 0 (where ), then the entry in row j and column i must be 1; if the entry in row i and column j is 1 (where ), then the entry that is in row j and column i must be 0. Such a matrix is called asymmetric.

EXAMPLE 1

   Each of the following matrices comes from a dominance situation. Complete the matrix.

(a)

   Because the matrix obtained from a dominance situation must be asymmetric, the 1 in row 2, column 1 leads to a 0 in row 1, column 2. Complete the matrix as follows.

(b)

   The 1 in row 1, column 3 leads to 0 in row 3, column 1, and the 0 in row 2, column 3, leads to a 1 in row 3, column 2. Complete the matrix as follows.

EXAMPLE 2

   Write a matrix for the dominance situation in Figure 7. List all dominances.

   The directed edge from Q to P shows that Q dominates P; also, P dominates R, and Q dominates R. Entering 1 for such dominances and 0 for a lack of dominance leads to the following matrix.

   The matrix shows that P dominates R, S, and T; Q dominates P, R, and T; R dominates S and T; S dominates Q and T; and T dominates no one.

   Since P dominates R, S, and T directly, as seen in the first row, P is said to have three one-stage dominances. Adding the numbers in the second row of the matrix shows that Q has three one-stage dominances; from the third and fourth rows, R and S have two each; from the fifth row, T has none.

   In Example 2, Q dominates R and R dominated S, but Q did not dominate S. However, Q does have an indirect dominance over S, through R. Because of this, Q is said to have a two-stage dominance over S. Also, S has two-stage dominance over P.

   Although we shall not prove it, the number of two-stage dominances can be found by squaring the adjacency matrix. If we use M for the matrix above, then

   The 1 in row 1, column 2 of this result shows that P has two-stage dominance over Q (through S), while P has two-stage dominance over T in two ways (through R or through S). Adding the numbers in each row of this matrix shows that P has a total of 0 + 1 + 0 + 1 + 2 = 4 two-stage dominances, while Q has 5, R has 2, S has 3, and T has non. (Notice that matrix M² is not an adjacency matrix.)

   Adding matrices M and M² gives the total number of one-stage or two-stage dominances.

   The entry 3 in the upper right-hand corner of the result shows that P has a total of 3 one-stage or two-stage dominances of T. Also, Q has a total of 2 one-stage or two-stage dominances over both R and S.

   The sum of the entries in the P-column of matrix M + M² gives the numbers of ways that P is dominated. For example, from the first column, P is dominated in 0 + 1 + 0 + 1 + 0 = 2 ways, while Q is dominated in 3 ways, R in 4 ways, S in 5 ways, and T in 10 ways. (This dominance is assumed to be in one stage or two stages.)

   This process could be continued; finding M³ would give the number of three-stage dominances, M⁴ would give the number of four-stage dominances, and so on. A generalization of this idea follows.

EXAMPLE 3

   A league is made up of six teams, A, B, C, D, E, and F. In a recent tournament, the teams played each other exactly once, with results as shown in the digraph in Figure 8. (No ties were allowed.)

   The adjacency matrix for the tournament follows.

			A	B	C	D	E	F
M	=
								A
								B
								C
								D
								E
								F

   It is not possible to use this matrix to decide on a winner, since both teams D and E won four games, while all other teams won fewer games. To help choose a winner, we could find M² to get two-stage wins for each team. Find M² as follows.

   The sum M + M² gives the total number of one-stage and two-stage wins for each team.

   The results show that team D had a total of 2 + 3 + 4 + 0 + 1 + 3 = 13 one- or two-stage wins, while all other teams had fewer wins. Based on this result, team D could be declared the winner of the tournament.

Exercises

For each matrix in Exercises 1-10 that is the matrix of a dominance digraph, find the matrix representing two-stage dominance. Assume the matrices represent the result of 2-, 3- 4-, or 5-person games. Find the total number of people dominated by each person in one or two stages.

1.	A B A B	2.	A B A   B	3.	P Q R P Q R	4.	Z W T Z W T
5.	X Y Z X Y Z	6.	M N P M N P	7.	R S T V R S T V	8.	P Q R S P Q R S
9.		A B C D E A B C D E		10.		X Y Z W T X Y Z W T
For each digraph in Exercises 11-14, write the corresponding matrix. Find the number of two-stage dominances for A, B, C, and D. List all two-stage dominances.
11.		12.		13.		14.

Applications