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:
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). Weight values allow for modeling more complex problems that more accurately represent real-life systems through graphs. In many real-life applications, the weight of an edge is also commonly referred to as the cost of the edge; real-life examples of edge weights in graphs include measuring the length of a route, the capacity of a cable or the energy required to move across a certain path. The image below provides a quick visual guide of what our example graph were to look like if it contained weighted edges:
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.
