Description

We kick off season 3 with time travel! We go all the way back to 1735 to a lovely place called Königsberg. It had seven bridges and a tricky math problem that led to the creation of graph theory. Can you solve the problem?

Show Notes

This episode of the Basecs podcast is based on Vaidehi's blog post, Königsberg: Seven Small Bridges, One Giant Graph Problem from her basecs blog series.

Transcript

[00:00:00] SY: (Music) Welcome to the Basecs Podcast, where we explore the basics of computer science concepts. I'm your host, Saron, founder of CodeNewbie.

[00:00:09] VJ: And I'm Vaidehi Joshi, author and developer.

[00:00:12] SY: And she is the brilliant mind behind the basecs blog series. We are back with Season 3, and today we're talking about...

[00:00:19] VJ: Graph theory.

[00:00:21] SY: This season of the Basecs Podcast is brought to you by our wonderful friends at Twilio. If you haven't checked out their API yet, you totally should. With Twilio, your app can send text messages and make phone calls with just five lines of code. And for a lot of developers, Twilio is the first API they've ever used. And that first time you type a few lines of code, run your program and see your phone light up with the text message? It's kind of magical. And as a thank you for being a podcast listener, you get a promo code for twenty dollars in free Twilio credit. Just text your name to 480-485-4321. You'll also get a link to a quick start guide for your favorite programming language. So text 480-485-4321. Link to that is in your show notes. Ok. Let's get started.

[00:01:11] SY: Ok so this episode is going to be about graph theory, but that's not where we're going to start. We're actually gonna start by talking about bridges. Why are we talking about bridges?

[00:01:22] VJ: Because bridges are awesome. They let you get from...

[00:01:25] SY: They are awesome.

[00:01:25] VJ: They let you get from point A to point B, which like, you know, is pretty cool. But also they, they kind of are the fundamental origin of where graph theory came from because if bridges didn't exist, we would've have probably never ended up with graph theory and graphs and graph traversal algorithms and all the cool things in computer science and math and around us that are related to graphs.

[00:01:53] SY: Ok. So when I think of bridges, I definitely don't think of computer science. I think of—what's the engineering that's for real life? (Laughing)

[00:02:04] VJ: Civil engineering

[00:02:04] SY: Like physical... Ok. Thank you. Not that fake life. Not that, you know, programming crap. Yeah, like, like physic—buildings, and you know, people who build buildings. That's what I think of when I think of bridges. I definitely don't think of—well I guess math is a part of that. Ok I definitely I don't think of computer science. So how, how do bridges relate to computer science?
[00:02:31] VJ: Well bridges are connections usually, right? And usually, if you think about bridges, you probably start to visualize a bridge over water, and it's usually connecting one landmass to another.

[00:02:47] SY: Yes.

[00:02:48] VJ: But really if you think about it even more abstractly—and we kind of mentioned this little bit earlier—bridges are connections between point A and point B and some sort of origin and some sort of destination. And the interesting thing about bridges and connections between two different places is that we think about it often in the context of a map, but connections between two things don't always have to be on maps. They can be, you know, more abstract. And we've kind of hinted at that I think in the season finale of Season 2. We talked a little bit about graphs and like how they're connections between things. So the interesting thing with bridges is that they're connections. They're connections between two landmasses, but if you think about it even more abstractly and kind of forget a bridge between land and over water, bridges are connections between two things. They could be really anything, and you know, for the sake of simplicity we could just say a bridge could be a connection between A and B; some sort of origin and some sort of destination. And if you think about this in terms of graphs, we've kind of talked about this in a previous episode, but graphs are also connections between two different points. And the technical term that we use is nodes or vertices.

[00:04:10] SY: Right.

[00:04:10] VJ: And those are like our point A and our point B. And we've defined graphs in previous episodes, but the thing that connects the vertices—the nodes, if we need a quick refresher—those are called edges. Those are the links that connect one vertex to another vertex. So you can kind of think of a bridge connecting two landmasses as an edge between one node and another.

[00:04:37] SY: Ok, so all that makes sense, and we did talk about those, those terms, the nodes and the vertices and stuff. I can't remember what episode it was, but definitely in Season 2. But you keep talking about landmasses and I have a feeling you have some particular landmasses in mind. Are you referring to a particular place or something that has to do with...?

[00:05:00] VJ: Oh yes I am.

[00:05:02] SY: Ok. Ok. (Laughing)

[00:05:04] VJ: I'm…

[00:05:04] SY: Ok, tell me about that.

[00:05:04] VJ: ...so glad you asked. I love this place. I really wanna go if anybody wants to fund my trip here. (Laughing) I'm gladly taking donations. Except it's like... Now it's in Russia. So I guess—I don't know what the visa process is like for me to go there. (Laughing)

[00:05:21] SY: Right. We may have to wait a while.

[00:05:22] VJ: Yeah. Maybe. The town that I wanna I tell you about is a town that is now in Russia but used to be in Germany. We're talking about back in 1735, there was a place called Königsberg. And Königsberg was a city that was built on a river. It was called the Pregel River. And it actually was like a bunch of settlements at first, and then over time, the settlements started like, you know, combining and turned into a city. And it was pretty cool because the settlements one of them was on this island in the middle of the river and then there were other settlements around the river. So what they did was they created bridges to connect the different parts of the city. And the city had like, as I mentioned, this river going through it. So those bridges were kind of important in terms of like getting around from one end of the city to the other, and it ended up becoming a connection from different ends of the city of Königsberg. The reason that this city is so interesting and the reason that I think it kind of is like the heart of where graphs and graph theory and this entire branch of math and computer science came from was that it had a very interesting problem. It was kind of like, you know, this fun little game that the citizens of Königsberg would play, which is that there used to be seven bridges. And these seven bridges connected the different settlements, the different sections of the city. And the citizens of Königsberg, they used to like do this thing where on Sunday's when it was beautiful outside, they would walk around the town. And they played this game where they had this goal of trying to cross every single bridge only once and going from one land mass to the other without repeating themselves.

[00:07:11] SY: That sounds like such a, a healthy game. Like it sounds like the city said, "we need to be healthier, you know? Break out those fitbits. (Laughing) We're gonna play a town game, and everyone has to join." Doesn't it sound like that? Doesn't it sound like a sneaky health initiative...

[00:07:27] VJ: Oh my gosh. It does.

[00:07:28] SY: ...that the town came up with? That's brilliant. That's really smart.

[00:07:31] VJ: Yeah.

[00:07:31] SY: I like that.

[00:07:31] VJ: All these, all these folks would like walk around the city of Königsberg, and they were like, "oh let's see if we can like try to, you know, solve this riddle. And like let's see if I'm the one who can cross every single bridge once." But nobody actually ended up being able to do it. The word about this city and its kind of complex bridge situation kind of spread from one town to the other. And eventually, this bridge problem made its way to a very, very intelligent fellow named Leonhard Euler.

[00:08:05] SY: I've heard that name.

[00:08:06] VJ: Yeah, and...

[00:08:07] SY: Was he particularly oily? (Laughing)

[00:08:11] VJ: I mean I don't think they showered that much back then, so probably everybody was.

[00:08:16] SY: There you go.

[00:08:16] VJ: You know?

[00:08:16] SY: There you go, there you go. I've waited seventy minutes to say that joke. I'm so... (Laughing)

[00:08:21] VJ: You've been waiting since the beginning. You're like, "where can I, how do I work it in?" (Laughing) Wow. I'm getting so side-railed about this oily thing.

[00:08:31] SY: Sounds like a slippery problem.

[00:08:32] VJ: Oh God. So anyways Leonhard Euler. He finds out about this town. An important fact: he's a mathematician. And he hears about this town of Königsberg and he's like, "this seems, this seems like kind of a boring question of like can you walk across it? Who really cares?" But then he thinks about it more, and when he realizes he can't just solve it easily, he's like, "wait, this is not that simple. Why can't I use like geometry or algebra or even just counting to solve this problem? If I can't solve it so easily like this is maybe worth investigating." So...

[00:09:11] SY: He sounds like a douche. (Laughing)

[00:09:15] VJ: Oh no.

[00:09:16] SY: He's like if I can't solve it easily, this is finally interesting, worthy of my big, massive brain.

[00:09:23] VJ: Oily, oily brain. I feel so bad. Maybe Euler was really nice, and I'm just personifying him in a terrible way. Oh he did, he did, he did say that though. He did say that it only seemed worthy of his attention when he realized that he couldn't use geometry, algebra or even the art of counting to solve this problem. So...

[00:09:45] SY: "The art of counting." Wow.

[00:09:46] VJ: Maybe he was kind of an asshole, but it's fine.

[00:09:49] SY: It's ok. It's fine.
[00:09:51] VJ: But anyways, he got so entranced by this eventually, that he was like "I need to figure out how to solve this problem." And that's where we suddenly have graphs and bridges come together.

[00:10:04] SY: Ok, that seems like a pretty big leap. (Laughing) That seems like a pretty—like there's this oily guy. And he's like finally I, you know, I have an interesting problem with this, you know, town and their bridge situation. And then we have graphs.

[00:10:18] VJ: The interesting thing is that this is back in 1735, and graph theory doesn't exist. Graphs aren't a thing. Nobody's been like, "hey, look at these nodes and vertices." (Laughing) No. It's not a thing. What Euler does is he's like, he's looking at this map of Königsberg, and he realizes that it's kind of going to be painful to like write down every single path you can take. And you can kind of imagine like if you had to do this for—solve this problem on your own, that would probably be a really inefficient way of solving it because you'd have to, you know, write every single path in every single way you could go. And depending on how many bridges there are, that could be a very bad approach. So when he realized that it wasn't going to be very sustainable and not very scalable, what he decided to do instead was he simplified the problem. And the way that he simplified it was by visualizing it. He looked at the bridges, and he looked at the two landmasses, and he looked at the connection between them. And he realized that what mattered was less the actual map and more the connections between the landmasses. If you look at his old, his old notebooks, which luckily are preserved so we have his writings and his, you know, thought process and explanations of how he solved this problem, he has like these landmasses that are like A, B, C and D. He's just labeled them on the map. And then he abstracts them out, and then he just turns them kind of into basically like dots and lines a little bit. If you look at his drawings, and if you can kind of visualize dots on lines, then you start to see that these are kind of the earliest graphs and those dots and lines eventually become vertices and edges.

[00:12:04] SY: Interesting. So he kind of through this weird secret health initiative of this town, (Laughing) it sounds like he created the first what we would, you know, call a graph.

[00:12:17] VJ: Yeah. Graphs in computer science are actually based on graphs and the representations of graphs in mathematics. So in mathematics we represent graphs with sets of vertices and edges. And it's usually through an ordered pair if it's a directed graph, which means there's directional flow. And if it's an unordered pair that means there's no directional flow. You can go from one node to another. But at the end of the day, it's just sets of either letters or numbers to represent what the different nodes are and how to get from one to another. So he basically took the mathematical idea behind that, actually created it—he's basically the father of graph theory—because nobody had really thought to take this topological, this map and turn it into a math problem, which is really the genius behind what he did. And that's kind of where graph theory started from, and that's—the mathematical foundations of it are what led to computer science borrowing from math. And graphs are kind of everywhere in computer science as we've talked about in previous episodes and networks and in...

[00:13:26] SY: Yeah.

[00:13:26] VJ: ...social networks and in lots of different traversal problems, too.

[00:13:30] SY: Ok, so what did he, what did he find? What did he discover about the, the problem of can you in fact go across all these bridges and landmasses but only go through each thing once?

[00:13:43] VJ: He found out that it is not possible to cross over those seven bridges only once without repeating yourself.

[00:13:50] SY: Why?

[00:13:52] VJ: He figured out that there are only certain situations in which you can not repeat yourself. And I, I've been using the word like not repeat yourself, I've been using that phrase, but there's some probably good technical terms that we can kind of use to help ourselves out here because they're pretty common in talking about graphs and you'll hear these terms used. And it's good to know what it means. So we talked a little bit about graphs and getting from point A to point B. The reason that we usually talk about going from one point, one node or one vertex to another is because we're trying to go from one place to another. And whether that means crossing from a landmass to another landmass over a bridge or we're trying to get from one node A and find another node B, something like that, you are usually when you're working with graphs going to have to work with more than just one node. You're usually looking at connections between nodes. So usually the term that most people are talking about when they talk about traversing through a graph is they're usually trying to get at the word "path," which is finding a path from one node to another. And when we use the term "path," what we're really talking about is having a node that we start from and finding the edges that we need to pass through in order to get to the node we're ending at. So we're usually starting with an origin node, and then we have to go pass through and go through different edges to get to our destination node. Another important thing is that if you look at some graphs, you'll see that there's lots of nodes and lots of edges and usually there's many, many different connections, which means that there are lots of different paths that you can take. So paths are just a general thing. Like you can probably take 16 different paths through, you know, one graph. That doesn't really help you that much. There's no rules. Like you're just saying, "oh, I just wanna get from point A to point B," and it doesn't, you know, it doesn't really matter if I'm taking the shortest route or not. I'm just trying to go from one place to another.

[00:15:53] SY: So let's say I have a, a graph that looks like a—what is called—a triangle. It's like "what is that shape with three points...?" So I have A, B and C, right? If I want to go from A to C, right? And it's a triangle, so they, they are connected. And I say "ok, I'm gonna do that by going just straight from A to C." That's one path.

[00:16:23] VJ: Yep.

[00:16:23] SY: Right?

[00:16:24] VJ: That is.

[00:16:25] SY: But if I say "I wanna go through B. So I'm gonna go A to B to C." That's another path.

[00:16:30] VJ: Yep. Those are two...

[00:16:33] SY: Ok. So those are two, just two independent paths.

[00:16:35] VJ: Yeah, and they're totally valid because all we're doing is just looking for possible paths.

[00:16:41] SY: Ok. What if I want to go from A back to A? Is that, like is that, is that a path? Or is that, is that—like if I wanna go A to B to C to A. Can I do a path back to myself?

[00:16:56] VJ: You can. And that's actually a special kind of path. The term for that is a cycle, which kinda makes sense because you're kind of going...

[00:17:04] SY: Yeah.

[00:17:04] VJ: ...in a circle.

[00:17:05] SY: That's very intuitive.

[00:17:07] VJ: The only rule with a cycle is that you have to end your traversal at the exact same node that you started off at.

[00:17:14] SY: Ok. Ok, I'm cool with that. Ok, so we talked about how from my triangle situation I can either go A-C, I can go A-B-C. I guess technically I could do like A-B-C-B-A-C. Like is that a path, too?

[00:17:29] VJ: Yeah. You're, you're going back, and you're going back through edges and nodes that you've been through before, but it is still...

[00:17:34] SY: Right.

[00:17:34] VJ: ...a path, technically.

[00:17:36] SY: Ok, so that kind of brings us back to this Königsberg problem where the whole thing is like you don't repeat yourself. So is that a different type of path? Is there something special about that situation, the circumstance?

[00:17:50] VJ: Yes. So that is something called a simple path. And I'm really glad that you brought it up because a lot of the times in computer science and like sometimes when people are in technical interviews are like, you know, they have a, a graph problem. It's very easy to confuse path with simple path, and what you just described is very different from, you know, your previous example of going through your triangle graph and going back repeating yourself and going back through nodes you've already been through before. So a simple path is unique in that it has a lot more rules. It's very constricted. In a simple path, you cannot repeat nodes or edges you've been through before while you're traversing. So your A to B to C to B to A—that is not a simple path because you're, you're backtracking. You're repeating nodes and edges you've done. But...

[00:18:38] SY: Inefficient.

[00:18:39] VJ: Yeah. It's, it's inefficient, which, which is why I think in computer science, people are usually talking about, you know, the quickest path or, you know, the one where you're not backtracking and repeating yourself. So what really most people are talking about and what the Königsberg problem was was finding a simple path where you don't repeat any bridge, you don't repeat any edge and you don't repeat any node or landmass that you've already crossed through.

[00:19:09] SY: So simple path is going from point A to point B without repeating yourself. Does that mean there's, there's like a simple cycle? Go back to A without repeating myself? Is that a thing?

[00:19:19] VJ: There is a type of cycle where you end up the same place that you started without repeating yourself.

[00:19:26] SY: Ok, what's that called?

[00:19:27] VJ: That's actually called a Eulerian cycle because...

[00:19:28] SY: Oh.

[00:19:30] VJ: I think it's also called a Eulerian circuit. That's, that's one of the actually like really cool things that Euler discovered through his abstraction, which is that you can have something called a Eulerian cycle, Eulerian circuit where you start at a node, you pass through all of the edges and all of the other nodes exactly once and you still end up at the same place you started.

[00:19:58] SY: Ok. So this idea of having a simple path—it feels like it would only happen in certain situations. And clearly with this town and their, you know, bridge configuration it did not work. What is that about their—I assume it's the, it's something to do with their setup. What is it about their setup that made a simple path just not exist?

[00:20:23] VJ: What Euler discovered and what he wrote in his proof was that the landmasses, or the nodes of the town of Königsberg, were just constructed in such a way that there weren't enough connections between the right nodes to make that type of path, that type of circuit possible. And in order to like really talk about connections the formal way, we need to talk about one term that we haven't gotten to yet. So we've talked about how edges are the connections between nodes, right?

[00:20:52] SY: Yeah.

[00:20:52] VJ: And that's how you figure out like which node is like possible to get to from another. But the term that we've kind of been, you know, circling around but not using is something called degrees. And what that really means is how many neighbor vertices does any vertex or node have? And that's kind of like when I say "this node can be connected to another node." Well maybe it's connected to three other nodes, which means it has three neighbors. So in your example of...

[00:21:23] SY: And three degrees.

[00:21:25] VJ: Exactly. That is totally right. So that's, that's the term that you would probably wanna use in your example of, you know, a simple triangle graph with A, B and C. Every single one of those nodes has a degree of two because every single one of those nodes has two neighbor vertices, two possible, you know, (Music) nodes that you can travel to.

[00:21:46] SY: And that is the end of today's show. If you liked what you heard, leave us a review and make sure to check out Vaidehi's blog post. Link to that is in your show notes. Also wanna give a huge shout out to Twilio for sponsoring the season. Make sure to check out their awesome API. To get your twenty dollars in free Twilio credit, text your name 480-485-4321. Phone number and link are in your show notes. Vaidehi, you wanna say good-bye?

[00:22:12] VJ: Bye, everyone.

[00:22:13] SY: Thanks for listening. See you next episode.

[00:22:17] VJ: Let me just start the sentence again. I got confused by my drawing for a second. (Laughing) It's like what? What am I saying?