Graphs Beyond the Coordinate Plane (Part 1)

The world of graphs is not a grid; rather, it is the connection of circles and lines.

When given the word graph, most people think of two axes and a grid. However, that’s the simple coordinate plane that you learn in elementary school. There are much more to graphs than the basic functions which are derived from your f(x) or y=; they expand to much more advanced fields of mathematics, and further, computer science. The “graph” we discuss today is used in a multitude of advanced algorithms in computer science; it is a data structure that contains a series of edges and vertices. Such a graph is shown below:

graph

At first sight, the structure may seem slightly confusing. However, the concept is actually quite simple. Essentially, you have a bunch of circular points, or vertices, which are connected to other points with lines, or edges. With typical computer science jargon, vertices are referred to as nodes. Also, the edges can sometimes carry more numerical data, which is called edge weight. While the above graph does not display any edge weights, the majority of graphs will contain edge weight data. Finally, the series of steps that define the traveling between one node to another through edges is called a path.

Now, why are these types of graphs important? Well, as mentioned above, graphs in computer science give leeway to a multitude of algorithms, many of which impact the technologically dependent elements of human civilization. Trading, navigation—even your Wi-Fi and cellular connections—are all completely based on graphs.

Let’s take navigation, for example. Each individual node, or circle, would represent a location, and the edges, or lines, connecting them would represent the path taken to travel from one location to another. Along the edges, the edge weights would likely classify the distance or time required between one location and another. Navigation apps such as GPS would attempt to find the optimal path between one location and another, or in terms of the graph, one node and another. This optimal path would be determined by being the minimum distance or time required to travel from one location to another. Therefore, the optimal path would be the path through the nodes and edges which gives the minimum edge weight.

Let us look at the below graph for an example of a navigational problem. Simulating a GPS, let us say that the user wishes to know the directions from their current location node¹ to their desired location node³. If one wished to travel between node¹ to node³ in the below graph, one would find that the optimal path would be to travel through node² and cover a total edge weight of 6 + 1 = 7. There are, of course, other routes; however, those other routes are not as sufficient and therefore will not be recommended by the GPS. weighted

In addition to the above problem, in the real world, there may be other variables such as a blocked road, which will be accounted for when one utilizes the graph. In that case, one would simply block off an edge, essentially not accounting for it. There are infinitely many scenarios that can be applied to graphs.

This is only the introduction to the world of graphs. As mentioned above, there are numerous applications of graphs. The GPS problem discussed above was solved by a famous graph algorithm known as Dijkstra’s algorithm, which utilizes a great number of other complex graph algorithms to find the shortest path between nodes. What we believe to be a simple problem of selecting a path grows to new heights of difficulty as more and more specifications are added. I encourage you to take your (possibly newfound) knowledge of the graph and think of its potential applications; think not of the graphs beyond the coordinate plane, but of the graphs beyond graphs.

-Yucheng Niu

 

Image Credits:

http://abacles.com/pcprog/index.html

https://tex.stackexchange.com/questions/166083/showing-weights-on-tikz-graph-using-draw-edge-commands

https://en.wikipedia.org/wiki/File:6n-graf.svg

 

 

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.