November 27, 2018
Beyond Calculus
A graph G consists of two sets of items: vertices (V) & edges (E). In other words, a graph G = <V,E>.
In this article, in contrast to the opening piece of this series, we’ll work though graph examples. The first example graph we’ll review contains specific properties that classify it as a simple graph. Simple graphs are graphs whose vertices are unweighted, undirected, & exclusive of multiple edges & self-directed loops. It’s okay to not understand the previous terms as we’ll cover graph properties extensively in the following article. For now let’s start with an example visualization below:
Visual graph representations, like the one depicted above, contain a plethora of useful information; however, in order to uncover this data in a way that’s operation-capable, we need a different way to describe the graph. First, let’s go ahead & notate the example graph above in order to better understand the opening G = <V,E> formula. To start notating, since our vertices are missing labels, we go ahead & assign any random node the label “A” — then go around the graph labeling every node an alphanumeric character larger than the previous one. Nothing fancy yet, all we did was assign a representative character to the vertices in the graph above:
Now, let’s go ahead & construct the numerical notation of the graph by creating our two number sets: vertices & edges. The first set of the example graph, the vertices, is fairly straight forward: it’s a set of the characters A–F (inclusive). But how about our set of edges? Simple. Recall that an edge is what connects two nodes. So it follows that an edge can be represented by the two nodes it connects; which means that the set of edges contains a list of coordinate-like vertices. For example, our first edge between vertice A & vertice B is best expressed as AB. Let’s go ahead & write out the the set representation for the rest of the graph:
As the image above depicts, the standard notation for our graph G can be perfectly described by two separate sets, one representing vertices, & one representing edges.
Yet is this the best way to notate the graph for carrying out mathematical & analytical operations? How about for feeding it for a computer to process? As it turns out, matrices provide a powerful vehicle to transcribe graphs for a more computer-friendly data-set. Let’s review the two main methods & notate our example graph accordingly.
Computers are more adept at manipulating numbers than at recognizing pictures. Which is one of the many reasons why it’s more common to communicate the specifications of a graph to a computer in matrix form. Two main types of matrix setups are industry-practice: adjacency matrices & incidence matrices.
Adjacency Matrix
Connected vertices are known as neighbor, or adjacent to one another. An adjacency matrix therefore describes whether two vertices are adjacent (1) or not (0). Every item in an adjacency matrix is simply a Boolean that describes connectivity.
In an adjacency matrix, the graph G with the set of vertices V & the set of edges E translates to a matrix of size V². Rows & columns are both labeled after the same the single set of vertices for any graph G. Inside the matrix we find either a 0 or a 1 — a 1 denotes that the vertice labeled in the row & the vertice labeled in the column are connected, or in more appropriate terms, they’re adjacent. An adjacency matrix, therefore, is a graph represented as a matrix where adjacent vertices are the sole focus. Let’s go ahead & transcribe our example graph as an adjacency matrix below:
Incidence Matrix
The second common syntax for transcribing graphs as matrices is through an incidence matrix. In an incidence matrix, the graph G with the set of vertices V & the set of edges E translates to a matrix of size V by E. Rows & columns are labeled after vertices & edges respectively. Inside the matrix, we again find that all items are labeled as either a 0 or a 1 —more Booleans. This time, however, a 1 denotes that the vertice labeled in the row & the edge labeled in the column are connected.
An interesting property of incidence matrices: adding up every item in a column always adds up to two. This should intuitively make sense since any & every edge in a simple graph only ever has two vertices connected to it. Let’s go ahead & write out our example graph as an incidence matrix:
Comparing both matrix notations we can deduce a few differentiators. For one, since there are always more edges than vertices, it follows that adjacency matrices have fewer columns than incidence matrices. Accordingly, incidence matrices are more sparse (0’s to 1’s), therefore likely less informative per matrix item. Lastly, adjacency matrices always follow a square-matrix pattern while incidence matrices are much more likely to represent a rectangle.
The key difference is that in former rows & columns represent vertices, while in the latter, rows & columns represent vertices & edges respectively.
With basic notation now out of the way, it’s time to move on studying fundamental graph properties that are commonly used to describe different types of graphs. Recall that our example graph was earlier defined as a simple graph; in the next article, we’ll explore a few graphs before jumping to the most exciting topic within graph theory: network theory.
sources
