Guión de Video

	Imágenes a colocar	Texto a colocar	Sonido o Efectos	Narración	Segundos
Portada		Algoritmo de Kruskal	Happy – Pharell Williams	Buenas tardes, en este video hablaremos sobre el algoritmo de Kruskal, un poco de su historia, su autor y también resolveremos un problema utilizándolo.	15 s
Introducción		El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa).	Happy – Pharell Williams	Fue sugerido por primera vez por Joseph Kruskal, de los laboratorios AT&T Bell, en los años 50, cuando un matemático checo le presentó un problema. Su trabajo dio a lugar a aplicaciones como tanto en diseño de redes informáticas, ferroviarias como en industrias de comunicaciones. Este algoritmo fue publicado por primera vez en el año de 1956, los hermanos de Joseph   eran otros estudiosos, como William Kruskal (matemático también) y de Martin Kruskal, un físico.. El algoritmo de Kruskal tiene como objetivo construir un árbol, dada un gráfica con pesos en los arcos, para encontrar la ruta más corta que conecte a todos los nodossin formar ciclos. Algunas aplicaciones pueden ser la construcción de carreteras, vías ferroviarias, o la construcción de redes de ductos.	70s
Planteamiento		En la tabla se muestran las distancias en millas entre cuidades. Es necesario construir un sistema estatal de carreteras.	Happy – Pharell Williams	En este problema se pide hacer un sistema de carreteras, plantearemos la red a partir de las distancias dadas en la tabla.	10s
Resolución		El primer paso en el algoritmo es ordenar los caminos de menor a mayor. Se analiza cada camino, ingresándolo al árbol. Se seguirán agregando los camino al árbol, si y solo si no se creen circuitos dentro del mismo. El algoritmo termina hasta que se tienen n-1 arcos en el árbol. En este caso, podemos agregar el camino de 5,1. Luego el de 5,2 ya que no genera circuito, el camino 3,4 también se agrega, y el camino 1,4 también. El  algoritmo termina cuando se tienen n-1 arcos, en este caso hay 5 nodos, así que 5-1 =4. Si continuamos con el método, solo encontraremos que los demás arcos generan ciclos, así que de todos modos no se pueden agregar al árbol. Y se tiene la red de menor costo para conectar todas las ciudades.	Happy – Pharell Williams	Según pide el algoritmo, ordenaremos todos los caminos de la gráfica, los pondremos de menor a mayor en una tabla como está. Iniciamos con la revisión del primer camino, el de peso más pequeño, en este caso 5,1. Este nodo se agrega al árbol, ya que no puede generar ciclo. El segundo camino, de 5,2 tampoco forma un circuito, así que lo ponemos dentro del árbol. El camino de 3,4 tampoco genera un circuito, también lo podemos agregar al árbol. Podemos ver que por el momento, el camino 3,4 no está conectado con los demás, aunque en este paso no sea un árbol, continuamos. El camino 1,4 no genera circuito, así que también lo agregamos al árbol. Aquí se termina el algoritmo ya que tenemos 4 arcos en el árbol. El árbol que conecta la red queda de esta forma. Aunque haya muchos otros árboles en la red, este es el de menor peso.	90s
Resultados		Tenemos el árbol de costo mínimo.	Happy – Pharell Williams	Aquí se presenta el árbol resultante de aplicar el algoritmo de Kruskal, este árbol es la solución óptima para la unión de todas las ciudades con costo mínimo.	15s
Créditos de imágenes, voces, música y producción		Producción: Eduardo Galván Lara y Manuel Uribe Torres Voz: Manuel Uribe	Happy – Pharell Williams	Esto es todo, los autores Eduardo Galván Y Manuel Uribe nos despedimos. Gracias por su atención.	10s