11'06'2019 - Heineken97/Portafolio GitHub Wiki
Ultima clase
Warshall.
Si hay ruta disponible entre nodos, grafos dirigidos Matriz de cierre transitivo de n vertices, Representado con matriz de adyacencia
- P0= 1 si existe entre i y j
- P1 Agrega vertice 1, si hay comunicacion entre i y j por medio del vertice
Minimal spanning tree
Grafo NO dirigido para relaciones simetricas y encuentra arbol de expansion minima. Subconjunto de grafo, que tiene todos los vertice, sumando sus aristas obtenemos el menor valor de suma(pueden existir varios pero ocupamos el menor)
Si logramos el vertices que pertenezcan en el arbol, es conectado
Esta conectado y no tiene ciclos.
-
Grafo posee n vertices, se poseen n-1 aristas
-
Una unica ruta entre cualquier par de vertices del arbol
-
Agrega 1 arista, causa ciclo
-
Solo 1 camino, no ciclos
Se aplica algoritmo de Prim
El arbol se arma en distintas etapas, se agrega cierto nodo, en cuanto se cambia, se establece comunicacion. Se add el vertice de menor costo entre las opciones disponibles. Tabla de Nodos Nodo|Know|peso|from
Kruskal
Selecciona aristas de menor a mayor por peso, y va aceptando aristas mientras no causa ciclo. Va generando conjunto de arboles y alfinal un bosque si u pertenece a arbol y v a otro (u,v) forman otro arbol Rechaza si genera ciclos o pertenece al mismo arbol
Se Realiza actividad 4
Adjunta respuestas de las preguntas ( si no se visualiza la imagen se encuentra en el repo 3f396f04-6b94-4e98-83f8-d014af741ae2.jpg)