Name: Lec 8 | 麻省理工學院 6.042J 計算機科學數學，2010年秋季。 (Lec 8 | MIT 6.042J Mathematics for Computer Science, Fall 2010)
Uploaded: 2021-01-14T06:25:39.000Z
Duration: 1 h 23 min 26 s
Description: 【看影片學英語】數萬部 YouTube 影片，搭配英漢字典即點即查，輕鬆掌握單字發音與用法，長久累積看電影不必再看字幕。

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

We're going to talk about some very special ones,

and look at examples to explain how it works.

So you've already seen a bit of graph theory.

We've talked about graph colorings and so on.

But now we're going to talk about special types of graphs,

and special structures within such graphs.

Well, let's start with the first definition.

You walk from one vertex in the graph over an edge

to a next vertex, to a next vertex, and so on.

A walk is a sequence of vertices that are connected by edges.

And an edge that goes to a second vertex.

say, at vk, which we call the end of the walk.

And we say that the length is actually equal to k.

But let's first give an example of a graph

that you will study throughout the whole lecture, especially

So let's have a look at the following graph.

Well, I can go many ways in this particular one.

I may go all the way to this part over here.

And I finally, I take this edge for example back to--

over this edge, I will end in the last vertex vk.

have a walk that actually gets to this particular vertex,

So for a few other edges, and then goes all the way to vk.

So if you talk about the path, then we really

want all the difference vertices not to occur twice.

So let's define this so the destination is

Is a walk where all edges, where all vertices,

In this particular case-- well for example,

you will get a path from v0 to here, to here, to here.

And all these vertices on the path on this walk

It is possible to construct from a walk a path.

As you can see, we started off with this particular walk.

a part where we sort of came back to the same vertex again.

And when we delete all those kinds of parts,

So can we formalize this a little bit better?

So we want to show that if there exists a walk from, say,

a vertex u to-- well, maybe I should not use arrows.

That's confusing-- from u to v. Then there

So what kind of proof techniques can we use here?

And maybe one of the principles that we have seen?

It's basically if you visit one vertex-- let's

Then we just take out the 4, you just go 1, 2, 3, 6.

字幕列表影片播放

Lec 8 | 麻省理工學院 6.042J 計算機科學數學，2010年秋季。 (Lec 8 | MIT 6.042J Mathematics for Computer Science, Fall 2010)

assume

essentially

suppose

start