Graph Theory

Have you ever wondered how self-driving cars reach their destination safe and sound? Well, look no further as I explain one of the most basic elements of this property, aside from GPS that is, to you. That basic element is graph theory.

Graph theory is a branch of mathematics and computer science, and not like what you might think, it does not deal with graphs like your bar graphs and pie charts. Instead, these graphs are specifically referred to a set of nodes (or vertices) which are interconnected with lines (or edges). Graph theory deals with the properties of these graphs. Here are a few properties of these graphs and some interesting types of graphs to make you grasp the concept better:

Vertices and edges are the primary components of the graph that we are concerned with, a graph can be denoted as G (V, E). Where V is the number of vertices and E is the number of edges in the graph. The number of V and E can never go below 0, for obvious reasons. When a vertex is connected to E edges, we may say that vertex has a degree of E.

For example, abcd is a graph with 4 vertices and 4 edges.

Interestingly, vertices with a degree of 1 are called the pendent vertex, and those with a degree of 0 are called the isolated vertex.

Now, this may sound stupid, but when an edge makes a vertex connect to itself, it is called a “loop.”

Like this:

Edges can sometimes be directional, like a vector. They are present in graphs called “directed graphs”, as the name suggested, all edges in directed graphs have a direction.

For example, aedcb is a directed graph as seen with the directed edges.

In addition to having degrees, each vertex in directed graphs has “indegrees” and “outdegrees”. They basically do what they say: indegrees measure the number of edges pointing to the vertex, and the number of edges pointing from the vertex. For example, from the graph, b would have an outdegree of 2 as both edges it is connected to points from b. c would have an indegree of 2 as both edges it is connected to points at it.

When 2 vertices are connected to each other using more than 1 edge, those edges are parallel edges.

For example, the edges that connect vertices ab are parallel edges.

When a graph contains those edges, they are called multigraphs. The graph mentioned earlier, is actually a multigraph even though it contains only 2 vertices and edges.

That is all for your graph theory knowledge today, come again another day for a larger dosage!

‍