Eulerian Path - Intro to Algorithms Udacity English Japanese

Eulerian Path - Intro to AlgorithmsYouTube↗ IA↗(long shot)
Education 55.8K views 144 likes 30 dislikes 27 Jun 2012

Udacity 651K subscribers United States YouTube↗

Click to Play Video

In the graph, we can talk about something called an Eulerian path.

グラフにはオイラーパスというものがあります

This is the path that starts off with some node on the graph, let's say A in this case.

グラフ上のあるノード例えばAから出発し

And it moves along the edges from node to node,

エッジに沿ってノードからノードへと移動すると

hitting every edge exactly once, and then ending it from node to the graph.

全エッジを1度だけ通って終点のノードにたどり着きます

In this case, we have an Eulerian path that's started at A and ended with D.

このグラフにはAで始まりDで終わるオイラーパスがあります

Euler by the way was a famous mathematician, Leonhard Euler.

オイラーとは数学者レオンハルト･オイラーのことです

He made a number of contributions to discrete math and ultimately, computer science.

離散数学やコンピュータ･サイエンスに貢献しました

Here's something that we can notice about a graph.

ここから何が分かるでしょうか

If it has a Eulerian path, notice what has to happen to all the nodes along the path.

オイラーパスがある場合の移動経路に着目しましょう

Here's what we did in this example, we went from A to B, to D, to A, to C, to D.

この例ではAからB、D、A、C、Dと移動しました

Now let's consider the degree of all the nodes in the graph.

ではノードの次数はどうなっているでしょう

A has a degree of 3, B has a degree of 2, D has a degree of 3, and C has a degree of 2.

Aの次数は3 Bの次数は2 Dの次数は3 Cの次数は2です

Notice that these nodes B and C, which were not either at the beginning or ending of the path,

このようにオイラーパスの始点でも終点でもないBとCの次数は

the Eulerian path, have an even degree and that has to be.

偶数でなければならないのです

What happens if all the nodes that are not in the beginning and ending nodes

始点でも終点でもないノードの次数は絶対に偶数です

have to had even degree because the path has to go in one edge and out another edge.

一方のエッジから入ったパスはもう一方のエッジから必ず出るからです

Every time that node gets passed through, 2 of the edges are visited,

ノードを通過する時は必ず2本のエッジを通ります

and none of them are visited twice and none of them are skipped.

しかも通るのは1度だけです

So it has to be that all these nodes that are intermediate on the path have even degree.

だからパスの中間にあるノードの次数はすべて偶数なのです

The beginning and ending nodes are different though.

始点と終点のノードは違います

If the path starts off at A and leaves A along one of the edges and that consumes one of those edges.

Aから出発すればAから出ているエッジのうちの 1本を使用することになります

The beginning and ending nodes, A and D in this case, have to have odd degree

このため始点と終点の次数は奇数でなければなりません

because, in addition to any times that the path moves through them and comes up the other side,

なぜなら中間のノードを通って再び始点に戻ってきたあとに

it either leaves in the beginning or enters at the end without a corresponding other side.

終点に向かうためのエッジが必要になるからです

Those have to be odd, all the other ones have to be even.

始点と終点のみ次数が奇数である

It turns out that this relationship is in "if and only if"--that is to say if the graph is connected

というのはオイラーパスの十分条件です

and has exactly 2 odd degree nodes, then it has an Eulerian path, and if not, then it doesn't.

すなわち2つだけ次数が奇数のノードがあればそのグラフにはオイラーパスが存在するということです

Now, there is one exception to this. What if all of the nodes in the graph are even degree?

ただしもう1つオイラーパスが存在する場合があります全ノードの次数が

Let's take a quick look at a special case here.

偶数の場合はどうでしょうか

Here is a graph with 5 nodes and the degree of all of the nodes is even--2, 4, 2, 4, and 2.

ここに次数が偶数の5つのノードを持つグラフがあります　ノードの次数は2、4、2、4、2です

Can a graph like this with only even degree nodes have an Eulerian path?

全ノードの次数が偶数のグラフにもオイラーパスは存在するのでしょうか

One possible answer is no, the start and the end edges of the path had to have odd degree,

考えうる解答の1つは始点と終点の次数は必ず奇数でなければならないため

which is the ruling in this case, so it can't have an Eulerian path.

オイラーパスは存在しないというものです

Another possible answer is yes, but it depends on the particulars of the graph in question.

もう1つの考えうる解答はグラフによって異なるというものです

Some graphs with only even degree nodes have Eulerian paths and some don't.

つまりオイラーパスが存在するものとそうでないものがあるということです

Another possibility is that the answer is yes, all such graphs do.

もう1つはこのようなグラフすべてに存在するという解答です

Any graph that's connected and has only even degree nodes

すべてのノードの次数が偶数のグラフには

will have an Eulerian path in a particular form.

必ずオイラーパスが存在するということです

Another possible answer is yes, because all graphs do.

もう1つはどんなグラフにもオイラーパスは存在するので

You can't really have a graph that doesn't have an Eulerian path.

オイラーパスがないグラフなどないという解答です

Similar videos:

Algorithms Are Cool - Intro to Algorithms
Udacity
5.4K views 12 likes 0 dislikes 27 Jun 2012100% match

Erdos Renyi - Intro to Algorithms
Udacity
7K views 20 likes 2 dislikes 23 Feb 2015100% match

Build Heap - Intro to Algorithms
Udacity
20.8K views 75 likes 4 dislikes 19 Jul 2012100% match

Connected Components - Intro to Algorithms
Udacity
18.9K views 16 likes 35 dislikes 23 Feb 2015100% match

Order Statistics - Intro to Algorithms
Udacity
5.4K views 6 likes 9 dislikes 19 Jul 2012100% match

Clique Problem in NP? - Intro to Algorithms
Udacity
5.3K views 15 likes 3 dislikes 23 Feb 2015100% match

Magic Trick - Intro to Algorithms
Udacity
28.5K views 39 likes 6 dislikes 27 Jun 2012100% match

Russian Peasants Algorithm - Intro to Algorithms
Udacity
9.7K views 8 likes 2 dislikes 27 Jun 2012100% match

NP-Hard - Intro to Algorithms
Udacity
6.3K views 17 likes 3 dislikes 23 Feb 2015100% match

Case Study - Intro to Algorithms
Udacity
13K views 8 likes 0 dislikes 27 Jun 2012100% match

Reduce SAT to 3-Colorability - Intro to Algorithms
Udacity
10.8K views 14 likes 84 dislikes 23 Feb 2015100% match

Eulerian Path - Intro to Algorithms
Udacity
5.2K views 2 likes 0 dislikes 27 Jun 2012100% match

Eulerian Path Solution - Intro to Algorithms
Udacity
15.9K views 64 likes 1 dislikes 27 Jun 2012100% match

Clique Problem - Intro to Algorithms
Udacity
8K views 11 likes 7 dislikes 23 Feb 2015100% match

Reduce 3-Colorability to SAT - Intro to Algorithms
Udacity
11.8K views 53 likes 8 dislikes 23 Feb 2015100% match

Magic Trick - Intro to Algorithms
Udacity
7.7K views 21 likes 1 dislikes 27 Jun 2012100% match

How Many Additions - Intro to Algorithms
Udacity
7.4K views 1 likes 0 dislikes 27 Jun 2012100% match

Correctness: Naive - Intro to Algorithms
Udacity
10.6K views 41 likes 2 dislikes 27 Jun 2012100% match

Steps For Naive - Intro to Algorithms
Udacity
5.7K views 1 likes 0 dislikes 27 Jun 2012100% match

Finding Bridge Edges - Intro to Algorithms
Udacity
7.8K views 21 likes 20 dislikes 23 Feb 2015100% match

NP-Completeness - Intro to Algorithms
Udacity
8.9K views 30 likes 9 dislikes 23 Feb 2015100% match

Recurrence Relation - Intro to Algorithms
Udacity
6.3K views 7 likes 1 dislikes 27 Jun 2012100% match

Longest Simple Path - Intro to Algorithms
Udacity
17.4K views 32 likes 27 dislikes 23 Feb 2015100% match

Graph Coloring is NP-Complete - Intro to Algorithms
Udacity
10.1K views 20 likes 12 dislikes 23 Feb 2015100% match

Lower Bound on Complexity - Intro to Algorithms
Udacity
11.9K views 21 likes 23 dislikes 23 Feb 2015100% match

Degree Centrality - Intro to Algorithms
Udacity
7K views 5 likes 5 dislikes 19 Jul 2012100% match

Down Heapify - Intro to Algorithms
Udacity
5.1K views 10 likes 1 dislikes 19 Jul 2012100% match

Running Time - Intro to Algorithms
Udacity
9.8K views 12 likes 1 dislikes 27 Jun 2012100% match

Code for Dijkstra - Intro to Algorithms
Udacity
9.9K views 20 likes 4 dislikes 23 Feb 2015100% match

Top K Code - Intro to Algorithms
Udacity
722 views 2 likes 0 dislikes 19 Jul 2012100% match

Settings Privacy About Contact Donate