PDF de programación - Manual de Algorítmica

Imágen de pdf Manual de Algorítmica

Manual de Algorítmicagráfica de visualizaciones

Publicado el 14 de Enero del 2017
1.587 visualizaciones desde el 14 de Enero del 2017
3,4 MB
248 paginas
Creado hace 17a (19/10/2006)
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
  • Links de descarga
http://lwp-l.com/pdf270

Comentarios de: Manual de Algorítmica (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad