A. Brief Background

Adjacency Matrices of Graphs

Matrix algebra has important applications to graph theory. Graphs are now major tools in operations research, electric engineering, computer programming and networking, business administration, sociology, economics, marketing, and communications network; the list can go on and on.

A graph is a set of points, called vertices, or nodes, together with a set of "lines", called edges, connecting some pairs of vertices. Two vertices P and Q connected by an edge e are called adjacent, or, neighbors, and P and Q are said to be incident to e. An edge from a vertex to itself is called a loop. Vertices can be connected with more than one edge, in which case it is said there is a multiple edge.

An example of a multiple-edged graph, also called a multigraph, is a communications network where two points can be connected with more that one phone line.

Matrices are used in the study of graphs. The easy computer programming of matrix operations enable us to study the behavior of very large graphs. For example, in applications to telephone networks, a graph may have tens of thousands of vertices.

The matrix of a graph is the n x n matrix whose (i, j) entry is the number of edges connecting the ith and the jth vertex.

The adjacency matrix A(G) of a graph G is the matrix whose (i, j) entry is 1 if the ith and the jth vertex are adjacent and zero if they are not.

For large graphs it is often easier to extract information from the adjacency matrix than from the graph itself, which may be visually complicated.

Let we have a graph with no loop and no multiple edges, and two fixed vertices, P and Q. A walk of length m from P to Q is a sequence of vertices

P = V1, V2, ..., Vm, Vm+1 = Q

It can be shown that the number of walks of lengths m from vertex i to vertex j in a graph G is equal to the (i, j)th entry of A(G)^m.

Directed Graphs

A directed graph, or digraph, is a graph whose edges are directed line segments.

The adjacency matrix A(D) of a digraph D is the matrix whose (i, j)th entry is 1 if there is at least one directed edge connected the ith to the jth vertex and zero otherwise.

The number of walks of length m from vertex i to vertex j in a digraph D is equal to the (i, j) entry of A(D)^m.

So compared to a simple graph, the only difference is that the edge are directed.

Graphs in Sociology and Psychology

Sociologists and psychologists use graphs to determine various kinds of relationships, such as influence, dominance, and communication, in groups.

Suppose that in a group, for every pair of members Vi and Vj, either Vi influences (or dominates) Vj or Vj influences Vi, or there is no direct influence between Vi and Vj. This situation can be described by a digraph D that has at most one directed edge connecting any two vertices. Such a digraph is called a dominance digraph.

B. Problem

1. From graph to the model

Fig.1 displays the dominance relationships among seven individuals, V1, ..., V7. Consider the adjacency matrix of the digraph and find out who is the most influential member of the group in direct influence and second-stage influence.

Fig.1. A dominance graph

If the resolution of your screen does not allow you to make out the directions of the arrows, be aware that they are pointing down everywhere except from V4 to V2 and V6 to V3.

2. From the model to the graph

A group of 5 people, V1, ..., V5, who have been stationed on Antarctica to operate a weather station. The following social relationship have been observed:

V1 get along with V2, V3, and V4
V2 get along with V1, and V3
V3 get along with V1, V2, and V4
V4 get along with V2, V3, and V5
V5 get along with V4.

C. Helpful Sources

The Course Text, Chapter 1, Section 1.4; Chapter 8, Section 8.1.
References from Further Reading sub-section, Section 8.1.