Modelling with Directed Graphs

Definition of a Graph

A (directed) graph is simply a set of points V, whose elements are called vertices, together with a set E of ordered pairs from V´V, whose elements are called (directed) edges.  In the edges are not directed in the sense that whenever (a,b) is an edge, so is (b,a), then the graph is called undirected or simply, a graph.  All the graphs we examine will be directed.
Throughout the following discussion unless otherwise stated, the graph G is understood to have  n vertices in the set V = {1,  2, ... , n}  and m edges in the set  E = {e1, e2, ... , em}.  Here each edge ei is an ordered pair.

A picture is worth a thousand words.  So use your Browser to look in the subdirectory 
/Users/Math314Files for the file called GraphExample.eps  Now activate the figures by double clicking on the file name.  You will see the Example used for the following discussion.  Next click inside the Mathematica window to get back to this tutorial.  Notice that the Example graph G has vertices V = {1, 2, 3, 4} and edges  E = {e1, e2, e3, e4, e5}.  To be exact, e1 = (1,2), e2 = (2,3), e3 = (1,3), e4 = (3,4) and e5 = (1,4).  We will sometimes abuse the language and refer to the edges as simply  edges 1, 2, 3 ,4 and 5.  Now for some terminology we need to talk about graphs :

The graphs we shall consider are all connected:  this means that between any two vertices  i and j there is a sequence of vertices, each of which is connected by an edge, though these edges may run in different directions.  Note this is not the same as saying that there is a path between any two vertices.  Our Example graph is connected, yet there is not a path from vertex 4 to vertex 2, for instance; yet we see that there is an edge between vertex 4 and 3, and then one between vertex 3 and 2.  This notion of connecting vertices by edges not all running in the same direction is a useful one.  We can represent such an object as a vector whose coordinates are indexed by the edges of the graph and whose entries are 0, -1 or 1.  For instance, in our Example, the connection from vertex 4 to 2 may be represented by the vector {0, -1, 0, -1, 0}.   The minus signs indicate that edges 2 and 4 are traversed in the negative direction, i.e., from head to tail.

A sequence of edges which goes from a vertex back to itself without passing through any vertex except the initial one more than once, is called a  loop (or a  cycle).  As in the previous paragraph, loops can be represented by a vector indexed by the edges.  For instance, in our Example graph, {0,0,1,1,-1} represents the loop starting at vertex 1, passing through vertex 3 by way of edge 3, through vertex 4 by way of edge 4, and finally back to 1 by way of edge 5.  Notice, the -1 in the 5th place means that edge 5 is traversed in the negative direction.  There are other loops  in our graph; for example,  {1,1,-1,0,0} and {1,1,0,1,-1}.  Interestingly enough, {1,1,0,1,-1} = {1,1,-1,0,0} + {0,0,1,1,-1}.  As a matter of fact, all loops are built from the smallest loops {1,1,-1,0,0} and {0,0,1,1,-1}.

The Adjacency Matrix

Adjacency Matrix:  The adjacency matrix of a graph G is an n´n matrix whose (i,j)th entry is 1 if there is an edge from vi to vj, i.e., if (vi,vj) Î E, and is 0 otherwise.  For example, the adjacency matrix A of our Example is a 4´4 matrix defined in the cell below.  Activate this cell by putting the insertion point in it and pressing enter or by marking it and choosing the option Action, then Evaluate Selection.

A = {{0,1,1,1},{0,0,1,0},{0,0,0,1},{0,0,0,0}}

Next, you might prefer to see the matrix in standard form.  Activate the next cell:

MatrixForm[A]

Here is the connection between adjacency matrices and paths:  the number of distinct paths of length 1 from vertex i to vertex j is simply the (i,j)th entry of A.  Likewise, the number  of distinct paths from vertex i to j of length 2 is the (i,j)th entry of A A.  And so on!  The (i,j)th entry of A times itself m times gives the number of paths from vertex i to vertex j of length m.   It follows that the number of  paths from vertex i to j of length less than or equal to m is the (i,j)th entry of the sum of matrices A + A A + ... + A A ... A, where the last product is A multiplied by itself m times.  Try experimenting with the following two cells and compare with the picture of our Example A to see how things work.  Activate them, then change them to see the effects of computing longer paths by adding more terms.  For example, the following product has (1,4)th entry equal to 1 and, sure enough, there is only one path of length two from vertex 1 to vertex 4 (see it?).  Also notice that the next cell has (1,4)th entry equal to 2, which is exactly the number of paths of length at most 2 from vertex 1 to vertex 4.

MatrixForm[A.A]

MatrixForm[A + A.A]

There are several ideas that are very important in applications of graph theory to the social sciences.  One of the idea of a ªdominance-directedº graph.  This is a graph that has no paths  from a vertex to itself, and for any pair of distinct vertices, i and j, there may be a path from i to j, or from j to i, but not both.  For such a graph, the ªpowerº of a vertex is defined to be the number of paths of length 1 or 2 from that vertex to any other vertex.  For instance, you can see in our Example, which is a dominance-directed graph, that the power of vertex 2 is 2 (there is a path of length 1 to vertex 3 and one of length 2 to vertex 4).  In general, the power of the ith vertex is simply the sum of all the entries in row i of A + A A, in view of the discussion of the previous paragraph.   Here is an illustration of the idea: suppose a group of teams play a round-robin tournament of games with no ties.  Build a graph as follows.  The vertices of the graph are the teams.  There is an edge from i to j if team i defeated team j.  Thus, the power of a team is the number of teams that it has defeated or that have been defeated by a team it defeated.  Add up the entries of each row of the matrix A + A A in our Example and you see that vertex 1 is the most powerful of the vertices, while vertex 4 is the least powerful.  
   This  idea of dominance-directed graphs is used in sociological studies of group interactions, where ªdominanceº means cooperation between groups, which are represented as vertices of a graph.  In voting analysis studies, dominance represents influence with respect to voting choice.  In communications, dominance can mean the ability of one vertex to communicate with another.

The Incidence Matrix

The next important idea about graphs that we will discuss is that the the  edge-vertex incidence matrix (incidence matrix for short) of a graph.  Here is the idea:  form a matrix  B whose rows are indexed by the edges of the graph, and whose columns are indexed by the vertices of the graph.  Now if edge ei is the ordered pair (j,k), put a -1 in the jth column of row i, a  +1 in the kth column of row i and 0 in every other entry of row i.  The result is the incidence matrix B of the graph.
    For instance, the incidence matrix of our Example is given below.  Activate this cell to define the incidence matrix and the subsequent cell to get a nice form for the matrix.

B = {{-1,1,0,0},{0,-1,1,0},{-1,0,1,0},{0,0,-1,1},{-1,0,0,1}}

MatrixForm[B]

Notice that the sum of the entries in each row is 0.  Hence the vector {1,1,1,1} belongs to the null space of B.  Now it is not hard to see that the rank of B is 3.  In fact, it in instructive to see the row-echelon form of B.  Try activating the next cell to see this.

MatrixForm[RowReduce[B]]

Next, have a look at the null space of B:

NullSpace[B]

Is this an accident?  No.  Here is what happens in general: if G is a connected graph and B is the incidence matrix of G, then the rank of B is exactly n - 1, where G has n vertices, and the vector {1,1,...,1} spans the null space of B.

An even more interesting object is the null space of the transpose of B.  Try activating the next cell.

NullSpace[Transpose[B]]

Now compare this output to the discussion of loops at the end of the introductory section of these notes and note that these amount to two of the three loops (up to a factor of ±) of our Example graph.  Moreover, we could get the third loop (up to a sign) by subtracting these two loops.  In other words, all the information about loops is contained in the null space of the transpose of B.

There is one more context in which the incidence matrix turns out to be interesting.  Suppose our graph G represents an electrical curcuit.  The edges might represent locations in the circuit where objects like resistors or capacitors are placed.  At each vertex we would have a potential assigned; say at vertex i we have potential value xi.  Then the jump in potential across the kth edge e = (i, j) would simply be xj - xi.  Interestingly enough, this is exactly the kth entry of Bx.  So suppose we wanted to design a circuit where the potential differences across the edges is given by the vector f.  Is it possible for any vector f?  The answer is no.  For f represents the potential differences across edges corresponding to some distribution of potential values x if and only if the equation Bx = f is consistent.  Since the rank of B is n - 1, this will not always happen, because the system will not be consistent for every choice of b.  When will it happen?

Both null spaces can be informative in this context of electrical curcuits.  For example, we get a necessary condition for Bx = f to have a solution.  Let y be any element of the null space of the transpose of B.  Then yB = 0.  Given that Bx = f, we can multiply on the left by (the transpose of) y to obtain that y f = yBx = 0 x = 0 .  In particular, if y represents a loop, then the condition y f  = 0 really says that the total potential drop around the loop should be 0.
The null space of B is also relevant.  If x0 is any particular solution to the equation Bx = f, then so is x0 + z, where z is any element of the null space of B.  We have seen above that z will simply be a multiple of {1,1,...,1}.  So what does this say?  It says that if we add the same constant to the potential at each vertex of a circuit, we obtain a new vector of potentials whose potential differences is the same as before.

Exercises

You are given that the (directed) graph  G  has vertex set V = {1,2,3,4,5} and edge set  
E = {(2,1), (1,5), (2,5), (5,4), (4,2), (4,3), (3,2)}.  Answer the following questions about the graph  G:

(1)  What does the graph look like?  You may  draw this by hand or, if you prefer, you may use the Draw application (it has the icon with a compass on it) to draw the  picture.  

(2)  Next view the graph as representing an electrical circuit with  potentials x1,...,x5  to be assigned to the vertices.  Find  N(A)  and N(AT)  using the Mathematica command NullSpace.  What does the latter tell you about the loop structure of the circuit?  Finally, use that fact that  Ax = b  implies that for all  y  in  N(AT),  yT b = 0  to find conditions that a vector  b must satisfy in order for it to be a vector of potential differences for some potential distribution on the vertices.

Math 314H students :  this last exercise is not part of the assignment.  Do not turn it in.

(3)   View this graph as representing a communications network.  First  find the adjacency matrix of the graph.  Notice that  G  is a dominance-directed graph.  Which point(s) have the greatest power?  Which point(s) would be the best from which to initiate communications, based on this information?