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
[email protected]
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
Comentarios de: Prácticas de matemática discreta con MaGraDa (0)
No hay comentarios