Actividad No 1 - Conceptos Basicos (MON G2M)

Vista previa del material en texto

UNIVERSIDAD DE CÓRDOBA 
FACULTAD DE INGENIERÍAS 
Programa de Ingeniería de Sistemas 
Asignatura: TEORÍA DE GRAFOS Semestre: IX Horario: Actividad No. 1 
Profesor: Jose Waldo de la Ossa Temática: Conceptos Básicos 
 
1 | T e o r í a d e G r a f o s V e r . 4 . 2 3 
Consideraciones Generales 
 La presente actividad debe ser desarrollada y entregada en grupo (3 personas). 
FECHA ENTREGA MIÉRCOLES 12 DE ABRIL AL INICIO DE LA CLASE. 
 Debe imprimir el taller y desarrollar a mano. Pero, antes de entregar, un integrante 
del grupo debe escanear todo el documento y subirlo a la plataforma. 
 
 
Parte 1 – Ejercicios 
1. Represente el grafo no dirigido G= (V, A) donde: V = {1, 2, 3, 4, 5, 6}; A = {(1,2), (1,3), 
(1,5), (3,3), (3,4), (4,3), (4,5), (5,6)} 
 
2. Construir un grafo conexo no dirigido de 8 vértices en los que cada uno tenga los siguientes 
grados: 1,2,2,2,3,3,3,4. 
 
3. ¿Cuántas aristas tiene un grafo conexo si sus vértices tienen los siguientes grados: 
4,3,3,2,2? Dibujarlo. 
 
4. Dado el siguiente grafo G escribir explícitamente el conjunto de vértices y el conjunto de 
aristas de G. Indique el orden del grafo. 
 
 
 
5. Indicar cuál de los siguientes grafos corresponde a un multigrafo, a un digrafo, a un 
árbol, a un grafo ponderado y a un grafo completo: 
 
 
 
UNIVERSIDAD DE CÓRDOBA 
FACULTAD DE INGENIERÍAS 
Programa de Ingeniería de Sistemas 
Asignatura: TEORÍA DE GRAFOS Semestre: IX Horario: Actividad No. 1 
Profesor: Jose Waldo de la Ossa Temática: Conceptos Básicos 
 
2 | T e o r í a d e G r a f o s V e r . 4 . 2 3 
 
 
 
 
6. Dado el siguiente grafo ponderado G no dirigido: 
 
a) Definir el grado de cada uno de los vértices. 
Aplique el teorema de los grados. 
b) Definir dos caminos simples de longitud 
100 y 130 respectivamente. 
c) Definir un camino cerrado de longitud 60. 
 
 
 
 
7. Dado el siguiente grafo g, encontrar en él: 
 
 
 
 
 
 
 
 
 
a) Un camino que conecta a v1 y v4. 
b) Un camino simple de longitud 5 entre v1 y v4. 
c) Un camino de longitud 6 entre v1 y v4. 
d) Un camino cerrado con origen en v4 y de longitud 6.