Manual de algorítmica
MANUAL DE ALGORÍTMICA
Proyecto fin de carrera
Escuela Técnica Superior de Ingeniería Informática
Departamento Matemáticas Aplicadas I
Tutor: Alberto Márquez Pérez
Borrego Ropero, Rafael
[email protected]
Recio Domínguez, Daniel
[email protected]
Borrego Ropero Rafael 1 de 248
Recio Domínguez Daniel
Manual de algorítmica
Borrego Ropero Rafael 2 de 248
Recio Domínguez Daniel
Manual de algorítmica
1.- Introducción................................................................................................... 6
2.- Conceptos generales. ................................................................................... 8
Grafos, tipos, ejemplos................................................................................ 8
Algunas definiciones. ................................................................................ 12
Algunos grafos básicos. ............................................................................ 17
Tipos de rutas ........................................................................................... 46
Grafo complementario............................................................................... 48
Grafo de línea. .......................................................................................... 50
3.- Algoritmos implementados.......................................................................... 54
3.1.- Algoritmos sobre caminos mínimos...................................................... 54
Algoritmo de Dijkstra. ................................................................................ 54
Algoritmo de Floyd. ................................................................................... 61
3.2.- Algoritmos de distancias....................................................................... 65
Excentricidad de un vértice. ...................................................................... 65
Radio de un grafo...................................................................................... 67
Diámetro de un grafo................................................................................. 69
Distancia de un vértice.............................................................................. 70
Algoritmo de la mediana............................................................................ 72
Algoritmo del centro. ................................................................................. 73
3.3.- Conectividad......................................................................................... 75
Algoritmo de componentes conexas. ........................................................ 75
Vértices de corte. ...................................................................................... 77
Aristas puente. .......................................................................................... 78
Bloques. .................................................................................................... 79
3.4.- Algoritmos de búsquedas. .................................................................... 88
Búsqueda en profundidad (DFS) .............................................................. 88
Búsqueda en anchura (BFS) .................................................................... 90
3.5.- Árboles recubridores de peso mínimo. ................................................. 92
Algoritmo de Boruvka................................................................................ 92
Algoritmo de Prim...................................................................................... 98
Algoritmo de Kruskal. .............................................................................. 100
3.6.- Prufer.................................................................................................. 103
Algoritmo de codificación. ....................................................................... 103
Algoritmo de decodificación. ................................................................... 110
3.7.- Algoritmo de emparejamientos ........................................................... 120
Algoritmo de emparejamiento maximal simple........................................ 121
Algoritmo de Kuhn-Munkres.................................................................... 128
Algoritmo de Kuhn-Munkres con preprocesamiento (peso mínimo)........ 142
Algoritmo de emparejamiento maximal de peso óptimo.......................... 146
3.8.- Euler ................................................................................................... 157
¿ Es euleriano ?. ..................................................................................... 157
3.9.- Algoritmos de búsqueda de trayectorias eulerianas. .......................... 162
Algoritmo de Fleury ................................................................................. 162
Algoritmo de Tucker. ............................................................................... 183
Algoritmo de Hierholzer........................................................................... 201
Problema del cartero............................................................................... 205
3.10.- Algoritmos de vértice coloración....................................................... 212
Algoritmo de coloración Secuencial o Voraz. .......................................... 213
Borrego Ropero Rafael 3 de 248
Recio Domínguez Daniel
Manual de algorítmica
Algoritmo de coloración Welsh-Powell .................................................... 215
Algoritmo de coloración Matula-Marble-Isaacson ................................... 216
Algoritmo de coloración de Brelaz........................................................... 217
¿Es bipartito? .......................................................................................... 221
3.11.- Algoritmos de aristas coloración....................................................... 225
Algoritmo basado en rellenar un cuadrado latino .................................... 225
Algoritmo basado en emparejamientos maximales................................. 228
3.-12.- Hamilton .......................................................................................... 235
Algoritmo de Dirac................................................................................... 235
Búsqueda de trayectorias hamiltonianas................................................. 239
4.- Bibliografía ................................................................................................ 248
Borrego Ropero Rafael 4 de 248
Recio Domínguez Daniel
Manual de algorítmica
Borrego Ropero Rafael 5 de 248
Recio Domínguez Daniel
Manual de algorítmica
La aplicación desarrollada tiene como objetivos mejorar algunos
Nos encontramos ante una aplicación desarrollada para el departamento
1.- Introducción.
de matemática aplicada I con el objetivo de proporcionar una herramienta que
ayude al desarrollo de las prácticas de las asignaturas dedicadas al estudio de
los grafos y la investigación.
aspectos de la aplicación “Algraf” la cual ha sido punto de partida de este
proyecto por lo que se mantiene la compatibilidad con versiones anteriores.
anteriores de “Algraf” y se han incluido algunos nuevos por los que ahora la
aplicación da solución a gran cantidad de problemas entre los que podemos
destacar.
La aplicación resuelve todos los problemas recogidos en versiones
- Problema de rutas.
- Problemas de ubicación.
- Problemas de compatibilidades o coloración.
- Problemas de minimización de costes.
- Problemas de emparejamientos.
Los conceptos expuestos a continuación están enfocados a la
comprensión única y exclusivamente a los algoritmos desarrollados para la
aplicación. Se ha pretendido que sea un manual autocontenido por lo que
cualquier concepto necesario para entender de los algoritmos o funcionamiento
de la aplicación está debidamente explicado.
Borrego Ropero Rafael 6 de 248
Recio Domínguez Daniel
Manual de algorítmica
Borrego Ropero Rafael 7 de 248
Recio Domínguez Daniel
Manual de algorítmica
2.- Conceptos generales.
Grafos, tipos, ejemplos.
Un grafo G es un conjunto finito, no vacío de vértices V(G) y un
conjunto de aritas E(G) que puede ser vacío formado por pares no
ordenados de elementos pertenecientes a V(G). Solo se establecerá un
orden cuado hablemos de grafos dirigidos y a las aristas se las
denomina arcos.
Ejemplo de grafo no dirigido.
La matriz de adyacencias del grafo es simétrica respecto a la
diagonal principal por ser no dirigido.
1
1
1
1 1 1
v7
v1
v2 1
1
v3
v4 1 1
v5
1
v6
v1 v2 v3 v4 v5 v6 v7
1
1
1
1
1
Borrego Ropero Rafael 8 de 248
Recio Domínguez Daniel
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
¥
Manual de algorítmica
Si dos o más aristas unen el mismo par de vértices se llaman
aristas paralelas y en este caso tenemos un multigrafo.
Si una arista une un mismo vértice se trata de un lazo o bucle.
Si en un grafo se permite aristas paralelas y bucles obtenemos un
Comentarios de: Manual de Algorítmica (0)
No hay comentarios