Gestión Curricular

Asignatura: Matemática discreta

Presentación

Al presentar este trabajo “Guía de Aprendizaje”, se hace con el sano propósito de contribuir
decididamente en el proceso del aprendizaje de la asignatura de Matemática Discreta

Esta recopilación de ejercicios está destinada para los alumnos del segundo periodo de la
Universidad Continental, cada ejercicio está seleccionado, permitiendo preparar y capacitar
debidamente al estudiante para seguir sus estudios superiores.

La formación básica de los estudios impartidos en la universidad, en el área de Ciencias y

Formación General, son muy importantes y la asignatura de Algebra Matricial y Geometría
Analítica, juega un rol fundamental, debido a los avances de los temas que comprende esta
materia y que están relacionados a las especialidades que brinda la Universidad.

Es así como estas guías de aprendizaje se han dividido en cuatro unidades y que son:

Unidad I: Lógica y teoría de conjuntos.

Unidad II: Relaciones de recurrencia y análisis combinatorio.

Unidad III: Teoría de grafos.

Unidad IV: Máquinas de estado finito.

Por último, quisiéramos agradecer a los colegas que han hecho posible esta recopilación de
ejercicios.

Los autores

[Link] | 3
 Gestión Curricular
Asignatura: Matemática discreta

SESIÓN – 2 ......................................................................................................................... 19
Primer y segundo principio de conteo .................................................................... 19
SESIÓN – 3 ......................................................................................................................... 20
Permutaciones, Combinaciones y Variaciones .................................................... 20
SESIÓN – 1 ......................................................................................................................... 24
Inducción matemática. ............................................................................................... 24
Sucesiones de primer orden, progresiones aritméticas ...................................... 24
SESIÓN – 2 ......................................................................................................................... 24
Sucesiones de segundo orden, progresiones geométricas .............................. 24
SESIÓN – 3 ......................................................................................................................... 26
Demostraciones de proposiciones matemáticas mediante la inducción
matemática. ................................................................................................................... 26
SESIÓN – 1 ......................................................................................................................... 26
Aplicativo Práctico ........................................................................................................ 26
SESIÓN – 2 ......................................................................................................................... 26
Evaluación 2 consolidado 1........................................................................................ 26
SESIÓN – 3 ......................................................................................................................... 26
Ejercicios unidad repaso, pruebas orales unidades 1 y 2 ................................. 26
SESIÓN – 1 ......................................................................................................................... 26
Evaluación Parcial. ........................................................................................................ 26
SESIÓN – 2 ......................................................................................................................... 26
Solucionario ..................................................................................................................... 26
SESIÓN – 3 ......................................................................................................................... 26
Entrega de notas............................................................................................................ 26
UNIDAD III:................................................................................................................................................ 27
Teoría de Grafos .................................................................................................................................... 27
SESIÓN – 1 ......................................................................................................................... 28
Teoría de conjuntos ....................................................................................................... 28
SESIÓN – 2 ......................................................................................................................... 28
Operaciones con conjuntos y las leyes de la teoría de conjuntos. ................ 28
SESIÓN – 3 ......................................................................................................................... 28
Algebra de conjuntos. .................................................................................................. 28
SESIÓN – 1 ......................................................................................................................... 29
Teoría de grafos .............................................................................................................. 29

[Link] | 5
 Gestión Curricular
Asignatura: Matemática discreta

Autómatas de estado finito. Gramáticas y lenguajes formales ...................... 44

SESIÓN – 3 ......................................................................................................................... 45
Ejercicios unidad repaso, pruebas orales unidades 3 y 4 ................................. 45
SESIÓN – 1 ......................................................................................................................... 45
Evaluación Final.............................................................................................................. 45
SESIÓN – 2 ......................................................................................................................... 45
Presentación del solucionario .................................................................................... 45
SESIÓN – 3 ......................................................................................................................... 45
Entrega de notas............................................................................................................ 45
Básica: ............................................................................................................................... 46
Complementaria: ........................................................................................................... 46

[Link] | 7
 Gestión Curricular
Asignatura: Matemática discreta

SEMANA 1

SESIÓN – 1
Examen diagnóstico.

SESIÓN – 2

Lógica Proposicional, Lógica proposicional, Formulación de proposiciones moleculares y

atómicas

1. Determine cuáles de los siguientes enunciados son proposiciones:

1.1 La informática es una ciencia formal

1.2 Que día para tan bello
1.3 [(p →q)  (q → r)]
1.4 ¿Quieres ser mi enamorada?
1.5 El invierno está muy lluvioso
1.6 x + y + 10 = -5
1.7 Todo organismo viviente se adapta a su medio físico
1.8 Más vale pájaro en mano que cientos volando
1.9 Hoy tendré un mal día, se me cruzo un gato negro
1.10 ¿Habrá juicio final?
1.11 Dios mío, haz que me gane la lotería
1.12 Rocinante es el caballo de don Quijote de la Mancha
1.13 “VALLEJO” es una Universidad
1.14 Ningún numero par es divisible por dos
1.15 Ingresaré a la Universidad
1.16 Mi deseo es trabajar por el Perú

2. Formule los siguientes enunciados:

2.1 Luis es el director de una empresa, si tiene el mayor número de acciones: y si tiene el mayor
número de acciones, entonces tiene mucho dinero. Ocurre que Luis tiene el mayor número
de acciones. En consecuencia, tiene mucho dinero
2.2 El paciente no sobrevivió porque no recibió atención adecuada”.
2.3 El puente colapsó porque los materiales de construcción no eran los adecuados”.
2.4 La conferencia programada se efectuará o se postergará
2.5 Si no compro el boleto de entrada, entonces no disfrutaré del espectáculo”.
2.6 Están por decidir si tu viaje es por tierra o por avión.
2.7 Participamos de las danzas si y solo si tenemos parejas.

[Link] | 9
 Gestión Curricular
Asignatura: Matemática discreta

6. Si p y q son proposiciones falsa y verdadera respectivamente, halle el valor de verdad de

las siguientes proposiciones:

a) p V ( p → q ) c) p Λ ( p→ q )
b) ( p V q ) → p d) (p V q ) ↔ [ p Λ ( p→ q ) ]

7. Si p=V, q= V, r= F. Halle el valor de verdad de los siguientes esquemas moleculares:

a) (p Λ q) → (˜ p V r) b) p Λ q → r c) ( p ↔ ˜ q ) → r

SEMANA 2

SESIÓN – 1
Leyes lógicas

1.- Utilizando las tablas de verdad, compruebe cada una de las simplificaciones
dadas, subraye en que parte se está aplicando la ley lógica, luego determinen si
cumplen o no las igualdades.

1.1. p → (q → r)  q → (p → r)
p → (q → r)  p  (q  r) Condicional
 (p  q)  r Asociativa
 (q  p)  r) Conmutativa
 q  (p  r) Asociativa

1.2. (p → q)  p  p  q
(p → q)  p  [(p → q) → p]  [p → (p → q)] Bicondicional
 [(p → q)  p]  [p  (p → q)] Condicional
 [(p  q)  p]  [p  (p  q)] Condicional
 [(p  q)  p]  [p  (p  q)] De Morgan
 p  [p  (p  q)] Absorción
 p  [(p  p)  q] Asociativa
 p  (p  q) Idempotencia
 p  q Absorción

1.3. (p → q)  (p → r)  p → (q  r)
(p → q)  (p → r)  (p  q)  (p  r) Condicional
 [(p  q)  p]  r Asociativa
 [p  (p  q)]  r Conmutativa
 [(p  p)  q]  r Asociativa

[Link] | 11
 Gestión Curricular
Asignatura: Matemática discreta

SESIÓN – 2
Demostraciones de proposiciones utilizando leyes lógicas

1. Simplifique utilizando leyes lógicas y luego verifique mediante tablas de

verdad

1.1 (p →q) → q Resp: T

1.2 [(p  q) → q]  p Resp: p
1.3 {[(p → q)  (p  r)]  (p → r)} Resp: p  q
1.4 {[(p  q)  (p  q)] → p}  [(p  q)  (q  p)] Resp: p
1.5 [(p  q)  (q → r)] → p Resp: p
1.6 [(p  q) → (p → q)] → [r  (q  p)] Resp: p  q
1.7 [(p  q) → (q  p)]  [(p  p) → (q → r) Resp: T
1.8 [(p → q) → (p  q)]  [r  (q  p)] Resp: p  r
1.9 {[(p  q)  (p  q)] v (p  q)}  [(q → r)  r] Resp: q  r

SESIÓN – 3
Demostraciones de proposiciones utilizando leyes lógicas

1. Simplificar las siguientes leyes lógicas.

1.1 [(p→ p)  q]  [~q  (r  q)]  [p → (p  ~q)] = ~q  r
1.2 [~(p  q)  (~p  q)] → (~p  q)= p  q

SEMANA3

SESIÓN – 1
Deducción Natural

1. Demuestre la conclusión de cada uno de los siguientes razonamientos:

1.1 Demostrar A  B, si:

C→A
C
C→B

1.2 Demostrar B  D, si:

BC
B→D

[Link] | 13
 Gestión Curricular
Asignatura: Matemática discreta

1.11 Demostrar x > y  y ≥ 6, si:

x>yx>5
x≤5y≥6
x+y=1x>y

1.12 Demostrar x ≠ 3  x > 2, si:

x + 2 ≠ 5  2x = 6
x+2≠5→x≠3
2x – 2 = 8 → 2x ≠ 6
x + 3 = 8  2x – 2 = 8

SESIÓN – 2
Demostración de premisas utilizando deducción natural

1 Analice los siguientes razonamientos y verifique las conclusiones:

1.1 P(1) x = y → x = z

P(2) x = z → x = 1

P(3) x = 0 → x  1

P(4) x = y /∴ x  0

Solución:

1.2 P(1) (P → Q)  (Q  R)

P(2) (R  S) → (P → Q) /∴ R  (S  Q)

Solución:

1.3 P(1) (P  R)

P(2) Q  P

P(3) R → S

P(4) (Q  S) → (T  S) /∴ T  S

Solución:

[Link] | 15
 Gestión Curricular
Asignatura: Matemática discreta

SESIÓN – 2
Intercambio de cuantificadores, silogismo categórico

1. Utilizando intercambio de cuantificadores halle el equivalente de:

1.1 No es probable que nadie sea honesto

1.2 Cualesquiera son trabajadores
1.3 No es cierto que pocos son generosos
1.4 Es falso que cualquiera es cantante.
1.5 No es verdad que, ciertos animales vuelan.
1.6 Ningún ateo cree en Dios.
1.7 Nada de lo que vive es eterno
1.8 Los felinos son veloces y carnívoros
1.9 No es posible que, ciertos sacerdotes no sean moralistas

SESIÓN – 3
Evaluación 1 consolidado 1

[Link] | 17
 Gestión Curricular
Asignatura: Matemática discreta

SEMANA 5

SESIÓN – 1
Análisis Combinatorio

1. Analizar el siguiente ejemplo

Una persona desea construir su casa, para lo cual considera que puede construir los cimientos
de su casa de cualquiera de dos maneras (concreto o block de cemento), mientras que las
paredes las puede hacer de adobe, adobón o ladrillo, el techo puede ser de concreto o
lámina galvanizada y por último los acabados los puede realizar de una sola manera
¿cuántas maneras tiene esta persona de construir su casa?

Solución:

Considerando que r = 4 pasos

N1= maneras de hacer cimientos = 2

N2= maneras de construir paredes = 3

N3= maneras de hacer techos = 2

N4= maneras de hacer acabados = 1

N1 x N2 x N3 x N4 = 2 x 3 x 2 x 1 = 12 maneras de construir la casa

SESIÓN – 2
Primer y segundo principio de conteo

1. Resolver utilizando principios de conteo

1.1. ¿De cuántas formas se puede cruzar un río una vez, si se cuenta con 1 bote y 2 barcos?

1.2. ¿De cuántas formas se puede vestir una persona que tiene 2 pantalones y 3 camisas?

1.3. ¿Cuántos resultados se pueden obtener si se lanza un dado 2 veces?

1.4. ¿De cuántas formas se puede ordenar una pizza, si hay 2 opciones de masa (tradicional
y especial), y 4 sabores (hawaiana, carne, vegetariana y americana)? Solo se puede
pedir una masa y un sabor.

1.5. ¿Cuántos resultados se pueden obtener si se lanza una moneda o un dado?

1.6. a) ¿Cuántos resultados distintos se puede obtener si se lanza una moneda 3 veces?

b) ¿Y si se lanza 5 veces?

[Link] | 19
 Gestión Curricular
Asignatura: Matemática discreta

13)Un barco tiene diez banderas diferentes para hacer señales y cada señal se forma
colocando 4 banderas en un mástil. ¿Cuántas señales distintas pueden hacer desde el
barco?

14)A un congreso asisten 60 personas de las cuales 40 sólo hablan inglés y 20 sólo alemán.
¿Cuántos diálogos pueden establecerse sin intérprete?

15)Una cafetería vende 10 tipos de café diferentes. Cinco amigos quieren tomar cada uno
un café. ¿Cuántas formas posibles tienen de hacerlo?

16)a) ¿Cuántos números de 6 cifras puedes escribir con los dígitos 1, 2 y 3?. b) ¿Cuántos de
ellos contienen todos los dígitos 1, 2 y 3 al menos una vez?

17)En un plano hay rectas que no son paralelas, ni concurren tres en un mismo punto. Si el
número de intersecciones es 21. ¿Cuántas rectas hay?

18)Todas las personas que asisten a una reunión se estrechan la mano. Si hubo 105
apretones, ¿cuántas personas asistieron?

19) ¿Cuántos triángulos quedan determinados por 10 puntos si tres cualesquiera no están
alineados?.

20) ¿De cuántas formas se pueden sentar tres personas en seis sillas?.

21) Con los números 2, 5, 7 y 9:

a)¿Cuántos números de tres cifras puedes formar?

b)¿Cuántos números de tres cifras distintas puedes formar?

c)¿Cuántos números de cuatro cifras distintas puedes formar?

d)¿Cuántos de los números del apartado b) son pares?

22) ¿Cuántas columnas tenemos que cubrir para acertar seguro una quiniela?. Cada
columna tiene 15 resultados a elegir entre 1, X, 2.

23) Para hacer una apuesta en la lotería hay que marcar con cruces seis números (donde
figuran números del 1 al 49). ¿De cuántas formas diferentes puede marcar una
persona?.

24) ¿De cuántas formas se pueden cubrir los puestos de Presidente y Secretario de una
comunidad de vecinos, contando con 10 vecinos para ello?.

25) Te enseñan 6 discos para que elijas 3 como regalo. ¿De cuántas formas puedes elegir?.

26) ¿Cuántas palabras se pueden escribir con las letras de SOBRE, sin repetir ninguna?.

27) Ocho amigos van de viaje llevando para ello dos coches. Si deciden ir 4 en cada coche.
a) ¿De cuántas formas pueden ir si todos tienen carnet de conducir?
b) ¿De cuántas formas pueden ir si sólo tres tienen carnet de conducir?

28) En una carrera compiten 10 caballos. En los boletos hay que indicar el nombre del 1º, 2º
y 3º. ¿Cuántos deberemos rellenar para asegurarnos de que ganaremos?

[Link] | 21
 Gestión Curricular
Asignatura: Matemática discreta

44) ¿De cuántas formas distintas se pueden sentar cinco personas alrededor de una mesa
circular?

45) Un matrimonio quiere invitar a sus amigos a cenar. Debido a las dimensiones de su casa
sólo puede invitar a 5 de cada vez. Si quieren invitar a 10 amigos. ¿De cuántas maneras
puede invitar a 5 de ellos?

46) ¿De cuántas formas se pueden colocar 10 personas en una fila si dos de ellas tienen que
estar siempre en los extremos?

47) En una urna hay tres bolas rojas, tres verdes, cuatro negras y dos azules. ¿De cuántas
maneras distintas pueden sacarse, bola a bola, de la urna?

48) En una clase hay 10 niños y 5 niñas.

a) ¿De cuántas maneras puede escoger el profesor un grupo de 3 alumnos?
b) ¿En cuántos grupos habrá una sola niña?

49) ¿Cuántas palabras distintas se pueden formar con las letras de la palabra
MATEMATICAS?

50) ¿De cuántas formas distintas pueden llegar a la meta cinco atletas en una carrera?
51) ¿De cuántas formas distintas pueden tres chicas y dos chicos en una fila de butacas de
un cine teniendo en cuenta que no pueden estar dos chicos juntos ni dos chicas juntas?

52) En un determinado programa de televisión intervienen cuatro presentadores. Si en la

emisora trabajan 10 presentadores, ¿de cuántas formas distintas se puede presentar el
programa?

53) ¿Cuántas jugadas diferentes se pueden obtener si se sacan cinco cartas de una baraja
de 40 cartas?

54) ¿De cuántas maneras pueden ordenarse 6 libros en un estante si:

a) es posible cualquier ordenación?
b) 3 libros determinados deben estar juntos?
c) dos libros determinados deben ocupar los extremos?
d) tres libros son iguales entre sí?

55) Se quiere preparar una salsa con tres ingredientes. Si disponemos de siete ingredientes
en la despensa. ¿Cuántas salsas distintas se podrían preparar?

56) En un centro escolar hay 40 en 1º de ESO, 35 en 2º, 32 en 3º y 28 en 4º. Para hablar con
la dirección se quiere formar una comisión que esté integrada por un alumno de cada
curso. ¿Cuántas comisiones se pueden formar?

57) A una reunión asisten 15 personas y se intercambian saludos entre todos, ¿cuántos
saludos se han intercambiado?

58) ¿De cuántas maneras se pueden distribuir las ocho últimas localidades de un partido de
fútbol entre los doce aficionados que aún esperan en la cola de entrada?

59) ¿Cuántas apuestas hay que rellenar en las quinielas de fútbol para tener la seguridad
de acertar seis resultados, aparte del complementario?

[Link] | 23
 Gestión Curricular
Asignatura: Matemática discreta

1. En una progresión geométrica decreciente se sabe que el cuarto término

es 1/8 del primero. Si los dos primeros términos suman 12, hallar el décimo
término de la progresión.

2. En el arreglo que se indica, hallar la diferencia entre el último término y el

término central de f15.
f1 → 1

f2 → 4 9

f3 → 16 25 36

f4 → 49 64 81 100

… … … … … … … … …

3. A los tres primeros términos de una progresión aritmética de razón 2 se le

suma 1, 3 y 9 respectivamente. Entonces, los nuevos números están en
progresión geométrica. Hallar el t20 de la progresión aritmética.

4. Si se sabe que a, a2 y 3a son los tres primeros términos de una progresión

aritmética, la suma de los 10 primeros términos es:

5. Hallar el término que ocupa el lugar 18 de la siguiente progresión

aritmética:
20, 16, 12,…
6. La suma de tres números en progresión aritmética creciente es igual a 15.
Si se suma 1, 4 y 19 respectivamente a ellos, se obtendrá tres números en
progresión geométrica. Hallar el menor de estos tres números.

7. ¿Cuál es la razón de una progresión geométrica de 12 términos siendo el

primero 1 y el último 2048?

8. Claudia se propone leer una novela diariamente, el primer día lee 3

paginas, el segundo día lee 8 paginas, el tercer día 15 paginas, el cuarto
día 24 páginas y así sucesivamente hasta que cierto día se da cuenta que
el número de páginas que ha leído ese día es 14 veces el número de días
que ha estado leyendo. Hallar el número de páginas leídas en dicho día.

[Link] | 25
 Gestión Curricular
Asignatura: Matemática discreta

UNIDAD III:
Teoría de Grafos

RES0ULTADO DE APRENDIZAJE DE LA UNIDAD

Al finalizar la unidad, el estudiante será capaz de interpretar las

estructuras de grafos y presenta técnicas de optimización, utilizando
los fundamentos de la teoría de grafos.

[Link] | 27
 Gestión Curricular
Asignatura: Matemática discreta

3.1 (A  B)  (A – B)
3.2 (A – B)  (A  B’ )
3.3 (A – B’ ) – (A  B)
3.4 (A → B) → (B  A’ )
3.5 (A  B) → (A  B)

SEMANA 10
SESIÓN – 1
Teoría de grafos

1. Traces grafos que tengan las propiedades dadas en cada uno de los
ejercicios, o explique por qué no existen tales grafos:
1.1. Que tenga exactamente 5 vértices y cada uno de ellos tenga valencia 3.
1.2. Que posea exactamente 6 vértices y 4 aristas.
1.3. Que posea exactamente 4 vértices con valencias 1, 2, 3, 4.

1.4. Un grafo simple que tenga exactamente 5 vértices con valencias 2, 3, 3, 4, 4.

1.5. Un grafo simple que tenga exactamente 5 vértices con valencias 2, 2, 4, 4,
4.

2. En un departamento formado por 25 personas donde reina la discordia. ¿Es

posible que cada persona se lleve bien con exactamente cinco de las
restantes?

3. Si G = ( V, E ) es un grafo no dirigido con número de vértices v y número de

aristas e y no tiene lazos; demuestre que 2e  v2 – v.

4. Si G es un grafo con n vértices, para n  2 y G no es conexo, demuestre que

el complemento de G es conexo.

5. ¿Cuántos caminos simples de longitud 4 hay en el grafo completo k7?

6. Sea G = ( V, E ) un grafo conexo no dirigido ¿ Cuál es el valor más grande

posible para el número de elementos de V, si el número de elementos de E =
19 y el grad ( v )  4  v  V ?

7. Si G=(V,E) es un grafo conexo con E= 17 y grad (v)  3,  v  V ¿Cuál es el

valor máximo para  V  ?.

8. Halle una fórmula para el número de aristas de Kn.

9. Obtenga una fórmula para el numero de aristas de Km,n

[Link] | 29
 Gestión Curricular
Asignatura: Matemática discreta

i j

k l

m m

a b c d e f g h i j k l m n

Es un grafo completo

Es un grafo Simple

Grafo Acíclico

Grafo Bipartito

Es un grafo plano

Es un grafo conexo

[Link] | 31
 Gestión Curricular
Asignatura: Matemática discreta

SESIÓN – 2
Matriz de adyacencia, incidencia grafos conexos

1.- Dada la siguiente matriz de adyacencia dibujar el grafo correspondiente luego hallar la
función de adyacencia y función de adyacencia inversa.

2. Hallar la función de adyacencia y la matriz de acceso determinar la ruta más corta

desde el vértice S hacia los demás vértices

[Link] | 33
 Gestión Curricular
Asignatura: Matemática discreta

SEMANA 12

SESIÓN – 1
Evaluación 1 consolidado II

SESIÓN – 2
Árboles definiciones, propiedades

1. darle solución a las siguientes interrogantes

1.1. Demuestre que cualquier árbol con dos o más vértices tiene al menos un
vértice de valencia 1.
1.2. Verifique que un árbol es un grafo bipartito.
1.3. Trace, si es posible, el grafo que corresponda a cada una de las
propiedades dadas en los siguientes ejercicios, o explique por qué no
existe dicho grafo:

a) Árbol, con todos los vértices con valencia 2.

b) Árbol, con cinco vértices, que tienen valencias 1, 1, 2, 2, 5.

c) Árbol, con cuatro vértices internos y seis vértices terminales.

1.4 Un bosque es un grafo simple libre de circuitos. Si un bosque F consiste

en m árboles y tiene n vértices. ¿Cuántas aristas tiene F?
1.5 Halle la altura máxima de un árbol binario completo con t vértices
terminales.
1.6 ¿Qué condiciones se deben cumplir para que una arista de un grafo
conexo G esté contenido en todo árbol generador de G?
1.7 Si un árbol tiene 4 vértices de grado 2, uno de grado 3, dos de grado 4
y uno de grado 5. ¿Cuántos vértices terminales tiene?
1.8 En los siguientes ejercicios, cada relación está definida sobre el
conjunto A. En cada caso determine si R es un árbol, y si lo es, encuentre
su raíz.

a) A={ a, b, c, d, e } ; R={( a, b), (b, e) , (d, c), (b, d) , (c ,a) }

b) A={1, 2, 3, 4, 5 , 6} ; R={(2,1) , (3,4) , (5,2) , (6,5) , (6,3 ) }

c) A={1, 2, 3, 4, 5, 6, 7, 8, 9} ; R={(1, 2), (1, 3), (2, 4), (4, 5) , (4, 6), (6, 7), (6, 8),
(6, 9)}

d) A={r, s, t, u, v, w, x, y, z} ; R={( u,x) , (u,v) , (v, w) , (x z), (x,y), (w, r), (w, s),

(w, t)}.

[Link] | 35
 Gestión Curricular
Asignatura: Matemática discreta

Considere un árbol con n vértices. Tiene exactamente n-1 aristas y por eso la
suma de las valencias de sus vértices es 2n-2. Cierto árbol tiene 2 vértices de
valencia 2, 1 vértice de valencia 3 y tres vértices de valencia 4. ¿Cuántos vértices
de valencia 1 tendrá el árbol?

SUGERENCIA. Si un árbol tiene n vértices, n-6 de ellos deben tener valencia 1.

2.- Sean T1 y T2 dos árboles recubridores de un grafo conexo G. Sea a una arista
que está en T1 pero no en T2. Demuestre que existe una arista b en T2 pero no en
T1, tal que, tanto (T1 – {a})  {b}, como (T2 – {b})  {a} son árboles recubridores de
G.

3.- Considere un árbol con n vértices. Tiene exactamente n-1 aristas y por eso la
suma de las valencias de sus vértices es 2n-2. Cierto árbol tiene 2 vértices de
valencia 4, 1 vértice de valencia 3 y 1 vértice de valencia 2. Si todos los demás
vértices tienen valencia 1 ¿Cuántos vértices tendrá el árbol?

4. Sea F un bosque con 7 árboles, con 40 aristas. Determine el número de vértices.

5. Si F es un bosque con 62 vértices y 51 aristas. Cuantos árboles tiene F.

6. Si un árbol T = (V,E) tiene v2 vértices de grado 2, v3 vértices de grado 3, v4

vértices de grado 4, …, vm vértices de grado m. ¿Cuántos vértices y aristas en
total tiene el árbol?

7. En un torneo individual de tenis masculino cada uno de los 25 jugadores trae

una lata con pelotas de tenis. Al jugar un partido se abre y utiliza una lata, que
es conservada por el perdedor. El ganador lleva la lata no abierta a su siguiente
encuentro. ¿Cuántas latas de pelotas de tenis se abrirán durante el torneo?
¿Cuántos partidos se juegan en el torneo?

8. Un árbol tiene 2 vértices de valencia 2, 1 vértice de valencia 3 y 3 vértices de

valencia 4. ¿Cuántos vértices de valencia 1 tendrá el árbol?

3.- Un árbol tiene 2n vértices de valencia 1, 3n vértices de valencia 2 y n vértices

de valencia 3. Determine el número de vértices y aristas en el árbol.

[Link] | 37
 Gestión Curricular
Asignatura: Matemática discreta

SEMANA 13

SESIÓN – 1
Árboles ponderados

SESIÓN – 2
Recorrido de árboles Pre order post order in order

1.- Raizar el recorrido de los siguientes arboles binarios, Realizar los recorridos árboles Pre order post
order in order

1.1.-

[Link] | 39
 Gestión Curricular
Asignatura: Matemática discreta

SESIÓN – 3
Optimización algoritmo de camino más corto Dijkstra

1. Teniendo el siguiente mapa determinar si salgo de mi casita

Si No ¿Por qué?
Podre recorrer todas las librerías sin repetir el camino
Sera Bipartido
Será Grafo ponderado

Si recorro las librerías Voronoi Casita – Fibonacci – Hilbert –

Fahrenheit – Celsius
La longitud de la cadena es 6

Si recorro las librerías Casita – Fahrenheit - Fibonacci – Hilbert –

Celsius – Fahrenheit – Casita
¿Es un ciclo?

3.- Del gráfico anterior determinar la ruta mas corta hacia todas las librerías

[Link] | 41
 Gestión Curricular
Asignatura: Matemática discreta

SESIÓN – 2
Algoritmos de árboles recubridores

1.- Determinar el árbol generador de coste mínimo usando cualquier algoritmo

SESIÓN – 3
Evaluación 2 consolidada 2

SEMANA 15

SESIÓN – 1
Máquinas y autómatas de estado finito.

1. Si:

f g

I
A b a b
S

S0 S1 S0 0 0

S1 S0 S0 1 1

[Link] | 43
 Gestión Curricular
Asignatura: Matemática discreta

SESIÓN – 3
Ejercicios unidad repaso, pruebas orales unidades 3 y 4

SEMANA 16

SESIÓN – 1
Evaluación Final

SESIÓN – 2
Presentación del solucionario

SESIÓN – 3
Entrega de notas

[Link] | 45