MATEMÁTICAS DISCRETAS
CÓDIGO: 204041
Unidad 3 - Tarea 3 – Grafos y Árboles
Presentado al tutor (a):
Escriba aquí los nombres y apellidos del tutor (Tutor)
Entregado por el (la) estudiante:
Escriba aquí sus nombres y Apellidos (Estudiante)
Grupo: 204041_XX
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA - UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍA E INGENIERÍA
FECHA
CIUDAD
1
INTRODUCCIÓN
En esta actividad, se profundiza en la teoría de grafos y árboles, elementos fundamentales
en matemáticas discretas y ciencias de la computación. El primer ejercicio requiere
representar gráficamente los grafos E y F, identificando sus conjuntos de nodos y aristas, y
calculando el grado y paridad de cada vértice en el grafo E, así como el grado total de este
grafo. Para el grafo F, se elaborarán las matrices de incidencia y adyacencia, que permiten
comprender mejor las conexiones entre sus nodos.
En el segundo ejercicio, se explora la teoría de grafos aplicada a las redes sociales,
analizando cómo los nodos representan usuarios y las aristas simbolizan las interacciones
entre ellos. Este enfoque permite visualizar cómo los grafos pueden modelar redes
complejas y reflejar las conexiones en plataformas sociales.
El tercer ejercicio se enfoca en la teoría de árboles, donde se trabaja con un árbol específico
definido por un conjunto de aristas. Aquí, se realizarán tareas como la representación
gráfica del árbol, la construcción de las matrices de adyacencia e incidencia, y se ejecutará
el recorrido en preorden, un método útil para entender la estructura jerárquica y las
relaciones en un árbol. Estos ejercicios nos ofrecen una visión completa de cómo los grafos
y árboles se aplican en distintos contextos y facilitan la representación estructurada de
relaciones complejas.
2
Desarrollo de los ejercicios
Literal seleccionado: C
Ejercicio 1. Enunciado del ejercicio.
Teoría de grafos.
Represente gráficamente los grafos dados y responda las preguntas.
Grafo E = {(2, 3), (2, 4), (3, 4), (3, 7), (4, 5), (4, 6), (4, 7), (6, 7), (7, 8)}
Grafo F = {{r, s}, {t, u}, {r, r}, {u, t}, {t, t}}
Determine:
a. Conjunto de nodos de cada grafo
b. Conjunto de aristas de cada grafo
c. Grado y paridad de cada vértice del grafo E
d. Grado del grafo E
e. Matrices de incidencia y adyacencia del grafo F
Desarrollo del ejercicio 1:
Grafo E
1. Teoría de grafos
Grafo E:
Conjunto de aristas:
(2,3),(2,4),(3,4),(3,7),(4,5),(4,6),(4,7),(6,7),(7,8)
a. Conjunto de nodos de Grafo E
Para el Grafo E, los nodos son los puntos que forman parte de las aristas.
• Nodos de Grafo E:
3
{2,3,4,5,6,7,8}
b. Conjunto de aristas de Grafo E
• Aristas de Grafo E:
{(2,3),(2,4),(3,4),(3,7),(4,5),(4,6),(4,7),(6,7),(7,8)}
c. Grado y paridad de cada vértice del Grafo E
Calculamos el grado de cada vértice (nodo) contando el número de aristas que llegan a él:
Nodo 2: grado 2 (aristas con 3 y 4), par (2 conexiones).
Nodo 3: grado 3 (aristas con 2, 4, y 7), impar (3 conexiones).
Nodo 4: grado 4 (aristas con 2, 3, 5, y 6), par (4 conexiones).
Nodo 5: grado 1 (arista con 4), impar.
Nodo 6: grado 2 (aristas con 4 y 7), par.
Nodo 7: grado 4 (aristas con 3, 4, 6, y 8), par.
Nodo 8: grado 1 (arista con 7), impar.
d. Grado del Grafo E
El grado total del grafo es la suma de los grados de todos sus vértices:
Grado total:
2+3+4+1+2+4+1=18
Grafo F:
Conjunto de aristas: {(r,s),(t,u),(r,r),(u,t),(t,t)}
a. Conjunto de nodos de Grafo F
• Nodos de Grafo F: {r,s,t,u}
b. Conjunto de aristas de Grafo F
• Aristas de Grafo F: {(r,s),(t,u),(r,r),(u,t),(t,t)}
c. Grado y paridad de cada vértice del Grafo F
Nodo r: grado 2 (conexiones: (r,s),(r,r)(r, s), (r, r)(r,s),(r,r)), par.
Nodo s: grado 1 (conexión: (r,s)(r, s)(r,s)), impar.
Nodo t: grado 3 (conexiones: (t,u),(u,t),(t,t)(t, u), (u, t), (t, t)(t,u),(u,t),(t,t)), impar.
Nodo u: grado 2 (conexiones: (t,u),(u,t)(t, u), (u, t)(t,u),(u,t)), par.
d. Matrices de incidencia y adyacencia del Grafo F
4
1. Matriz de incidencia: cada columna representa una arista, y cada fila, un nodo. El valor es 1 si el nodo participa
en la arista.
Nodos: r,s,t,u
Aristas: (r,s),(t,u),(r,r),(u,t),(t,t)
Matriz de incidencia:
1 0 1 0 0
1 0 0 0 0
[ ]
0 1 0 1 1
0 1 0 1 0
2. Matriz de adyacencia: indica si existe conexión entre dos nodos.
1 1 0 0
1 0 0 0
[ ]
0 0 1 1
0 0 1 0
Ejercicio 2. Enunciado del ejercicio.
Teoría de grafos. (Sustentar mediante un vídeo) Los grafos pueden ser utilizados
para modelar y resolver problemas en una variedad de dominios,
proporcionando una manera clara y estructurada de representar relaciones y
conexiones complejas. Con un ejemplo particular, explique cómo, las redes
sociales, pueden ser descritas mediante la teoría de grafos.
Desarrollo del ejercicio 2:
Teoría de grafos: Ejemplo de redes sociales
En redes sociales, cada persona es un nodo, y la amistad o conexión entre dos personas es una
arista. Este modelo permite identificar comunidades, evaluar la influencia de usuarios, y
analizar cómo se propagan informaciones o tendencias.
Enlace del video del Ejercicio 2:
2. Teoría de grafos: Ejemplo de redes sociales
Ejemplo de explicación en vídeo:
Ejercicio 3: Enunciado del ejercicio.
Teoría de árboles.
Con el árbol cuyas aristas son: 1-2, 2-3, 2-4,2-5,2-6,3-7,7-8,7-9,8-10
Realice lo solicitado:
a. Dibujar el árbol
5
b. Encontrar la matriz de adyacencia
c. Encontrar la matriz de incidencia
d. Escribir el recorrido preorden
Desarrollo del Ejercicio 3:
Teoría de árboles
Árbol con aristas: 1−2,2−3,2−4,2−5,2−6,3−7,7−8,7−9,8−10
a. Dibujo del árbol
b. Matriz de adyacencia
Nodos: 1,2,3,4,5,6,7,8,9,10
Matriz de adyacencia:
6
0 1 0 0 0 0 0 0 0 0
1 0 1 1 1 1 0 0 0 0
0 1 0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 1 0
0 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 1 0 0 0
[0 0 0 0 0 0 0 1 0 0]
b. Matriz de incidencia
Aristas: 1−2,2−3,2−4,2−5,2−6,3−7,7−8,7−9,8−10
Matriz de incidencia:
1 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0
0 1 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 1 0
[0 0 0 0 0 0 0 0 1 ]
d. Recorrido preorden
1, 2, 3, 7, 8, 10, 9, 4, 5, 6
Ejercicio 4: Participación Evento Académico.
Participación evento.
Ejercicio de la participación asignada a un evento académico:
conferencia, charla, taller, congreso o workshop nacional o
internacional. La participación puede ser sincrónica o asincrónica. El
estudiante debe dejar evidencia de la participación mediante un
informe que contenga:
• Nombre del evento.
• Nombre del(los) conferencista(s)
• Objetivo de la conferencia.
Informe del Ejercicio 4:
• Nombre del evento:
7
Día 2 Matemáticas Applets de GeoGebra en la resolución de problemas
de cálculo – 4to Workshop de ciencias básicas 2024.
• Nombre del(los) conferencista(s):
Andrés Felipe Ramírez y Daniel Steven Moran
• Objetivo de la conferencia:
Examinar y descubrir cómo los Applets de GeoGebra contribuyen a
optimizar y simplificar el proceso de enseñanza y aprendizaje en temas
relacionados con los cálculos matemáticos. Estas herramientas
proporcionan una comprensión más clara y dinámica de conceptos
complejos, favoreciendo la resolución eficiente de problemas,
incentivando la participación activa de los estudiantes y fortaleciendo
sus habilidades analíticas dentro del ámbito del cálculo.
• Resumen del aprendizaje obtenido, un escrito entre 200 y 300 palabras.):
En el evento se abordaron estrategias innovadoras para el aprendizaje
del cálculo matemático mediante el uso de Applets de GeoGebra. Este
enfoque práctico permitió a los estudiantes participar de manera activa
en el desarrollo de ejercicios y ejemplos, promoviendo una interacción
dinámica que favorece la comprensión de conceptos complejos. Una de
las principales ventajas destacadas fue la capacidad de los Applets para
experimentar con variables y observar cómo los cambios impactan en
gráficos y funciones, lo que refuerza una comprensión más intuitiva y
profunda.
El uso de GeoGebra marca una diferencia significativa frente a los
métodos tradicionales, ya que facilita la resolución de problemas al
ofrecer representaciones visuales y manipulaciones interactivas en
tiempo real. Esto permite a los estudiantes comprobar su razonamiento
de manera inmediata y explorar diversas estrategias de solución. La
conferencia subrayó que esta herramienta no solo fomenta un
aprendizaje autónomo y activo, sino que también mejora las habilidades
analíticas al involucrar a los estudiantes en procesos exploratorios que
fortalecen su confianza para abordar problemas matemáticos.
Además, se resaltó el valor pedagógico de GeoGebra como recurso clave
tanto para docentes como para estudiantes. Los Applets se presentan
como una manera efectiva y atractiva de ilustrar conceptos complejos,
optimizando el proceso de enseñanza y haciendo más accesible el
aprendizaje. En resumen, el uso de GeoGebra en el aula no solo mejora
la comprensión de los conceptos de cálculo, sino que también desarrolla
en los estudiantes habilidades críticas para resolver problemas de
manera independiente y eficaz.
8
Conclusiones
En conclusión, el desarrollo de esta actividad ha permitido explorar de manera detallada
conceptos fundamentales de la teoría de grafos y árboles, aplicándolos en representaciones
gráficas y cálculos específicos que destacan su utilidad en diversos contextos. A través del
análisis de los grafos E y F, se ha podido observar cómo los nodos y aristas representan
interacciones y relaciones entre elementos, lo cual tiene un impacto directo en áreas como
redes sociales y sistemas de información.
La creación de las matrices de incidencia y adyacencia para el grafo F ha facilitado una
comprensión más estructurada de sus conexiones internas, mostrando cómo estas
herramientas matemáticas sirven para modelar y analizar interacciones complejas. Además,
el ejercicio práctico de representación de un árbol específico, junto con los recorridos en
preorden, refuerza la utilidad de los árboles en la organización y clasificación de datos
jerárquicos, comúnmente aplicados en algoritmos de búsqueda y organización de
información.
Finalmente, el ejercicio de aplicar los grafos a un caso de redes sociales ha mostrado cómo
estas estructuras matemáticas nos permiten descomponer y analizar grandes volúmenes
de datos de interacción social, ayudando a resolver problemas complejos de forma
estructurada. Estos conceptos, por tanto, son esenciales para el desarrollo de habilidades
de análisis crítico y resolución de problemas en áreas de gran aplicabilidad en el mundo
moderno.
9
Referencias bibliográficas
1. Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. Springer. Disponible en
[SpringerLink](https://link.springer.com/book/10.1007/978-1-84628-970-5).
2. Diestel, R. (2017). Graph Theory (5ª ed.). Springer. Disponible en
[SpringerLink](https://link.springer.com/book/10.1007/978-3-662-53622-3).
3. Gross, J. L., & Yellen, J. (2006). Graph Theory and Its Applications (2ª ed.). Chapman
and Hall/CRC. Disponible en [CRC Press](https://www.routledge.com/Graph-Theory-
and-Its-Applications/Gross-Yellen/p/book/9780367578882).
4. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to
Algorithms (3ª ed.). MIT Press. Disponible en [MIT
Press](https://mitpress.mit.edu/books/introduction-algorithms-third-edition).
5. Harary, F. (1969). Graph Theory. Addison-Wesley.
6. West, D. B. (2001). Introduction to Graph Theory (2ª ed.). Prentice Hall. Disponible
en [Pearson](https://www.pearson.com/store/p/introduction-to-graph-
theory/P100000633745).
7. Gibbons, A. (1985). Algorithmic Graph Theory. Cambridge University Press.
Disponible en [Cambridge University
Press](https://www.cambridge.org/core/books/algorithmic-graph-
theory/6F2F7BD63FA7B7F71E75851A4AD71764).
8. Wilson, R. J. (1996). Introduction to Graph Theory (4ª ed.). Addison Wesley.
9. Berge, C. (1976). Graphs and Hypergraphs. North-Holland Publishing.
10
