Hokage

Solo disponible en BuenasTareas
  • Páginas : 26 (6365 palabras )
  • Descarga(s) : 0
  • Publicado : 9 de octubre de 2010
Leer documento completo
Vista previa del texto
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....
tracking img