Planteamientos

1. Arboles de peso mínimo ° Es un grafo conexo °No tiene ciclos °Red no dirigida °La suma de sus pesos de las aristas es la menor °Cualquier nodo es raíz

1.1. Métodos:

1.2. Kruskal (Glotón)

1.3. PRIM

2. Ruta más corta entre dos nodos específicos Es una red conexa No dirigida Tiene 2 nodos (origen y destino) A cada arco se asocia una distancia Su objetivo es encontrar una ruta más corta (la trayectoria con la mínima distancia total) entre nodo origen y el nodo destino

2.1. Método

2.2. Algoritmo Dijkstra: Analiza toda la red a partir del origen, identifica de manera sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias mientras se va etiquetando la menor distancia hasta el momento, el problema queda resuelto en el momento de etiquetar el nodo destino

3. Ruta más corta entre todo par de nodos Encuentra la ruta más corta entre todo par de nodos °Tiene costos en sus arcos

3.1. Método

3.2. Algoritmo de Floyd:

3.3. Es una red conexa

3.4. No dirigida (varios nodos iniciales y varios terminales)

3.5. Compara todos los posibles caminos a través del grafo entre cada par de vértices

4. Arborescencia de ruta más corta Son redes dirigidas Nodo raíz No tiene ciclos Árbol con dirección Se tiene n-1 trayectorias Se tienen n-1 aristas No es una gráfica conectada Grafica ponderada

4.1. Metodo

4.2. Algoritmo Dijkstra Encuentra una arborescencia, obtiene un escalar para los arcos que no pertenecen a la arborescencia, actualizan distancias y se ubica al arco al que ya no pertenece a la arborescencia

5. Método

6. Flujo máximo Todo flujo a través de una red dirigida se origina en un nodo fuente (inicial) y termina en un nodo destino (terminal) Debe ser conectada del nodo inicial al terminal El resto de los nodos son nodos de transbordo o intermedios El flujo es permitido solo por la dirección del arco El objetivo es maximizar la cantidad de flujo de la fuente al destino

6.1. Métodos

6.2. Ford y Fulkerson

6.3. Flujo mínimo

7. Flujo mínimo Busca la mínima cantidad que pueda pasar por el arco

7.1. Métodos

7.2. Algoritmo de flujo mínimo

8. Flujo a costo mínimo Todos los arcos son direccionales (un sentido). Un costo de flujo por unidad (no negativo) está asociado con cada arco. Los arcos pueden tener límites positivos de capacidad inferior. Cualquier nodo en la red puede actuar como un punto de origen. El modelo determina los flujos en los diferentes arcos que minimizan el costo Total, al mismo tiempo que satisfacen las restricciones del flujo en los arcos y Las cantidades de la oferta y la demanda en los nodos.

8.1. métodos

8.1.1. método de los circuitos negativos.

8.1.2. método basado en utas más cortas.

8.1.3. método simplex para redes.

9. Redes de actividad la planeación con enfoques en proyectos específicos se pone cualquier actividad que se necesite y sirve para casos muy sencillos o para grandes planeaciones, proyectos y obras.

9.1. Metodos

9.2. PERT (Program Evolution and Review Technique)

9.2.1. Planeación.

9.2.2. Programación.

9.2.3. Control.

9.2.4. requiere de 3 tiempos para obtener el tiempo esperado de duración de cada actividad:

9.2.5. Tiempo optimista: Si todo sale bien.

9.2.6. Tiempo optimista: Si todo sale bien.

9.2.7. Tiempo más probable: Si todo va normal

9.3. Ruta crítica CPM (Critical Path Method).

9.4. Ambos se utilizan para administrar proyectos, aunque, la diferencia entre éstos, radica principalmente en los tiempos de las actividades. En el modelo CPM se manejan tiempos deterministicos y en PERT, probabilisticos.