Actividad No 3 - Subgrafos y subdigrafos (MON G2M)

Vista previa del material en texto

UNIVERSIDAD DE CÓRDOBA 
FACULTAD DE INGENIERÍAS 
Programa de Ingeniería de Sistemas 
Asignatura: TEORIA DE GRAFOS Semestre: IX Sede: Actividad No. 3 
Profesor: Jose Waldo de la Ossa Temática: Subgrafos y Subdigrafos 
Nombres 
 
1 | T e o r í a d e G r a f o s V e r . 4 . 2 2 
 
Consideraciones Generales 
 La fecha de presentación es el 19-04-2023. En grupo (3 personas). 
 Recuerde que debe imprimir la actividad, desarrollarla a mano (bien presentado) y 
entregarlo al inicio de la clase. Pero, antes de entregar, un integrante del grupo debe 
escanear todo el documento y subirlo a la plataforma. 
 
Parte 1 – Subgrafos 
1. Considere el siguiente grafo G = (V, A) donde: V = {0, 1, 2, 3, 4} y A = {(0,0), 
(0,1), (0,2), (1,2), (1,3), (3,4), (4,4)} 
a) Represente gráficamente el grafo G. 
b) Sea G’ = (V’, A’) donde V’ = {1, 2, 3} y A’ = {(1,2), (1,3), (2,3)}. Dibuje el 
grafo G’. ¿Es G’ un subgrafo de G? Justifique. 
c) Sea G’’ = (V’’, A’’) donde V’’ = {0, 1, 2} y A’’ = {(0,2), (0,1)}. Dibuje el grafo 
G’’. ¿Es G’’ un subgrafo de G? Justifique. 
 
2. Sea G el grafo no dirigido de la figura 1. 
 
 
Figura 1 
 
a) ¿Cuantos subgrafos conexos de G tienen cuatro vértices e incluyen un ciclo? Trace 
los subgrafos. 
b) Para el grafo G, sea e la arista {c, f}. Trace el subgrafo G – e. 
 
UNIVERSIDAD DE CÓRDOBA 
FACULTAD DE INGENIERÍAS 
Programa de Ingeniería de Sistemas 
Asignatura: TEORIA DE GRAFOS Semestre: IX Sede: Actividad No. 3 
Profesor: Jose Waldo de la Ossa Temática: Subgrafos y Subdigrafos 
Nombres 
 
2 | T e o r í a d e G r a f o s V e r . 4 . 2 2 
 
c) Sean e1, e2 las aristas {a, c}, {a, d}, respectivamente, del grafo G. Trace el siguiente 
subgrafo de G: (G - e1) - e2 
 
Parte 2 – Subdigrafos 
Sea G un grafo dígrafo. 
 
1. A partir del dígrafo anterior proponga un ejemplo en la cual se aplique cada uno de 
los siguientes conceptos. 
 
a) Subdigrafo 
b) Subdigrafo cobertor 
c) Vértices disyuntos 
d) Aristas disyuntas 
e) Supresión de vértice y de aristas