Spanish 字幕

← 01-05 Eulerian Path Solution

01-05 Solución del Camino Euleriano

埋め込みコードを取得する
3言語

Subtitles translated from 英語(米国) Showing Revision 5 created 02/17/2013 by Néstor Noziglia.

  1. Bien. Veamos la respuesta.
  2. Aquí tenemos un grafo especial en el que todos los nodos tienen grado par.
  3. Vamos a ver qué pasa cuando tratamos de seguir un camino euleriano.
  4. Basta con elegir cualquier nodo para iniciar - digamos E - e ir a C.
  5. Hay algunas opciones aquí. Vamos a seguir una arista hacia B.
  6. Luego podríamos ir a D, a C, a A, a B, y a E.
  7. Así que parece que hemos sido capaces de pasar por todas las aristas exactamente una vez.
  8. Este grafo tiene un camino euleriano.
  9. Pero hay algo muy especial en ese camino,
  10. y es que se inicia y termina en E.
  11. Puesto que el camino en realidad comenzó y terminó en el mismo nodo,
  12. ese nodo debe tener grado par,
  13. porque cada vez que ingresamos a un nodo
    luego salimos,
  14. a excepción de la primera vez en que salimos pero después, la última vez, volvemos
  15. Todo coincide y se termina con grado par.
  16. Este es un tipo especial de camino euleriano llamado "tour euleriano".
  17. "Hacer un tour" en el sentido de que nos ponemos en marcha en nuestra ciudad,
  18. vamos por ahí, visitamos varios lugares, y volvemos a nuestra ciudad.
  19. Es como hacer un recorrido por el grafo, pero muy pintoresco.
  20. Eso es un tour euleriano.
  21. La primera respuesta definitivamente no es correcta.
  22. Este grafo puede tener un camino euleriano.
  23. No, no depende del grafo.
  24. Resulta que esto va a estar bien sin importar qué,
  25. porque vamos a comenzar y terminar en el mismo nodo.
  26. Podríamos haber comenzado y finalizado en cualquiera de los nodos
  27. y hubiera funcionado de la misma manera. Todos estos grafos lo hacen.
  28. Todos los grafos que tengan solo nodos de grado par tienen caminos de eulerianos,
  29. específicamente tours eulerianos, pero no es el caso que todos esos grafos lo tengan.
  30. Vamos a hacer un rápido grafo de ejemplo para que puedan verlo.
  31. Para que esto funcione necesitamos tener un grafo donde más de dos de los nodos tengan grado impar.
  32. Hagamos uno con cuatro de los nodos con grado impar.
  33. Tenemos estos cuatro nodos - F, G, H e I.
  34. Vamos a hacerlo de modo que cada uno de ellos tenga grado impar.
  35. Ahora todos ellos tienen grado par. Ahora, dos de ellos tienen grado impar.
  36. Si conectamos estos dos chicos, entonces tienen grado impar también.
  37. Todos los nodos tienen grado impar. No son sólo 0 o 2.
  38. Todos ellos tienen un grado de 3.
  39. Vamos a ver qué pasa cuando tratamos de hacer un camino euleriano.
  40. Tomemos algún nodo como I.
  41. 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.
  42. Tal vez no queríamos hacer eso. En lugar vayamos a H, a G donde también llegamos a un callejón sin salida.
  43. De hecho, pueden hacer esto todo el día, y lo que van a descubrir
  44. es que siempre va a haber por lo menos una arista que no puedan visitar,
  45. porque, de nuevo, cada nodo en este caso tiene un grado impar.
  46. Cada tramo del camino tiene que entrar en el nodo y salir de él,
  47. por lo que tiene que tener grado par, excepto para el extremo.
  48. No importa lo que hagamos, vamos a estar atascados.