1 00:00:00,820 --> 00:00:03,920 So, in this set of lectures we'll be discussing the minimum cut problem and 2 00:00:03,920 --> 00:00:07,300 graphs and we'll be discussing the randomized contraction algorithm. 3 00:00:07,300 --> 00:00:10,562 Randomize algorithm which is so simple and elegant and it's almost impossible to 4 00:00:10,562 --> 00:00:14,380 believe that it can possibly work but that's exactly at what we'll be approving. 5 00:00:14,380 --> 00:00:17,790 So one way you can think about these set of lectures, as a segue of sorts, 6 00:00:17,790 --> 00:00:20,920 between our discussion of randomization and our discussion of graphs. 7 00:00:20,920 --> 00:00:23,610 So we just finished talking about randomization in the context of sorting 8 00:00:23,610 --> 00:00:24,510 and searching. 9 00:00:24,510 --> 00:00:27,010 We'll pick it up again toward the end of the class when we discuss hashing. 10 00:00:27,010 --> 00:00:29,590 But while we're in the middle of randomization probability review, 11 00:00:29,590 --> 00:00:32,130 I'm going to give you another application of randomization 12 00:00:32,130 --> 00:00:33,360 in a totally different domain. 13 00:00:33,360 --> 00:00:37,590 In particular to the domain of graphs, rather than to sorting and searching. 14 00:00:37,590 --> 00:00:39,620 So that's one high level goal of these lectures. 15 00:00:39,620 --> 00:00:42,630 The second one, is we'll get our feet wet talking about graphs, and 16 00:00:42,630 --> 00:00:43,740 a lot of the next couple weeks, 17 00:00:43,740 --> 00:00:46,750 that's what we're going to be talking about, fundamental graph primitives. 18 00:00:46,750 --> 00:00:49,960 So this will give us an excuse to start warming up with the vocabulary, 19 00:00:49,960 --> 00:00:53,789 some of the basic concepts of the graphs and what a graph algorithm looks like. 20 00:00:55,360 --> 00:00:58,270 Another perk, although it's not one of the main goals, but I want to do, 21 00:00:58,270 --> 00:01:03,280 I do want to point this fact, compared to most of this stuff that we're discussing 22 00:01:03,280 --> 00:01:08,690 in this class, this is a relatively recent algorithm, the contraction algorithm. 23 00:01:08,690 --> 00:01:11,631 By relatively recent I mean, it's 20 years old. 24 00:01:14,309 --> 00:01:17,711 But at least that means most of us, I know not all of us, but 25 00:01:17,711 --> 00:01:22,410 most of us at least were born at the time that this algorithm was invented. 26 00:01:22,410 --> 00:01:24,220 And so just one quick digression. 27 00:01:24,220 --> 00:01:28,510 In an intro course like this, most of what we're going to cover are oldies but 28 00:01:28,510 --> 00:01:31,200 goodies, stuff from as much as 50 years ago. 29 00:01:31,200 --> 00:01:33,790 And while it's kind of amazing, given how much the world and 30 00:01:33,790 --> 00:01:36,130 how much technology has changed over the past 50 years, 31 00:01:36,130 --> 00:01:40,280 that ideas in computer science from that long ago are still useful, they are. 32 00:01:40,280 --> 00:01:42,960 It's just sort of an amazing thing about the stuff that 33 00:01:42,960 --> 00:01:45,160 the first generation of computer scientists figured out. 34 00:01:45,160 --> 00:01:47,340 It's still relevant to this day. 35 00:01:47,340 --> 00:01:52,150 That said, algorithms is still a vibrant field with lots of open questions. 36 00:01:52,150 --> 00:01:55,540 And when I have an opportunity, I'll try and give you glimpses of that fact. 37 00:01:55,540 --> 00:01:58,490 So I do want to point out here that this is a somewhat more recent algorithm 38 00:01:58,490 --> 00:02:01,860 than most of the other ones we'll see, which dates back to the 90s. 39 00:02:03,210 --> 00:02:04,770 So let's talk about graphs. 40 00:02:04,770 --> 00:02:08,840 Fundamentally, what a graph does is represent pair-wise relationships among 41 00:02:08,840 --> 00:02:10,110 a set of objects. 42 00:02:10,110 --> 00:02:12,239 So, as such, a graph is going to have two ingredients. 43 00:02:13,960 --> 00:02:16,600 So first of all, there's the objects that you're talking about. 44 00:02:16,600 --> 00:02:20,430 And these have two very common names and you're just going to have to know both of 45 00:02:20,430 --> 00:02:22,120 the names, even though they're completely synonymous. 46 00:02:22,120 --> 00:02:24,160 The first name is vertices. 47 00:02:26,310 --> 00:02:30,000 So vertex is the singular, vertices is the plural. 48 00:02:30,000 --> 00:02:32,270 Also known interchangeably as nodes. 49 00:02:34,200 --> 00:02:37,610 I'll be using the notation V for the set up of vertices. 50 00:02:38,610 --> 00:02:41,980 So those are the objects, now I want to represent pair wise relationships so 51 00:02:41,980 --> 00:02:43,580 these pairs are going to be called edges. 52 00:02:45,050 --> 00:02:47,710 Will be noted by, denoted by E. 53 00:02:49,840 --> 00:02:52,950 And there's two flavors of graphs and both are really important. 54 00:02:52,950 --> 00:02:56,980 Both come up all the time in applications, so you should be aware of both kinds. 55 00:02:56,980 --> 00:02:59,770 So there's undirected graphs and directed graphs and 56 00:02:59,770 --> 00:03:04,670 that just depends on whether the edges themselves are undirected or directed. 57 00:03:04,670 --> 00:03:08,840 So edges can be undirected by which I mean this pair is unordered. 58 00:03:08,840 --> 00:03:12,010 There are just two vertices of an edge the two endpoints, say U and V, 59 00:03:12,010 --> 00:03:14,890 and you don't distinguish one as the first and one as the second. 60 00:03:16,540 --> 00:03:20,380 Or edges can be directed, in which case you have a directed graph. 61 00:03:20,380 --> 00:03:24,600 And here, a pair is ordered, so you do have a notion of a first vertex, or 62 00:03:24,600 --> 00:03:25,900 a first end point. 63 00:03:25,900 --> 00:03:28,560 And the second vertex or second end point of an edge. 64 00:03:28,560 --> 00:03:30,960 Those are often called the tail and the head respectively. 65 00:03:32,810 --> 00:03:36,030 And once in a while, although I will try to not use this terminology, 66 00:03:36,030 --> 00:03:38,090 you hear directed edges called arcs. 67 00:03:39,780 --> 00:03:42,480 Now I think all of this is much clearer if I just draw some pictures. 68 00:03:42,480 --> 00:03:45,880 Indeed one use to call graphs, dots and lines. 69 00:03:45,880 --> 00:03:51,070 The dots would refer to the vertices, so here's four dots, or four vertices. 70 00:03:51,070 --> 00:03:53,010 And the edges would be lines, 71 00:03:53,010 --> 00:03:57,670 so the way you denote one of these edges is you just draw a line between the two 72 00:03:57,670 --> 00:04:01,670 end points of that edge, the two vertices that it corresponds to. 73 00:04:01,670 --> 00:04:05,880 So this is undirected graph with four vertices and five edges. 74 00:04:05,880 --> 00:04:08,770 We can equally we'll have a directed version of this graph. 75 00:04:08,770 --> 00:04:14,500 So let's still have four vertices and five edges, but 76 00:04:14,500 --> 00:04:19,300 to indicate that this is directed graph and then each edge was first vertex and 77 00:04:19,300 --> 00:04:23,110 the second vertex, were going to add arrows to the line. 78 00:04:23,110 --> 00:04:28,670 So the arrow points to the second vertex, or to the head of the edge. 79 00:04:28,670 --> 00:04:32,520 So, the first vertex is often called the tail of the edge. 80 00:04:32,520 --> 00:04:34,075 So, graphs are completely fundamental, 81 00:04:34,075 --> 00:04:38,500 they show up not just in computer science but in all kinds of different disciplines, 82 00:04:38,500 --> 00:04:42,120 social sciences and biology being two prominent ones. 83 00:04:42,120 --> 00:04:45,733 So, let me just mention a couple of reasons you might use them just off 84 00:04:45,733 --> 00:04:49,783 the top of my head but literally there's hundreds or thousands of others, so 85 00:04:49,783 --> 00:04:52,304 a very literal example would be road networks. 86 00:04:52,304 --> 00:04:57,257 So imagine you type in asking for your driving directions from point A to point B 87 00:04:57,257 --> 00:05:02,374 in some web application or software, or whatever, it computes a route for you. 88 00:05:02,374 --> 00:05:05,985 What it's doing, is it's manipulating some representation of a road network, 89 00:05:05,985 --> 00:05:09,596 which inevitably is going to be stored as a graph, where the vertices corresponds to 90 00:05:09,596 --> 00:05:12,393 intersections and the edges correspond to individual roads. 91 00:05:12,393 --> 00:05:16,725 The Web is often fruitfully thought of as a directed graph, so 92 00:05:16,725 --> 00:05:23,110 here the vertices are the individual web pages, and edges correspond to hyperlinks. 93 00:05:23,110 --> 00:05:26,680 So the first vertex in an edge detail is going to be the page that contains 94 00:05:26,680 --> 00:05:27,792 the hyperlink. 95 00:05:27,792 --> 00:05:29,210 The second vertex, or the head of the edge, 96 00:05:29,210 --> 00:05:31,490 is going to be what the hyperlink points to. 97 00:05:31,490 --> 00:05:34,430 So that's the Web as a directed graph. 98 00:05:34,430 --> 00:05:38,660 Social networks are quite naturally represented as graphs. 99 00:05:38,660 --> 00:05:43,730 So here the vertices correspond to the individuals in the social network. 100 00:05:43,730 --> 00:05:45,550 And the edges correspond to relationships. 101 00:05:45,550 --> 00:05:46,940 They have friendship links. 102 00:05:46,940 --> 00:05:50,610 I encourage you to think about among the popular social networks these days, 103 00:05:50,610 --> 00:05:53,520 which ones are undirected graphs and which ones are directed graphs, 104 00:05:53,520 --> 00:05:55,980 we have some interesting examples of each of those.. 105 00:05:56,990 --> 00:06:01,200 And often graphs are useful even when there isn't such an obvious network 106 00:06:01,200 --> 00:06:02,210 structure. 107 00:06:02,210 --> 00:06:03,450 So just to mention one example. 108 00:06:03,450 --> 00:06:05,910 Let me just write down precedence constraints. 109 00:06:06,910 --> 00:06:09,370 So to say what I mean, you might think about, 110 00:06:09,370 --> 00:06:12,755 let's say you're a freshman in college and you're looking at your majors, 111 00:06:12,755 --> 00:06:17,920 you're a science major and you want to know what courses to take in what order. 112 00:06:17,920 --> 00:06:21,720 And you can think about the following graph where each of the courses in your 113 00:06:21,720 --> 00:06:27,590 major corresponds to a vertex And you draw a directed edge from course A to course B, 114 00:06:27,590 --> 00:06:29,720 if course A is a prerequisite for course B. 115 00:06:29,720 --> 00:06:33,700 That is, it has to be completed before you begin course B. 116 00:06:33,700 --> 00:06:38,520 Okay, so that's a way to represent dependencies, sort of a temporal ordering, 117 00:06:38,520 --> 00:06:41,040 between pairs of objects using a directed graph. 118 00:06:42,270 --> 00:06:44,470 So that's the basic language of graphs. 119 00:06:44,470 --> 00:06:46,310 Let me now talk about cuts in graphs. 120 00:06:46,310 --> 00:06:48,740 because again, this set of lectures is going to be about so 121 00:06:48,740 --> 00:06:50,020 called minimum cut problem. 122 00:06:51,090 --> 00:06:54,700 So, the definition of a cut of a graph is very simple, it's just a grouping, 123 00:06:54,700 --> 00:06:58,570 a partition of the vertices of the graph into two groups, A and B, and 124 00:06:58,570 --> 00:07:02,140 both of those two groups should be non-empty. 125 00:07:02,140 --> 00:07:03,580 So, to describe this in pictures, 126 00:07:03,580 --> 00:07:07,656 let me give you a cartoon of the cut in both the undirected and directed cases. 127 00:07:07,656 --> 00:07:13,270 So for an undirected graph, you can imagine drawing your two sets, A and B. 128 00:07:13,270 --> 00:07:15,320 And once you've defined the two sets A and 129 00:07:15,320 --> 00:07:18,730 B, the edges then fall into one of three categories. 130 00:07:18,730 --> 00:07:20,990 You've got edges with both of the endpoints in A. 131 00:07:22,380 --> 00:07:25,780 You've got edges with both of the endpoints in B. 132 00:07:25,780 --> 00:07:28,850 And then, you've got edges with one endpoint in A, and one endpoint in B. 133 00:07:31,300 --> 00:07:34,680 So that's generically what the picture of the graph looks like viewed through 134 00:07:34,680 --> 00:07:36,760 the lens of a particular cut, A B. 135 00:07:38,200 --> 00:07:40,430 The picture for directed graphs is similar. 136 00:07:40,430 --> 00:07:45,320 You would again have an A, and you'd again have a B, you have directed edges with 137 00:07:45,320 --> 00:07:49,880 both endpoints in A, directed edges with both endpoints in B. 138 00:07:52,016 --> 00:07:56,730 And now you should have two further categories, so you have edges who cross 139 00:07:56,730 --> 00:08:01,880 the cut from left to right, that is tail vertex is in A and 140 00:08:01,880 --> 00:08:05,900 the head vertex is in B and you can also have edges which cross the cut in 141 00:08:05,900 --> 00:08:10,713 the opposite direction, that is their tail is in B and their head is in A. 142 00:08:12,680 --> 00:08:14,030 Usually when we talk about cuts, 143 00:08:14,030 --> 00:08:17,570 we're going to be concerned with how many edges cross the given cuts. 144 00:08:17,570 --> 00:08:22,110 And by that I mean the following, the crossing edges of a cut (A,B) 145 00:08:22,110 --> 00:08:26,282 are those that satisfy the following property. 146 00:08:26,282 --> 00:08:28,060 So in the undirected case, 147 00:08:28,060 --> 00:08:31,090 it's exactly what you think it would be, one of the endpoints is an A, 148 00:08:31,090 --> 00:08:33,340 the other endpoint is in B, that's what it means to cross the cut. 149 00:08:34,870 --> 00:08:38,070 Now in the directed case, there's a number of reasonable definitions you could 150 00:08:38,070 --> 00:08:40,480 propose, about which edges crossed the cut. 151 00:08:40,480 --> 00:08:43,230 Typically and in this course, we're going to focus on the case 152 00:08:43,230 --> 00:08:47,530 where we only think about edges that cross the cut from the left to the right, and 153 00:08:47,530 --> 00:08:51,730 we ignore edges which cross from the right to the left. 154 00:08:51,730 --> 00:08:55,392 So that is the edges that cross the cut are those with tail in A and head in B. 155 00:08:55,392 --> 00:09:01,270 So referring to our two pictures, our two corrections of cuts for the underrated 156 00:09:01,270 --> 00:09:07,550 one all three of these blue edges would be the edges crossing the cut AB. 157 00:09:07,550 --> 00:09:09,530 because they're the ones that have one end point on the left side and 158 00:09:09,530 --> 00:09:10,600 one end point on the right side. 159 00:09:10,600 --> 00:09:13,449 Now for the directed one, we only have two crossing edges. 160 00:09:14,500 --> 00:09:17,640 So the two that cross from left to right. 161 00:09:17,640 --> 00:09:19,290 We have tail in A and head in B. 162 00:09:19,290 --> 00:09:21,560 The one that's crossing backwards does not contribute. 163 00:09:21,560 --> 00:09:24,465 We don't count it as a crossing edge of the cut. 164 00:09:24,465 --> 00:09:28,686 So the next quiz is just a sanity check that you've absorbed the definition 165 00:09:28,686 --> 00:09:29,758 of a cut of a graph. 166 00:09:32,531 --> 00:09:35,190 All right, so the answer to this quiz is the third option. 167 00:09:36,450 --> 00:09:39,620 Recall what is the definition of a cut, it's just a way to group 168 00:09:39,620 --> 00:09:44,560 the vertices into two sets A and B, both should also be not empty. 169 00:09:44,560 --> 00:09:48,729 So we have N vertices and essentially we have one binary degree of freedom for 170 00:09:48,729 --> 00:09:52,505 each, for each vertex, we can decide whether or not it goes in set A or 171 00:09:52,505 --> 00:09:56,672 it goes in set B, so two choices for each of the N vertices, that gives us a two 172 00:09:56,672 --> 00:10:00,159 to the N possible choices, two to the N possible cuts overall. 173 00:10:00,159 --> 00:10:03,185 Now that's slightly incorrect because we call that a cut. 174 00:10:03,185 --> 00:10:05,724 You can't have a non empty set A or a non empty set B, so 175 00:10:05,724 --> 00:10:09,130 those are two of the two to the N options which are disallowed. 176 00:10:09,130 --> 00:10:12,820 So strictly speaking the number is two to the N minus two, but 177 00:10:12,820 --> 00:10:15,969 two to the N is certainly the closest answer of the four provided. 178 00:10:17,230 --> 00:10:20,850 Now, the minimum cut problem is exactly what you'd think it would be. 179 00:10:20,850 --> 00:10:26,084 I give you as input a graph and among these exponentially, many cuts, 180 00:10:26,084 --> 00:10:31,595 I want you to identify one for me with the fewest number of crossing edges. 181 00:10:31,595 --> 00:10:36,391 So a few quick comments, so first of all the name for this cut is a min cut. 182 00:10:36,391 --> 00:10:39,986 A min cut is one with the fewest number of crossing edges. 183 00:10:39,986 --> 00:10:46,260 Secondly, to clarify, I am going to allow in the input what's called parallel edges. 184 00:10:46,260 --> 00:10:50,120 There will be lots of applications where parallel edges are sort of pointless, but 185 00:10:50,120 --> 00:10:53,190 for minimum cut actually it's natural to allow parallel edges. 186 00:10:53,190 --> 00:10:56,590 And that means you have two edges that correspond to exactly the same 187 00:10:56,590 --> 00:10:57,540 pair of vertices. 188 00:11:00,050 --> 00:11:02,990 Finally, the more seasoned programmers among you are probably wondering what I 189 00:11:02,990 --> 00:11:05,560 mean by, you're given the graph as input. 190 00:11:05,560 --> 00:11:08,210 You might be wondering about how exactly that's represented, so 191 00:11:08,210 --> 00:11:10,050 the next video's going to discuss exactly that, 192 00:11:10,050 --> 00:11:13,600 the popular ways of representing graphs and how you're usually going to do it in 193 00:11:13,600 --> 00:11:16,899 this course, specifically via what's called an adjacency list. 194 00:11:19,200 --> 00:11:22,060 Okay, so I want to make sure that everybody understands exactly what 195 00:11:22,060 --> 00:11:24,430 the minimum problem is asking. 196 00:11:24,430 --> 00:11:26,960 So, let me draw for you a particular graph 197 00:11:28,660 --> 00:11:33,020 with eight vertices and quite a few edges. 198 00:11:34,970 --> 00:11:39,680 And what I want you to answer is what is the min cut value in this graph? 199 00:11:39,680 --> 00:11:42,081 That is, how many edges cross the minimum cut, 200 00:11:42,081 --> 00:11:44,616 the cut with the fewest number of crossing edges? 201 00:11:48,205 --> 00:11:51,100 All right, so the correct answer is the second choice. 202 00:11:51,100 --> 00:11:54,030 The min cut value is 2 and 203 00:11:54,030 --> 00:11:57,649 the cut which shows that, is just to break it basically in half. 204 00:11:58,670 --> 00:12:00,130 And there were two halves. 205 00:12:00,130 --> 00:12:06,190 In this case, there are only two crossing edges, this one and this one. 206 00:12:07,210 --> 00:12:07,910 And I'll leave it for 207 00:12:07,910 --> 00:12:12,780 you to check that there's no other edge that has as few as two edges. 208 00:12:12,780 --> 00:12:16,820 Now in this case, we got a very balanced split when we took the minimum cut. 209 00:12:16,820 --> 00:12:18,160 In general, that need not be true. 210 00:12:18,160 --> 00:12:22,903 Sometimes even a single vertex can define the minimum cut of a graph, and 211 00:12:22,903 --> 00:12:27,355 I encourage you to think about a concrete example that proves that. 212 00:12:27,355 --> 00:12:30,062 So why should you care about computing the minimum cut? 213 00:12:30,062 --> 00:12:33,510 Well, this is one problem among a genre called graph partitioning, 214 00:12:33,510 --> 00:12:37,610 where you're given a graph and you want to break it into two or more pieces. 215 00:12:37,610 --> 00:12:40,404 And these kinds of graph partitioning problem comes up all the time, 216 00:12:40,404 --> 00:12:43,040 in a surprisingly diverse array of applications. 217 00:12:43,040 --> 00:12:45,790 So let me just mention a couple at a high level. 218 00:12:45,790 --> 00:12:49,603 So one very obvious one when your graph is representing its physical network, 219 00:12:49,603 --> 00:12:52,489 when identifying something like a min cut allows you to do, 220 00:12:52,489 --> 00:12:55,150 is identify weaknesses in your network. 221 00:12:55,150 --> 00:12:56,811 Perhaps it's your own network, and 222 00:12:56,811 --> 00:13:00,189 you want to understand where you soup of the infrastructure because it's, 223 00:13:00,189 --> 00:13:02,777 in some sense, a hot spot of your network or a weak point. 224 00:13:02,777 --> 00:13:05,038 Or, maybe there's someone else's network and 225 00:13:05,038 --> 00:13:07,476 you want to know where the weak spot in their network. 226 00:13:07,476 --> 00:13:11,880 In fact, there are some declassified documents about 15 years ago or so. 227 00:13:11,880 --> 00:13:15,570 Which showed that the United States and Soviet Union militaries, 228 00:13:15,570 --> 00:13:19,160 back during the Cold War, were actually quite interested in computing 229 00:13:19,160 --> 00:13:22,400 minimum cuts, because they were looking for things like, for example, what's 230 00:13:22,400 --> 00:13:27,070 the most efficient way to disrupt the other country's transportation network? 231 00:13:29,490 --> 00:13:33,710 Another application, which is a big deal in social network analysis these days, 232 00:13:33,710 --> 00:13:35,040 is the idea of community detection. 233 00:13:37,410 --> 00:13:39,910 So the question is among the huge graph, 234 00:13:39,910 --> 00:13:43,030 say the graph of everybody who is on Facebook or something like that. 235 00:13:43,030 --> 00:13:46,460 How can you identify small pockets of people that seem tightly knit, 236 00:13:46,460 --> 00:13:48,350 that seem closely related, 237 00:13:48,350 --> 00:13:51,410 from which you like to infer that there are community of some sort? 238 00:13:51,410 --> 00:13:54,520 Maybe they all go to the same school, maybe they all have the same interest, 239 00:13:54,520 --> 00:13:57,520 maybe they're part of the same biological family whatever. 240 00:13:57,520 --> 00:14:01,160 Now, it's to some degree still an open question how to best define communities 241 00:14:01,160 --> 00:14:02,290 and social networks. 242 00:14:02,290 --> 00:14:05,200 But as a quick and dirty sort of first order heuristic, 243 00:14:05,200 --> 00:14:09,640 you can imagine looking for small regions, which on the one hand, are highly 244 00:14:09,640 --> 00:14:15,029 interconnected among themselves, but quite weakly connected to the rest of the graph. 245 00:14:16,400 --> 00:14:19,280 So sub-routines like the minimum cut problem, can be used for 246 00:14:19,280 --> 00:14:22,800 identifying these small densely interconnected, but 247 00:14:22,800 --> 00:14:25,440 then weakly connected to everybody else, pockets of a graph. 248 00:14:26,870 --> 00:14:30,680 Finally, cut problems are also used a lot in vision. 249 00:14:30,680 --> 00:14:34,420 So for example, one way you can use them in what's called image segmentation. 250 00:14:36,040 --> 00:14:39,960 So here what's going on is you're given as input a 2D array 251 00:14:39,960 --> 00:14:42,100 where each entry is a pixel from some image. 252 00:14:43,500 --> 00:14:47,240 And there's a graph, which is very natural to define, given a 2D array of pixels. 253 00:14:47,240 --> 00:14:50,780 Namely, you have an edge between two pixels if they are neighboring. 254 00:14:50,780 --> 00:14:53,650 So for two pixels that are immediately next to each other left and 255 00:14:53,650 --> 00:14:55,920 right or top to bottom, you put an edge there. 256 00:14:55,920 --> 00:14:57,720 So that gives you what's called a grid graph. 257 00:14:57,720 --> 00:15:02,930 And now unlike the basic minimum cut problem that we're talking about here, 258 00:15:02,930 --> 00:15:06,030 in image segmentation it's most natural to use edge weights. 259 00:15:06,030 --> 00:15:10,090 Where the weight of an edge is basically how likely you expect those two 260 00:15:10,090 --> 00:15:12,019 pixels to be coming from a common object. 261 00:15:14,060 --> 00:15:17,420 Why might you're expect to enabling pixels to come from the same object, 262 00:15:17,420 --> 00:15:20,190 well perhaps their color maps were almost exactly the same and 263 00:15:20,190 --> 00:15:22,750 you just expected that they're part of the same thing. 264 00:15:22,750 --> 00:15:25,840 So once you've defined the screen graph which suitable edge ways now you run 265 00:15:25,840 --> 00:15:29,890 a graph partitioning or maybe cut type separate team, and the hope is that 266 00:15:29,890 --> 00:15:34,350 the cut that it identifies rips off one of the contiguous objects in the picture. 267 00:15:34,350 --> 00:15:36,000 And then you do that a few times and 268 00:15:36,000 --> 00:15:38,250 you get the major objects in the given picture. 269 00:15:39,730 --> 00:15:43,350 So this list is by no means exhaustive of the applications of min cut and 270 00:15:43,350 --> 00:15:46,230 graph partitioning server teams, but I hope it serves as 271 00:15:46,230 --> 00:15:49,440 sufficient motivation to watch the rest of the lectures in this sequence.