Teoria De Grafos

Teoría de Graficas Entrevista 1
Profa. Virginia Haro Sánchez

Equipo 2
Integrantes:
Aguilar Macias Ivan
Antonio Jacinto Hugo
Luz Luz Antonio Erick de Jesús
Madrigal Ceballos Diana Janette
Ortiz García Alan Michael

Parte 1: Conexión
Ejercicio 1

Tómese el Grafo i (cargar en Algraf el fichero grafoi.txt), el cual modela el proyecto de líneas de metro para una ciudad. Se pide:a) Determinar el mínimo número de líneas de que consta el proyecto, así como el número de estaciones y túneles que hay en cada línea. ¿Hay zonas del recorrido que permitan hacer trayectos circulares, sin necesidad de tomar la misma línea en sentido inverso?
Numero de líneas: 2
Línea 1:
Número de estaciones: 25
Número de túneles: 42
Línea 2:
Número de estaciones: 25
Número de túneles:47

R = No. Porque por definición el grafo es un grafo simple, por lo cual el hecho de que este tenga un recorrido circular implicaría que fuera un multígrafo con aristas paralelas.

b) Determinar el mínimo número de túneles que se han de construir de entre los previstos para poder garantizar el servicio entre todas las estaciones. ¿Es única la manera de llevar a cabo este esquema de red deservicios mínimos? En caso negativo, dar más de una alternativa, y reseñar si hay algún tramo cuya construcción sea ineludible en cualquiera de los casos.
R= 3 túneles
Arista (V3, V38)
Arista (V40, V43)
Arista (V45, V1)

c) El ayuntamiento quiere llevar a cabo el proyecto de manera que se satisfagan las exigentes medidas de seguridad europeas, para lo cual es necesario queen caso de que eventualmente una (y sólo una) estación deba cerrarse debido a una emergencia (incendio, por ejemplo) el servicio de metro no se vea mermado en el resto de la ciudad. Determinar si el proyecto actual satisface esta condición, y en caso negativo, precisar cuál es el mayor número de zonas que en el peor de los casos podrían quedar incomunicadas en la red de metro. Hallar el menornúmero de tramos de metro que habría que añadir y entre qué estaciones para subsanar esta circunstancia, de manera que el proyecto sí pudiera ser homologado en Europa.
R=No, por que tiene vértices de corte.
Las zonas incomunicadas son 8

d) La Unión Europea otorga la calificación de máxima seguridad (lo que redunda en una financiación extra, mediante subvenciones especiales) si el metro no veafectado su servicio por la eventual clausura simultánea de 2 estaciones. Justificar si este proyecto, con las modificaciones del apartado anterior, obtendrá dicho galardón.
R=Si se obtiene el galardón, por que si se eliminan vértices de corte y aristas puente el si el sistema no se ve afectado si se llegara a cerrar una o hasta dos estaciones por lo tanto no queda incomunicada ninguna zona.Grafo original

Línea 1

Línea 2

Líneas juntas

Aristas puente

Tramos a añadir

Zonas incomunicadas

Vértices de corte

Tramos que faltan
Parte 2: Caminos y recorridos
Ejercicio 1

Un salto del caballo consiste en repartir las sílabas de una frase en los cuadros (llamados escaques en la jerga ajedrecística) de un tablero de ajedrez (donde entendemos por tablero cualquieresquema compuesto por escaques), de manera que siguiendo el movimiento del caballo de ajedrez se pueda leer la frase original, recorriendo en cierto orden todos los escaques sin repetir ninguno.
Se pretende diseñar un salto del caballo para las 20 sílabas de la frase Si eres capaz de leer esto, entonces te has equivocado, según el esquema de la Figura i adjunta en el archivo saltos.txt. Paraello, el grupo de trabajo debe crear y progresar sobre el grafo hi asociado al salto del caballo de la Figura i de saltos.txt, cuyos vértices son los 20 escaques y cuyas aristas relacionan escaques que son accesibles uno del otro por medio de un movimiento del caballo de ajedrez.
Recuérdese que un caballo en ajedrez puede realizar los siguientes movimientos básicos: desplazarse dos unidades...