1> Linear Algebra, Part 8: Graph theory (Mathematica) es

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.

Elements of Graph theory

A graph can be defined as a pictorial representation or a diagram that represents data or values in an organized manner. The points on the graph often represent the relationship between two or more things.
   
Example 1:    ■
End of Example 1

Directed Graph:

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

Directed Graph

Connected Graph:

   
Example 5:    ■
End of Example 5
A graph is called connected if given any two vertices Xi, Xj, there is a path from Xi to Xj.

Directed Graph

Vertex Matrices

   
Example 5:    ■
End of Example 5
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:

Vertex Matrix

Clique

A subset of a directed graph satisfying the following conditions is called a clique:
  1. The subset contains at least 3 points.
  2. If Xi and Xj are in the clique, then Xj to Xi holds.
  3. The subset is the largest possible.
   
Example 5:    ■
End of Example 5
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 -

Problem

Liu please move exercises into subsection "Exercises"

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.

Graph G

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 M3. 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.