Actividad de aprendizaje 4. Teoría de grafos

ACTIVIDAD DE APRENDIZAJE 4. TEORIA DE GRAFOS

NOMBRE DEL ALUMNO: ALAN ALEJANDRO OLVERA NAVARRETE

MATRICULA: 91619

GRUPO: K048

MATERIA: (11) ALGORITMOS Y ESTRUCTURAS DE DATOS

DOCENTE: DR. AGUSTIN LEOBARDO HERRERA MAY

CIUDAD: CIUDAD DE MÉXICO

FECHA: 30/07//2018

ACTIVIDAD DE APRENDIZAJE 4. TEORÍA DE GRAFOS

        Un grafo dirigido G consiste en un conjunto de vértices y un conjunto de arcos o aristas. A los vértices también se les conoce como nodos o puntos, y estos pueden usarse para representar objetos. Los arcos se utilizan para representar las relaciones que existen entre estos objetos. Un arco, es un par ordenado de vértices (V, W) donde V es el vértice inicial y W es el vértice terminal del arco. Un arco se expresa como: V → W, y se puede representar de la siguiente manera:

[pic 2][pic 3][pic 4]

        Existen diversas aplicaciones de los grafos como pueden ser:

• Determinar tiempos máximos y mínimos en un proceso
• Flujo y control en un programa
• Ruta entre ciudades

En el caso del problema a resolver, tenemos que representar los distritos que se muestran en un mapa con vértices y aristas.

[pic 5]

Figura 1: Mapa

Los vértices se representan con un círculo y una letra que distingue a cada distrito. Las aristas son las flechas que existen entre cada círculo. El distrito o vértice B comparte color de arista con el distrito/ vértice A y D.

1. Encuentra una representación en términos de vértices y aristas de un grafo a partir del mapa dado.

[pic 6][pic 7][pic 8][pic 9]

[pic 10][pic 11][pic 12][pic 13][pic 14][pic 15][pic 16][pic 17][pic 18][pic 19][pic 20][pic 21]

A continuación, se irá formando o uniendo los vértices de paso a paso. Empezaremos con un grafo cíclico, el cual es un grafo que contiene por lo menos un ciclo, y seguiremos hasta tener todos los vértices integrados. Empezaremos con vértice A.

[pic 22][pic 23][pic 24][pic 25][pic 26][pic 27][pic 28][pic 29][pic 30][pic 31][pic 32][pic 33]

[pic 34]

[pic 35]

[pic 36]

[pic 37][pic 38][pic 39]

[pic 40][pic 41]

                [pic 42][pic 43]

[pic 44][pic 45]

[pic 46][pic 47][pic 48][pic 49]

[pic 50]

[pic 51][pic 52]

[pic 53][pic 54][pic 55]

[pic 56][pic 57][pic 58][pic 59]

[pic 60][pic 61]

[pic 62][pic 63][pic 64]

[pic 65][pic 66]

[pic 67][pic 68][pic 69][pic 70]

[pic 71][pic 72][pic 73]

[pic 74][pic 75][pic 76]

[pic 77][pic 78]

[pic 79][pic 80][pic 81][pic 82]

[pic 83][pic 84][pic 85]

[pic 86][pic 87][pic 88][pic 89]

[pic 90][pic 91]

[pic 92][pic 93][pic 94][pic 95]

[pic 96][pic 97][pic 98]

[pic 99][pic 100][pic 101][pic 102]

[pic 103][pic 104]

[pic 105]

[pic 106][pic 107][pic 108][pic 109]

[pic 110][pic 111][pic 112][pic 113][pic 114]

[pic 115][pic 116][pic 117]

[pic 118][pic 119]

[pic 120]

[pic 121][pic 122][pic 123][pic 124]

[pic 125][pic 126][pic 127][pic 128]

[pic 129][pic 130][pic 131][pic 132][pic 133]

[pic 134][pic 135]

[pic 136]

[pic 137][pic 138][pic 139][pic 140]

[pic 141][pic 142][pic 143][pic 144][pic 145]

[pic 146][pic 147][pic 148][pic 149]

[pic 150][pic 151]

[pic 152]

        [pic 153]

[pic 154][pic 155][pic 156]

[pic 157][pic 158][pic 159][pic 160][pic 161][pic 162]

...