>> Hello and welcome back to another screencast about relations. We saw in the last video what a relation is. A relation from A to B is just a set of ordered pairs in A cross B or a subset of A cross B. When the A and the B are the same, so we just have a bunch of ordered pairs from A cross A, then we say that the relation is a relation on A. Relations are pretty minimalistic and do not come with much in the way of rules to obey. So they're very flexible and they're able to model all sorts of interesting mathematical relations as well as data structures like social networks. Relations are sets of ordered pairs. But it's also helpful to represent them visually. Our very first example of a relation that social network that had five people in it, started as a sort of web of arrows where we represented each person as a point and an arrow pointing from one person to another if the first person follows the second person. In mathematics, the system of points and arrows is formally known as a directed graph. This is a different usage of the word graph than you are used to. In a directed graph, or digraph as we sometimes call it, we have points that represent people or objects, and those are called vertices. An individual one of these is called a vertex. And the arrows pointing from one vertex to another are called directed edges or just edges. So a directed graph is a system of points and edges where an edge points from one vertex to another. In our earlier example with the social network, we drew a directed graph for the network and then turned it into a set of ordered pairs. But we can also go backwards and that's what this video is all about, representing a relation on a finite set as a directed graph. It turns out that we can see things visually about a relation if we're represented in this way that might not be obvious just from looking at a relation as a set. So here's a simple example. Let's suppose we have a class full of students and you have them in a seating arrangement like this. We're going to keep the class size small, just 12 students, and we're going to label the students A through L. Now let's form a relation S on the set of students by letting A,B belong to S if and only if A sits next to B in the same row. So, for example, B,C belongs to the set S and so does J,K because B sits next to C immediately in the same row and so does J with relationship to K. But not A,C because A does not sit immediately next to C. Now what would the directed graph or this relation look like? Well, we're going to start by making 12 vertices, one for each student. And we're just going to draw an edge from one vertex to another, if the first vertex sits immediately next to the second one and in the same row. So in the back row or first row, however you want to think of this, I would draw an edge from A to B and also from B to A, because if A sits next to B then the vice versa is pretty clearly true, as well. I'd also draw an edge from B to C and also from C to B. But I wouldn't draw an edge from A to C, nor from C to A. And I also wouldn't draw one from A to D because, although, A and D are sort of next to each other, they are not in the same row. So it doesn't satisfy the relationship criterion. So I would just continue drawing edges like so. And here is the final result. As a second example, let's look at the Z7, which consists of the numbers zero, 1, 2, 3, 4, 5, and 6. And let's define a relation R on Z7 by setting A,B to be in this relation if A divides B. So let's draw the directed graph for this relation. We'll begin by introducing one vertex for each element of Z7. I'm going to arrange these in a circle here this time, just to make things easier to see. But there's no particular reason to arrange them this way. We're just going to draw a directed edge from A to B if A divides B. So let's start with zero. Now, zero doesn't divide anything. So there are no edges coming out of this vertex at all. And moving on to 1, 1 does divide everything here in the list. So I need to draw an edge from 1 to everything else. And also 1 divides itself. So I need an edge pointing from 1 back to itself, which is a directed loop, like so. And moving on to the number 2, 2 divides zero, itself, and 6. But nothing else. So we're going to draw three edges this way. And then we'll actually have to draw a loop, as well, from 2 to itself. The number 3 divides zero, itself, and 6. So I draw the loop and then these two other edges. The number 4 divides only zero and itself. And the same is true for 5 and 6. So all we'll do is draw loops and also an edge from those numbers back to zero. And that is the complete directed graph. So let's see how well you understand this concept with a concept check. Here's the digraph or directed graph for relation R on the set A, B, C, D. Looking at the graph, which of the following ordered pairs belongs to the relation R? Check all that apply and come back from pausing the video when you're ready. So all of these pairs, except the last one, belong to the relation R. The first four belong to the relation because we can see there's an edge pointing from the first coordinate to the second, A to itself, A back to B, B back to A, and C to D. But there is no edge pointing from D to C. So now you know how to represent a relation on a finite set as a digraph. Congratulations and thanks for watching.