Hokage
Páginas: 26 (6365 palabras)
Publicado: 9 de octubre de 2010
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
rafaborrego@gmail.com Recio Domínguez, Daniel danird@gmail.com
Borrego Ropero Rafael Recio Domínguez Daniel
1 de 248
Manual de algorítmica
Borrego Ropero Rafael RecioDomínguez Daniel
2 de 248
Manual de algorítmica
1.- Introducción................................................................................................... 6 2.- Conceptos generales. ................................................................................... 8 Grafos, tipos, ejemplos................................................................................ 8Algunas definiciones. ................................................................................ 12 Algunos grafos básicos. ............................................................................ 17 Tipos de rutas ........................................................................................... 46 Grafocomplementario............................................................................... 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 ungrafo...................................................................................... 67 Diámetro de un grafo................................................................................. 69 Distancia de un vértice. ............................................................................. 70 Algoritmo de la mediana............................................................................ 72 Algoritmo delcentro. ................................................................................. 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 dePrim...................................................................................... 98 Algoritmo de Kruskal. .............................................................................. 100 3.6.- Prufer.................................................................................................. 103 Algoritmo de codificación. ....................................................................... 103 Algoritmo de decodificación....
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 248
Manual de algorítmica
Borrego Ropero Rafael RecioDomínguez Daniel
2 de 248
Manual de algorítmica
1.- Introducción................................................................................................... 6 2.- Conceptos generales. ................................................................................... 8 Grafos, tipos, ejemplos................................................................................ 8Algunas definiciones. ................................................................................ 12 Algunos grafos básicos. ............................................................................ 17 Tipos de rutas ........................................................................................... 46 Grafocomplementario............................................................................... 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 ungrafo...................................................................................... 67 Diámetro de un grafo................................................................................. 69 Distancia de un vértice. ............................................................................. 70 Algoritmo de la mediana............................................................................ 72 Algoritmo delcentro. ................................................................................. 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 dePrim...................................................................................... 98 Algoritmo de Kruskal. .............................................................................. 100 3.6.- Prufer.................................................................................................. 103 Algoritmo de codificación. ....................................................................... 103 Algoritmo de decodificación....
Leer documento completo
Regístrate para leer el documento completo.