Description

We’re back in Königsberg, crossing bridges and taking names! We use a triangle to trace simple paths and finally get to the bottom of the seven bridges problem that helped launch graph theory.

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. Today we're continuing our conversation on...

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

[00:00:20] 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: Okay. So we are revisiting—or I guess we're staying 'cause we haven't actually technically left yet—an area...

[00:01:18] VJ: We got ourselves a little room. We committed.

[00:01:20] SY: We got a little AirBnB.

[00:01:21] VJ: Staying the night.

[00:01:22] SY: You know, just hanging out in Königsberg.

[00:01:26] VJ: Yeah. Königsberg.

[00:01:27] SY: I never feel like I'm saying that right 'cause it has the, the dots and the... You know what I'm saying? On the "o."

[00:01:34] VJ: Yeah. The dots throw everything for a loop.

[00:01:36] SY: Yeah. It makes me feel like I—there's no way I'm gonna be able to do this. We have seven bridges. And this area and this interesting mapping of their—is it a town? Is it a city? Where are we?

[00:01:49] VJ: Yeah, it was a... It's a town.

[00:01:51] SY: It's a town. Ok.

[00:01:52] VJ: Small city.

[00:01:53] SY: We're at this small city slash town essentially burst—that's a fun word to say. Burst graph theory. Kind of a big deal. Pretty big deal. Ok so just a recap. How it did that—there is the seven bridges problem, which has to do with the layout of the city slash town. So we have four landmasses, ok? Visualize four landmasses. We have a landmass A, which is kind of like in the middle. We have a landmass C, which is pretty big. Landmass—why did I go A, C? I don't know why I did that. I should've gone (Laughing) A, B, C, D.

[00:02:30] VJ: Just not into B today, I guess.

[00:02:35] SY: Screw B. B's being a real B. So we have landmass A in the middle; landmass B, which is kind of hanging out on the bottom; landmass C, which—well according to your, your drawing, it looks like the biggest. I'm assuming yours is accurate and correct.

[00:02:52] VJ: Obviously.

[00:02:53] SY: Obviously. Of course. Of course. To scale.

[00:02:56] VJ: It's not though.

[00:02:58] SY: And it's kind of taken over, you know, a good chunk of the, the top area. And then net to A in between B and C is our final landmass D. So if you imagine it is like a sandwich then C the top slice of bread, B is the bottom slice of bread. You got A, your peanut butter. And then to the right you have D, your jelly. You did not make a good PB and jelly sandwich.

[00:03:29] VJ: You made some semblance of bread, peanut butter and jelly in some order vaguely. You got the ingredients.

[00:03:34] SY: You got the ingredients right, but you didn't layer them properly. That's ok though. That's all right. (Laughing) Peanut butter and jelly was like we're tired of being together. We just want our own space. But it's not the landmasses really that we care about; it's the bridges connecting them. So between A and C we have two bridges. Between A and D—that's our peanut butter and jelly situation—we have a bridge. So they want space, but you know, they're still connected. Between A and B, we have two bridges. Between C and D—that's our top slice of bread and our jelly—we have one bridge. And then finally between D and B—that's our jelly and our bottom slice of bread—we have our last bridge. So we have seven bridges. And if this is hard to visualize, check out the blog post. Link is in your show notes.

[00:04:23] VJ: Yep. You did a great job of recapping that.

[00:04:26] SY: Yes. And I worked in food. This episode is going great. Ok. So before we get into this little bit more, we have to recap some terms. We just need to make sure we're all on the same page. So the first one is degree. What is a degree?

[00:04:44] VJ: Great question. So a degree is kind of exactly what you were describing just now when you were talking about the landmasses and how many bridges they have to other landmasses. But it's like a, a more technical term, so let's talk about it in the context of a graph. So if we think about Königsberg as the graph—or even if we just think about any old graph—a degree of a vertex or a node—just another name for a vertex—a degree of a vertex is the number of vertices that are adjacent to it. So in other words, the number of edges. That connect other nodes to that node or in even simpler terms, how many neighbors a node has.

[00:05:29] SY: Yep. Yep. Ok, so now what is a simple path?

[00:05:32] VJ: A simple path is a type of path that you use; basically use to traverse a graph. In other words, it's, it's like how you walk a graph. And usually what people are talking about when they're talking about graph traversal is going through the nodes and edges of the graph only once. So a simple path is basically walking through a graph and only traversing through each node and edge once and never repeating yourself.

[00:05:57] SY: Ok. So the not repeating yourself is important.

[00:06:00] VJ: Exactly.

[00:06:00] SY: So last episode, we used a triangle just to kind of solidify this. Let's do a quick recap of that. So if I have a triangle, triangle's got 3 points. That's why it's called a triangle. Well actually it's because it has three angles. Dammit. (Laughing)

[00:06:16] VJ: You said it with such confidence. I like that.

[00:06:18] SY: I did. I was like yes, nailing it. No, not at all. Ok, so my, my three points are A, B and C. So if I wanna get from node A to node C, right? That's a path. That's like... that's, that's one path.

[00:06:35] VJ: Exactly, yeah. And because you're working with a triangle, you could go to different directions, right? There's only three nodes, so you could basically go straight to C or you could go another direction. I guess that would be to B. And the fact that you've gone from one node to another that is a path. And in fact, it is the shortest path. The easiest way to go from A to C is literally just start at A; go to C 'cause you can.

[00:06:55] SY: Yeah. Ok. But if I wanted to visit all the nodes, all the people in the town and go A, B to C, that's also one path.

[00:07:06] VJ: Exactly. Yeah. And that is a path where you're visiting every single node. You're not repeating yourself. So you're following all the rules. And that's it actually. (Laughing)

[00:07:19] SY: Cool. And then if I want to start at A but then go back to A—so I'm gonna do an A-B-C-A, that's not only a path; it's kind of a special path.

[00:07:31] VJ: Yeah. It's almost like you came full circle, right?

[00:07:33] SY: Yeah.

[00:07:33] VJ: Even though it's a triangle, which is funny. We started at one node and you traversed through the whole path and ended back exactly where you started. And that is what we call a cycle or a circuit. And the reason that these terms are pretty important is because in the context of Königsberg, the Königsberg problem—and we kind of talked about this last episode—the types of paths that you can walk they're actually called Eulerian paths or Eulerian circuits. So an Eulerian path is one where you visit every single edge in the graph once and every single node. And a Eulerian circuit is exactly like a path except the one stipulation is that not only do you visit every single edge once, you also end on the exact same node that you started. So you walk around the town and you end up where you started versus you just walked around the town and walked through every single place once maybe not ending up in the same place you started.

[00:08:27] SY: Ok, cool. So we're gonna really dig into this bridge problem, and how, how that works and, and what the rules might be around that. But in order to do that, we are going to revisit this triangle, but we're gonna remix it. Can we remix it? Can we remix the triangle?

[00:08:46] VJ: Oh. We can remix it.

[00:08:47] SY: Yes. So there's a triangle, and you have A, right? And then off of A was—A, B, C—D, right? (laugher) I was like what’s the alphabet?

[00:08:57] VJ: I like that.

[00:09:01] SY: It was, was D, right? It's like isolated just only off of the A.

[00:09:03] VJ: D's just hanging out on its own.

[00:09:04] SY: D's just hanging out just, you know, just chillin'. It's living...

[00:09:07] VJ: Antisocial.

[00:09:07] SY: ...its best life. Antisocially. So D has one degree because it's only connected to A.

[00:09:16] VJ: One neighbor.

[00:09:17] SY: But A now has three degrees 'cause it has the B and the C, which it was already connected to because of the triangle. And then now it has, and now it has D. It has its little antisocial buddy. (Laughing) It's—"come on, D. Let's go." But then the C and the B, they each still have only 2 degrees because they're not actually connected to D.

[00:09:41] VJ: Correct.

[00:09:42] SY: Nice.

[00:09:43] VJ: So C and... C and B do not have any connections to D. D can only be connect, like gotten to, you can gotten to— (laughter) you can only reach D through A 'cause D is, you know, a little bit of an introvert. And...

[00:09:56] SY: Yeah.

[00:09:56] VJ: ...I get that. But another thing to note is you can have two neighbors, you can have three neighbors, you can have one neighbor. And so one of the ways that you can classify nodes and their degrees is by whether the degree is odd or even. So in your example, B and C are both of an even degree 'cause they have only two other nodes connected to them.

[00:10:17] SY: Ok.

[00:10:17] VJ: D, however, has an odd degree. It only has one connection. And the same thing with A. A has three neighbors. So that means A has an odd degree.

[00:10:28] SY: Ok.

[00:10:29] VJ: This is a really good way to bring it back to Euler, I think, because what Euler realized is that the degree of the nodes in a graph pretty much play the most significant role in terms of how you can get from one place to another and whether or not it's possible to create a cycle or a path. So what he realized is if you have an undirected graph—like the city of Königsberg would be an undirected graph because you can go from one end of the bridge to the other. There's no rule that you can only—you can travel bridges in both directions, right? So it's an undirected graph. But what Euler realized is that in order for you to be able to pass through all of the nodes in that Königsberg graph and pass through them only once and also end up at the same place you started, you must always have vertexes that are connected with an even degree.

[00:11:24] SY: All around.

[00:11:24] VJ: Yeah. So if you have any vertices that have degrees greater than zero, which means you can get to them basically—that's, that's the first rule. If you have like a landmass that's over there and you can't connect to it, it's not possible.

[00:11:36] SY: Yeah.

[00:11:37] VJ: So that's number one.

[00:11:39] SY: Yeah. Fair enough.

[00:11:40] VJ: You must have vertices with degrees that are greater than zero, which means you must...

[00:11:43] SY: Ok.

[00:11:43] VJ: ...have them connected. So all the vertices with degrees that are greater than zero have to be connected. And then also, they have to be connected with an even degree not an odd degree.

[00:11:54] SY: Ok. So with my triangle handle antisocial D situation, it sounds like we're kind of screwed because my B and my C have even degrees, so they have two each, which is great. But A has three degrees, and D has one. So they kinda of ruined it for everyone.

[00:12:14] VJ: Yeah. And if you think about it, imagine if you started D and then you go to A and then you get to B, then you go to C, then you go back to A. Oh no. You've already repeated yourself.

[00:12:24] SY: Yeah.

[00:12:25] VJ: You're back at A.

[00:12:25] SY: Yeah.

[00:12:26] VJ: And you can't even go back to D 'cause you will also repeat the path you already took.

[00:12:29] SY: Yeah. Dammit D.

[00:12:30] VJ: But previously, when you had just the triangle—A, B and C—all of them had...

[00:12:34] SY: Yeah.

[00:12:35] VJ: ...even degrees. And you could start from A, go to B and C and end up back at A. And you will remember that the Königsberg problem, that puzzle wasn't even about ending up back where you started. All it was was just a path. Just start from one place and end up...

[00:12:48] SY: Oh.

[00:12:49] VJ: ...at a different place, but just do not repeat yourself. It's a simple path. You cannot repeat yourself. So one Euler realized is that's a slightly easier situation. The cycle is like—it's very constricted.

[00:13:01] SY: That's hard.

[00:13:01] VJ: You gotta have even...

[00:13:02] SY: Yeah.

[00:13:02] VJ: ...degrees. But if you just wanna do a simple Eulerian path, then you still need all your vertices that have, you know, more than one degree to be connected, but also there is another rule which is that either two vertices must have an odd degree and the rest have to have an even degree or all the vertices in the graph have to have an even degree and none of them can have an odd degree. So either two odds and the rest are even or all evens.

[00:13:33] SY: Ok. So we have, we have a little bit more flexibility.

[00:13:36] VJ: A little bit more, yeah. And that, that's like still workable. You can still create a Eulerian path. Königsberg did not fall into that situation. Königsberg had, it had at least I think, four, four nodes, I think, that were of an odd degree, which is problematic because you can't have more than two nodes having an odd degree.

[00:14:01] SY: Ok so if we go back to our triangle with a handle example, we said that it does not qualify for an Eulerian—that's such a hard word to say—Eulerian circuit, which is fine. It's cool. It's fine. We still love it for what it is. But it sounds like it could work for an, a simple path, an Eu—is it called an Eulerian path as well?

[00:14:26] VJ: Yep. That's the term.

[00:14:27] SY: Yes. Ok. Ok Because if I were to start with my D, with my little shy buddy over there and then we go to A. And then we go to B. Then we go to C, and we go back to A and then we stop there, even though I've repeated my visit to A, I've only touched each edge one time.

[00:14:53] VJ: I—yeah, I think that would qualify because...

[00:14:56] SY: Woo-hoo. Yeah, yeah, yeah.

[00:14:58] VJ: ...you actually do have only two vertices with an odd degree, right? D and A.

[00:15:03] SY: Yeah. Yep, yep. Exactly.

[00:15:05] VJ: D and A both have a hard degree, and the other two are even. So that...

[00:15:07] SY: Yep.

[00:15:08] VJ: ...just makes the cut I think.

[00:15:09] SY: We did it. Yay. Aw, I’m so proud of you.

[00:15:13] VJ: See?

[00:15:14] SY: Good job. Good job triangle handle. (Laughing) Ok. So if we look at the, the graph version, the re-visualized version of the Seven Bridges of Königsberg, we have our A, B, C, D. So we have our four nodes, our four vertices, but the way they're connected is—I'm trying to decide what it—it almost looks like, like a row, like a leaf. It kind of looks like a leaf, actually.

[00:15:43] VJ: It does, yeah.

[00:15:43] SY: And if you haven't seen—yeah, if you have you haven't seen this, you should definitely check it out. It's in—we have, we'll have a link to it in the show notes, and it's a great illustration on Vaidehi's blog post. But yeah, it kind of looks like a leaf. Like you have—A is connected to D just going straight across. Ok this is when, you know, I, I wish I knew leaf parts. What's the part that goes from the bottom of the leaf to the top of the leaf? You know, the part that's like pointy? Whatever that is.

[00:16:11] VJ: Oh, not the stem, but whatever that... Yeah.

[00:16:14] SY: I wanna say stem, but it's not stem. Yeah. Ok whatever that is, right?

[00:16:16] VJ: It's like the continuation of the stem.

[00:16:18] SY: Here we go. Upside down heart. Ok?

[00:16:20] VJ: Parts of a leaf. Sure.

[00:16:22] SY: It kinda looks like a heart, a little bit. A little bit like a heart. We have the—I don't know heart parts. It doesn't matter. It doesn't matter because I don't know heart parts. (Laughing) Ok. Ok, the point is there's A on the left, D on the right. There's a line going straight from A to D. Then there's C on top, like above. So in between the A and the D. And there's B right below it. So it's like a, like a diamond-ish kind of thing. Like A and then above C and then to the right D and then at the bottom B. Ok?

[00:16:57] VJ: Yep.

[00:16:58] SY: Now A and D are connected, straight line. And then A and C are connected in two ways. This is the part that's just like what's happening? It has (Laughing) two edges, and—why does it actually have two edges? What is the C and the D edges? Why are there... Why are there two of them?

[00:17:17] VJ: Because if you, if you look at a map of Königsberg, there were two bridges that got you from one mainland to the island.

[00:17:24] SY: I don't know why these people like bridges so much. Ok, so (Laughing) we have, we have two bridges that are connecting A to C. And then we have another two bridges connecting A to B. So if we focus on A, we now have one bridge from A to D. We have two bridges from A to C, and then another two from A to B. So we are already at five, five degrees?

[00:17:50] VJ: Yep.

[00:17:50] SY: Or is it still three degrees?

[00:17:52] VJ: Nope. It's five.

[00:17:54] SY: Five degrees for A. So we're already at one odd, and we can have—well, ok. So the fact that we have one odd means that we've killed this whole cycle situation, right? Can't be...

[00:18:04] VJ: Cycle's definitely impossible.

[00:18:05] SY: Euler—yeah, totally impossible. No Eu... Eulerian—Jesus Christ. Eulerian (Laughing) circuit possible here, but we still, technically we still have a chance for the, for the path, the simple path, right? Ok. So now let's look at C, which is the one up top. Now C has remember those two bridges connected to S. So we're at two degrees, but then it has another connection, another edge from C to D. Dammit. So we're at three. We have three degrees. Ok.

[00:18:37] VJ: Ok. So we have one more. We're out.

[00:18:39] SY: We're screwed.

[00:18:40] VJ: We're out. We're out.

[00:18:41] SY: Ok, so we are—we've maxed out our number of acceptable...

[00:18:44] VJ: Odd degrees.

[00:18:45] SY: ...odd degrees. Yeah. Ok. So let's go down to B. B has those two connections, those two edges to A, and it's also connected to D. And we're out three.

[00:18:59] VJ: Yep, 'cause now you have three nodes that are odd, and the rule is two max.

[00:19:05] SY: Only 2.

[00:19:06] VJ: So...

[00:19:07] SY: And, you know, like...

[00:19:08] VJ: Thanks for playing. (Laughing)

[00:19:09] SY: Yeah. And you failed. If we look at D, though, like D is also kind of annoying. It has this connection to A, and it's also connected to C and connected to B. So it still has three. No one here wants to be a simple path. None of these vertices are cooperating on any level. All of them are odd.

[00:19:31] VJ: Yeah, you're right actually. I, I didn't even think about the fact that they're all odd so...

[00:19:35] SY: I feel like this was rigged. This whole thing was just rigged.

[00:19:37] VJ: These bridges have been laughing at us the whole time like...

[00:19:40] SY: The whole time.

[00:19:40] VJ: ...ha, ha, ha. Look at them trying to cross us. (Laughing) We'll show them. Silly humans.

[00:19:44] SY: They don't even know. Cool. Ok. Interesting. So what do we, what do we take away from this? Why, why are we—why do we even care about simple paths and Eulerian circuits and bridges in a, in a town? Like why, as computer scientists, as programmers, why do we care about any of this stuff?

[00:20:09] VJ: Two reasons. One, graphs are a very, very easy—well, let's, let's use the term "easy" loosely. (Laughing) Sometimes they're hard. But they're a very, very convenient way of visualizing and representing a lot of difficult problems. So like if you think about, you know, social networks. Social networks and the connections between people and social networks are basically graphs. So that's a very, very easy way of representing large amounts of data and the connections and relationships between that data. So that's part one of the answer. Part two of the answer is great. You have all this data, and you have the connections between them. You're usually trying to concern yourself with not just one piece of data but how it relates to other data. That's why graphs are so powerful. And when you start concerning yourself with the relationships between data, now what you're really thinking about is, you know, the edges, the connections between nodes, and really the degrees and how to get from one node, one piece of data and relate it and connect it to another, which really brings us to graph traversal. And graph traversal is a huge part of computer science because if you use graphs to represent data, then finding the relationships and the connections between that data means you have to walk through the graph. You have to find a path or sometimes you need to find a circuit or a cycle. But usually, what you're trying to do is you're trying to search through a graph or you're trying to find the shortest path. So you're not just trying to find one path. You're not just trying to be efficient and find a simple path where you don't repeat yourself. Sometimes you're trying to find all the simple paths and then take it a step further and find the quickest one. Or, you know, the one that will bring you from point A to point B the fastest. So this is really where the core of graph theory started from, and it's a great example of how something very practical can be abstracted to represent concepts that are (Music) sometimes easy, sometimes complicated, but in both cases can be broken down into a smaller problem and make it, makes it a little bit easier to solve, which is basically what Euler did. And we kind of see those same things in computer science and in mathematics today.

[00:22:26] 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:52] VJ: Bye, everyone.

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