Universidad Politécnica

de Gómez Palacio.
Ingeniería en Tecnologías de la Información.

Lenguajes y Autómatas

Trabajo de investigación.

Docente: José Ángel Flores Velazco

Alumno: Jesús Rogelio Jiménez Guerrero / 20080102
Grupo: ITI 7°A

03 de Diciembre del 2022

Gómez Palacio Dgo.
Algoritmos para grafos:

Recorrido en anchura:

"En Ciencias de la Computación, Búsqueda en es un algoritmo para recorrer o buscar

elementos en un. Intuitivamente, se comienza en la raíz (eligiendo algún nodo como
elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo.

Un recorrido en anchura se refiere a recorrer un grafo por niveles, es decir, partiendo de

un nodo inicial recorro todos sus vecinos, posteriormente los vecinos de los vecinos hasta
que todos los nodos hayan sido visitados.

A continuaci´on, describimos la idea de un procedimiento recursivo para realizar un

recorrido en anchura de un grafo no dirigido G. Para ello, en primer lugar, a cada nodo,

v, del grafo se le asocia un procedimiento, BF S(G, v), que se denomina recorrido en

anchura de G con origen v.

La idea del procedimiento BF S(G, v) es la siguiente:

• Se marca el nodo v.

• Si todos los nodos adyacentes a v est´an marcados, entonces TERMINAR; si no,

marcar todos los nodos v1, v2, . . . , vk adyacentes a v que no est´en marcados.

• Repetir el proceso con los nodos adyacentes a los nodos que se han marcado en el

paso anterior.
Recorrido en profundidad:

"Una Búsqueda en es un algoritmo que permite recorrer todos los nodos de un grafo o
árbol (teoría de grafos) de manera ordenada, pero no uniforme. Su funcionamiento
consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma
recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho
camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de
los hermanos del nodo ya procesado."

Un recorrido en profundidad es que partiendo de un nodo inicial, visite toda una rama,
luego otra hasta que todos los nodos hayan sido visitados.

La estrategia de recorrido en profundidad es la siguiente:

1. Se toma un nodo “s” como comienzo, y se marca.

2. A continuación se toma y se marca un nodo no marcado adyacente a “s”, y ese

nodo pasa a ser el nuevo nodo de partida, dejando posiblemente por el momento al

nodo inicial original con nodos no explorados.

3. La búsqueda continúa por el grafo hasta que el camino en curso finalice con un

grafo de salida igual a cero, o bien en un nodo en que todos los nodos adyacentes

estén marcados.

4. A continuación la búsqueda vuelve al último nodo que todavía tenga nodos

adyacentes sin marcar, y continúa marcando todos los nodos de forma recursiva

hasta que ya no queden nodos sin marcar.

Algoritmo Dijkstra.

Algoritmo de Dijkstra. También llamado algoritmo de caminos mínimos, es un

algoritmo para la determinación del camino más corto dado un vértice origen al
resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a
Edsger Dijkstra, quien lo describió por primera vez en 1959.
Pasos del algoritmo

Sea V un conjunto de vértices de un grafo.

Sea C una matriz de costos de las aristas del grafo, donde en C[u,v] se almacena el costo
de la arista entre u y v.

Sea S un conjunto que contendrá los vértices para los cuales ya se tiene determinado el
camino mínimo.

Sea D un arreglo unidimensional tal que D[v] es el costo del camino mínimo del vértice
origen al vértice v.

Sea P un arreglo unidimensional tal que P[v] es el vértice predecesor de v en el camino

mínimo que se tiene construido.

Sea vinicial el vértice origen. Recordar que el Algoritmo Dijkstra determina los caminos
mínimos que existen partiendo de un vértice origen al resto de los vértice.
Árbol de expansión mínima.

La modelación de redes permite la resolución de múltiples problemas de programación

matemática mediante la implementación de algoritmos especiales creados para tal fin,
conocidos como Algoritmos de optimización de redes. Dentro de los problemas más
comúnmente resueltos mediante la modelación de redes se encuentran los ya vistos
modelos de transporte, transbordo además de los muy conocidos modelos de
determinación de cronograma de actividades para proyectos como lo son el PERT y el
CPM.

El algoritmo de árbol de expansión mínima enlaza los nodos de una red, en forma directa
o indirecta, con la mínima longitud de las ramas enlazantes. Una aplicación característica
es en la construcción de carreteras pavimentadas que unen varias poblaciones. El camino
entre dos

poblaciones puede pasar por uno o más poblaciones adicionales. El diseño más
económico del sistema de caminos indica que se minimice la distancia total de caminos
pavimentados, resultado que se obtiene implementando el algoritmo de árbol de
expansión mínima.

Los pasos del procedimiento son los siguientes. Sea N . {1, 2, ..., n} el conjunto de nodos
de la red, y se definen.
Flujo máximo:

Modelo del flujo máximo: En algunas redes circula por los arcos un flujo (envío o circulación de
unidades homogéneas de algún producto: automóviles en una red de carreteras, litros de petróleo
en un oleoducto, bits por un cable de fibra óptica) desde el origeno fuente al destino, también
denominado sumidero o vertedero. Los arcos tienen una capacidad máxima de flujo, y se trata de
enviar desde la fuente al sumidero la mayor cantidad posible de flujo, de tal manera que:

El flujo es siempre positivo y con unidades enteras.

El flujo a través de un arco es menor o igual que la capacidad.

El flujo que entra en un nodo es igual al que sale de él.

En el caso de que el origen o el destino no existan en el problema, se añaden ficticiamente

utilizando arcos unidireccionales de capacidad infinita, como en grafo mostrado a continuación:

Corte: Un corte define una serie de arcos cuya supresión de la red causa una interrupción
completa del flujo entre el origen y el destino. La capacidad de corte es igual a la suma de las
capacidades de los arcos asociados. Entre todos los cortes posibles en la red , el corte con la
menor capacidad proporciona el flujo máximo en la red.

El siguiente grafo ilustra 3 cortes: el Corte 1 con capacidad 60, el Corte 2 con capacidad 110 y el
Corte 3 con capacidad 70. Todo lo que podemos obtener de los 3 cortes es que el flujo máximo en
la red no excede de 60 unidades. No podemos saber cual es el flujo máximo hasta que se hayan
enumerado todos los cortes en la red:
Las capacidades se identifican como sigue: por ejemplo, para el arco (3,4), el límite de flujo es de
10 unidades de 3 a 4 y de 5unidades de 4 a 3.

Algoritmo de Floyd-Warshall

Análisis e implementación

Elalgoritmo de Floyd-Warshall es la opción utilizada cuando se desea determinar el

camino mínimo entre todos los pares de vértices de un grafo, comparando todos los
posibles caminos logra mejorar paulatinamente la estimación hasta llegar a la más óptima.
Esto puede presentarse de manera más clara a través de un ejemplo de implementación.
Pero antes, revisaremos el análisis del tiempo de ejecución para este caso.

Análisis del algoritmo

Al momento de analizar un algoritmo revisamos el conjunto de operaciones primitivas de

alto nivel que son independientes del lenguaje de programación que se utilice, estas
pueden ser identificadas en el pseudocódigo del mismo.
Pseudocódigo del algoritmo Floyd-Warshall

Si queremos dar una caracterización O(·) del tiempo de ejecución en términos de n del
algoritmo debemos llevar a cabo tres sencillos pasos.

Conteo de operaciones primitivas

Para ésto, revisamos cada paso del algoritmo en el pseudocódigo y contamos las
operaciones que se ejecutan. A continuación se muestra el procedimiento llevado a cabo:
Conteo de operaciones primitivas del algoritmo

Estimación del tiempo de ejecución

Ahora, calculamos el tiempo de ejecución t(n) del algoritmo Floyd-Warshall sumando el

costo obtenido de las operaciones primitivas.

Caracterización Big-O

Aplicando la definición de Big-O, obtenemos una constante c > 0 que pertenezca a los
reales.