Actividad No 2 - Problemas (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 Horario: Actividad No. 2 
Profesor: Jose Waldo de la Ossa Temática: Conceptos Básicos: Problemas, grafos bipartitos, digrafos 
Nombres 
 
1 | T e o r í a d e G r a f o s V e r . 4 . 2 3 
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 – Problemas (Valor 3 puntos) 
1. Una compañía de autopistas ha contratado a una empresa de seguridad para que patrulle la red 
de autopistas cuyo mapa está esquematizado en el siguiente grafo: 
 
 
La empresa de seguridad quiere realizar el 
servicio con un solo vehículo y quiere determinar 
la existencia de un recorrido de manera que se 
vigilen los tramos (aristas) de la autopista una 
única vez. ¿Cuál es ese recorrido? ¿Longitud del 
camino? 
 
 
2. Un grafo conexo con 21 aristas, tiene 7 vértices de grado 1, 3 de grado 2, 7 de grado 3, y el 
resto de grado 4. ¿Cuántos vértices debe tener? Utilice el teorema de la suma de los grados. 
 
3. Un departamento de una empresa tiene establecidas dos redes locales de comunicación distintas 
entre sus ocho terminales. Las líneas de conexión de cada red están esquematizadas en los 
siguientes grafos (RED I y RED II). Comprobar si los grafos de las redes son bipartitos y 
encontrar un emparejamiento de los conjuntos disjuntos para el mismo. 
 
 
 
UNIVERSIDAD DE CÓRDOBA 
FACULTAD DE INGENIERÍAS 
Programa de Ingeniería de Sistemas 
Asignatura: TEORIA DE GRAFOS Semestre: IX Horario: Actividad No. 2 
Profesor: Jose Waldo de la Ossa Temática: Conceptos Básicos: Problemas, grafos bipartitos, digrafos 
Nombres 
 
2 | T e o r í a d e G r a f o s V e r . 4 . 2 3 
 
 
 
 
 
Parte 2 (Valor 2 puntos) 
1. Dibujar el dígrafo a partir de la siguiente información. 
Sea V = {V1, V2, V3, V4, V5, V6}, A = {ai, i ∈ N, 1 ≤ i ≤ 10}. La función de incidencia 𝜑(ai)= 
(Vi, Vj) está definida por: 
 
𝜑(a1) = (V1, V2); 𝜑(a2) = (V2, V1); 𝜑(a3) = (V2, V6); 𝜑(a4) = (V2, V5); 𝜑(a5) = (V2, 
V3); 𝜑(a6) = (V3, V5); 𝜑(a7) = (V3, V5); 𝜑(a8) = (V3, V5); 𝜑(a9) = (V2, V2); 𝜑(a10) 
= (V6, V6); 
 
2. Calcule los grados para cada vértice del digrafo anterior y aplique el teorema de la suma de 
grados. 
3. Encuentre las adyacencias para cada uno de los (Vi) del dígrafo. 
4. Identifique las aristas paralelas, en caso de que existan.