MATEMÁTICAS DISCRETAS
CÓDIGO:
Tarea 3 - Grafos y árboles
Presentado al tutor (a):
Entregado por el (la) estudiante:
Grupo:
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA - UNAD
ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍA E INGENIERÍA
FECHA
1
INTRODUCCIÓN
En el desarrollo del presente trabajo se abordarán varias temáticas del curso de
Grafos y Arboles como lo son: definición de grafos, multígrafos, aplicando los
conceptos en el desarrollo de cada ejercicio, teniendo en cuenta los vértices o
nodos identificando las aristas. Se construyo gráficamente algunos ejercicios y se
identificaron los árboles y la relación que hay en cada uno de los vértices
enraizado incluyendo su nivel y altura.
2
Desarrollo de los ejercicios
Literal seleccionado: Estudiante (B)
Ejercicio 1. Enunciado del ejercicio.
1. con el siguiente grafo:
a. Describa formalmente el grafo
b. Halle el grado y paridad de cada vértice
c. Verifique si cumple que la suma de los grados de los vértices de un grafo
es igual a dos veces el número de arista
Desarrollo del ejercicio 1:
a. Describa formalmente el grafo
G1=V , E
V =1 , 2 , 3 , 4 , 5 ,6
E=
{ }
(1 , 2),(2 , 3),
(3 , 4 ) , ( 4 , 5 ) ,(5 , 6)
b. Halle el grado y paridad de cada vértice
deg (1 )=1 ℑ par
deg (2 )=2 par
deg (3 )=2 par
deg ( 4 )=2 par
3
deg (5 )=2 par
deg (6 )=1 impar
c. Verifique si cumple que la suma de los grados de los vértices de un grafo
es igual a dos veces el número de arista
1 + 2 + 2 + 2 + 2 + 1 = 10
Luego, multiplicamos el número de aristas por 2:
5 * 2 = 10
La suma de los grados de los vértices es igual a dos veces el número de
aristas, por lo tanto, se cumple la propiedad.
Ejercicio 2. Enunciado del ejercicio.
2. Con base al grafo escogido en el punto 1, realice lo siguiente
a. La matriz de adyacencia
b. La matriz de incidencia
Desarrollo del ejercicio 2:
4
a. La matriz de adyacencia
1 2 3 4 5 6
1 0 1 0 0 0 0
2 1 0 1 0 0 0
3 0 1 0 1 0 0
4 0 0 1 0 1 0
5 0 0 0 1 0 1
6 0 0 0 0 1 0
b. La matriz de incidencia
a b c d e
1 1 0 0 0 0
2 -1 1 0 0 0
3 0 -1 1 0 0
4 0 0 -1 1 0
5 0 0 0 -1 1
6 0 0 0 0 -1
Ejercicio 3: Enunciado del ejercicio.
3. Para el siguiente árbol
Determine:
a. nodos hoja, nodos rama
5
b. la raíz de árbol
c. las relaciones entre vértices de un árbol enraizado
d. subárboles
e. nivel y altura del árbol
Desarrollo del Ejercicio 3:
a. nodos hoja, nodos rama
Los nodos hoja son aquellos que no tienen hijos, es decir, son los
extremos del árbol. En el árbol dado, los nodos hoja son: 7, 8, 9, 11,
13.
Los nodos rama son aquellos que tienen al menos un hijo. En el
árbol dado, los nodos rama son: 1, 2, 3, 4, 5, 6, 10, 12.
b. La raíz del árbol
La raíz del árbol es el nodo que no tiene ningún padre. En el árbol
dado, el nodo raíz es el nodo 1.
c. Las relaciones entre vértices de un árbol enraizado
En un árbol enraizado, cada nodo tiene un único padre, excepto la raíz que
no tiene padre. Los nodos se conectan mediante aristas que representan
las relaciones padre-hijo. En el árbol dado, las relaciones entre vértices
son las siguientes:
1 es padre de 2 y 3.
2 es padre de 10.
3 es padre de 4 y 9.
4 es padre de 5 y 6.
10 es padre de 11 y 12.
5 es padre de 7.
6 es padre de 8.
12 es padre de 13
d. Subárboles
Un subárbol es un árbol que se obtiene al seleccionar un nodo y todos sus
descendientes. En el árbol dado, algunos ejemplos de subárboles son:
Subárbol con raíz en el nodo 2: 2-10-11-12-13.
6
Subárbol con raíz en el nodo 3: 3-4-5-7, 3-4-6-8, 3-9.
Subárbol con raíz en el nodo 4: 4-5-7, 4-6-8.
e. Nivel y altura del árbol
El nivel de un nodo es la distancia entre ese nodo y la raíz. La raíz tiene
nivel 0, sus hijos tienen nivel 1, y así sucesivamente.
La altura del árbol es la longitud máxima de un camino desde la raíz hasta
un nodo hoja. En el árbol dado, la altura es 4.
Espero que esto te ayude a comprender mejor el árbol dado. Si tienes
alguna otra pregunta, no dudes en hacerla.
Ejercicio 4: Enunciado del ejercicio.
4. Ese ejercicio se sustentará por medio del video. Consulte y explique con un
ejemplo propio los conceptos de circuitos eulerianos y circuitos
hamiltonianos
Desarrollo del Ejercicio 4:
circuitos eulerianos
un circuito euleriano De un grafo de g contiene todas las aristas de g se
caracteriza por que cada uno de sus vértices debe tener un grafo par, los
vértices pueden repetirse varias veces, pero las aristas solo una vez y como es
un circuito donde comienza de terminar
circuitos hamiltonianos
se identifica porque solo pasa una vez por sus vértices y donde comienza debe
terminar
7
Ejercicio 5: Enunciado del ejercicio.
5. Ejercicio de la participación asignada a un evento académico: conferencia,
charla, taller, congreso o workshop nacional o internacional. La
participación debe ser sincrónica o asincrónica. El estudiante debe dejar en
evidencia de la participación mediante un informe que contenga:
Nombre del evento
Nombre del(los) conferencista(s)
Objetivo de la conferencia
Resumen del aprendizaje obtenido, un escrito entre 200 y 300
palabras
El evento se asignará en el trascurso del periodo académico y será
publicado en el foro noticias del curso, en el entorno de información
inicial y también por mensajería interna del curso
Desarrollo del Ejercicio 5:
SIMULEL Día 3 - 3er Workshop en Ciencias Básicas
Andrés Villabón Aldana
Enseñar como estan formado los algoritmos y para que sirven
El aprendizaje automático es el estudio de algoritmos y modelo matemáticos que
se usan que se usa mayormente en computadores para realizar tareas sin la
necesidad de dar instrucciones para que lo realice. Estos algoritmos los usan
muchas aplicaciones como YouTube, Spotify, Netflix etc. Para recomendar el
música, película y videos. a medida de lo que uno consume es esas plataformas
8
el algoritmo lo que hace es detectar que contenido le gusta a uno y sugiere
contenido similar.
Y los veneficios que vamos a tener al utilizar estos algoritmos es la toma de
decisiones de una manera más rápida porque al tener un algoritmo que nos
muestra una cantidad de opciones que arroja el modelo en un tiempo récord y
entonces podemos tomar más agiles.
El algoritmo trabaja para darle una personalización a cada cliente como lo hace
Netflix y Spotify que se personaliza dependiendo del tiempo de la cuenta te da
una sugerencia de las tendencias actuales en aprendizajes automáticos que son
estos algoritmos que se emplean en la inteligencia artificial.
Conclusiones
Se identifico la diferencia entre grafos y árboles, y que la teoría de grafos es una
de las teorías más aplicables en la cotidianidad
Referencias bibliográficas
Villalpando, B. J. F. (2014). Definiciones básicas. Matemáticas Discretas
Aplicaciones y ejercicios. (pp. 186- 189).
9
https://elibronet.bibliotecavirtual.unad.edu.co/es/ereader/unad/39454
Villalpando, B. J. F. (2014). Terminología y caracterización de los grafos.
Matemáticas Discretas Aplicaciones y ejercicios. (pp. 190- 198).
https://elibronet.bibliotecavirtual.unad.edu.co/es/ereader/unad/39454
Villalpando, B. J. F. (2014). Paseos y circuitos. Matemáticas Discretas Aplicaciones y
ejercicios. (pp. 199- 209).
https://elibronet.bibliotecavirtual.unad.edu.co/es/ereader/unad/39454
Villalpando, B. J. F. (2014). Representaciones matriciales. Matemáticas Discretas
Aplicaciones y ejercicios. (pp. 213- 215).
https://elibronet.bibliotecavirtual.unad.edu.co/es/ereader/unad/39454
Villalpando, B. J. F. (2014). Isomorfismo de grafos. Matemáticas Discretas
Aplicaciones y ejercicios. (pp. 216 - 217).
https://elibronet.bibliotecavirtual.unad.edu.co/es/ereader/unad/39454
10
