Sample Blog Post Math 381

Graphs and Digraphs

A graph is a structure used in discrete math that is used to show the relationship between various objects. The objects form the vertices of the graph. Two vertices are connected by a line if they satisfy a certain relationship. We call these lines edges. By formalizing the way we connect the dots we are able to rigorously prove mathematical claims.

For example, the graph below has vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\big\{\{1,2\},\{2,3\},\{3,4\}\big\}\).

Graphs can be used to model a variety of things such as

  • study groups in a class,
  • showing genetic relationships between organisms,
  • sudoku puzzles,
  • committee assignments, and
  • computer program dependencies.

If we make the edges of a graph point in only one direction then we get what is called a digraph (or a directed graph). A digraph is perfect for displaying a heirarchy of objects. For example, we can use a digraph to see the math courses and prerequisites at NSC. In the digraph below the class numbers are the vertices, and one class points to another if it is listed as a prerequisite in the NSC course catalog.

From this digraph we see that a student can take discrete math (Math 381) only if they have first satisfied the requirements of Math 126, 127, 181, and 182.

One of the most famous applications of graphs is in studying the Traveling Salesman problem. In this problem a salesman must determine the optimal path in which to visit all the cities in his area. When the number of cities is small the problem is fairly easy. However, when the problem gets large (more than 10,000 vertices) there is no way to consider all the possibilities. Mathematicians and computer scientists have developed various algorithms for approximating the shortest/cheapest path. Delivery companies such as FedEx need to solve such problems thousands of times per day.