Graph Theory is Wonderful!: Yeti Lunch and Learn

Video Transcript

Dean: Hi Everyone, I'm Dean. I work at Yeti as a software developer. this is going to be kind of a development related talk. It's called Graph Theory is Wonderful! This is a topic that I found on Wikipedia, trying to find a topic for the lunch and learn, and I was on it for like more than thirty minutes so I figured this would be good to talk about.

So kind of an overview of what we’re going to talk about. What is graph theory? I’m going to define it. We’ll have an example of it, and I’ll also talk about a little bit of the history like how did it start. I’ll also talk about why it matters particularly when it comes to graphs programming, and I’m going to have an example of a graph programming problem.

So what is graph theory? Graph theory is a branch of math that describes the networks of data as a simple ordered pair. Another example of an ordered pair would be like a Cartesian plane where you have like X is, your horizontal, and Y is like your vertical. But in graph theory we don’t really care about the physical nature of anything so the X or the V is the set of all the nodes that the graph is made up of. And then E is the set of all the edges that connect all of the nodes. And so I’ll show you what that looks like.

So here’s a really simple example of the graph. As you can see V are the nodes 1, 2, 3, and 4. And then we define E as the edge between 1 and 2, the edge between 1 and 3, the edge between 2 and 3, and the edge between 2 and 4.  So kind of as I stated earlier this isn’t like a Cartesian plane. So we don’t really care about the X, Y of where these points are on the map. We don’t really care about the shape. We just care about how they are connected.

So here’s an example of a problem. Let’s say that you’re at a conference with sixty-six other registered participants. That means you’re sixty-seven in total because it’s including you. The facilitator wants you to create a secret handshake with exactly five other participants in an effort to increase engagement. At the end of the event you’d be forced to demonstrated all five secrets handshakes on stage at the end of the event in front of everyone. Very scary.

Some conditions. You can’t create a secret handshake with yourself. A handshake must be between you and only one other participant. And so no three-ways handshakes, four-ways handshakes, more-ways handshakes. And each handshake has to be unique. So the problem is, is this possible given the number of registered participants and has the facilitator gone too far?

So kind of what we’ve learnt so far about graph theory in this scenario what would we represent as a vertex or a node?

AM: Person.

Dean: The people, right? The participants. Cool. And what would be like the edge or the link?

AM: Handshakes.

Dean: The handshakes? Yeah, cool. Everyone is paying attention. So this actually brings up a property of graphs that like mathematicians have figured out over time, and this property is called the handshake lemma, appropriately named. And so this states that all undirected, finite graphs have an even number of vertices that are connected with an odd number of edges. So if you’ll look to the graph on my left, your guess is right. The nodes don’t have ID numbers on them. They have the number of edges that are attached to them. So as you can see in this version, we have two nodes. One of them has three edges, the other one has one. And this holds true for pretty much any graph that you’re able to draw on paper. And you can try that out at home if you want. In our case with our handshake problem, this translates to, in the set of all participants there must be an even number of participants who have engaged in an odd number of handshakes.

So when we go back to our problem we have sixty-seven participants. Each one is asked to do exactly five handshakes with other participants. So that’s an odd number of vertices and an odd number of edges. So according to the handshake lemma, this isn’t actually possible. And so the conference must be cancelled.

So on your own at some point, originally we’re going to have pieces of paper to hand out and you could try it out for like five minutes or so. Try scaled-down scenario where you have five nodes or five participants and each doing exactly one handshake with each other. I will bet real life money that it can’t be done.

So kind of going into the history of graph theory, like how did it start? It’s pretty interesting. It kind of started with just basic geography. There’s a city in current day Russia called Kaliningrad. Its old name was Konigsberg when it used to be a part of Prussia.  And so Konigsberg had seven bridges connecting two of their islands to the rest of the landmasses. So it kind of looks like that map. And the residents would challenge people like visitors and each other. You should try to find a path that would cross all of the seven bridges exactly once. And they didn’t know if it was possible amongst themselves. But I like to imagine that if you do it then you find like the bridge to a like untold treasure. So they actually recruited a mathematician from Switzerland. H is name was Leonard Euler. He created a whole bunch of stuff by this point. So he did a lot of work to kind of prove that this path was actually impossible. The way he did that was he started by representing the landmass as a series of dots and the bridges as a series of lines connecting the dots. So as you can see this already looks familiar to like graph theory as we know it today.

And after some work he had proof for the following theorem. For there to be a single path through all the bridges, in which all the bridges are crossed exactly once across all landmasses there must be exactly either zero or two landmasses that have an odd number of bridges. And so we can kind of look at this diagram together and see if that’s the case. So how many bridges does A have? A is like the one at the bottom left. So that’s three. The one in the middle has how many? Like five. And then the third one at the bottom, like on the far right, how much does that have? Three. So it already kind of violates that principle. And so there is no way to draw a single path that hits each bridge once, and only once.

So why graph theory matters. Graphs are used a lot in programming in a lot of different applications. It’s a useful abstraction and it’s seen in places like databases. There’s a specific kind of NoSQL database called the graph database that really focuses on storing the relationship between things and not so much the structure, kind of that typological over format. And GraphQL is another example of technology that uses the graphs. Pretty much every piece of data you hook up to a resolver, that becomes a part of the big graph. And then we can use graphing algorithms to kind of track really important things like what is the closest path from point A to point B, and stuff like that. It’s a lot of algorithms that make solving problems with them much easier.

So here’s an example of such a problem. We are going to commute with graphs. My personal commute is on the board right now. So I go from home and I can take the Powell Street Station which will take me to the Civic Centre Station, to Van Ness, and then to Yeti. Or I could walk pretty much to any of the stations directly. I didn’t draw it here but I could get on to Powell, take the station to Civic Centre and then walk the rest of the way. So there’s a lot of different ways that this network can go. And let’s actually add weights to each of the edges. Let’s say the walk from my house to Powell Street is ten minutes. But if I wanted to walk all the way to Van Ness, it would take thirty-five minutes. Or I could walk to the Civic Centre and that would be like twenty minutes. You get the gist. So the problem is what path from home to Yeti do I could take to minimize my travel time?

So there’s a lot of algorithms for such a problem. The problem is called finding the minimum span tree. So the minimum span tree is just the path that you can take through all of the different nodes that will minimize the weight of each edge. And so in this case the weight of the edge is the travel time. So I would simply just google it and my programming language of choice is Python. As you can see there’s a bunch of different algorithms and actually even at the very bottom here there’s an implementation of minimum spanning tree. So that’s pretty promising. And I’d use that to basically plug in all the data from this graph and kind of try out a path. So pretty quickly to do like problem solving without too much work on my end, without too much research on my end.

So conclusion; graph theory is a very old branch of math that’s still being used today for computer science. It’s really easy to find graphs in nature and model problems off of graphs. There’s many graph algorithms that others have made and have researched that have opened the door to solving many actual problems. I have a bunch of sources at the bottom. If you’re interested I can share the slides with everyone. The one at the very bottom is actually pretty interesting because it talks about all the different algorithms that they found with graphs that you can use to solve a bunch of cool problems. And are there any questions? Let me play this. I’m sure people know what this one is. [Music Playing]. Cool. That’s it.

‍