MATEMÁTICA DISCRETA MA265
Clase integral EU3
2024 – 01
1. Dado el árbol T cuyos elementos son:
(1; 12), (2; 3), (2; 4), (3; 1), (3; 5), (3; 6), (4; 8),
𝑇 ={ }
(4; 9), (6; 13), (9; 10), (9; 11), (8; 7)
a. Trace el dígrafo del árbol T ordenado indicando la raíz y el tipo de n - árbol.
b. Trace el dígrafo del árbol binario etiquetado B(T) formado a partir del árbol T ordenado.
c. Determine el contenido de los arreglos LEFT, DATA y RIGHT.
d. Liste los nodos (vértices) del árbol B(T) en preorden y postorden.
2. A continuación, se muestra el arreglo Left – Data – Right del árbol T.
ÍNDICE LEFT DATA RIGHT
1 5
2 3 A 6
3 0 B 0
4 9 C 8
5 2 D 4
6 7 E 0
7 0 F 0
8 0 G 0
9 10 H 0
10 0 I 0
a. Trace el dígrafo del árbol binario B(T).
b. Determine el árbol T (expréselo en notación de pares ordenados).
c. Liste los nodos del árbol B(T) en Preorden y Postorden.
3. En un parque nacional con ocho puntos de interés turístico (vistas panorámicas, cascadas,
lagos, etc.) que son A, B, C, D, E, F, G y H queremos diseñar una red de senderos para
senderismo que permita a los visitantes recorrer todos estos puntos de forma eficiente. Cada
punto de interés se representa como un nodo, y las conexiones posibles entre ellos se
representan como aristas con un peso (en miles de soles) asociado que indica el costo de
construcción del sendero entre esos puntos (el costo de cada conexión depende de la distancia
entre los puntos y la dificultad del terreno) que se muestran en la tabla inferior.
El objetivo es construir la red de senderos con el menor costo total posible que conecte todos
los puntos de interés. Juan un ingeniero ambiental en base a su conocimiento del terreno
estima que el costo total de la red será menor a S/. 30 000 o que los nodos A y B tendrán una
conexión directa ¿es correcta la afirmación de Juan?
Nodo A B C D E F G H
A 5 8
B 5 7 6
C 8 3
D 7 6
E 6 3 15 4
F 6 15 5
G 4 2
H 5 2
4. Una empresa de telecomunicaciones desea establecer una red de fibra óptica que conecte
varias ciudades en una región para proporcionar servicios de internet de alta velocidad. La
empresa tiene una lista de posibles conexiones entre las ciudades con el costo asociado a cada
una de ellas. El objetivo es conectar todas las ciudades de manera que el costo total de la
instalación de la fibra óptica sea el mínimo posible.
La región incluye las siguientes ciudades y los costos de conexión directa entre ellas son los
dados en la tabla inferior. Pedro un ingeniero de telecomunicaciones en base a su experiencia
estima que el costo total de la red será mayor a S/. 32 000 o que las ciudades 2 y 4 tendrán
una conexión directa ¿es correcta la afirmación de Pedro?
Costo
Ciudad A Ciudad B
(miles de soles)
Ciudad 1 Ciudad 2 7
Ciudad 1 Ciudad 3 9
Ciudad 1 Ciudad 6 14
Ciudad 2 Ciudad 3 10
Ciudad 2 Ciudad 4 15
Ciudad 3 Ciudad 4 11
Ciudad 3 Ciudad 6 2
Ciudad 4 Ciudad 5 6
Ciudad 5 Ciudad 6 9
5. Dado el conjunto de vectores: 𝑆 = {(1,1, −2), (−1,2,1), (2, −1, 𝑡))}
a. Halle el(los) valores de 𝑡 para que el conjunto 𝑆 de vectores sea linealmente independiente
b. Para 𝑡 = 2. Exprese, de ser posible, el vector (5, −4,13) como combinación lineal de los
elementos de 𝑆.
6. Dados el siguiente subespacio vectorial
𝑊 = {(𝑥, 𝑦, 𝑧) ∈ ℝ3 / 2𝑥 + 4𝑦 = 12𝑧}
Responda lo siguiente:
a. ¿Una base de 𝑊 es {(−2,1,0), (−6,0,1))}? Justifique su respuesta
b. La dimensión de 𝑆
c. Un elemento de otra base puede ser (−12,0,2)
7. La empresa “Concretomex”, que se especializa en formular mezclas de cemento, agua y
arena para la elaboración de placas de cimentación, almacena tres mezclas básicas A, B y C
(ver tabla). La empresa puede preparar “mezclas especiales” de cemento, agua y arena
efectuando combinaciones de las tres mezclas básicas. En consecuencia, las “mezclas
2
especiales” posibles pertenecen al espacio generado por los tres vectores que representan
las mezclas básicas.
Materiales A B C
Agua (L) 10 10 10
Arena (kg) 15 10 20
Cemento (kg) 10 15 10
Un ingeniero civil puede preparar “mezclas especiales” posibles pertenecientes al espacio por
los tres vectores que representan las mezclas básicas, este afirma que: el espacio generado es
{(𝑎; 𝑏; 𝑐) ∈ ℝ3 /𝑎 − 𝑏 + 𝑐 = 0} o que el vector (50; 95; 45) es una mezcla posible de las tres
mezclas básicas. ¿Es cierta la conclusión del ingeniero?
8. Determine el valor de verdad de las siguientes proposiciones:
a. 𝑇(𝑥, 𝑦, 𝑧) = (0, 𝑥 + 𝑦 − 𝑧) es una TL
b. 𝑇(𝑥, 𝑦) = (𝑥, 𝑥𝑦) es una TL
c. La matriz asociada a la TL dada por 𝑇(𝑥, 𝑦, 𝑧) = (𝑥 − 𝑦 + 𝑧, 𝑥 + 𝑦 − 𝑧) es
1 −1 1
𝐴=( )
1 1 −1
d. La matriz asociada a la TL dada por 𝑇(𝑥, 𝑦, 𝑧) = (𝑥 − 𝑦, 𝑦 − 𝑥) es
1 −1
𝐴=( )
−1 1
9. Sea 𝑇: R3→R2 una transformación lineal tal que 𝑇(1; −1; 0) = (−3; 2), 𝑇(0; 1; 1) = (2; 5)
y 𝑇(1; 0; −1) = (5; 7). Determine 𝑇(𝑥; 𝑦; 𝑧).
10. Sea 𝑇: R2→R3 una transformación lineal tal que 𝑇(1; 2) = (2; 3; 1) y
𝑇(1; −1) = (2; 0; −2). Determine 𝑇(𝑥; 𝑦).
11. Determine el polinomio característico, los autovalores y los autovectores de la siguiente matriz
−1 2 −1
𝐴 = 0 −1 3 ).
(
0 1 1
1 1 2
12. Dada la siguiente matriz 𝐴 = 2 −3 0). Determine el valor de verdad de las siguientes
(
−1 1 4
proposiciones:
a. Un autovector de A, asociado a 𝜆 = 1, es (4, −2, 1)
b. Un autovector de A, asociado a 𝜆 = −3, es (0, −2, 1)
c. El polinomio característico de la matriz de a es: 𝑃 (𝜆) = −𝜆3 − 3𝜆2 + 𝜆 + 3
d. Los autovalores de la matriz A son: 𝜆1 = 1, 𝜆2 = −3 y 𝜆3 = −1.
13. En la unidad de cuidados intensivos de un determinado hospital, cada paciente es clasificado
con un estado: crítico, serio o estable. Estas clasificaciones son actualizadas cada mañana por
3
un médico, de acuerdo con la evolución experimentada por el paciente. Las probabilidades
con las cuales cada paciente se mueve de un estado a otro se resumen en la tabla siguiente:
Crítico Serio Estable
Crítico 0,6 0,3 0,1
Serio 0,4 0,4 0,2
Estable 0,1 0,4 0,5
Juan ingresa al hospital en estado crítico un jueves y el médico de turno, en base a su
experiencia, les dice a sus familiares, dado que Juan es joven, él tiene por lo menos un 80% de
probabilidad de estar estable el domingo ¿es correcta la afirmación del doctor?
14. Supongamos que en un país hay tres tipos de universidades: la literaria, científica y la
politécnica. La influencia familiar en la elección de la universidad se cifra en que el hijo de un
graduado literario en el 80 por ciento de los casos sigue una carrera afín a la de su padre o de
lo contrario ingresa a la universidad científica. El hijo de un graduado en ciencias sigue el 50
por ciento de las veces en dicho tipo de universidad y en caso contrario muestra igual
preferencia por una carrera literaria o una politécnica. El hijo de un licenciado politécnico sigue
en el 60 por ciento de los casos la senda del padre, el 30 por ciento pasa a la rama científica y
el 10 por ciento a la literaria. Víctor graduado literario afirma que lo menos probable es que su
nieto sea un científico o que a largo plazo por lo menos el 40% de la población de universitarios
será literario ¿estás de acuerdo con la afirmación de Víctor?
Problemas adicionales
15. Un alumno del curso de Matemática Discreta desea descubrir el mensaje que se encuentra
en el siguiente árbol:
(𝐴, 𝑆), (𝐿, 𝐽 ), (𝐸, 𝐿), (𝑈, 𝐶 ), (𝑅, 𝑀),
𝑇={ }.
(𝐴, 𝑅), (𝑄, 𝑂), (𝑆, 𝐷), (𝐿, 𝐴), (𝐴, 𝑈), (𝐿, 𝑄)
Para ello el alumno debe seguir los siguientes pasos:
a. Trace el dígrafo del árbol ordenado T.
b. Trace el dígrafo del árbol binario posicional B(T).
c. Liste los nodos del árbol B(T) en PreOrden y postorden.
16. Los recorridos en PostOrder y EnOrder del árbol binario posicional 𝐵(𝑇) son:
PostOrder: MIELDHAJBKGCF
EnOrder: EIMADLHCBJGKF
Se pide:
a. Trace el dígrafo del árbol binario posicional 𝐵(𝑇)
b. Trace el dígrafo del árbol T.
c. Determine el recorrido del árbol en PreOrder.
17. Se muestran la lista de los precios (soles) mínimos de costo de viaje en avión por tramo entre
algunas de las principales ciudades del Perú:
• Lima a Cusco: S/ 150
• Lima a Arequipa: S/ 180
• Lima a Iquitos: S/ 250
• Lima a Piura: S/ 220
• Lima a Trujillo: S/ 170
4
• Lima a Chiclayo: S/ 190
• Lima a Tacna: S/ 280
• Cusco a Arequipa: S/ 120
• Arequipa a Iquitos: S/ 350
• Arequipa a Trujillo: S/ 220
• Cusco a Iquitos: S/ 350
Una empresa debe enviar desde Lima en un mismo día supervisores a las ciudades de la lista
dada con la condición de que visiten una o más ciudades con un precio mínimo de vuelo, para
lo cual se debe de determinar una ruta de costo total mínimo que visite todas las ciudades. Juan
quien es el encargado de estimar los costos del proceso de envío de supervisores estima que el
costo total en vuelos de ida será menor a S/. 2000 y que las ciudades de Arequipa y Cusco
tendrán conexión directa, ¿es correcta la estimación de Juan?
18. El grafo adjunto representa a un conjunto de 8 ciudades y las principales carreteras entre estas
ciudades. Los pesos en las aristas son el costo por eje del vehículo en el peaje de la carretera.
Una empresa envasadora de balones de Gas necesita distribuir su producto a todas las 8
ciudades con el menor costo total posible en peajes, para lo cual se debe determinar una ruta
de costo total mínimo que visite todas las ciudades. La empresa solo dispone de camiones de
4 ejes. Pedro, quien es gerente de la empresa estima que el costo total en peajes solo de ida
será menor a S/. 240, ¿es correcta la estimación de Pedro?
Nota: Todos los precios de peaje por eje son enteros y están entre los S/. 7 a S/. 10.
19. Dados el siguiente subespacio vectorial
a. 𝑆 = {(𝑥, 𝑦, 𝑧) ∈ ℝ3 / 3𝑥 − 12𝑧 = 0 }
b. 𝑊 = {(𝑥, 𝑦, 𝑧) ∈ ℝ3 / 𝑥 − 2𝑦 − 𝑧 = 0 }
Encuentre en cada uno de los subespacios la base y dimensión de estos.
20. Determine el valor de verdad de las siguientes afirmaciones:
a. 𝑇(𝑥, 𝑦) = (𝑥 − 2𝑦, 𝑥 + 𝑦 + 1) es una TL.
b. La matriz asociada a la TL dada por 𝑇(𝑥, 𝑦, 𝑧) = (𝑥 − 2𝑦, 𝑧 − 𝑦) es:
1 −2 0
a. 𝐴 = ( )
0 −1 0
c. La matriz asociada a la TL dada por 𝑇(𝑥, 𝑦) = (2𝑥 + 3𝑦, −𝑥 + 2𝑦, 𝑦) es:
2 3
a. 𝐴 = (−1 2)
1 0
21. Sea 𝑇: R3→R2 una transformación lineal tal que 𝑇(1; 1; 1) = (1; 3), 𝑇 (1; 0; −1) = (2; −2) y
𝑇(0; 1; 0) = (−1; 1). Determine 𝑇(𝑥; 𝑦; 𝑧).
5
22. Sea 𝑇: R2→R3 una transformación lineal tal que 𝑇(1; 1) = (−1; 0; 1) y
𝑇(2; 1) = (0; 1; 1). Determine 𝑇(𝑥; 𝑦).
23. Dada la siguiente matriz,
1 −2 0
𝐴 = (−1 3 −3)
0 −2 1
Indique el valor de verdad de las siguientes proposiciones:
a. Un autovector de 𝐴 asociado al autovalor de 𝜆 = 1, es (−3,0,1)
b. Un autovector de 𝐴 asociado al autovalor de 𝜆 = −1, es (1,1,1 )
c. El polinomio característico de la matriz 𝐴 es 𝑃 (𝜆) = −𝜆3 + 5𝜆2 + 𝜆 − 5.
d. Los autovalores de la matriz 𝐴 son 𝜆 = 1, 𝜆 = −1 y 𝜆 = 5.
24. El ascensor de un edificio de 3 pisos realiza viajes de uno a otro piso; el piso en el que finaliza
el enésimo viaje sigue una cadena de Markov. Se sabe que el 50% de los viajes que parten del
primer piso se dirigen al segundo piso; mientras que, si un viaje comienza en el segundo piso,
solo el 25% de las veces termina en el tercero. Si un viaje comienza en el tercer piso, siempre
finaliza en el primero. Considere que ningún viaje termina en el mismo piso y que el ascensor
inicia su recorrido en el primer piso.
a. Determine la matriz estocástica asociada al problema.
b. ¿Con qué probabilidad se encontrará en cada piso al finalizar su tercer viaje?
c. ¿Con qué probabilidad se encontrará en cada piso a largo plazo?
25. En cierto estado de la Amazonía de Brasil se produce dos tipos de harina: A y B. Cuando cierto
poblador compra harina tipo A, hay una probabilidad de 90% que la vuelva a comprar la
siguiente vez. Si un poblador compra harina tipo B, hay una probabilidad de 80% que la vuelva
a comprar la siguiente vez.
a. Si cierto poblador, actualmente compra harina tipo B, el afirma que comprará harina tipo
A después de dos compras a partir del día de hoy con una probabilidad del 80% ¿es
correcta esta afirmación?
b. Si actualmente un poblador compra harina tipo A, ¿cuál es la probabilidad de que compre
el mismo tipo de harina después de tres compras a partir del día de hoy?
26. En una comunidad hay 3 supermercados: 𝑆1 , 𝑆2 , 𝑆3 y existe la movilidad de un cliente de uno a
otro. El 1 de septiembre, 1/4 de los clientes va al 𝑆1 , 1/3 a 𝑆2 y 5/12 a 𝑆3 de un total de 10000
personas. Cada mes 𝑆1 retiene el 90% de sus clientes y pierde el 10% que se va a 𝑆2 . Se averiguó
que 𝑆2 solo retiene el 5%, el 85% se va a 𝑆1 y el resto se va a 𝑆3 , el 𝑆3 retiene solo el 40%,
pierde el 50% que va a 𝑆1 y el 10% va a 𝑆2 .
a. María quien es gerente del supermercado 𝑆1 afirma que dentro de tres meses o seis meses
ellos tendrán por lo menos al 80% del total de personas como clientes, ¿estás de acuerdo
con la afirmación de María?
b. Pedro gerente del supermercado 𝑆2 afirma que a largo plazo ellos tendrán por lo menos el
9% del mercado.
UPC, junio del 2024
