November 27, 2018

Beyond Calculus

Let’s take a step back in order to take a few more forward in our walk through the basics of graph theory. The previous article in this series mainly revolved around explaining & notating something labeled a *simple graph*. We’ll now circle back to highlight the properties of a simple graph in order to provide a familiar jump-off point for the rest of this article.

In the previous article, we defined our graph as *simple *due to four key properties: *edges are undirected & unweighted; the graph is exclusive of multiple edges & self-directed loops**. *That’s by no means an exhaustive list of all graph properties, however, it’s an adequate place to continue our journey. This article will takes us from simple graphs, to more complex (yet fairly common) graphs through the introduction of key graph properties.

Graphs, like the dynamic systems of objects they represent, take on an unfathomable amount of shapes & sizes; it therefore helps to create a set of properties in order to specify unique graph attributes. Let’s examine the defining properties of our example simple graph:

- Undirected Edges
- Unweighted Edges
- Excluding Multiple Edges & Loops

The edges represented in the example above have *no *characteristic other than connecting two vertices. They distinctly *lack direction.*

The clearest & largest form of graph classification begins with the *type of edges* *within a graph*. Two main types of edges exists: those with direction, & those without. An undirected graph, like the example simple graph, is a graph composed of undirected edges. In a directed graph, or a *digraph*, every vertice has a minimum of one incoming edge & one outgoing edges — signifying the strict direction of each edge relative to it’s two connected vertices.

Similarly, a *weighted edge *is simply an edge with an associated number, or value, alternatively known as a ** weight **(usually in the form of non-negative integers).

The third our simple properties highlighted in our example graph introduces two separate graph relationships that are both based off the same property: the *simplicity *of the graph based on vertex relationships.

In our example graph, each vertex has *exactly one edge* connecting it to another vertex — no vertex connects with another vertex through multiple edges. Additionally, no vertex loops back to itself. A graph that *does *contain either or both, multiple edges & self-loops, is known as a *multigraph.*

The image below highlights these two distinctions with the graph on the right:

We didn’t list this property earlier on because both acyclic & cyclic graphs can count as simple graphs, however, the cyclical property of a graph is a key form of classification that’s worth covering. In graph theory, a ** cycle **is a path of edges & vertices wherein a vertex is reachable from itself; in other words, a cycle exists if one can travel from a single vertex back to itself without repeating (retracing) a single edge or vertex along it’s path.

A graph that contains at least one cycle is known as a *cyclic* graph. A graph without a single cycle is known as an *acyclic* graph. In our example below, we’ll highlight one of many cycles on our simple graph while showcasing an acyclic graph on the right side:

*sources*

Having now covered a basic understanding of key properties associated with graphs, it’s time to make a leap to a much exciting topic with graph theory: networks! In the next article & onward, we’ll begin constructing an understanding of networks at a deeper level — eventually applying these principles to network analysis.