Name: Lec 10｜MIT 6.042J コンピュータサイエンスのための数学 2010年秋学期 (Lec 10 | MIT 6.042J Mathematics for Computer Science, Fall 2010)
Uploaded: 2021-01-14T06:26:15.000Z
Duration: 1 h 22 min 50 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: So today we're going to continue

It's going to be a mixture of all kinds of topics.

And we'll talk about a special type, which

and hopefully you will all contribute to make this work

So next week we will continue with graph theory,

We will use directed graphs in communication networks.

And on Thursday, we'll actually use these special types

of graphs that we'll talk about in a moment, DAGs.

Euler, a famous mathematician, he asked the question

He was wondering, can you traverse all the bridges

So he would start walking and try to cross all those bridges.

And apparently this little islands in sort of the river

This is actually the birth of graph theory.

And this particular problem is named after him.

It's a walk that traverses every edge exactly once.

So it turns out the you can actually characterize

So we are talking here about undirected graph,

So the edges that we consider have no direction.

So Euler tour is a walk that traverses every edge exactly

So that means that it actually starts and finishes

the graphs that we've been talking about,

those that Euler tours can be easily characterized.

And that's the theorem that we're going to prove next.

if and only if, every vertex of the graph has even degree.

So that's a very nice and simple and straightforward

So first of all, we have an if and only if statement.

We need to proof that if I have a connected graph that

has an Euler tour, I need to show that every vertex has

And also the reverse-- if I have a graph for which every vertex

has even degree, I need to show that it has an Euler tour.

So we have G with the vertex at V, edge is at E,

We can go all the way around to V1, and some more, and so on,

And then end vertex is the same as the start vertex.

So we have a walk that goes all around the whole graph.

So every edge in this walk are exactly the edges

And each edge in the graph is offered exactly once.

So since every edge is traversed once-- every edge in E

is traversed once-- what can we conclude from that?

Can we say something about, given such as walk of length k,

what can we say about the number of edges, for example?

What can we say about the degree of the vertices?

Because that's what you want to show, right?

You want to show that every vertex has even degree.

So what kind of properties can we derive?

字幕リスト動画再生

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

sort

assume

essentially

audience