Magrada

Prácticas de matemática discreta con MaGraDa

´ Indice

Portada Créditos Prólogo 1 Introducción a MaGraDa 1.1 Introducción . . . . . . . . . . . . . . . . . . . . . 1.2 El modo de texto . . . . . . . . . . . . . . . . . . 1.2.1 Introducción de un grafo . . . . . . . . . 1.2.2 Borrando un grafo ya existente . . . . . . 1.2.3 Seleccionando un grafo . . . . . . . . . . 1.2.4 Uso de ficherospara abrir o guardar un grafo . . . . . . . . . . . . . . . . . . . . . 1.2.5 Modificación de un grafo . . . . . . . . . 1.2.6 Salir de MaGraDa . . . . . . . . . . . . . 1.2.7 Práctica 1 . . . . . . . . . . . . . . . . . . 1.3 El modo gráfico . . . . . . . . . . . . . . . . . . . 1.3.1 El lienzo . . . . . . . . . . . . . . . . . . . 1.3.2 Introducción de un grafo . . . . . . . . . 1.3.3 Práctica 2 .. . . . . . . . . . . . . . . . . 9 13 13 17 19 23 23 24 25 27 28 31 33 34 41

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

´ Indice

2.2.1 2.2.2 2.2.3 2.2.4 2.2.5 2.2.6 2.3 Matriz 2.3.1

Grado . . . . . . . . . . . . . . . . . . . . Ver . . . . . . . . . . . . . . . . . . . . . . Grafo(simple, cíclico, completo y conexo) Grafo no dirigido asociado . . . . . . . . Grafos isomorfos . . . . . . . . . . . . . . Práctica 3 . . . . . . . . . . . . . . . . . . de adyacencia . . . . . . . . . . . . . . . Práctica 4 . . . . . . . . . . . . . . . . . .

46 50 50 52 53 57 68 70 73 73 73 73 76 78 81 89 94 107 107 107 112 119 123

3 Estudio de la accesibilidad y conectividad 3.1 Introducción .. . . . . . . . . . . . . . . . . . 3.2 Matriz de accesibilidad y matriz de acceso . 3.2.1 Vértices alcanzables desde otro . . . 3.2.2 Vértices que alcanzan a otro . . . . . 3.2.3 Accesibilidad y algoritmo de Warshall 3.2.4 Práctica 5 . . . . . . . . . . . . . . . . 3.3 Cálculo de componentes conexas . . . . . . 3.3.1 Práctica 6 . . . . . . . . . . . . . . . . 4 Problemas de recorrido de aristasy vértices 4.1 Introducción . . . . . . . . . . . . . . . . . . 4.2 Problema de recorrido de aristas . . . . . . 4.2.1 Práctica 7 . . . . . . . . . . . . . . . 4.3 Problema de recorrido de vértices . . . . . 4.3.1 Práctica 8 . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . .

. . . . .

. . . . .

´ Indice

5 Introducción a la estructura de árbol 5.1Introducción . . . . . . . . . . . . . 5.2 Definiciones y propiedades . . . . 5.2.1 Práctica 9 . . . . . . . . . . ´ 5.3 Arboles con raíz . . . . . . . . . . 5.3.1 Práctica 10 . . . . . . . . . 5.4 Notación polaca . . . . . . . . . . 5.4.1 Práctica 11 . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .129 129 129 132 140 142 149 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.2Secuenciación de actividades (PERT) . . 172 6.3.3 Práctica 13 . . . . . . . . . . . . . . . . . 176 7 Caminos más cortos y árboles generadores de peso mínimo 191 7.1 Introducción . . . . . . . . . . . . . . . . . . . . . 191 7.2 Caminos más cortos . . . . . . . . . . . . . . . . 191 7.2.1 Algoritmo de Dijkstra . . . . . . . . . . . . 191 7.2.2 Algoritmo de Floyd y Warshall . . . . . . 199

´ Indice7.2.3 Práctica 14 . . . . . . . . . . . . . . ´ 7.3 Arboles generadores de peso mínimo . . . 7.3.1 Algoritmo de Kruskal . . . . . . . . . 7.3.2 Algoritmo de Prim . . . . . . . . . . 7.3.3 Práctica 15 . . . . . . . . . . . . . . Bibliografía

. . . . .

. . . . .

. . . . .

204 219 219 222 227 237

M. Caballero, V. Migallón y J. Penadés Prácticas de matemática discreta con MaGraDa...