Background

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph is made up of vertices and nodes which are connected by edges, arcs, or lines. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another. Next, I will be talking about the important aspects of graph theory.

Directed Graph:

A finite set of objects (called vertices or nodes) that are connected together, where all the edges are directed from one vertex to another.

Connected Graph:

A graph is called connected if given any two vertices X_i, X_j, there is a path from X_i to X_j.

Vertex Matrix:

We can associate a matrix with each graph storing some of the information about the graph in a matrix. This matrix can be used to obtain more detailed information about the graph. If a graph has n vertices, we may associate an n x n matrix M which is called vertex matrix or adjacency matrix. The vertex matrix M is defined by:

Clique:

The clique is one of the most important concepts in graph theory. Also known as a complete graph, it is defined as a graph where every vertex is adjacent to every other. In computational biology cliques are used as a method of abstracting pairwise relationships such as protein-protein interaction or gene similarity. If we were to find a clique in such a graph, we would have an important finding. A goal might be to find the largest clique in the graph.

Definition - A subset of a directed graph satisfying the following conditions is called a clique:

1. The subset contains at least 3 points.
2. If X_i and X_j are in the clique, then Xj to Xi holds.
3. The subset is the largest possible.

Problem

Consider this graph G with seven nodes that contain either one or two directions. To begin, we would like to find the vertex matrix of G. Then we would like to know all the paths of the graph that have a length of 3. We will be able to come up with another matrix that shows these paths. Finally, we would like to find if the graph is connected or not, and what cliques are contained within the graph if any.

A)

First, we want to find the vertex matrix of this matrix G. To do so, we look at what direction each node is pointing towards, then we create the matrix with 1s and 0s based on if a node is pointing towards another node. Here is the resulting matrix that is created from the graph G. For the columns and rows, the connections go from P1 to P5 respectively.

B)

Next we would like to know the number of paths that contain length 3; this can be denoted as M³. This is shown in matrix form as:

C)

Now we want to see if the graph is either connected or not connected. To do this, we can find the number of paths that contain all lengths. Here are the matrices that contain the lengths of every path possible, if one node contains no paths for every length, it is not connected.

With the exception of the paths that were previously covered, you can see that node 5 does not contain any number of paths to any other nodes. Therefore, this graph is not connected.

D)

Finally, we would like to find any cliques that the graph contains. We use the graph to get this matrix:

Next we take the paths with length 3 and find this matrix that shows there is a clique within P2, P3, and P4.

Subsection: Exercises

 

References