[MUSIC] Hello, everybody. Today, we continue with graph theory. And the topic of today's lecture is subgraphs, paths, and connectivity. So here is a graph that we have already seen. And observe what I'm doing now. I'm selecting some of the vertices. Let's say, kind of the right half of this graph. And I select some of the edges that run between these vertices. Maybe like this. So what I get here is a subgraph of the big graph. Formally, (V prime, E prime) is a subgraph of (V, E) if V prime is a subset of V and E prime is a subset of E, okay. So again, here is the graph, and now we'll look at a different kind of subgraph. Again, I select some vertices. But now let's say the rule is, I have to take all the edges that run between these vertices. So I have to take this edge, I have to take this edge, this edge. This, this edge, and this edge. So I have a choice which vertices I take, but then I have to take all the edges between these vertices. This is called an induced subgraph. And here is the definition, it reads kind of a technical. So V prime is a subset of V, and E prime is now simply the edge set intersected with everything that lies within V prime. And you see, if you give me the set V prime that already determines the induced subgraph. But just setting G of V prime induced by V prime to be the following graph, V prime and E intersect with the set, okay? So this is an example, as we have seen, if my set is for example this, that's V prime, And then this is G[V prime], that's the induced subgraph, okay? So there is a difference between a subgraph, where I can take an edge or I don't have to take an edge, and the induced subgraph, where I have to take every edge that run between the selected vertices. A specific type of subgraphs are paths. So if, for example, I select these vertices and these edges, I get a subgraph, Which is 1, 5, 4, 1, 2, 3, 4, 5. Which is isomorphic to P5, to the path of length 5. And note, this is an example of a subgraph that is not an induced subgraph, because I didn't take this edge, and I didn't take this edge. But still, you see, it's a subgraph, and it's isomorphic to a path. So we just say, G contains, P5, just we say G contains a path of length 5, okay, because it does. It's a path, and paths are important, because of the following definition. If there is a path from every vertex to every other vertex, so you can go from everywhere to everywhere else. Maybe by quite longs paths, then we say the graph is connected. So connected means you can go from everywhere to everywhere else. And here is an observation that is almost trivial, but maybe you should take some time to prove it. If D is not connected, then it consist of two or more connected parts. In other words, you can partition the set of vertices into two parts, such that no edge goes from V1 to V2. So let me show an example for the last lemma. Here you have a graph, which is not connected. Because you, for example, cannot go from this vertex to this vertex. And of course, I can partition my vertex set into two parts. Okay, that's very easy. So is connectivity an easy problem? Well, it's not too difficult, but don't be fooled. So in this graph, for example, we just see that it's not connected because we drew it nicely, but how about this graph? Well, can you go from here to here? It's probably not difficult to find out, but it's not obvious if you look at it. How about this graph that we seen a couple of lectures before? Where this is a vertex, and an edge connects a vertex to a neighboring vertex, which, just one of these configurations that is one move apart. So this would, for example, be an edge. This would be a neighboring vertex, that's a third vertex, and that's the second vertex again. This graph, on many, many vertices, is it connected? Try to think about it. But you can see it's not always obvious whether a graph is connected or not. How about this graph? This doesn't look too complicated, it is in the plain, we can see everything of it. Is it connected? Well, you can try to find out. But here I can clearly demonstrate it to you that it's not connected, because I can take this part and move it apart. And then you see it's not connected. All right, so let's talk a little bit about algorithms. How can we find out whether a graph is connected? There is a very simple algorithm, it's called depth-first search. So it does the following, given a graph G, we start at some vertex u, and we mark u as visited. Just that later, we see that we've already visited u. And then what we do, for all neighbors of u, we check whether v is already marked. And if not, we recursively call depth-first search and continue. And the point is that, in the end, which vertices are marked? Well, the marked vertices are exactly the vertices that are in the same connected component as u. So such that there is a path from u to v. So let's do depth-first-search in an example. Here is, again, the graph from before. So let's start here, this is vertex number 1. And now it iterates over all its neighbors, and it sees this is not yet visited. So we call it recursively, and now we are here. So technically, the way I implemented it, this would now check whether the vertex appears as already marked. Yes, it's already marked. So we go to the next neighbor and we mark it. This has no more neighbors, so we go back. This has another neighbor, so we explore it, go up here. We try to go to this neighbor, but we see this is already marked. Well, let's actually give them numbers. Vertex 1 is already marked. So we go up here, mark it, and call it 5. 5 has no neighbors, so we go back to 4. 4 has no more neighbors, so we go back to 2. 2 has another neighbor, which is this, 6, and now you see, the red vertices are exactly the vertices that are in some way connected to 1. That's depth-first search. And here is a theorem, it's also obvious if think about it. If you have a graph, then you can partition the vertices in such sets that each G[Vi] is connected, and there is no edge between Vi and Vj. And these are called the connected components. And there's a little bit linguistic ambiguity. Because sometimes you call the vertex set the connected component, sometimes we call the induced graph the connected component. So pictorially, here's an example. Here is a graph. And now, by these colors, black, green, red and blue, I show you the four connected components of this graph. All right, these are the connected components. And that's it for today, thanks. [MUSIC]
