Algortimos De Grafos

Documentación de la aplicación Algraf Project

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

Borrego Ropero Rafael
Recio Domínguez Daniel

1 de 210

Documentación de laaplicación Algraf Project

Borrego Ropero Rafael
Recio Domínguez Daniel

2 de 210

Documentación de la aplicación Algraf Project
TABLA DE CONTENIDOS

1.- Introducción................................................................................................... 5
2.- Conceptos generales. ................................................................................... 7
Grafos,tipos, ejemplos................................................................................ 7
Algunas definiciones. ................................................................................ 11
Algunos grafos básicos. ............................................................................ 15
Tipos de rutas........................................................................................... 41
Grafo complementario............................................................................... 43
Grafo de línea. .......................................................................................... 45
3.- Algoritmos implementados. ......................................................................... 47
3.1.- Algoritmos sobre caminos mínimos...................................................... 47
Algoritmo de Dijkstra. ................................................................................ 47
Algoritmo de Floyd. ................................................................................... 53
3.2.- Algoritmos de distancias....................................................................... 57
Excentricidad de un vértice....................................................................... 57
Radio de un grafo...................................................................................... 58
Diámetro de un grafo................................................................................. 60
Distancia de un vértice. ............................................................................. 61
Algoritmo dela mediana............................................................................ 63
Algoritmo del centro. ................................................................................. 64
Algoritmo de componentes conexas. ........................................................ 66
Vértices de corte. ......................................................................................68
Aristas puente. .......................................................................................... 69
Bloques. .................................................................................................... 70
3.3.- Algoritmos de búsquedas. .................................................................... 77
Búsqueda en profundidad (DFS).............................................................. 77
Búsqueda en anchura (BFS) .................................................................... 79
3.4.- Árboles recubridores de peso mínimo. ................................................. 81
Algoritmo de Boruvka. ............................................................................... 81
Algoritmo dePrim...................................................................................... 86
Algoritmo de Kruskal. ................................................................................ 88
3.5.- Prüfer.................................................................................................... 91
Algoritmo de codificación. ......................................................................... 91
Algoritmo de decodificación....