Chapter 8 : Discrete Mathematics

803 Graph Theory

Gregory Moore

P U R P O S E

Explore the world of graphs, create graphs in Maple and generate diagrams and adjacency matrices, examine equivalency of graphs, and the concepts of connected and unconnected graphs.

To begin, enter these commands :

> restart; with( networks): with(linalg):

Warning, the names charpoly and rank have been redefined

Warning, the protected names norm and trace have been redefined and unprotected

________________________________________________________________________

A. Creating Graphs

________________________________________________________________________

A graph is a diagram with vertex points, and edges connecting some or all of the vertices.

Lets consider this example. An airline only flies to certain cities : New York, Toronto, Los Angeles, San Francisco, Chicago, Denver, and New Orleans. We can create a set with these cities. Remember that names in Maple can not contain blank characters, so its necessary to use an underscore between two word city names.

> cities := { New_York, Toronto, Los_Angeles, San_Francisco, Chicago, Denver, New_Orleans};

Well inform Maple that we wish to create a new graph with these cities as vertices.

> new(G):

> addvertex( cities, G);

The airline does not have flights from every city to every other city. There are flights from New York to Los Angeles, Toronto, and Chicago. We indicate this by informing Maple of connections between these cities.

> connect( {New_York}, {Los_Angeles, Toronto, Chicago}, G):

In a similar way, we indicate that Los Angeles also has flights to San Francisco, Denver, and Chicago. We dont need to mention New York because that connection was already established above.

> connect( {Los_Angeles}, {San_Francisco, Denver, Chicago}, G):

Also, there are flights from Chicago to Toronto and New Orleans, and from San Francisco to Denver.

> connect( {Chicago}, {Toronto, New_Orleans }, G):

> connect( {San_Francisco}, {Denver}, G):

Now lets see what this routing looks like by drawing the graph.

> draw(G);

As we can see, there are plenty of connections. However, not every city is connected to every other one by a direct flight. For example, there is no direct flight from Denver to Chicago, New York, Toronto, or New Orleans.

________________________________________________________________________

B. Adjacency Matrics

________________________________________________________________________

It can be difficult to work graphs as diagrams. A more convenient way to analyze graphs mathematically is to represent them as matrices. A matrix representation for a graph is called an adjacency matrix.

The way it works is this. For each vertex, there is a row and column of the matrix. For example if there are six vertices, then the matrix will be six by six. If there is a connection between vertex 2 and vertex 5, then there will be a 1 in row 2, column 5 and also in row 5, column 2. The 1 appears in two places to indicate a path from 2 to 5 and from 5 to 2. If there is no connection between vertex 3 and vertex 4, then there will be a zero in row 3 column 4 and row 4 column 3. Maple will create these matrices for us. Lets see this in action.

> points := { A,B,C,D,E,F};

> new(G1):

> addvertex( points, G1);

> connect( {A},{B,C}, G1):

> connect( {B}, {E}, G1):

> connect( {C}, {D,F}, G1):

> draw(G1);

> A1 := adjacency(G1);

This matrix represents all of the connections between the vertices. Vertex A is connected to vertices B and C. We can see that in the matrix by looking down the first column and seeing 1s in the 2nd and 3rd rows. Vertex B is connected to A, and E. This is indicated by looking down the 2nd column and seeing 1s in the 1st and 5th locations. C is connected to A, D, and F, so the 3rd column has 1s in the 1st, 4th, and 6th positions. And so forth.

________________________________________________________________________

C. Equivalent Graphs

________________________________________________________________________

Sometimes two graphs appear to be different graphs, however in reality they are essentially the same graph with the vertices re-arranged with the connections the corresponding places. For example if you start with any graph diagram, and simply move some of the vertices to new location, keeping the connections attached, it would cause the graph to appear different, but actually it would be contain the same connection information as before the alteration. It can be very hard to see that two graphs are equivalent just by inspecting the diagram. Also, at times two graphs can appear to be equivalent but actually be different.

There is a method to determine if two graphs are equivalent using their adjacency matrices. Even two equivalent graphs can have different adjacency matrices. However, interchanging vertices on the graph is equivalent to interchanging rows and columns of the matrices. Lets consider an example with two graphs.

> restart; with(networks): with(linalg):

Warning, the names charpoly and rank have been redefined

Warning, the protected names norm and trace have been redefined and unprotected

> points := {X,Y,Z,W};

> new(G1) : addvertex(points, G1);

> connect( {X},{X,Z,W}, G1):

> connect( {W}, {Z}, G1):

> draw(G1);

> points := {X,Y,Z,W};

> new(G2) : addvertex(points, G2);

> connect( {X},{X,Z,W}, G2):

> connect( {W}, {Z}, G2):

> draw(G2);

Now lets look at their adjacency matrices which are apparently not the same.

> A1 := adjacency(G1);

> A2 := adjacency(G2);

> if equal(A1, A2) then print('same') else print(`not the same`); fi;

Lets define a matrix function that will interchange two rows and columns.

> interchange := (A,i, j) -> evalm( swaprow(swapcol(A,i,j),i,j) );

Now if we interchange the 2nd and 3rd rows and columns of A2 we see that we get A1! This means that these two graphs are actually equivalent.

> interchange( A2,2,3);

How do we know which rows and columns to interchange? If you look very long and hard at the matrices you can sometimes see which rows and columns to swap. We can create a little Maple procedure that will check all of the possibilities and then tell us if the matrices are equivalent, and if so, which vertices need to be swapped.

> check := proc(A,B)
local i ,j, n, equiv;
n := rowdim(A); equiv := false;
for i from 1 to (n-1) do
for j from (i+1) to n do
if equal( A, swaprow( swapcol(B,i,j),i,j))
then equiv := true;
print(`( Interchange vertices `,i,j,`)`); fi;
od; od;
if equiv then print(`The Graphs are Equivalent !`);
else print(`The Graphs are NOT equivalent`); fi;
end:

> check(A1, A2);

________________________________________________________________________

D. Unconnected Graphs

________________________________________________________________________

In all of the graphs weve seen so far, it has been possible to get from any vertex to another by travelling one or more edges. This type of graph is called a connected graph. There are other graphs where it may not be possible to reach every other vertex starting at a given vertex. In this case there may be separate components of the graph which are connected. These components are called subgraphs. Lets examine an example.

> points := { A,B,C,D,E,F };

> new(G1):

> addvertex( points, G1 );

> connect( {A}, {B,C}, G1):

> connect( {D}, {E,F}, G1):

> draw(G1);

Notice that the graph is composed of two smaller graphs which are not connected to each other. How is demonstrated by the adjacency matrix?

> A1 := adjacency(G1);

Notice the matrix is a block diagonal matrix. If you draw a vertical line between the 3rd and 4th columns, and a horizontal line between the 3rd and 4th rows, it splits the matrix up into 4 smaller 3 by 3 matrices. Only upper left corner sub-matrix and the lower right corner sub-matrix are non-zero.

Here is another disconnected graph. Lets see if the same thing happens again.

> points := { A,B,C,D,E,F };

> new(G1):

> addvertex( points, G1 );

> connect( {A}, {B,E}, G1):

> connect( {D}, {C,F}, G1):

> draw(G1);

> A1 := adjacency(G1);

This matrix is not a block diagonal matrix. However, we can interchange vertices to transform it into a block diagonal matrix. First we interchange E and F, the 5th and 6th vertices, then C and F, the 3rd and 6th vertices. The result is a block diagonal matrix where each block is 3 by 3.

> A2 := interchange( A1, 5,6);

> interchange(A2, 3,6);

>