Scribd
Cargar
2 vistas3 páginas

Actividades de Grafos en Matemática Discreta

El documento presenta un conjunto de actividades relacionadas con el análisis de grafos, incluyendo la identificación de caminos, circuitos y recorridos en un grafo específico. Se requiere calcular distancias entre vértices, modelar situaciones con grafos dirigidos y determinar propiedades de conectividad entre ciudades. Además, se solicita la construcción de diversas estructuras de grafos y sus matrices de adyacencia e incidencia.

Cargado por

cambion555
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
2 vistas3 páginas

Actividades de Grafos en Matemática Discreta

El documento presenta un conjunto de actividades relacionadas con el análisis de grafos, incluyendo la identificación de caminos, circuitos y recorridos en un grafo específico. Se requiere calcular distancias entre vértices, modelar situaciones con grafos dirigidos y determinar propiedades de conectividad entre ciudades. Además, se solicita la construcción de diversas estructuras de grafos y sus matrices de adyacencia e incidencia.

Cargado por

cambion555
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

ESCUELA SUPERIOR DE INFORMÁTICA – TECNOLOGO EN INFORMÁTICA

CURSO: MATEMÁTICA DISCRETA Y LÓGICA 2

PROFESOR: ING. RAMÓN SALINA

REPARTIDO 1 GRAFOS

Actividad 1:
Considera el grafo de la figura adjunta y las siguientes listas de vértices:
1) b, c, b, e, a 2) b, d, b, c, e, d 3) e, b, a, d, b, e 4) c, b, d, a, e, c
¿Cuáles de ellas forman un camino?

¿Qué caminos son simples? ¿Cuáles son circuitos?


¿Qué longitud tienen los que son caminos?

Actividad 2:
Observa el grafo de la figura adjunta. Determina, si es posible:
a) Un camino b - e que no sea un recorrido.
b) Un recorrido b - c que no sea un camino simple.
c) Un ciclo en e.
d) Un circuito en b que no sea un ciclo.
e) Un ciclo en d.
Actividad 3:
Para el grafo de la actividad anterior:
¿Cuántos recorridos de longitud menor a 4 existen desde a hasta f?

Actividad 4:
Teniendo en cuenta el grafo G de la figura adjunta, calcula la distancia del vértice h a
cada uno de los restantes vértices de G. Nota: se denomina distancia entre dos vértices,
a la longitud más pequeña que existe entre éstos.

Actividad 5:
Siete ciudades a, b, c, d, e, f y g, están conectadas por un sistema de rutas como sigue:
La ruta 1, va de la ciudad a a la c, pasando por la ciudad b. La ruta 2, va de c a d, pasa
por b y llega a f. La ruta 3, va de d hacia a, pasando por e. La ruta 4, va de f a b, pasando
por g. La ruta 5, va de g a d. a) Dibuja un grafo dirigido que modele esta situación,
utilizando como vértices, las ciudades, y como aristas dirigidas, los tramos de rutas que
las unen.
b) Describe los caminos simples que existen desde g hasta a.
c) ¿Cuál es el menor número de tramos de ruta que tendrían que cerrarse para
interrumpir el paso de la ciudad b a la ciudad 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 la ciudad c?
f) ¿Es posible comenzar un viaje en alguna ciudad y recorrer todas las rutas exactamente
una vez? (Se permite visitar a las ciudades más de una vez, y no es necesario regresar a
la ciudad donde se inició el viaje)
Actividad 6:
Determine las matrices de adyacencia e incidencia del grafo adjunto en la figura:

Actividad 7:
Construye: a) K3; b) k*5; c) k3,3; d) k3,3 completo

También podría gustarte