For Which Values Of N > 3 Is It Possible To Draw A 3-regular Graph With N Vertices?

A Gentle Introduction To Graph Theory

And then many things in the world would accept never come up into existence if there hadn't been a problem that needed solving. This truth applies to everything, but male child, is it obvious in the world of informatics.

Someone needed a way of keeping track of the lodge of things, so they played effectually with and created different data structures until they institute the one that worked the best for the specific problem that they were trying to solve. Someone else needed a skilful way of storing data, and then they played around with different number systems until they found one that worked all-time for the kind of information that they wanted to contain. People needed a practiced style of labeling and processing tasks, so they institute a way to build upon the tools they had and created a manner to juggle all the things that one single system needed to do, at any given time.

Of form, informatics isn't the only field to introduce and build upon what came earlier it, just I do think that it's unique in ane manner: calculator science's innovations rely and build upon its own abstractions.

I've talked about abstractions a whole lot in this series, because ultimately, that's what this series is almost: finding the joy in the abstractions that prevarication beneath the things that all of us use, every single day. And, for what it's worth, when I say "us", I'chiliad just partially talking about united states as programmers, the producers of technology — I also mean united states of america as users, the consumers of technology.

So, which amazing abstraction shall nosotros learn about next? Well, now that nosotros're experts in tree data structures, it only seems correct to sympathize where trees came from. Trees are actually a subset of something you might have already heard about: graphs. Only in order to truly know why we utilise graphs and what they are, we'll need to go deep down to the very roots of something that stems from discrete mathematics: graph theory.

If this is your very showtime foray into detached math, fear not — information technology's mine, also! Let'southward tackle information technology together — and try not to lose our sanity in the process.

Loosey–goosey graphs

When we first started looking at not-linear structures, we learned most their most central characteristic: that their data doesn't follow an order — at least, non an obvious numerical i, like we see in arrays or linked lists. Trees, equally nosotros learned, start with a root node, and might connect to other nodes, which means that could contain subtrees within them. Trees are defined by a certain set up of rules: ane root node may or may non connect to others, but ultimately, it all stems from one specific place. Some trees have even more specific rules, like binary search trees, which can only ever have two links to two nodes at any given time.

But what if we did something kind of crazy and just…threw these rules out the window? Well, as it turns out, we totally can do that! It'due south merely that we wouldn't be dealing with trees anymore — we'd be dealing with something called a graph.

Trees are nothing more than than restricted types of graphs, but with many more than rules to follow . A tree volition e'er exist a graph, but not all graphs will be trees.

So, what is it that makes a tree different from the large umbrella of graphs?

Well, for 1 affair, a tree tin only catamenia in one management, from the root node to either leaf nodes or child nodes. A tree can too only have 1-way connections — a kid node tin only have ane parent, and a tree can't have whatever loops, or cyclical links.

Tree data structures as compared to graph data structures

With graphs, all of these restrictions go direct out the window. Graphs don't have any concept of a "root" node. And why would they? Nodes can exist connected in any way possible, really. I node might be connected to 5 others! Graphs also don't have any notion of "one-directional" flow — instead, they might accept management, or they might accept no management whatsoever. Or, to complicate matters farther, they could accept some links that have direction and others that don't! Only we won't get into that today.

Let'south stick with the unproblematic stuff to start.

Graphs with direction, and graphs without

Okay, so we know that graphs pretty much interruption all the rules that nosotros know. Even so, there is one characteristic that every graph must accept: every graph always needs to take, at the very to the lowest degree, one single node. Just as how copse need at least one root node in society to be considered a "tree", similarly, a graph needs at least a single node in order to be considered a "graph". A graph with just one node is unremarkably referred to as a singleton graph, although nosotros won't really be dealing with those.

Virtually of the graphs we'll exist dealing with are a bit more than complex. But, don't be worried — we won't be diving into the super complicated graphs today. And trust me, some graphs really are complicated!

Instead, let's wait at the two types of graphs that are pretty easy to spot, and besides pretty common in graph theory problems: directed graphs, and undirected graphs.

Equally we know, at that place are no real rules in the way that one node is continued to another node in a graph. Edges (sometimes referred to equally links) tin can connect nodes in any mode possible.

Edges can connect nodes in any way possible!

The dissimilar types of edges are pretty of import when it comes to recognizing and defining graphs. In fact, that's one of the biggest and most obvious differentiators between 1 graph and another: the types of edges that it has. For the most part (aside from 1 exception, which we won't cover today), graphs can have 2 types of edges: a edge that has a direction or flow, and an edge that has no direction or menses. We refer to these as directed and undirected edges, respectfully.

In a directed border, two nodes are continued in a very specific way. In the example below, node A connects to node B; at that place is only one way to travel betwixt these two nodes — just one management that we can go. It's pretty common to refer to the node that we're starting from as the origin, and the node that we're traveling to as the destination. In a directed border, we can only travel from the origin to the destination, and never the other way around.

Directed edges compared to undirected edges

Notwithstanding, it's an entirely different story with undirected edges. In an undirected edge, the path that we can travel goes both means. That is to say, the path between the two nodes is bidirectional, pregnant that the origin and destination nodes are not stock-still.

This differentiation is actually pretty of import, because the edges in a graph determine what the graph is chosen. If all of the edges in a graph are directed, the graph is said to be a directed graph, also called digraph . If all of the edges in a graph are undirected, the graph is said to be — you guessed it — an undirected graph! Go figure, right?

Directed graphs equally compared to undirected graphs

This is all very cool, merely at this betoken, I desire to know two things — where did all of this graph stuff come from, exactly? And…why should we care?

Let's investigate.

Tread lightly: we're in graph country at present

Computer science loves to borrow stuff. More than specifically, it has borrowed a lot of concepts from logic and mathematics. Equally it turns out, this is the case with graphs.

Graph data structures as we know them to be computer science actually come from math, and the study of graphs, which is referred to equally graph theory.

In mathematics, graphs are a way to formally correspond a network, which is basically just a drove of objects that are all interconnected.

As it turns out, when computer scientists applied graph theory to code (and ultimately implemented graphs as information structures), they didn't alter a whole lot. So, a lot of the terms that nosotros apply to draw and implement graphs are the exact terms that we'll find in mathematical references to graph theory.

For example, in mathematical terms, nosotros describe graphs as ordered pairs. Retrieve high school algebra, when we learned about (x,y) ordered pair coordinates? Similar deal here, with 1 difference: instead of x and y, the parts of a graph instead are: five , for vertices, and e , for its edges.

The formal, mathematical definition for a graph is but this: K = (V, E). That's information technology! Really. I promise.

A very cursory introduction to graph theory

But hang on a second — what if our graph has more than one node and more than one edge! In fact…information technology volition pretty much always take multiple edges if it has more than than one node. How on world does this definition piece of work?

Well, it works because that ordered pair — (V, E) — is actually made up of 2 objects: a ready of vertices, and a set of edges.

Okay, that makes more sense to me at present. Simply it would be a whole lot clearer if I had an instance and actually wrote out the definition of a graph! So we'll do just that. In the example below, nosotros have an undirected graph, with 8 vertices, and 11 edges.

Then what's going on here?

Well, nosotros wrote out our ordered pair (V, E), but considering each of those items is an object, we had to write those out also. We divers Five as an unordered fix of references to our 8 vertices. The "unordered" part is really of import hither, considering remember, unlike trees, there is no hierarchy of nodes! Which ways that we don't demand to order them, since order doesn't matter here.

Nosotros also had to define E as an object, which contains a bunch of edge objects within it. Notice yet once more that our edge objects are also unordered. Why might that be? Well, what type of graph is this? Is there any direction or flow? Is there a fixed sense of "origin" and "destination"?

Nope, there's not! This is an undirected graph, which means that the edges are bidirectional and the origin node and destination node are not stock-still. So, each of our border objects are also unordered pairs.

This particularity, of grade, leads us to wonder: what if this were a directed graph? Fourth dimension for some other example! Here'due south a directed graph, with three vertices and three edges:

The way nosotros define the vertices here doesn't look whatsoever different, just permit's await more closely at our edge definition. Our border objects in this instance are ordered pairs, because management actually matters in this case! Since we tin can but travel from the origin node to the destination node, our edges must be ordered, such that the origin node is the first of the two nodes in each of our edge definitions.

Absurd, so that's how nosotros ascertain graphs. But…when would we ever really use graphs? Well, you probably used one today. You might just not know it nonetheless! Time to change that.

Super social graphs

Graphs are all around us, we just don't always see them for what they are.

In fact, by the very act of reading this post, you lot are literally on a graph right now. The web is a massive graph construction! When we click between websites and navigate back and forth between URLs, we're really simply navigating through a graph. Sometimes those graphs have nodes with edges that are undirected — I tin become dorsum and forth from one webpage to another — and others that are directed — I can but go from webpage A to webpage B, and never the other way around.

But in that location'southward an even improve example that beautifully illustrates our daily interactions with graphs: social networks.

Facebook, a massive social network, is a type of graph. And if we call up more near it actually functions, we start to meliorate understand how we tin define, and exactly what blazon of graph it is. On Facebook, if I add you as a friend, you must accept my request. Information technology'southward not possible for me to be your friend on the network without you likewise being mine. The human relationship betwixt two users (read: nodes or vertices in graph terms!) is bidirectional. There's no concept of an "origin" and a "destination" node — instead, you're my friend and I am yours.

Can you lot guess what blazon of graph Facebook is implemented every bit?

Facebook as an undirected graph structure

If you lot guessed undirected graph, and then you're right! Well done. Relationships are ii-way, and so if we were to define Facebook's friend network as a graph, its edges would all end upwards being unordered pairs when nosotros wrote them out.

Twitter, on the other hand, works very differently from Facebook. I tin can follow you lot, but you might not follow me dorsum. Example in point: I follow Beyonce, but she definitely does non follow me dorsum (sadly).

We could correspond Twitter equally a directed graph. Each edge we create represents a one-way relationship. When you follow me on Twitter, you create an edge in the graph with your account as the origin node, and my account as the destination node.

So what happens when I follow you dorsum? Do I change the edge you created when you followed me? Does information technology suddenly become bidirectional? Well, no, because I could unfollow you at whatsoever given bespeak. When I follow you back on Twitter, I create a 2nd edge, with my account equally the origin node and yours as the destination.

The same model applies to Medium, also, which lets yous follow and unfollow authors! In fact, this network model is all over the place. And all it is, once we abstruse all the layers away, is a graph. And truly, what a powerful affair it is.

Resources

Lots and lots of entire books have been written about graphs. I certainly didn't cover enough information here to fill up a book, only that doesn't mean you tin't continue learning about graphs! Fill your mind with more than graph theory awesomeness, starting with the great links below.

Departure betwixt trees and graphs, Poonam Dhanvani
What's the difference between the data structure tree and graph?, StackOverflow
Applications of Graph Theory In Computer Science: An Overview, Southward.Thou.Shirinivas et. al.
Graph Traversal, Professor Jonathan Cohen
Data Structures: Introduction To Graphs, mycodeschool