Universidad del Quindío
Facultad de Ingeniería
Programa de Ingeniería de Sistemas y Computación
Taller 1 de Teoria de Grafos
R.A.1: Reconozco que un grafo es una estructura matemática que permite representar problemas en
el desarrollo de procesos de modelación de manera gráfica, involucrando la identificación de nodos y
aristas, con el fin de representar las relaciones entre elementos de un conjunto que permitan aplicar
técnicas de análisis para comprender y resolver situaciones complejas.
1. Dados los siguientes grafos, determinar el conjunto de vértices, aristas, la función de
incidencia de cada arista, además nombrar sus vértices adyacentes, vértices aislados, aristas
paralelas, aristas adyacentes, bucles y aristas incidentes a un vértice.
2. El calendario de los aficionados al fútbol marca una fecha importante pasado mañana. Un
equipo de la Policía Nacional se encargará de velar por la seguridad de los aficionados, que
decide restringir el tráfico en las calles cercanas al perímetro de seguridad alrededor de
Bernabéu, tal y como se muestra en el siguiente grafo.
Contesta a las siguientes preguntas:
a. ¿de qué tipo de grafo se trata? Justifica tu respuesta
b. Escribe un camino simple y otro camino.
c. Escribe un circuito
Universidad del Quindío
Facultad de Ingeniería
Programa de Ingeniería de Sistemas y Computación
Taller 1 de Teoria de Grafos
3. Inventa un grafo dirigido cualquiera con las siguientes características:
a. Presenta un total de cinco vértices
b. Un vértice tiene grado de emisión 2 y grado de recepción 1.
c. Un vértice presenta un bucle
d. Hay un vértice aislado
4. Indica el grado de emisión y recepción de cada vértice en los siguientes grafos:
Universidad del Quindío
Facultad de Ingeniería
Programa de Ingeniería de Sistemas y Computación
Taller 1 de Teoria de Grafos
5. Determine que graficas en los ejercicios a y b son bipartidas. Si la gráfica es bipartida,
especifique los conjuntos ajenos de vértices:
6. En la siguiente gráfica los vértices representan ciudades y los números sobre las aristas son
los costos de construir las carreteras indicadas. Encuentra el sistema de carreteras menos
costos que conecte todas las ciudades.
7. Determinar si los siguientes grafos son isomorfos. Si lo son realice la relación entre los
conjuntos.
Universidad del Quindío
Facultad de Ingeniería
Programa de Ingeniería de Sistemas y Computación
Taller 1 de Teoria de Grafos
8. Dados los siguientes grafos, indicar de que tipo se tratan, hallar el grado de cada vértice y su
grado total y obtener su matriz de adyacencia, la lista de adyacencia y su matriz de incidencia
Universidad del Quindío
Facultad de Ingeniería
Programa de Ingeniería de Sistemas y Computación
Taller 1 de Teoria de Grafos
9. Del ejercicio anterior, calcular la cantidad de caminos diferentes para cada grafo, según las
condiciones dadas:
a. Longitud 3, desde el vértice 1 al 5
b. Longitud 2, desde el vértice a al d
c. Longitud 4, desde el vértice 1 al 3
10. Un grafo simple tiene 45 aristas y es completo. ¿Cuántos vértices tiene?
11. Un grafo simple tiene 10 vértices y 15 aristas. ¿Cuál es el grado medio de sus vértices?
12. Un grafo dirigido con 5 vértices no tiene lazos (aristas que van de un nodo a sí mismo). ¿Cuál
es el número máximo de aristas que puede tener?
13. Dado un grafo no dirigido ¿Cuál es la cantidad total de vértices de un grafo que tiene 3
vértices de grado 4, 2 de grado 3, 4 de grado 2 y el resto de grado 1?
14. En un grafo no dirigido ¿Cuál es la cantidad de vértices que tiene, si el máximo de sus aristas
es 15?
15. Dadas las siguientes matrices de adyacencia, dibujar los grafos que representan, e indicar de
que tipo se tratan. Luego hallar la matriz de incidencia.
16. Dado el siguiente grafo determinar la matriz de adyacencia y calcular el camino de longitud 5,
desde el vértice A al F.
Universidad del Quindío
Facultad de Ingeniería
Programa de Ingeniería de Sistemas y Computación
Taller 1 de Teoria de Grafos
17. 𝑆𝑒𝑎 𝐴 = {1, 2, 3, 4} 𝑦 𝑅 = {(1, 1), (1, 2), (2, 2), (3, 3), (3, 2), (4, 4)} una relación definida en A.
¿Es reflexiva? Dibujar el dígrafo y escribir la matriz de la relación.
18. Sea 𝐴 = {1, 2, 3, 4} 𝑦 𝑅 = {(1, 1), (1, 2), (2, 1), (2, 3), (3, 2), (3, 3)} una relación definida en A.
¿Es simétrica? Dibujar el dígrafo y escribir la matriz de la relación
19. Sea 𝐴 = {1, 2, 3, 4} 𝑦 𝑅 = {(1, 2), (1, 4), (2, 3), (2, 4), (3, 1), (4, 3)} una relación definida en A.
¿Es asimétrica? Dibujar el dígrafo y escribir la matriz de la relación
20. Sea 𝐴 = {1, 2, 3, 4} 𝑦 𝑅 = {(1, 2), (1, 3), (1, 4), (2, 3)} una relación definida sobre A. ¿Es
transitiva? Dibujar el dígrafo y escribir la matriz de la relación.
21. Sea 𝑅 = {(𝑎, 𝑏), (𝑎, 𝑐), (𝑏, 𝑐), (𝑎, 𝑎), (𝑏, 𝑏)} una relación definida en 𝐴 = {𝑎, 𝑏, 𝑐}. Hay que decir
que propiedades tiene, dibujar un dígrafo de esta y escribir su matriz.
22. Escribir la relación cuyos dígrafos son los de la figura siguiente, como conjunto de pares
ordenados.
Universidad del Quindío
Facultad de Ingeniería
Programa de Ingeniería de Sistemas y Computación
Taller 1 de Teoria de Grafos
23. Sea 𝑎 = {1,2,3,4,5} 𝑦 𝑹 la relación definida para 𝑎, 𝑏 ∈ 𝐴 por:
a. R b si y solo si 𝑎 < 𝑏 + 2
b. Escribe los pares que forman la relación R y que propiedad cumple
c. Calcula la relación 𝑹−1
d. Calcula 𝑹𝒄
24. Sea 𝐴 = {1,2,3,4,5,6} y consideremos las relaciones siguientes en A:
a. Para 𝑎, 𝑏 ∈ 𝐴 𝑎 𝑅 𝑏 𝑠𝑖 𝑦 𝑠𝑜𝑙𝑜 𝑠𝑖 𝑎 × 𝑏 = 6
b. Para 𝑎, 𝑏 ∈ 𝐴 𝑎 𝑹 𝑏 𝑠𝑖 𝑦 𝑠𝑜𝑙𝑜 𝑠𝑖 3𝑎 < 2𝑏
Par cada una de las relaciones anteriores, escribe los pares que forman la relación R y estudia sus
propiedades.
25. Prueba que la siguiente relación R definida en 𝐴 = {1,2,3,4,5} es de equivalencia.
𝑅 = {(1, 1)(1, 2)(1, 3)(2, 1)(2, 2)(3, 1)(2, 3)(3, 3)(4, 4)(3, 2)(5, 5)}
26. Sea A el conjunto de los enteros positivos divisores de 48 y R la relación en A: 𝑎 𝑹 𝑏 𝑠𝑖 𝑦 𝑠𝑜𝑙𝑜
𝑠𝑖 𝑏 𝑒𝑠 𝑚𝑢𝑙𝑡𝑖𝑝𝑙𝑜 𝑑𝑒 𝑎.
a. Escribir su matriz de relación
27. Sea 𝐴 = {1,2,3,4,5} y sea R definida en A: a R b si y solo si a divide a (𝑎 − 𝑏) (con residuo
cero). Establecer la matriz de relación y realice el grafo.
28. Sea 𝐴 = {1,2,3,4,5} y sea R definida en A: a R b si y solo si 3 divide a (𝑎 + 𝑏) (con residuo
cero). Establecer la matriz de relación y realice el grafo.
Universidad del Quindío
Facultad de Ingeniería
Programa de Ingeniería de Sistemas y Computación
Taller 1 de Teoria de Grafos
29. Sea 𝐴 = {1,2,3,4,5, 6} y sea R definida en A: a R b si y solo si 4 divide a (𝑎 − 𝑏) (con residuo
cero). Establecer la matriz de relación.
30. De las relaciones del ejercicio 22 y 23, realizar:
a. La unión entre R1 y R2
b. la intersección entre R1 y R2
c. el complemento de R2
Escribir sus respectivas matrices
31. Sea 𝐴 = {1,2,3,4,5} y sea R y S definidas en A: a R b si y solo si 𝑎 + 𝑏 = 7 y a S b si y solo
si 𝑎 + 𝑏 ≤ 4
a. La unión entre R y S
b. la intersección entre R y S
c. el complemento de S
d. la diferencia de R-S
determinar los pares ordenados, establecer cada una de las matrices y realizar el grafo
32. Sean 𝐴 = {1, 2, 3}, 𝐵 = {2, 4, 6, 8} 𝐶 = {𝑠, 𝑡, 𝑢} y sean 𝑹 =
{(1, 2), (1, 6), (2, 4), (3, 4), (3, 6), (3, 8)} 𝑦 𝑺 = {(2, 𝑢), (4, 𝑠), (4, 𝑡), (6, 𝑡), (8, 𝑢)}. Hallar la
compuesta.
33. Sean 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑}, 𝐵 = {𝑠, 𝑡, 𝑢, 𝑣} 𝐶 = {1, 2, 3, 4, 5} y 𝑠𝑒𝑎𝑛 𝑹 = {(𝑎, 𝑠), (𝑎, 𝑡), (𝑐, 𝑣), (𝑑, 𝑢)} 𝑦
𝑺 = {(𝑠, 2), (𝑡, 1), (𝑡, 4), (𝑢, 3)}. Hallar la compuesta
34. Sean 𝐵 = 𝐴 = {1,2,4,7,8} y sea 𝑅: 𝐴 → 𝐵 tal que 𝑎𝑅𝑏 𝑠𝑖 𝑎 ≥ 𝑏.
a. ¿Cuáles son los elementos de R?.
b. Encontrar MR y GR.
c. Mostrar que se trata de una relación de orden, probando que R es reflexiva, antisimétrica y
transitiva.
35. Sean 𝐴 = 𝐵 = {1, 2, 3, 6, 8} y 𝑅: 𝐴 → 𝐵 donde 𝑎𝑅𝑏 si y solo si b es divisible entre a.
a. Encontrar los elementos de R.
b. Encontrar GR y MR.
c. Mostrar que R es una relación de orden
