Name: Lec 7｜MIT 6.042J コンピュータサイエンスのための数学 2010年秋学期 (Lec 7 | MIT 6.042J Mathematics for Computer Science, Fall 2010)
Uploaded: 2021-01-14T06:24:46.000Z
Duration: 1 h 22 min 41 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

基礎受動態

The following content is provided under a Creative

Your support will help MIT OpenCourseWare

continue to offer high quality educational resources for free.

To make a donation or view additional materials

from hundreds of MIT courses, visit MIT OpenCourseWare

PROFESSOR: OK, on Tuesday we talked about sex,

so today we're going to talk about marriage.

and today we're going to talk about a matching algorithm that

for example, matching interns to hospitals on match day.

It's used for resource allocation problems,

for example, load balancing traffic on the internet.

In its simplest form of a matching problem,

you have a graph where the edges represent compatibility.

Two nodes can be paired together, or married,

and the goal is to create the maximum number

So let's define a matching, given a graph, G,

with nodes, V, and edges, E. In matching,

you can think of it as a collection of edges,

or a subgraph of G where every node has degree 1.

So everybody can be married just to one person.

So let's draw an example, maybe not put that edge in.

And let's label these nodes x1, x2, x3, x4, x5, x6, x7, and x8.

Now x1, x6 and x2, x5 is a matching, so x1, x6 and x2,

x5 is a matching with two edges, so we say it has size two.

All right, so I can pair these guys up and pair these guys up.

Is there any bigger matching in this graph?

All right, that's a matching of size three.

Can I make a bigger matching, one with size four--

Can anybody give me a reason why it can't be done?

AUDIENCE: x8 and x7 would have to be matched with someone.

AUDIENCE: They could only be paired with x1,

If I were to have a matching with four edges,

have to have all eight nodes involved in the matching.

And that means x7 and x8 would have to be in the matching,

Now, when you get every node in a matching,

And so in this case, it doesn't exist, but sometimes it does.

In other words, if the number of edges is v over 2,

All right, so that one doesn't have a perfect matching.

and I'll put in the compatibility edges here.

OK, Does that graph have a perfect matching?

here so that everybody is compatible with their mate,

All right, so there is a perfect matching in this graph.

are more desirable than others, and this can

字幕リスト動画再生

Lec 7｜MIT 6.042J コンピュータサイエンスのための数学 2010年秋学期 (Lec 7 | MIT 6.042J Mathematics for Computer Science, Fall 2010)

assume

couple

audience

day