All right. Let's look at the answer.
Here's a particular graph where all the nodes are of even degree.
Let's see what happens when we try to follow an Eulerian path.
Let's just pick any node to start--say E--and go to C.
There are some choices here. Let's follow an edge back to B.
Then maybe to D to C to A to B and to E.
So it looks like we were able to hit all of the edges exactly once.
This graph does have an Eulerian path.
But there's something very special about that path,
and that it is started at E and it ended with E.
Because the path actually started and ended at the same node,
that node should have even degree,
because each time we go into we come out,
except for the first time where we go out but then the last time we come back in.
Everything matches up and you end up with even degree.
This is a special kind of Eulerian path called an "Eulerian Tour."
"To tour" in the sense that we start off in our home city,
and we go around, we visit lots of things, and we come back to our home city.
We kind of did a tour of the graph, and it was very scenic.
That's an Eulerian Tour.
This first answer is definitely not correct.
Such a graph can have an Eulerian path.
No, it doesn't depend on the graph.
It turns out that this is going to be fine no matter what,
because we're going to end up starting and ending at the same node.
We could have actually started and ended on any of the nodes
and it would've worked out the same way. All such graphs do.
All graphs that have only even degree nodes do have Eulerian paths,
specifically Eulerian Tours, but it's not the case that all such graphs do.
Let's make a quick example graph just so that you can see it.
For this to work we need to have a graph where more than two of the nodes has odd degree.
Let's make one where four of the nodes has odd degree.
We have these four nodes--F, G, H, and I.
Let's make it so that each of them has odd degree.
Now they all have even degree. Now two of them have odd degree.
If we connect these two guys, then they have odd degree as well.
All the nodes have odd degree. It's not just 0 or 2.
All of them have degree of 3.
Let's see what happens when we try to make an Eulerian path.
We'll pick some node like I.
We'll go I to G, G to F, F to I, I to H, H to F, and now we hit a dead end.
Maybe we didn't want to do that. Let's instead go H to G where we also hit a dead end.
In fact, you can do this all day long, and what you're going to discover
is there's always going to be at least one edge that you just can't visit,
because again, each node in this case has an odd degree.
Every part of the path has to come into the node and out of it,
so it has to have even degree except for the endpoint.
No matter what we're going to be stuck.
Bien. Veamos la respuesta.
Aquí tenemos un grafo especial en el que todos los nodos tienen grado par.
Vamos a ver qué pasa cuando tratamos de seguir un camino euleriano.
Basta con elegir cualquier nodo para iniciar - digamos E - e ir a C.
Hay algunas opciones aquí. Vamos a seguir una arista hacia B.
Luego podríamos ir a D, a C, a A, a B, y a E.
Así que parece que hemos sido capaces de pasar por todas las aristas exactamente una vez.
Este grafo tiene un camino euleriano.
Pero hay algo muy especial en ese camino,
y es que se inicia y termina en E.
Puesto que el camino en realidad comenzó y terminó en el mismo nodo,
ese nodo debe tener grado par,
porque cada vez que ingresamos a un nodo luego salimos,
a excepción de la primera vez en que salimos pero después, la última vez, volvemos
Todo coincide y se termina con grado par.
Este es un tipo especial de camino euleriano llamado "tour euleriano".
"Hacer un tour" en el sentido de que nos ponemos en marcha en nuestra ciudad,
vamos por ahí, visitamos varios lugares, y volvemos a nuestra ciudad.
Es como hacer un recorrido por el grafo, pero muy pintoresco.
Eso es un tour euleriano.
La primera respuesta definitivamente no es correcta.
Este grafo puede tener un camino euleriano.
No, no depende del grafo.
Resulta que esto va a estar bien sin importar qué,
porque vamos a comenzar y terminar en el mismo nodo.
Podríamos haber comenzado y finalizado en cualquiera de los nodos
y hubiera funcionado de la misma manera. Todos estos grafos lo hacen.
Todos los grafos que tengan solo nodos de grado par tienen caminos de eulerianos,
específicamente tours eulerianos, pero no es el caso que todos esos grafos lo tengan.
Vamos a hacer un rápido grafo de ejemplo para que puedan verlo.
Para que esto funcione necesitamos tener un grafo donde más de dos de los nodos tengan grado impar.
Hagamos uno con cuatro de los nodos con grado impar.
Tenemos estos cuatro nodos - F, G, H e I.
Vamos a hacerlo de modo que cada uno de ellos tenga grado impar.
Ahora todos ellos tienen grado par. Ahora, dos de ellos tienen grado impar.
Si conectamos estos dos chicos, entonces tienen grado impar también.
Todos los nodos tienen grado impar. No son sólo 0 o 2.
Todos ellos tienen un grado de 3.
Vamos a ver qué pasa cuando tratamos de hacer un camino euleriano.
Tomemos algún nodo como I.
Iremos de I a G, G a F, F a I, I a A, A a F, y ahora llegamos a un callejón sin salida.
Tal vez no queríamos hacer eso. En lugar vayamos a H, a G donde también llegamos a un callejón sin salida.
De hecho, pueden hacer esto todo el día, y lo que van a descubrir
es que siempre va a haber por lo menos una arista que no puedan visitar,
porque, de nuevo, cada nodo en este caso tiene un grado impar.
Cada tramo del camino tiene que entrar en el nodo y salir de él,
por lo que tiene que tener grado par, excepto para el extremo.
No importa lo que hagamos, vamos a estar atascados.
では解説します
このグラフのノードの次数はすべて偶数です
オイラーパスが存在するか試してみましょう
それではEから出発しCへ
選択肢はいくつかありますがBへ進みます
そこからD、C、A、BそしてEへ
すべてのエッジを1度だけ通ることができたので
オイラーパスがあると言えます
しかしパスには特徴があります
それはEで始まりEで終わっているという点です
パスが同じノードで始まり 同じノードで終わっているため
Eの次数は偶数となります
なぜなら通過する時はもちろん
出発し戻ってくる時にもエッジを通るからです
すべてのノードの次数が偶数である
特殊なオイラーパスをオイラーツアーと呼びます
まるでツアーのように故郷を出発して
様々なノードを通り故郷に帰ってくるのです
私たちはグラフのツアーをしたということですね
以上がオイラーツアーの解説です
1つ目の解答は不正解です
オイラーパスは存在します
2つ目の解答も不正解です
このようなグラフには
必ずオイラーパスが存在します
どのノードから出発したとしても
必ず出発したノードに戻ってきます
全ノードの次数が偶数のグラフは 必ずオイラーパスを持ちますが
オイラーパスを持たないグラフもあります
分かりやすいように例を紹介します
3つ以上のノードの次数が 奇数のグラフを見てみましょう
4つのノードの次数が奇数のグラフを作ります
4つのノードF、G、H、Iがあります
すべてのノードの次数を奇数にします
HとGの次数が偶数なので
この2つを結べばすべての次数が奇数になります
これですべてのノードの次数が奇数になりました
どのノードも次数は3です
このグラフのオイラーパスを探してみましょう
Iから始めます
IからG、GからF、FからI、 IからH、HからF ここで行き止まりです
他の経路を試します HからGへ行ってもまた行き止まりです
一日中やり続ければ分かると思いますが
必ず1本のエッジが残ってしまいます
なぜなら全ノードの次数が奇数だからです
中間のノードは入って出るだけなので
次数は偶数にしかなり得ないのです
奇数だと行き詰まってしまいます