TEORIA DE GRAFOS
Enviado por furto • 10 de Julio de 2020 • Apuntes • 1.274 Palabras (6 Páginas) • 148 Visitas
TAREA 1 – GRAFOS
Nombres de los integrantes:
- Carla Gonzales
- Karen Vallejo
- Peter Martinez
- Gianella Damián
Luego de construir cada grafo, exprese el conjunto de nodos N, el conjunto de arcos o aristas A e indique la relación R.
- Si construimos un grafo representando la secuencia de requisitos para llevar el curso de Seminario de Tesis, ¿el grafo será orientado o no orientado? Representémoslo. Indicar la relación.
G1[pic 3]
[pic 4]
[pic 5]
El Grafo G1 es orientado
N= {1, 2, 3, 4}
A= {(1,4), (2,4), (3,4)}
El grafo G1 es anti reflexiva y anti simétrica.
- 1R4 Anti simétrica
- 2R4 Anti simétrica
- 3R4 Anti simétrica
- ¿Si el grafo a diseñar representa la comunicación entre todos los participantes del curso de Teoría de Grafos y Programación Entera, el grafo será orientado o no orientado? Diseñarlo. Expresar la relación.
G2
[pic 6]
Es un grafo no orientado
N= {a, b, c, d, e}
A= {[a, b], [a, c], [a, d], [a, e], [b, a], [b, c], [b, d], [b, e], [c, a], [c, b], [c, d], [c, e],
[d, a], [d, b], [d, c], [d, e], [e, a], [e, b], [e, c], [e, d]}
El grafo G2 presenta una relación anti reflexiva, transitiva y de simetría
aRb, bRc aRc Relación de transitividad[pic 7]
aRc, cRe aRe Relación de transitividad[pic 8]
dRe, eRc dRc Relación de transitividad[pic 9]
eRb, bRd eRd Relación de transitividad[pic 10]
- Si nos interesa representar mediante un grafo el recorrido que se puede hacer con un vehículo por el centro histórico de Lima, ¿qué tipo de grafo será: orientado, no orientado o mixto? Indicar la relación. Representar el grafo.
El grafo es orientado ya que el camino de un lugar al otro es de un sentido
- Alameda Chabuca Granda
- Convento santo domingo
- Iglesia santa rosa
- Iglesia las nazarenas
- Palacio de gobierno
- Plaza de armas
- Iglesia la merced
- Plaza san Martín
- Catedral de lima
- Basílica de san francisco
- Iglesia san pedro
[pic 11][pic 12][pic 13]
[pic 14][pic 15][pic 16][pic 17][pic 18][pic 19][pic 20]
[pic 21][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]
- Si una persona hace un recorrido que se inicia en el Parque Universitario, pase por la plaza San Martín, después pase por la plaza 2 de mayo y termine en la Av. Colonial, Considerando solo los puntos mencionados, construir un grafo que represente las relaciones entre ellos. Defina la relación correspondiente. Determine si esas relaciones son orientadas o no orientadas y establezca en qué nodos es posible considerar bucles.
*Parque Universitario = a
*Plaza San Martin = b
*Plaza 2 de mayo = c
*Av. Colonial = d
N =[pic 60]
A=[pic 61]
G4
[pic 62]
aRa , bRb, cRc …….relación reflexiva
aRb, bRc, cRd ……..relación de anti simetría
Tipo de relación: Relación de anti simetría
Grafo orientado.
Los posibles nodos con bucles son “a”, “b” y “c”; debido a que al ser parques se puede dar vueltas y vueltas alrededor de las plazas, siempre regresando al mismo lugar.
- Si deseamos representar mediante un grafo la relación que existe en una empresa determinada: en el primer nivel está el gerente de personal, en el segundo nivel están el jefe de relaciones humanas y el jefe de bienestar de personal, en el tercer nivel están el subjefe de relaciones humanas 1 y subjefe de relaciones humanas 2, así como el subjefe de bienestar de persona 1 y el subjefe de bienestar de personal 2. Si la relación que se desea representar es R: “i es jefe de j”, represente mediante el grafo adecuado.[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]
N= {a, b, c, d, e, f, g}
A= {[a, b], [a, c],[b.d],[b.e],[c, f],[c.g]}
El grafo es orientado
aRb, aRc, bRd, bRe, cRf, cRg presentan una relación anti simétrica
- Expresar un grafo que represente con qué países mantiene el Perú Tratados de Libre Comercio. Indique si el grafo es orientado o no orientado y cuál es la relación.
[pic 78]
a: Perú
b: Canadá[pic 79][pic 80][pic 81]
...