Paso 7 –Actividad Unidad 3
Por
Andrea Julieth Macias Lesmes Cód. 1013589127
Teorías de Números 551120
Grupo: 551120_14
Presentado a
Walberto José Roca
Universidad Nacional Abierta y a Distancia UNAD
ECEDU
Noviembre de 2019
2
Introducción
Mediante este trabajo abordaremos temas referentes a teoría de grafos, arboles, arboles binarios,
recorrido, vértices y bordes, trayectoria y ciclos; la teoría de grafos es una estructura matemática que
permite modelar problemas de la vida cotidiana, mediante una representación gráfica formada por
nodos o vértices que muestra a los actores y aristas que sirven para representar los lazos o relaciones
entre los actores.
3
Paso 7 –Actividad Unidad 3
Definición: Grafo
Un grafo es un conjunto de objetos llamados vértices unidos por enlaces llamados aristas, que
permiten representar relaciones binarias entre elementos de un conjunto.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos)
unidos por líneas (aristas).
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades
que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y
estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan
conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).
1. Considere el grafo G. Encuentre:
Definición de grado: El grado de un vértice en un grafo es el número de aristas incidentes a
él.
Un vértice aislado es un vértice con grado cero; esto es, un vértice que no es punto final de
ninguna arista.
Un vértice hoja es un vértice con grado uno.
4
En un grafo dirigido, se puede distinguir entre grado de salida ("outdegree", número de
aristas que salen del vértice) y grado de entrada ("indegree", número de aristas que llegan al
vértice)
Un vértice fuente es un vértice con grado de entrada cero, mientras que un vértice hundido
es un vértice con grado de salida cero.
a) El grado de cada vértice.
𝑔𝑟 (𝐴) = 2
𝑔𝑟 (𝐵) = 4
𝑔𝑟 (𝐶) = 3
𝑔𝑟 (𝐷) = 2
𝑔𝑟 (𝐽) = 2
𝑔𝑟 (𝐾) = 2
𝑔𝑟 (𝐿) = 3
𝑔𝑟 (𝑀) = 2
Definición de Camino: Un camino es una sucesión de vértices tal que de cada uno de sus
vértices existe una arista hacia el vértice sucesor.
Un camino simple es aquel que no repite vértices en su recorrido.
Dos caminos son ajenos o independientes si no tienen ningún vértice en común excepto el
primero y el último.
La longitud de un camino es el número de aristas que usa dicho camino, contando aristas
recorridas varias veces el mismo número de veces que las recorramos.
5
b) Todos los caminos simples de A a L.
𝑐𝑎𝑚𝑖𝑛𝑜1 = 𝐴, 𝐵, 𝐿
𝑐𝑎𝑚𝑖𝑛𝑜2 = 𝐴, 𝐵, 𝐾, 𝐿
𝑐𝑎𝑚𝑖𝑛𝑜3 = 𝐴, 𝐽, 𝐵, 𝐾, 𝐿
𝑐𝑎𝑚𝑖𝑛𝑜4 = 𝐴, 𝐽, 𝐵, 𝐿
c) Todos los recorridos de las aristas distintas de K a D.
𝑟𝑒𝑐𝑜𝑟𝑟𝑖𝑑𝑜1 = 𝐾, 𝐿, 𝐶, 𝐷
𝑟𝑒𝑐𝑜𝑟𝑟𝑖𝑑𝑜2 = 𝐾, 𝐿, 𝐶, 𝑀, 𝐷
𝑟𝑒𝑐𝑜𝑟𝑟𝑖𝑑𝑜3 = 𝐾, 𝐵, 𝐿, 𝐶, 𝐷
𝑟𝑒𝑐𝑜𝑟𝑟𝑖𝑑𝑜4 = 𝐾, 𝐵, 𝐿, 𝐶, 𝑀, 𝐷
En teoría de grafos se denomina distancia entre dos vértices de un grafo al número de
vértices mínimo que debe recorrerse para unirlos. La distancia entre dos nodos de un grafo
es la longitud del camino más corto.
Si no hubiera conexión alguna entre dos vértices se dice que la distancia es infinita.
Las distancias de todos los vértices de un grafo se computan en lo que se denomina matriz
de distancias.
d) d(A, C), la distancia de A a C.
𝑑(𝐴, 𝐶) = 3
En un grafo, la distancia entre dos vértices es el menor número de aristas de un recorrido
entre ellos. El diámetro, en una figura como un grafo, es la mayor distancia entre todos los
pares de puntos de la misma.
6
Un diámetro infinito puede significar que el grafo tiene una infinidad de vértices o
simplemente que no es conexo. También se puede considerar el diámetro promedio, como
el promedio de las distancias entre dos vértices.
e) Diámetro de G, diam (G).
𝑑𝑖𝑎𝑚(𝐺) = 7
2. Dibuje el grafo con las especificaciones dadas o explique por qué ese grafo no existe:
árbol, quince vértices, trece aristas.
El grafo mencionado anterioriormente no es posible realizarlo ya que para árboles finitos
debe cumplir la condición de que si un árbol G tiene un número finito de vértices, n,
entonces tiene n − 1 aristas; por lo tanto para un árbol de vértices n=15 deberá tener 14
aristas.
3. Enumere el orden en el que los vértices se procesan usando los recorridos pre orden,
in orden y postorden.
Definición de Recorrido: El recorrido de árboles se refiere al proceso de visitar de una
manera sistemática, exactamente una vez, cada nodo en una estructura de datos de árbol
(examinando y/o actualizando los datos en los nodos). Tales recorridos están clasificados
por el orden en el cual son visitados los nodos. Los siguientes algoritmos son descritos
para un árbol binario, pero también pueden ser generalizados a otros árboles.
Árbol binario
Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden,
hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con
el nodo de raíz:
Visite la raíz
Atraviese el sub-árbol izquierdo
7
Atraviese el sub-árbol derecho
Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden
(simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:
Atraviese el sub-árbol izquierdo
Visite la raíz
Atraviese el sub-árbol derecho
Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en
postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:
Atraviese el sub-árbol izquierdo
Atraviese el sub-árbol derecho
Visite la raíz
En general, la diferencia entre preorden, inorden y postorden es cuándo se recorre la raíz.
En los tres, se recorre primero el sub-árbol izquierdo y luego el derecho.
En preorden, la raíz se recorre antes que los recorridos de los subárboles izquierdo y
derecho
En inorden, la raíz se recorre entre los recorridos de los árboles izquierdo y derecho, y
En postorden, la raíz se recorre después de los recorridos por el subárbol izquierdo y el
derecho
Preorden (antes), inorden (en medio), postorden (después).
8
Pre orden: (raíz, izquierdo, derecho)
{𝐴, 𝐵, 𝐸, 𝐾, 𝐿, 𝐹, 𝐿, 𝑀, 𝐶, 𝐺, 𝑁, 𝑂, 𝐷, 𝐻, 𝐼, 𝐽, 𝑃, 𝑄, 𝑅}
In orden: (izquierdo, raíz, derecho)
{𝐵, 𝐾, 𝐸, 𝐿, 𝐹, 𝑀, 𝐶, 𝑁, 𝐺, 𝑂, 𝐴, 𝐻, 𝐼, 𝐽, 𝑄, 𝑃, 𝑅}
Post orden: (izquierdo, derecho, raíz)
{M, K, L, I, Q, R, H, B, F, N, O, G, E, D, C, A}
4. Represente la siguiente expresión como un árbol binario:
[ ((A+B) /C) - (D+E) ]+[ ((A-B+C) *D) / (A+B+C) ]
9
5. ¿Explique con sus propias palabras qué es un árbol de decisión? Y de un ejemplo.
Un árbol de decisión como su nombre lo dice es un esquema por medio del cual se pueden
tomar decisiones cuando las opciones son múltiples se puede utilizar desde el área
computacional hasta la economía y en general sirve para que por medio de unas condiciones
se resuelva un problema.
De acuerdo con la siguiente clasificación, se realizara un árbol de decisión.
Descuento del Envio con el 10%
Pago en efectivo de descuento
4%
De 6 a 24
Descuento del
Pago a credito 3% Envio Regular
Unidades
compradas
Descuento del
Pago en efectivo Envio Gratis
10 %
+ de 24
Descuento del 8 Envio con el 15%
Pago a credito
% de Descuento
10
Referencias Bibliográficas
stewart, J. (1999). Cálculo. Trascendentes temprana. México: Internacional Thonson
Editores. S.a de C.V.
Sangaku S.L. (2018) Máximo común divisor y Mínimo común múltiplo. sangakoo.com.
Recuperado de https://www.sangakoo.com/es/temas/maximo-comun-divisor-y-minimo-
comun-multiplo Licencia: by-nc-sa
https://www.youtube.com/watch?v=sDhQ5OfTMG0&t=171s
https://esacademic.com/dic.nsf/eswiki/356700
https://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos
