PDF de programación - Prácticas de matemática discreta con MaGraDa

Imágen de pdf Prácticas de matemática discreta con MaGraDa

Prácticas de matemática discreta con MaGraDagráfica de visualizaciones

Publicado el 14 de Enero del 2017
949 visualizaciones desde el 14 de Enero del 2017
2,1 MB
239 paginas
PRÁCTICAS DE MATEMÁTICA
DISCRETA CON MaGraDa
Manuel Ángel Caballero Palomino / Violeta
Migallón Gomis / José Penadés Martínez

TD

TEXTOSDOCENTES

PUBLICACIONES

Universidad de Alicante

© los autores

© de la presente edición

Publicaciones de la Universidad de Alicante

Campus de San Vicente s/n

03690 San Vicente del Raspeig

Publicaciones@ua.es

http://publicaciones.ua.es

ISBN: 84-7908-641-6

Depósito Legal: A-1480-2001

Reservados todos los derechos. No se permite reproducir, almacenar en sistemas
de recuperación de la información ni transmitir alguna parte de esta publicación,

cualquiera que sea el medio empleado -electrónico, mecánico, fotocopia,
grabación, etc.-, sin el permiso previo de los titulares de los derechos

de la propiedad intelectual.

Edición electrónica:
Espagrafic

M. Caballero, V. Migallón y J. Penadés

Prácticas de matemática discreta

con MaGraDa

Índice

Portada

Créditos

Prólogo

9

1 Introducción a MaGraDa

13
1.1 Introducción . . . . . . . . . . . . . . . . . . . . . 13
1.2 El modo de texto . . . . . . . . . . . . . . . . . . 17
1.2.1 Introducción de un grafo . . . . . . . . . 19
1.2.2 Borrando un grafo ya existente . . . . . . 23
1.2.3 Seleccionando un grafo . . . . . . . . . . 23
1.2.4 Uso de ficheros para abrir o guardar un

grafo . . . . . . . . . . . . . . . . . . . . . 24
1.2.5 Modificación de un grafo . . . . . . . . . 25
1.2.6 Salir de MaGraDa . . . . . . . . . . . . . 27
1.2.7 Práctica 1 . . . . . . . . . . . . . . . . . . 28
1.3 El modo gráfico . . . . . . . . . . . . . . . . . . . 31
1.3.1 El lienzo . . . . . . . . . . . . . . . . . . . 33
1.3.2 Introducción de un grafo . . . . . . . . . 34
1.3.3 Práctica 2 . . . . . . . . . . . . . . . . . . 41

2 Fundamentos

45
2.1 Introducción . . . . . . . . . . . . . . . . . . . . . 45
2.2 Cálculos básicos . . . . . . . . . . . . . . . . . . 46

Índice

2.2.1 Grado . . . . . . . . . . . . . . . . . . . . 46
2.2.2 Ver . . . . . . . . . . . . . . . . . . . . . . 50
2.2.3 Grafo (simple, cíclico, completo y conexo) 50
2.2.4 Grafo no dirigido asociado . . . . . . . . 52
2.2.5 Grafos isomorfos . . . . . . . . . . . . . . 53
2.2.6 Práctica 3 . . . . . . . . . . . . . . . . . . 57
2.3 Matriz de adyacencia . . . . . . . . . . . . . . . 68
2.3.1 Práctica 4 . . . . . . . . . . . . . . . . . . 70

3 Estudio de la accesibilidad y conectividad

73
3.1 Introducción . . . . . . . . . . . . . . . . . . . . . 73
3.2 Matriz de accesibilidad y matriz de acceso . . . 73
3.2.1 Vértices alcanzables desde otro . . . . . 73
3.2.2 Vértices que alcanzan a otro . . . . . . . 76
3.2.3 Accesibilidad y algoritmo de Warshall
. . 78
3.2.4 Práctica 5 . . . . . . . . . . . . . . . . . . 81
3.3 Cálculo de componentes conexas . . . . . . . . 89
3.3.1 Práctica 6 . . . . . . . . . . . . . . . . . . 94

4 Problemas de recorrido de aristas y vértices

107
4.1 Introducción . . . . . . . . . . . . . . . . . . . . . 107
4.2 Problema de recorrido de aristas . . . . . . . . . 107
4.2.1 Práctica 7 . . . . . . . . . . . . . . . . . . 112
4.3 Problema de recorrido de vértices . . . . . . . . 119
4.3.1 Práctica 8 . . . . . . . . . . . . . . . . . . 123

Índice

5 Introducción a la estructura de árbol

129
5.1 Introducción . . . . . . . . . . . . . . . . . . . . . 129
5.2 Definiciones y propiedades . . . . . . . . . . . . 129

5.2.1Práctica9.. ................132
5.3 Árbolesconraíz.. ................140
5.3.1Práctica10. ................142

5.4 Notación polaca . . . . . . . . . . . . . . . . . . 149
5.4.1 Práctica 11 . . . . . . . . . . . . . . . . . 153

6 Grafos ponderados. Caminos críticos en grafos

acíclicos
157
6.1 Introducción . . . . . . . . . . . . . . . . . . . . . 157
6.2 Creación de un grafo ponderado . . . . . . . . . 157
6.2.1 Práctica 12 . . . . . . . . . . . . . . . . . 160
6.3 Ecuaciones de Bellman . . . . . . . . . . . . . . 164
6.3.1 Caminos más cortos . . . . . . . . . . . . 164
6.3.2 Secuenciación de actividades (PERT) . . 172
6.3.3 Práctica 13 . . . . . . . . . . . . . . . . . 176

7 Caminos más cortos y árboles generadores de peso

191
mínimo
7.1 Introducción . . . . . . . . . . . . . . . . . . . . . 191
7.2 Caminos más cortos . . . . . . . . . . . . . . . . 191
7.2.1 Algoritmo de Dijkstra . . . . . . . . . . . . 191
. . . . . . 199
7.2.2 Algoritmo de Floyd y Warshall

Índice

7.3

7.2.3 Práctica 14 . . . . . . . . . . . . . . . . . 204
Árboles generadores de peso mínimo . . . . . . 219
7.3.1 Algoritmo de Kruskal . . . . . . . . . . . . 219
7.3.2 Algoritmo de Prim . . . . . . . . . . . . . 222
7.3.3 Práctica 15 . . . . . . . . . . . . . . . . . 227

Bibliografía

237

M. Caballero, V. Migallón y J. Penadés

Prácticas de matemática discreta con MaGraDa

Prólogo

E ste libro va dirigido al alumnado de las titulaciones de

informática de la Universidad de Alicante y cubre parte
de las prácticas de la asignatura Matemática Discreta.
Para la realización de estas prácticas se ha elegido el paquete
de software MaGraDa (Grafos para Matemática Discreta). Es-
ta aplicación se ha realizado en el Departamento de Ciencia
de la Computación e Inteligencia Artificial, inicialmente como
proyecto de la asignatura Sistemas Informáticos, por el
in-
geniero informático Manuel Ángel Caballero Palomino y bajo
el asesoramiento de la profesora Violeta Migallón Gomis y el
profesor José Penadés Martínez.

MaGraDa ha sido diseñado específicamente para fines do-
centes y cubre gran parte de los conceptos de la teoría de gra-
fos que se estudian en la asignatura de Matemática Discreta,
pretendiendo automatizar el trabajo con grafos y además que
quién utilice MaGraDa se familiarice con ellos de manera efi-
caz. Los objetivos que se pretenden alcanzar con la realiza-

ÍNDICE

9

Prólogo

ción de las prácticas de este libro no se limitan únicamente al
conocimiento de su manejo. Se desea también que al finalizar
dichas prácticas, se hayan afianzado los conceptos estudia-
dos en las clases teóricas, sabiendo plantear inicialmente el
problema propuesto, para posteriormente, utilizando o no Ma-
GraDa, poder obtener las conclusiones pertinentes.

Este libro comienza con un capítulo introductorio en el que
se describe MaGraDa y se dan algunas ideas básicas para
su manejo. El segundo capítulo se centra en la utilización
de MaGraDa para resolver problemas básicos de grafos, re-
lacionados con sus fundamentos. En el capítulo tercero se
estudiará la accesibilidad y la conectividad de un grafo con
MaGraDa. El capítulo cuarto está dedicado a los problemas
de recorrido de aristas y vértices. En el capítulo quinto se
tratará la estructura de árbol. Los capítulos sexto y séptimo
están dedicados a los grafos ponderados. En el capítulo sexto
se verá cómo introducir estos grafos con MaGraDa y la forma
de obtener caminos críticos. Por último, en el capítulo sépti-
mo, se tratan los problemas de caminos más cortos y árboles
generadores de peso mínimo.

En este libro las prácticas van entrelazadas con las expli-
caciones. Nuestro consejo es que antes de una sesión de
prácticas se lea el capítulo (o parte del capítulo) correspon-
diente a esa sesión, así como los apuntes de la parte teórica

ÍNDICE

10

M. Caballero, V. Migallón y J. Penadés

Prácticas de matemática discreta con MaGraDa

correspondiente. De esa forma, antes de empezar la práctica
y después de las explicaciones complementarias que se den
en las clases, se podrán tratar las dudas surgidas.

Esperamos que la realización de estas prácticas ayude al
alumnado de informática a comprender con más facilidad la
matemática discreta.

Por último, mencionar que los autores han decidido que
MaGraDa sea un software de dominio público, esperando que
sea útil a toda la comunidad universitaria. Está disponible en
Y}U\\bbbI{{$sZsR\I{{$s\$tP\sR$tsZsR\*\.

ÍNDICE

11

Prólogo

ÍNDICE

12

M. Caballero, V. Migallón y J. Penadés

Prácticas de matemática discreta con MaGraDa

1. Introducción a MaGraDa

1.1 Introducción

El paquete de software MaGraDa (Grafos para Matemática
Discreta) es una aplicación informática programada en lengua-
je Java y diseñada específicamente para trabajar con grafos.
MaGraDa trabaja con grafos tanto dirigidos como no dirigidos
y ponderados como no ponderados, pero por el momento, sólo
se trabajará con grafos no ponderados. Más adelante, en el
capítulo 6, introduciremos los grafos ponderados. Según la
filosofía de MaGraDa podríamos trabajar con un número ilimi-
tado de vértices, pero hemos creído conveniente sólo permitir
trabajar con grafos de hasta un máximo de x( vértices. Es-
te paquete es sencillo y cómodo de manejar, está basado en
menúes sobre pantalla y consta de dos pantallas de visuali-
zación:

(i) El modo de texto: Llamémoslo de esta forma para diferen-
ciarlo del otro. Permite trabajar con los grafos de forma
analítica. Es decir, trabajaremos en todo momento con

ÍNDICE

13

Introducción a MaGraDa

los datos del grafo, pero sin visualizarlo gráficamente.

(ii) El modo gráfico: Trabaja con los grafos de forma que

pueden verse gráficamente.

Ambas pantallas de trabajo son prácticamente equivalen-
tes en funcionalidad. Es decir, no hay ningún método que esté
sólo implementado para una forma de trabajo exclusivamen-
te. Sin embargo, la forma de ofrecer los resultados no es la
misma en los dos modos. En cada uno de ellos se mues-
tran los resultados intentando maximizar la comprensión de
los mismos. Básicamente, podemos agrupar las aplicaciones
que nos ofrece MaGraDa en tres partes:

T Manejo de grafos (Grafo): Ésta es la parte donde se
pueden crear grafos nuevos o abrir grafos ya creados
desde un fichero, modificarlos, borrarlos de memoria,
seleccionarlos o guardarlos en un fichero para su tra-
tamiento posterior.

T Cálculos básicos: Hay una serie de características o
propiedades básicas de los grafos que se pueden averi-
guar fácilmente con esta serie de métodos, tales como el
grado de un vértice, la matriz de adyacencia
  • Links de descarga
http://lwp-l.com/pdf768

Comentarios de: Prácticas de matemática discreta con MaGraDa (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad