[MUSIC] Hello everybody, today we will start with part two of this course and the topic of this part is graphs. So what is a graph, well that's easy to answer. For example, this here is a graph. So you see here some dots which are connected by lines. But in graph theory we call them specific names. So this such a thing here, a point, is called a vertex and the plural is vertices. So please don't say vertexes or something, no, no, no. Vertices. And a connection between two vertices is called an edge. That's just a name we give these things in graph theory. Okay, so you see here an example of a graph but what does it mean? Does it represent anything? So the nice thing about graph theory is a graph can represent a lot of things. For example, it could be that we have a dinner party with five guests, Alice, Bob, Daniel, Charlie and Eve. These are our five vertices and an edge between two people means that they have known each other already before this dinner party. So for example, Alice and Bob have known each other before coming to the dinner tonight. Whereas Eve and Charlie meet each other for the first time tonight. So this is kind of the relation that can be expressed as a graph. And why are graphs so important? Well because they appear literally everywhere, especially in all things that have to do with computers, where you want to solve some computational task. One example is this. This is the Shanghai Subway Network. It's actually kind of the middle part of the city because Shanghai is a big city. And here for example, our vertices would be the subway stations and there is an edge. An edge between two subway stations means that there is a direct subway line connecting the station to the next station. So this is also an example of a graph. Another example would be this. Which is an illustration of the internet. So here every vertex would be a computer. So most likely a server or an Internet router. And an edge between the two vertices means that there is a physical connection. Maybe a wire, or a fiber cable, or something like that between the two routers. And by the way, the colors in this picture, they represent the physical, the geographical locations, for example yellow, I think is Europe or something. But I don't want to give you any wrong impressions, so these graphs here, they can somehow nicely be drawn in 2D. There are some other graphs that are so huge that you are probably not able to depict them. So let's go back to our dinner party graph. And for now I just call my vertices 1 to 5 instead of Alice, Bob, and so on. So what is a graph? Mathematically speaking, a graph is a peer V, E where V is the set of vertices. And it's simply a finite set. There is also theory of infinite graphs but in this course we basically always state the finite graphs. And what is E, well E is the edge set, which describes which vertices are connected and which are not. And mathematically now with a notation that we have developed in the very beginning of this course, we can very elegantly say what E is. So E is a subset of of V choose 2. So it's a set of size two sets of vertices. This might sound very abstract so let's do it for this prop that you see here. The vertex set is simply the set of number one to five. And the set of edges is the following. So it contains 1,2, because there is an edge from 1 to 2. It contains 1,4. It contains 2,3, 2,5 what else? 3,4 and 4,5. So that's clearly a subset if V choose 2, that's our set edges. And a little bit more of notation, by n we denote the number of vertices and by m we denote the number of edges. So in this example n would be 5 and m would be 6. All right. That's the formal definition of a graph. So let's see, let's look at some more complicated graphs. Some of you might know this puzzle. I think it's called the fifteen puzzle if you want to go to Wikipedia and look it up. So we have this board, 4x4 board and we have fifteen tiles which are placed on this board and now you can move them. You can, for example, move tile number 6 into the empty space, and then you can move tile number 11 up, and if course you can make everything in reverse. You can move the 11 back where it came from. So how does that define a graph? So let's see. Every possibility how to arrange the tiles on this four by four square will be a vertex. So here I only show you three vertices but there is of course many more vertices. And what is an edge? Well let's say two configurations are connected by an edge if they are one move apart. So you see here for example, we can go in one step from here to here and back and therefore we insert an edge. So let's see this graph is really huge, how many vertices does it have? The number of vertices is equal, as you can see, to the number of injective functions from the numbers 1 to 15 into the set 4x4. You can convince yourself this is 16 factorial, so this is pretty huge. So this graph you can, most likely, not easily depict on paper. What is the number of edges? Well with what you know so far you can figure this out. So you should do that as a homework or you should just pause the video now and try to figure out what the number of edges is in this graph. Another example of a huge graph would be, for example, this. So this is Rubik's cube. I actually don't know how to solve it. I don't know how to bring it back into the order at state. But it can say, if I keep it like this in my hand, then this as the cube looks like, like now, that would be a vertex in your graph. And now I make a transition into a new configuration and I can do it back or I can go both ways. So this would be a new vertex and these two vertices are connected by an edge. So two states are connected by an edge, if I could go from one state to the other state in just one move. So this is a huge graph and it probably has a quite complex structure. Another example of a graph that is only implicitly given, and you usually don't draw it, is the so-called Kneser Graph. I'll let you plow through the definition. What I want to show you, just as an illustrative example, is the Kneser Graph 5,2. So here the vertex set are all element two subsets of the numbers one to five, and two sets are connected by an edge if these sets don't intersect. So if they are disjoined, here the graph would look like this. Well, this doesn't look too nice but we can actually make it very nice and symmetric by putting the vertices in kind of a different order like this. And then, the graph looks like this. This is also called, the Petersen graph. All right, so we have seen a lot of examples of graphs, what's next? There are some classes of graphs that appear over and over again. And we just have to go through them quickly and introduce the names. Such that you understand, in the future when I refer to them, what I'm talking about. The first important class of graphs, are the so called, complete graphs. Complete graphs. Well they're called complete because every edge that could possibly be there is there. So the set of edges is simply everything. It's the whole V choose tool. So this would be k6, that would be k5 and so on. And you see k1 just consists of just one lonely vertex. So these are the complete graphs. Another important graph class is cycles. A cycle is just a graph that looks like this, and well this will be Cn where you have let's say 1 invertices 1, 2, 3. Here is vertex i, here is vertex n-i, here is vertex n, here is vertex n-2. So cycles are also very important. And last, this is a class called paths. They are called paths because they look like paths. So this is a path of length two. Be careful, the length of a path is not the number of vertices in it. It is the number of edges in it. That's kind of a source of confusion, so we should be kind of clear about that. That's P3, this is one, two, three, four, five, that's P5, and this is P1, and this is P0. And this is a remark, this is actually equal to k1 and this is equal to k2. But of course this is equal to k3 because k3 looks like this. It has all the edges on three vertices and so on. So we have to find complete graphs, cycles and paths. This are arguably the most important graph courses. That's it for today, next time we'll do something interesting with graphs. Thank you for today. [MUSIC]
