En la teorica, hemos dado los grafos ponderados ( que vaya tela xD) que corresponde al tema 7 del temario. El la de practicas, seguimos con magrada, hallando matrices de accesibilidad y todas esas rayadas jajjajjaja xD
Teorica
Grafos Ponderados
Un grafo simple diremos que es un grafo ponderado si tiene asociado una función W: A→R llamada función de ponderación. La imagen de cada arista determinada por los vértices vi y vj la llamaremos peso de la arista y lo denotaremos por wij.
Para un grafo ponderado finito, llamaremos matriz de peso del grafo a la siguiente matriz nxn.
W=[aij]/aij= wij si (vi,vj) pertenece a A
∞ si (vi,vj) no pertenece a A
En un grafo ponderado llamamos peso de un camino a la suma de los pesos de las aristas que lo forman.
En un grafo ponderado llamamos camino más corto entre dos vértcies dados al camino de peso mínimo entre dichos vértices.
En un grafo ponderado llamaremos camino más largo o camino crítico entre dos vértices dados al camino de peso máximo entre dichos vértices.
Caminos más cortos
Para hallar los caminos más cortos de un grafo ponderado con el menor peso posible se ha de suponerque el grafo es dirigido y que los pesos asociados a los arcos son todos no negativos. Supondremos además que los vértices del grafo están numerados de 1 a n, de tal forma que el conjunto de vértices lo denotaremos por V= {v1,v2,…,vn}. Con esta notación, wij representará el peso del arco (vi,vj). Por último supondremoos que el vértice v1 es el origen de los caminos. Además, uj denotará el peso del camino más corto de v1 a vj.
Así tenemos que en un camino de 1 a 3 pasando por 2, podemos considerar que hay a su vez caminos más cortos de sus distintas secciones, siendo una sección el camino de 1 a 2 y otra el camino de 2 a 3.
Caminos críticos
El camino crítico es un camino de mayor longitud de S a T. La longitud de este camino se llama la hora de finalización más temprana. El método del camino crítico es un algoritmo para encontrar un camino crítico que se basa en la búsqueda de la longitud de la trayectoria más larga de la S a cada vértice intentando obtener el menor número de hora para realizar cierta actividad que empieza en S y termina T.
——————————-
Hasta aqui la clase de matematica discreta de esta semana
Felices fiestas a todos!!!!!! jejejejejee xD
Víctor