Explore
For Enterprise
Join for Free
Log In

예술 & 인문학
비즈니스
컴퓨터 공학
데이터 과학
정보 기술
건강
수학 및 논리
자기개발
물리 과학 및 공학
사회 과학
언어 학습
학위
수료증

Explore all of Coursera

검색
포 엔터프라이즈 (For Enterprise)
로그인
무료 회원 가입

Graphs and Minimum Cuts

Loading...

Divide and Conquer, Sorting and Searching, and Randomized Algorithms

스탠퍼드 대학교

4.8(2,798개의 평가) | 91K명의 학생이 등록함

알고리즘 전문 분야에서 4의 강좌 1

The primary topics in this part of the specialization are: asymptotic ("Big-oh") notation, sorting and searching, divide and conquer (master method, integer and matrix multiplication, closest pair), and randomized algorithms (QuickSort, contraction algorithm for min cuts).

강의 계획서 보기

배우게 될 기술

Algorithms, Randomized Algorithm, Sorting Algorithm, Divide And Conquer Algorithms

검토

4.8(2,798개의 평가)

5 stars
2,370 ratings
4 stars
364 ratings
3 stars
41 ratings
2 stars
10 ratings
1 star
13 ratings

FR

Mar 16, 2017

Very good course in algorithms. I bought the book to help me understand but the lectures make it way easier and thus much more fun to understand the analysis. Looking forward to complete the spec

NE

Nov 07, 2016

Personally, I would recommend this course to anyone who really wants to learn how things work in that sort of algorithms. I found the assignments a little difficult, but also extremely helpful.

수업에서

Week 4

Linear-time selection; graphs, cuts, and the contraction algorithm.

Graphs and Minimum Cuts15:50

Graph Representations14:22

Random Contraction Algorithm8:44

Analysis of Contraction Algorithm30:04

Counting Minimum Cuts7:18

강사:

Tim Roughgarden
Professor

스크립트

So, in this set of lectures we'll be discussing the minimum cut problem and

graphs and we'll be discussing the randomized contraction algorithm.

Randomize algorithm which is so simple and elegant and it's almost impossible to

believe that it can possibly work but that's exactly at what we'll be approving.

So one way you can think about these set of lectures, as a segue of sorts,

between our discussion of randomization and our discussion of graphs.

So we just finished talking about randomization in the context of sorting

and searching.

We'll pick it up again toward the end of the class when we discuss hashing.

But while we're in the middle of randomization probability review,

I'm going to give you another application of randomization

in a totally different domain.

In particular to the domain of graphs, rather than to sorting and searching.

So that's one high level goal of these lectures.

The second one, is we'll get our feet wet talking about graphs, and

a lot of the next couple weeks,

that's what we're going to be talking about, fundamental graph primitives.

So this will give us an excuse to start warming up with the vocabulary,

some of the basic concepts of the graphs and what a graph algorithm looks like.

Another perk, although it's not one of the main goals, but I want to do,

I do want to point this fact, compared to most of this stuff that we're discussing

in this class, this is a relatively recent algorithm, the contraction algorithm.

By relatively recent I mean, it's 20 years old.

But at least that means most of us, I know not all of us, but

most of us at least were born at the time that this algorithm was invented.

And so just one quick digression.

In an intro course like this, most of what we're going to cover are oldies but

goodies, stuff from as much as 50 years ago.

And while it's kind of amazing, given how much the world and

how much technology has changed over the past 50 years,

that ideas in computer science from that long ago are still useful, they are.

It's just sort of an amazing thing about the stuff that

the first generation of computer scientists figured out.

It's still relevant to this day.

That said, algorithms is still a vibrant field with lots of open questions.

And when I have an opportunity, I'll try and give you glimpses of that fact.

So I do want to point out here that this is a somewhat more recent algorithm

than most of the other ones we'll see, which dates back to the 90s.

So let's talk about graphs.

Fundamentally, what a graph does is represent pair-wise relationships among

a set of objects.

So, as such, a graph is going to have two ingredients.

So first of all, there's the objects that you're talking about.

And these have two very common names and you're just going to have to know both of

the names, even though they're completely synonymous.

The first name is vertices.

So vertex is the singular, vertices is the plural.

Also known interchangeably as nodes.

I'll be using the notation V for the set up of vertices.

So those are the objects, now I want to represent pair wise relationships so

these pairs are going to be called edges.

Will be noted by, denoted by E.

And there's two flavors of graphs and both are really important.

Both come up all the time in applications, so you should be aware of both kinds.

So there's undirected graphs and directed graphs and

that just depends on whether the edges themselves are undirected or directed.

So edges can be undirected by which I mean this pair is unordered.

There are just two vertices of an edge the two endpoints, say U and V,

and you don't distinguish one as the first and one as the second.

Or edges can be directed, in which case you have a directed graph.

And here, a pair is ordered, so you do have a notion of a first vertex, or

a first end point.

And the second vertex or second end point of an edge.

Those are often called the tail and the head respectively.

And once in a while, although I will try to not use this terminology,

you hear directed edges called arcs.

Now I think all of this is much clearer if I just draw some pictures.

Indeed one use to call graphs, dots and lines.

The dots would refer to the vertices, so here's four dots, or four vertices.

And the edges would be lines,

so the way you denote one of these edges is you just draw a line between the two

end points of that edge, the two vertices that it corresponds to.

So this is undirected graph with four vertices and five edges.

We can equally we'll have a directed version of this graph.

So let's still have four vertices and five edges, but

to indicate that this is directed graph and then each edge was first vertex and

the second vertex, were going to add arrows to the line.

So the arrow points to the second vertex, or to the head of the edge.

So, the first vertex is often called the tail of the edge.

So, graphs are completely fundamental,

they show up not just in computer science but in all kinds of different disciplines,

social sciences and biology being two prominent ones.

So, let me just mention a couple of reasons you might use them just off

the top of my head but literally there's hundreds or thousands of others, so

a very literal example would be road networks.

So imagine you type in asking for your driving directions from point A to point B

in some web application or software, or whatever, it computes a route for you.

What it's doing, is it's manipulating some representation of a road network,

which inevitably is going to be stored as a graph, where the vertices corresponds to

intersections and the edges correspond to individual roads.

The Web is often fruitfully thought of as a directed graph, so

here the vertices are the individual web pages, and edges correspond to hyperlinks.

So the first vertex in an edge detail is going to be the page that contains

the hyperlink.

The second vertex, or the head of the edge,

is going to be what the hyperlink points to.

So that's the Web as a directed graph.

Social networks are quite naturally represented as graphs.

So here the vertices correspond to the individuals in the social network.

And the edges correspond to relationships.

They have friendship links.

I encourage you to think about among the popular social networks these days,

which ones are undirected graphs and which ones are directed graphs,

we have some interesting examples of each of those..

And often graphs are useful even when there isn't such an obvious network

structure.

So just to mention one example.

Let me just write down precedence constraints.

So to say what I mean, you might think about,

let's say you're a freshman in college and you're looking at your majors,

you're a science major and you want to know what courses to take in what order.

And you can think about the following graph where each of the courses in your

major corresponds to a vertex And you draw a directed edge from course A to course B,

if course A is a prerequisite for course B.

That is, it has to be completed before you begin course B.

Okay, so that's a way to represent dependencies, sort of a temporal ordering,

between pairs of objects using a directed graph.

So that's the basic language of graphs.

Let me now talk about cuts in graphs.

because again, this set of lectures is going to be about so

called minimum cut problem.

So, the definition of a cut of a graph is very simple, it's just a grouping,

a partition of the vertices of the graph into two groups, A and B, and

both of those two groups should be non-empty.

So, to describe this in pictures,

let me give you a cartoon of the cut in both the undirected and directed cases.

So for an undirected graph, you can imagine drawing your two sets, A and B.

And once you've defined the two sets A and

B, the edges then fall into one of three categories.

You've got edges with both of the endpoints in A.

You've got edges with both of the endpoints in B.

And then, you've got edges with one endpoint in A, and one endpoint in B.

So that's generically what the picture of the graph looks like viewed through

the lens of a particular cut, A B.

The picture for directed graphs is similar.

You would again have an A, and you'd again have a B, you have directed edges with

both endpoints in A, directed edges with both endpoints in B.

And now you should have two further categories, so you have edges who cross

the cut from left to right, that is tail vertex is in A and

the head vertex is in B and you can also have edges which cross the cut in

the opposite direction, that is their tail is in B and their head is in A.

Usually when we talk about cuts,

we're going to be concerned with how many edges cross the given cuts.

And by that I mean the following, the crossing edges of a cut (A,B)

are those that satisfy the following property.

So in the undirected case,

it's exactly what you think it would be, one of the endpoints is an A,

the other endpoint is in B, that's what it means to cross the cut.

Now in the directed case, there's a number of reasonable definitions you could

propose, about which edges crossed the cut.

Typically and in this course, we're going to focus on the case

where we only think about edges that cross the cut from the left to the right, and

we ignore edges which cross from the right to the left.

So that is the edges that cross the cut are those with tail in A and head in B.

So referring to our two pictures, our two corrections of cuts for the underrated

one all three of these blue edges would be the edges crossing the cut AB.

because they're the ones that have one end point on the left side and

one end point on the right side.

Now for the directed one, we only have two crossing edges.

So the two that cross from left to right.

We have tail in A and head in B.

The one that's crossing backwards does not contribute.

We don't count it as a crossing edge of the cut.

So the next quiz is just a sanity check that you've absorbed the definition

of a cut of a graph.

All right, so the answer to this quiz is the third option.

Recall what is the definition of a cut, it's just a way to group

the vertices into two sets A and B, both should also be not empty.

So we have N vertices and essentially we have one binary degree of freedom for

each, for each vertex, we can decide whether or not it goes in set A or

it goes in set B, so two choices for each of the N vertices, that gives us a two

to the N possible choices, two to the N possible cuts overall.

Now that's slightly incorrect because we call that a cut.

You can't have a non empty set A or a non empty set B, so

those are two of the two to the N options which are disallowed.

So strictly speaking the number is two to the N minus two, but

two to the N is certainly the closest answer of the four provided.

Now, the minimum cut problem is exactly what you'd think it would be.

I give you as input a graph and among these exponentially, many cuts,

I want you to identify one for me with the fewest number of crossing edges.

So a few quick comments, so first of all the name for this cut is a min cut.

A min cut is one with the fewest number of crossing edges.

Secondly, to clarify, I am going to allow in the input what's called parallel edges.

There will be lots of applications where parallel edges are sort of pointless, but

for minimum cut actually it's natural to allow parallel edges.

And that means you have two edges that correspond to exactly the same

pair of vertices.

Finally, the more seasoned programmers among you are probably wondering what I

mean by, you're given the graph as input.

You might be wondering about how exactly that's represented, so

the next video's going to discuss exactly that,

the popular ways of representing graphs and how you're usually going to do it in

this course, specifically via what's called an adjacency list.

Okay, so I want to make sure that everybody understands exactly what

the minimum problem is asking.

So, let me draw for you a particular graph

with eight vertices and quite a few edges.

And what I want you to answer is what is the min cut value in this graph?

That is, how many edges cross the minimum cut,

the cut with the fewest number of crossing edges?

All right, so the correct answer is the second choice.

The min cut value is 2 and

the cut which shows that, is just to break it basically in half.

And there were two halves.

In this case, there are only two crossing edges, this one and this one.

And I'll leave it for

you to check that there's no other edge that has as few as two edges.

Now in this case, we got a very balanced split when we took the minimum cut.

In general, that need not be true.

Sometimes even a single vertex can define the minimum cut of a graph, and

I encourage you to think about a concrete example that proves that.

So why should you care about computing the minimum cut?

Well, this is one problem among a genre called graph partitioning,

where you're given a graph and you want to break it into two or more pieces.

And these kinds of graph partitioning problem comes up all the time,

in a surprisingly diverse array of applications.

So let me just mention a couple at a high level.

So one very obvious one when your graph is representing its physical network,

when identifying something like a min cut allows you to do,

is identify weaknesses in your network.

Perhaps it's your own network, and

you want to understand where you soup of the infrastructure because it's,

in some sense, a hot spot of your network or a weak point.

Or, maybe there's someone else's network and

you want to know where the weak spot in their network.

In fact, there are some declassified documents about 15 years ago or so.

Which showed that the United States and Soviet Union militaries,

back during the Cold War, were actually quite interested in computing

minimum cuts, because they were looking for things like, for example, what's

the most efficient way to disrupt the other country's transportation network?

Another application, which is a big deal in social network analysis these days,

is the idea of community detection.

So the question is among the huge graph,

say the graph of everybody who is on Facebook or something like that.

How can you identify small pockets of people that seem tightly knit,

that seem closely related,

from which you like to infer that there are community of some sort?

Maybe they all go to the same school, maybe they all have the same interest,

maybe they're part of the same biological family whatever.

Now, it's to some degree still an open question how to best define communities

and social networks.

But as a quick and dirty sort of first order heuristic,

you can imagine looking for small regions, which on the one hand, are highly

interconnected among themselves, but quite weakly connected to the rest of the graph.

So sub-routines like the minimum cut problem, can be used for

identifying these small densely interconnected, but

then weakly connected to everybody else, pockets of a graph.

Finally, cut problems are also used a lot in vision.

So for example, one way you can use them in what's called image segmentation.

So here what's going on is you're given as input a 2D array

where each entry is a pixel from some image.

And there's a graph, which is very natural to define, given a 2D array of pixels.

Namely, you have an edge between two pixels if they are neighboring.

So for two pixels that are immediately next to each other left and

right or top to bottom, you put an edge there.

So that gives you what's called a grid graph.

And now unlike the basic minimum cut problem that we're talking about here,

in image segmentation it's most natural to use edge weights.

Where the weight of an edge is basically how likely you expect those two

pixels to be coming from a common object.

Why might you're expect to enabling pixels to come from the same object,

well perhaps their color maps were almost exactly the same and

you just expected that they're part of the same thing.

So once you've defined the screen graph which suitable edge ways now you run

a graph partitioning or maybe cut type separate team, and the hope is that

the cut that it identifies rips off one of the contiguous objects in the picture.

And then you do that a few times and

you get the major objects in the given picture.

So this list is by no means exhaustive of the applications of min cut and

graph partitioning server teams, but I hope it serves as

sufficient motivation to watch the rest of the lectures in this sequence.

Coursera 카탈로그 살펴보기

무료로 참여해 맞춤화된 추천, 업데이트 및 제안을 받아보세요.

Coursera는 세계 최고의 교육에 대한 보편적인 접근 기회를 제공하며, 최고의 대학 및 기관들과 제휴하여 온라인 강좌를 제공합니다.

© 2019 Coursera Inc. All rights reserved.

앱스토어에서 다운로드하기

구글 플레이에서 받기

Coursera
소개
리더십
직업
카탈로그
수료증
MasterTrack™ 수료증
학위
포 엔터프라이즈 (For Enterprise)
정부용

커뮤니티
Learners
Partners
Developers
Beta Testers
Translators

연결
블로그
Facebook
Linkedin
Twitter
Instagram
YouTube
기술 블로그

이상
조건
개인정보 보호
도움말
접근성
보도 자료
문의하기
디렉토리
계열사