Buscar en el Blog

Mostrando entradas con la etiqueta grafos. Mostrar todas las entradas
Mostrando entradas con la etiqueta grafos. Mostrar todas las entradas

jueves, 11 de junio de 2015

MANUAL DE ALGORITMICA - Grafos


MANUAL DE ALGORITMICA
 Grafos
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
rafaborrego@gmail.com
Recio Domínguez, Daniel
danird@gmail.com

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
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