Scribd
Cargar
227 vistas4 páginas

Caminos y Circuitos en Grafos No Dirigidos

El documento contiene 7 preguntas sobre conceptos básicos de grafos como caminos, recorridos, caminos simples, circuitos y ciclos. Cada pregunta presenta un grafo y solicita identificar un ejemplo específico de uno de estos conceptos en el grafo dado, como un camino simple entre dos vértices o un ciclo.

Cargado por

Fernando
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 DOCX, PDF, TXT o lee en línea desde Scribd
227 vistas4 páginas

Caminos y Circuitos en Grafos No Dirigidos

El documento contiene 7 preguntas sobre conceptos básicos de grafos como caminos, recorridos, caminos simples, circuitos y ciclos. Cada pregunta presenta un grafo y solicita identificar un ejemplo específico de uno de estos conceptos en el grafo dado, como un camino simple entre dos vértices o un ciclo.

Cargado por

Fernando
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 DOCX, PDF, TXT o lee en línea desde Scribd

LOGICA

PREGUNTAS

1. Para el grafo de la siguiente figura determine:

A. Un camino de b a d que no sea recorrido

 (b,e,f,g,e,d)
B. Un recorrido b – d que no sea un camino simple

 (b,a,c,d)
C. Un camino simple de b a d

 (b,c,d)

D. Un camino cerrado de b a d que no sea un circuito

 (b,a,c
E. Un circuito de b a d que no sea un ciclo

 (b,a,c,d,e,b,c)
F. Un ciclo de b a d

 (b,e,d,c,b)

2. Para el grafo de la pregunta 1¿Cuántos caminos simples de b a f?


son 6 caminos simples
(b,a,c,d,e,g,f ) (b,a,c,d,e,f) (b,c,d,e,g,f) (b,e,g,f)(b,e,f)(b,c,d,e,f)

3. Cuantos camino simples diferentes existen entre los vértices a y f en el


grafo dado en la figura
LOGICA

Son 12 caminos simples que existen entre los vértices a y f

(a,d,c,b,g,b,e,f ) ( a,d,c,b,g,f) ( a,d,e,f) ( a,d,c,f) (a,h,e,d,c,b,g,f ) (a,h,e,f )


(a,h,g,b,c,f ) ( a,h,g,f) ( a,b,g,b,e,f) ( a,b,g,f) ( a,b,c,f) (a,b,c,d,e,f )

4. Sea G=( V,E) el grafo no dirigido de la presente figura ¿Cuántos


caminos simples existen en G de a a h?
¿Cuántos de ellos son de longitud 5

 Existen 9 caminos simples en G de a a h

(a,c,d,b ,g,h) (a,c,d,b,,g,e,f,h) (a,c,d,b,g,f,h) (a,c,b,g,f,h) (a,c,b,g,e,f,h)


(a,c,b,g,f,h)(a,b,g,e,f,h) (a,b,g,f,h) (a,b,g,h)

 Son 3 de longitud 5

5. La presente figura presenta un grafo no dirigido que representa una


sección de unos grandes almacenes. Los vértices indican el lugar donde
se localizan las cajas, las aristas indican los pasillos que hay entre ellas.
LOGICA

Los almacenes necesitan instalar un sistema de seguridad que concite


en colocar guardias (vestidos de civil) en cierta caja de manera que cada
cajero tenga un guardián en su lugar o que haya un solo pasillo entre
una caja con guardián y el cajero. Cual es el numero mínimo de guardias
necesarios?

6. En la figura que se muestra diga cual de las sucesiones de aristas


correspondientes a los siguientes ejercicios es :

a. Un camino
 (b,c,d,a,b,e,d,c,b)
b. Un camino simple
 (e, d,c,b)
c. -Un circuito
 (b,b)
d. Un ciclo
 (b,c,d,e,b,b)

7. En grafo
siguiente
determine:
LOGICA

a. Un camino de b a d que no sea recorido

 (b,a,c,b,d)
b. Un recorrido de b a d que no sea un camino simple

 (b,a,c,b,e,d)
c. Un camino simple de b a d

 (b,a,c,d)

d. Un camino cerrado de b b que no sea un circuito

 (b,,e,f,d,c,b)

e. Un circuito de b a b que sea ciclo

 (b,b)

También podría gustarte