Scribd
Cargar
144 vistas2 páginas

2 Act Rep Alg de Gra

Este documento presenta varios problemas relacionados con grafos. En la primera sección, se pide analizar las propiedades de un grafo dado y resolver preguntas sobre sus vértices, aristas, caminos y circuitos. La segunda sección describe un sistema de autopistas entre 7 ciudades y pide dibujar el grafo correspondiente, encontrar caminos entre ciudades y analizar las posibilidades de viajar por todas las autopistas.

Cargado por

FeernnaNdo Rh
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
144 vistas2 páginas

2 Act Rep Alg de Gra

Este documento presenta varios problemas relacionados con grafos. En la primera sección, se pide analizar las propiedades de un grafo dado y resolver preguntas sobre sus vértices, aristas, caminos y circuitos. La segunda sección describe un sistema de autopistas entre 7 ciudades y pide dibujar el grafo correspondiente, encontrar caminos entre ciudades y analizar las posibilidades de viajar por todas las autopistas.

Cargado por

FeernnaNdo Rh
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

En esta actividad, se pretende que primeramente definas algunos conceptos

básicos de la representación algebraica de las gráficas para resolver problemas,


una vez identificando estás definiciones podrás resolver las siguientes preguntas:

1. Sea el siguiente grafo G

a) ¿Es grafo simple?


b) ¿Es grafo K n ?
c) ¿Es grafo simple?
d) ¿Es grafo conexo?
e) ¿Es grafo plano? En caso de ser plano, ¿se cumple con la ecuación de Euler
A  L V  2
f) ¿Tiene un camino de Euler?
g) ¿Tiene un circuito de Euler?
h) ¿Tiene un circuito de Hamilton?
i) Encontrar:
 El conjunto de vértices (V )
 El conjunto de aristas (A)
 El conjunto de lazos L
 El conjunto de lados paralelos P
j) Encontrar la matriz de adyacencia y la matriz de incidencia.
k) ¿Cuál es la valencia de cada uno de los vértices?
l) Decir si los siguientes recorridos son caminos, camino simple, circuito,
circuito simple.
 (1,5,8,9,7,6,1,3)
 (5,8,4,10,10,7,6,5)
 (1,3,3,1)
 (4,10,9,7,6,5,1,3,8,4)
 (2,6,5,8,9,10)

2. Siete ciudades a, b, c, d , e, f y g están conectadas por un sistema de autopistas


como sigue:
(1) I-22 va de a a c , pasando por b;
(2) I-33 va de c a d , y entonces pasa por b y continua hacia f ;
(3) I-44 va de d por e hacía a ;
(4) I-55 va de f a b , pasando por g
(5) I-66 va de g a d
a) Use los vértices para las ciudades y las aristas dirigidas para los tramos de
autopista que las unen, y dibuje un grafo dirigido que modele esta situación.
b) Enumere los caminos simples de g a a
c) ¿Cuál es el menor número de segmentos de autopista que tendrían que
cerrarse para interrumpir el paso de b a d ?
d) Es posible salir de la ciudad c y regresar a ella, visitando una sola vez las
otras ciudades?
e) ¿Cuál es la respuesta de la parte ( d ) si no es necesario regresar a c ?
f) ¿Es posible comenzar en alguna ciudad y viajar por todas las autopistas
exactamente una vez? (Se permite visitar una ciudad más de una vez y no
es necesario regresar a la ciudad donde se inició el recorrido.)

También podría gustarte