Graph Theory
We now delve into our first application or matrices, graph theory, which shows its face in communications, sociology, business, transportation sciences, and many other fields. We begin by stating the basic definitions. A directed graph, also called a digraph, is a set of points P_{1}, P_{2}, ... , P_{n} called vertices and ordered pairs of points P_{i}P_{j} called edges. A digraph can have a vertex that does not belong to any edge or two points that are connected by edges in both directions. Example The digraph with points P, Q, R, S, and edges PQ, QP, PR, and QR is shown below.
Let G by a digraph with n vertices, then the adjacency matrix of A, written A(G), is the n x n matrix with A(G)_{ij} equal to 1 if P_{i}P_{j} is an edge and zero otherwise. Example The adjacency matrix of the graph in the example above is
Example Five students, Aurellio, Brian, Cindy, Dave, and Edward have formed a study group. Aurellio has Cindy and Dave's phone number, Brian has Edward's number, Cindy has Dave and Edward's number, Dave has Aurellio and Brian's number and Edward has everyone's number. The graph and the adjacency matrix are shown below.
One of the questions that we may ask, is if Aurellio wants to get a hold of Brian, how can he do this? More specifically we can ask how many ways are there of Aurillio getting Brian's number using no more than two edges. We say that P_{i} has r stage access to P_{j} if there is a way to get to P_{j} from P_{i} via r edges. The following theorem helps us to answer the question at hand. Theorem Let A(G) be the adjacency matrix of a digraph G then the number of r stage accesses that P_{i} has to P_{j} is given by [A(G)^{r}]_{ij} Thus the total number of ways that P_{i} has access to P_{j} in r or fewer stages is the ij^{th} element of the matrix A(G) + A(G)^{2} + ... + A(G)^{r} Now back to our problem. We have
To find out how many ways there are of Aurillio getting Brian's number using no more than two edges we just take the 1 2^{th} element of this matrix. This is 1, so there is exactly one way of Aurillio getting Brian's number using no more than two edges. Sociologists speak of cliques, which mean subgroups of a larger group that associate with each other but do not associate with others. In the language of graph theory we have the following. Definition A clique in a digraph is a subset S of the vertices satisfying the following three properties
Example In the digraph below, B, C, D, and E form a clique.
In the above example, it is relatively easy to spot any cliques. For larger digraphs, it is much more difficult to spot a clique just by looking. Fortunately, there is a way of doing this using matrices. Theorem Let A(G) be the adjacency matrix of a digraph and let S by the matrix whose entries are defined by
Then a vertex P_{i} belongs to a clique if and only if s_{ii}^{3} is nonzero.
Example Consider the diagraph with adjacency matrix
Then
We see that the positive diagonal elements correspond to P_{1}, P_{2}, P_{3}, and P_{6}. So these four vertices are in a clique. Strongly Connected Graphs If G is a graph then we are often concerned with ensuring that there is a path from any vertex to any other vertex. If the vertices represent street corners and the edges represent roads, then a civil engineer wants to ensure that a car can get from any street corner to any other corner. This idea also applies to networked systems such as telephone lines. A graph is called strongly connected if for every two distinct vertices P_{i} and P_{j} there is a path leading from P_{i} to P_{j} and from P_{j} to P_{i}. Otherwise they are not strongly connected. If there is a path that leads from P_{i} to P_{j} then at some stage P_{i} has access to P_{j} so that A(G)^{r} will be positive. Moreover, since there are n vertices, the shortest path will contain fewer than n edges. This leads us to the following theorem. Theorem Let G be a digraph and A(G) be its adjacency matrix, then G is strongly connected if and only if A(G) + A(G)^{2} + ... + A(G)^{n1} has no zero entries.
Example Consider the digraph below
The adjacency matrix is
Now use a calculator to find
We see that this matrix has no zero entries, so the graph is strongly connected. Back to the Matrices and Applications Home Page Back to the Linear Algebra Home Page Back to the Math Department Home Page email Questions and Suggestions
