UNIVERSIDAD DE GUADALAJARA

CENTRO UNIVERSITARIO DE CIENCIAS EXACTAS E INGENIERAS

DEPARTAMENTO DE MATEMTICAS

TAREAS
PARA LA MATERIA DE
MATEMTICAS
DISCRETAS
P R E S E N T A

M.S.I. JOS FRANCISCO VILLALPANDO BECERRA

NDICE
NDICE ...................................................................................................................................................... i
NOMENCLATURA ................................................................................................................................. ii
UNIDAD 1. RELACIONES ..................................................................................................................... 1
TAREA 1.1 ........................................................................................................................................... 1
TAREA 1.2 ........................................................................................................................................... 3
TAREA 1.3 ........................................................................................................................................... 4
TAREA 1.4 ........................................................................................................................................... 5
TAREA 1.5 ........................................................................................................................................... 7
TAREA 1.6 ........................................................................................................................................... 9
UNIDAD 2. INDUCCIN MATEMTICA ......................................................................................... 10
TAREA 2.1 ......................................................................................................................................... 10
TAREA 2.2 ......................................................................................................................................... 11
TAREA 2.3 ......................................................................................................................................... 12
UNIDAD 3. RELACIONES DE RECURRENCIA ............................................................................... 14
TAREA 3.1 ......................................................................................................................................... 14
TAREA 3.2 ......................................................................................................................................... 17
TAREA 3.3 ......................................................................................................................................... 19
UNIDAD 4. PRINCIPIOS DE CONTEO............................................................................................... 21
TAREA 4.1 ......................................................................................................................................... 21
TAREA 4.2 ......................................................................................................................................... 23
TAREA 4.3 ......................................................................................................................................... 25
TAREA 4.4 ......................................................................................................................................... 26
TAREA 4.5 ......................................................................................................................................... 28
UNIDAD 5. GRAFOS ............................................................................................................................ 29
TAREA 5.1 ......................................................................................................................................... 29
TAREA 5.2 ......................................................................................................................................... 31
TAREA 5.3 ......................................................................................................................................... 34
TAREA 5.4 ......................................................................................................................................... 36
UNIDAD 6. RBOLES.......................................................................................................................... 38
TAREA 6.1 ......................................................................................................................................... 38
TAREA 6.2 ......................................................................................................................................... 39
TAREA 6.3 ......................................................................................................................................... 41
TAREA 6.4 ......................................................................................................................................... 42

NOMENCLATURA
A, B, C
A B
a, b, c
A = {a, b, c}
|A|

...

(a, b)

t. q.

R, S, T
|R|
aRb
a b
Dom(R)
Cod(R)
R, ~R
R-1, R~
P(R)

Conjuntos
Producto Cartesiano de los conjuntos A y B
Elementos de algn conjunto
Conjunto A que consta de los elementos a, b, c
Cardinalidad del conjunto A
Menor o igual que
Mayor o igual que
Mayor que
Menor que
Aproximadamente igual
As sucesivamente
Disyuncin (y)
Conjuncin (o)
Conjunto de los nmeros naturales
Conjunto de los nmeros enteros
Conjunto de los nmeros racionales
Conjunto de los nmeros reales
Par ordenado
Subconjunto
Subconjunto propio
Tal que
Es elemento o pertenece a
No es elemento de o no pertenece
Para todo
Existe
Unin
Interseccin
Conjunto Vaco
Diferencia simtrica
Diferencia
Si y slo si equivalencia
Igual a
Diferente a
Si entonces
Relaciones
Cardinalidad de la relacin R
No es una relacin
a est en relacin con b
a no est en relacin con b
Dominio de la relacin R
Codominio de la relacin R
Complemento de la relacin R
Inverso de una relacin R
Conjunto potencia de la relacin R
ii

SR
R1
R*
[a]
a|b
a b
a

!
P(n, r)
C(n, r)
n
r
n
n1 , n2 , . . . , nt
G = (V, E)
(i, j) e
v
Kn
Km,n
(a, b, c, d )
(v)
w(i, j)
AG
IG
R
T = (V, E)
h(T)

Composicin de las relaciones R y S

Extensin transitiva de la relacin R
Cerradura transitiva de la relacin R
Clase de equivalencia de a
a divide a b (divisin entera)
a no divide a b
Orden parcial
a est en relacin con b en un orden parcial
No es un orden parcial
a no est en relacin con b en un orden parcial
Sumatoria
Multiplicatoria
Infinito
Ms menos
Factorial
Permutacin de un conjunto de n elementos tomando r elementos a la vez
Combinacin de un conjunto de n elementos tomando r elementos a la vez
Coeficiente binomial
Coeficiente multinomial
Grafo G
Lado arista de un grafo
Vrtice
Grafo completo de n vrtices
Grafo bipartita de m y n vrtices
Sucesin de lados
Grado o valencia del vrtice v
Peso del lado (i, j)
Matriz de Adyacencia del grafo G
Matriz de Incidencia del grafo G
Regiones o caras de un grafo
rbol T
Altura del rbol T

iii

UNIDAD 1. RELACIONES
TAREA 1.1
1.

Sean las siguientes relaciones en el conjunto de los nmeros enteros:

R = {(a, b) t. q. a b}
S = {(a, b) t. q. a > b}
T = {(a, b) t. q. a = b a = b}
U = {(a, b) t. q. a = b}
V = {(a, b) t. q. a = b + 1}
W = {(a, b) t. q. a + b 3}
Cules de las relaciones anteriores contienen a los siguientes pares ordenados?:
(1, 1), (1, 2), (2, 1), (1, 1), (2, 2), (4, 3), (1, 3), ( 1, 2), (3, 3), (2, 5), ( 3, 2), (2, 4), (1, 3)
R

(1, 1)
(1, 2)
(2, 1)
(1, 1)
(2, 2)
(4, 3)
(1, 3)
( 1, 2)
(3, 3 )
(2, 5)
( 3, 2)
(2, 4)
( 1, 3)
2.

Sean A={x t. q. x < 10, x

elementos de R.
A) {(6,1),(7,2),(8,3),(9,4),(10,5)}
C) {(6,1),(7,2),(8,3),(9,4)}
3.
A)

} y R={(x, y) t. q. 5 | (x y), x y (divisin entera)} una relacin sobre A. Determine los

[
]
B) {(5,0),(6,1),(7,2),(8,3),(9,4)}
D) {(5,0),(6,1),(7,2),(8,3),(9,4),(10,5)}

Sea R una relacin de equivalencia sobre

B)

. Determine el Codominio de R.
C)

D)

4. Sea R={(x, y) t. q. x + y = 3} una relacin sobre A = {1, 2, 3, 4}. Determinar el dominio de R.

A) {1, 2, 3, 4}
B) {1, 2, 3}
C) {1}
D) {1, 2}
5.

Sea A={1,2,3} y sea R={(1,1),(2,1),(3,2),(1,3)} una relacin sobre A. Coloque una V si la declaracin es verdaderas
una F si es falsa.
A) 1 R 1
[
]
B) 1 2
[
]
C) 2 R 3
[
]
6.

Sean A={1,2,,10} y B={1,2,3,4} y sea R={(a, b) t. q. a+3b=13} una relacin de A en B. Determine los elementos de
R.
[
]
A) {(10,1),(7,2),(4,3),(1,4)} B) {(1,10),(2,7)(3,4),{4,1)}
C) {(10,3),(9,4)}
D) {(3,10),(4,9)}

7.

Sea A={1,2,3} y sea R={(1,1),(2,1),(3,2),(1,3)} una relacin sobre A. Coloque una V si la declaracin es Verdadera y
una F si es falsa.
A) 2 1
[
]
B) 3 R 2
[
]
[
]
C) 3 1
8.

Sean A={1,2,3,4} y B={1,2,,10} y sea R={(a, b) t. q. 3a+b=13} una relacin de A en B. Determine los elementos de
R.
[
]
A) {(10,1),(7,2),(4,3),(1,4)} B) {(1,10),(2,7)(3,4),{4,1)}
C) {(3,10),(4,9)}
D) {(10,3),(9,4)}
9. Coloque una S si los siguientes conjuntos son relaciones de A={a, b, c} en B={1, 2} y una N en caso contrario.
R = {(a,1),(a,2),(c,2)}
[
U = {(1,a),(2,a),(2,c)}
[
T=
[

]
]
]

10. Sean A= 1,2,3,4 y B= 5,6,7 . Las relaciones R= (1,1),(2,2),(3,3),(4,4) , S= (1,2),(3,2) y T = (1,7),(2,6) estn
definidas como:
[
]
A) R sobre A, S de A en B, T de A en B
B) R de A en B, S de A en B, T de A en B
C) R sobre A, S sobre A, T de A en B
D) R sobre A, S sobre A, T sobre A
11. Coloque una S si los siguientes conjuntos son relaciones de A = {a, b, c} en B = {1, 2} y una N en caso contrario.
R = {(a,2),(b,1)}
[
T=A B
[
U = {(2,a),(1,b)}
[
12. Sean A= 1,2,3,4 y B= 5,6,7 . Las relaciones R= (1,1),(2,2),(3,3) , S= (3,5),(4,6) y T =
definidas como:
A) R de A en B, S de A en B, T de A en B
B) R sobre A, S de A en B, T de A en B
C) R sobre A, S sobre B, T de A en B
D) R sobre A, S sobre B, T sobre A

estn
]

13. Sea A ={a

t. q. a | 10} y R={(a,b) t. q. a b} una relacin sobre A. Determine R.
A) (1,1), (1,2), (1,5), (1,10), ( 2,2), (5,5), (5,10), (10,10), (2,10)
B) (1,1), ( 2, 2), (5,5), (10,10 )
C) (2,1), ( 2,5), (5,1), (5,2), (10,1), (10,2), (10,5)
D) (1,1), (1,2), (1,5), (5,5), (5,10)

14. Sea R={(x, y) t. q. 2 | y } una relacin sobre

A)

. Determine el codominio o rango de R.

B) {2, 4 ,6, ..., 2n, ...}

15. Sea A = {a
A) 1 1 1 1
0 1 1 1
0 1 1 1
0 0 0 1

t. q. a | 8} y R = {(x, y) t. q. x | y, x, y
B) 1 1 1 1
1 1 1 1
1 1 1 1

(1,7),(4,6)

]
]
]

C) {0, 2, 4, 6, ..., 2n, ...}

D) {2}

A}. Defina la Matriz de relacin resultante.

C) 1 1 1 1
D) 1 0 0

1 1 1 1

0 1 1 1
0 0 1 1

1 1 0 0
1 1 1 0

0 0 0 1

1 1 1 1

TAREA 1.2
1.

Sea A={1,2,3} y sean R={(1,1),(2,2),(3,3)} y S={(1,1),(1,2),(1,3)} dos relaciones sobre A. Relacione las columnas
colocando la letra correcta para indicar el resultado de cada una de las siguientes operaciones.
A) {(1,1),(2,2),(3,3)}
R S
[
]
B) {(1,2),(1,3)}
R S
[
]
C) {(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}
R S
[
]
D) {(1,1),(1,2),(1,3)}
S R
[
]
E) {(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)}
R S
[
]
F) {(2,2),(3,3)}
R
[
]
G) {(1,2),(1,3),(2,2),(3,3)}
S
[
]
H) {(1,1),(1,2),(1,3),(2,2),(3,3)}
S-1
[
]
[
]
I) {(1,1),(2,1),(3,1)}
(S R)
J) {(1,1)}
R1
[
]
2.

Sean A={1, 2, 3, 4, 5} y R={(x, y) t. q. x = y 1; x, y A}. Relacione las

de los siguientes conjuntos.
A) {2,3,4,5}
B) {(2,1),(3,2),(4,3),(5,4)}
C) {(1,2),(2,3),(3,4),(4,5)}
D) {1,2,3,4}

columnas, indicando que representa cada uno

Los elementos de R
Los elementos de R-1
El Dominio de R
El Dominio de R-1

3. Cul de las siguientes operaciones sobre relaciones es siempre verdadera:

A) R
=
B) R R =
C) R
=

D) R

4. Las siguientes operaciones sobre las relaciones son siempre verdaderas EXCEPTO:
A) R
=R
B) R
=
C) R
=

D) R

5. Sean R y S dos relaciones reflexivas. Ser verdadero que R S y R

A) Casi Siempre
B) Nunca
C) A veces

D) Siempre

7.

Sean A el conjunto
R1.
A) {(3,2)}

]
]
]
]

=R

R=

S son reflexivas.

6. Sean A={1,2}, B={a,b,c} y C={c,d}, Determine (A B) (A C).

A) {{1,d},{2,c}}
B) {(1,c),(2,c) }
C) {(1,d),(2,d)}

[
[
[
[

D) {(1,c),(2,d)}

de los nmeros naturales y sea R = {(a, b) t. q. 3a + 4b = 17} una relacin sobre A. Determine
[
]
B) {(10,7)}
C) {(2,3)}
D) {(1,16), (2,15)}

Sean R y S dos relaciones simtricas sobre algn conjunto A, entonces ser siempre verdadero que R
S y
R S son simtricas.
[
]
A) Casi Siempre
B) A veces
C) Siempre
D) Nunca
8.

9. Sean A={a,b}, B={1,2} y C={2,3}, Determine (A B)

A){(a,2),(a,3),(b,2),(b,3)} B){(a,3),(b,3)}

(A C).
C) {(a,2),(b,2)}

[
]
D) {(a,1),(a,2),(b,1),(b,2)}

10. Sean A el conjunto

de los nmeros naturales y sea R={(a,b) tal que 4a+3b=17} una relacin sobre A.
Determine R1.
[
]
A) {(3,2)}
B) {(1,16), (2,15),(3,14)}
C) {(2,3)}
D) {(10,7)}
11. Sea X={1,2,3,4,5,6} y sean las relaciones R={(2,4), (2,6), (3,3), (3,6), (4,4)} y S={(3,3),(4,2),(4,4),(6,2), (6,3)}. La
relacin S con respecto a la relacin R es:
[
]
A) El complemento
B) La cardinalidad
C) El conjunto potencia
D) El inverso

TAREA 1.3
1. Sean A={1,2,3,4}y R={(1,1),(2,1),(3,2),(4,3)}. Encuentre (RR)-1.
A) {(1,2),(2,3),(3,4),(4,1)} B) {(1,1),(1,2),(2,3),(3,4)} C) {(1,1),(2,2),(3,3),(4,4)}

[
]
D) {(1,1),(1,2),(1,3),(2,4)}

2. Sean A={1,2,3,4}y R={(1,1),(2,1),(3,2),(4,3)}. Encuentre R R.

A) {(1,1),(2,1),(3,1),(4,2)}
B){(1,1),(2,1),(3,2),(4,3)}
C){(1,1),(2,2),(3,3),(4,4)}

[
]
D){(1,2),(2,3),(3,4),(4,1)}

3. Las siguientes propiedades de la composicin de relaciones son verdaderas EXCEPTO:

A) SR = RS
B) SR RS
C) T (SR) = (TS)R

[
-1

-1

D) (SR) = R S

-1

4. Sean A={1,2,3,4} y R={(1,2),(3,2)} una relacin sobre A. Determine el Codominio o rango de RR-1.
A) {4}
B) {3}
C) {2}
D) {1}

5. Sean A={1,2,3,4} y R={(1,2),(3,2)} una relacin sobre A. Determine el Dominio de R-1R.

A) {2,4}
B) {1,2,3,4,5}
C) {1,2,3}
D) {1,3}

6. Cul propiedad de la composicin de relaciones es siempre verdadera:

A) SR = RS
B) SR RS
C) T(SR) (TS)R

D) T(SR) = R(ST)

7.

Sean R = {(1,1), (1,2), (2,1)} y S = {(1,1),(1,2),(2,2)}, dos relaciones. Determinar cul de las siguientes matrices
representa SR.
[
]
A) 1 1
B) 1 0
C) 1 1
D) 1 1
1 0
0 1
0 1
1 1
8.

Sea R={(1,1),(1,2),(2,1),(2,2),(3,3)} una relacin definida sobre el conjunto

resultante de RR.
A) {(1,2),(2,1) }
B) {(1,1),(1,2),(2,1),(2,2),(3,3)} C) {(1,1),(2,2),(3,3)}

A={1,2,3}. Determinar el conjunto

[
]
D){(1,1), (2,2)}

9. Sean A = {a, b, c, d} y R = {(a, b),(a, c),(c, b)},determinar el codominio (imagen) de RR.

A) {a}
B) {a, b}
C) {a, c}
D) {b}

10. Sean A = {a, b, c, d}y R = {(a, b),(a, c),(c, b)}, determinar RR.

A) {(a, c)}

B) {(a, b), (a, c), (c, b)}

C) {(a, b)}

D) {(a, c), (c, b)}

11. Sean R = {(1,2), (2,2), (3,4)} y S = {(1,3), (2,5),(3,1),(4,2)}, dos relaciones. Encontrar R(SR).
A) {(3,2)}
B) {(1,3),(2,5),(3,1),(4,2)}
C) {(1,2),(2,2),(3,4)}
D) {(2,3)}

TAREA 1.4
1.

Cules propiedades tiene cada una de las siguientes relaciones binarias?

A) R a B c d

B) S a b c d

C) T a b c d

a
a
b
b
c
c
d
d
Reflexiva, antisimtrica, no transitiva
Reflexiva, simtrica, no transitiva
Reflexiva, simtrica, transitiva
Irreflexiva, antisimtrica, transitiva
Irreflexiva, simtrica, no transitiva

a
b
c
d

D U a b c d

E) V a b c d

a
b
c
d

a
b
c
d
[
[
[
[
[

]
]
]
]
]

2.

Sean las siguientes relaciones sobre el conjunto A = {1,2,3}. Relacione las columnas colocando la letra correcta para
indicar las propiedades de cada relacin.
A) {(a, b) tal que a b}
Reflexiva, simtrica
[
]
B) {(a, b) tal que a > b}
Reflexiva, antisimtrica
[
]
C) {(a, b) tal que a = b}
Irreflexiva, antisimtrica
[
]
D) {(a, b) tal que a + b 3}
Simtrica
[
]
3. Escriba una V si la afirmacin es verdadera y una F si es falsa.
Si R es simtrica, entonces R-1 es simtrica
Si R y S son transitivas, entonces R S es transitiva
Si R y S son reflexivas, entonces R S es reflexiva

[
[
[

]
]
]

4. Escriba una V si la afirmacin es verdadera y una F si es falsa.

Si R y S son transitivas, entonces R S es transitiva
Si R es reflexiva, entonces R-1 es reflexiva
Si R y S son reflexivas, entonces R S es reflexiva

[
[
[

]
]
]

5.

Relacione las columnas indicando las propiedades que tiene cada una de las siguientes relaciones binarias sobre
A={1,2,3,4}. 12
A) {(1,2),(2,3),(1,3)}
Reflexiva, antisimtrica y transitiva
[
]
B) {(1,1),(1,2),(1,3),(2,2),(2,3),(3,3),(4,4)}
Irreflexiva, antisimtrica y transitiva
[
]
C) {(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}
Reflexiva, simtrica y transitiva
[
]
6.

Sea L el conjunto de las rectas del plano. Coloque una S si la relacin correspondiente es transitiva sobre L o una N en
caso contrario.47
U = L1 R L2 si L1 es paralela a L2
[
]
T = L1 R L2 si L1 es perpendicular a L2
[
]
7.

Una relacin es simtrica sobre un conjunto A si

[
]
A) (x, y) R
(y, x) R x y A
C) (x, y) R
(y, x) R x y A
8.

B) (x, x)
D) (x, y)

R x A
R
(y, x)

La relacin dada por el siguiente grafo dirigido (dgrafo) es:

A) Reflexiva y antisimtrica

B) Irreflexiva e antisimtrica

C) Irreflexiva y simtrica

x y

A
[

D) Reflexiva y simtrica

9. Una relacin es irreflexiva sobre un conjunto A si:

A) (x, y) R
(y, x) R x y A
C) (x, y) R
(y, x) R x y A
10. La relacin dada por el grafo dirigido

A) Reflexiva y antisimtrica

B) (x, x)
D) (x, y)

R x A
R
(y, x)

x y

C) Irreflexiva y simtrica

es:

B) Irreflexiva e antisimtrica

D) Reflexiva y simtrica

11. Sean A = {a, b, c, d} y R = {(a, b), (b, c), (c, b), (c, d)}. Encontrar R1.
[
A) {(a, b), (a, c), (a, d), (b, b), (b, c), (b, d), (c, b), (c, c), (c, d)}
B){ (a, b), (b, b), (b, c), (c, b), (c, c)}
C) {(a, b), (a, c), (b, b), (b, c), (b, d), (c, b), (c, c), (c, d)}
D) {(a, b), (a, c), (b, c), (b, d), (c, b), (c, d)}

12. Sea el conjunto A = {1, 2, 3, 4}, determine cual matriz de relaciones representa una relacin irreflexiva:

A)

0 1 1 1
1 1 1 1
1 1 1 1
1 1 1 0

B)

1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1

C)

1 1 1 0
1 1 0 1
1 0 1 1
0 1 1 1

D)

0 1 1 1
1 0 0 1
1 0 0 1
1 1 1 0

TAREA 1.5
1.

Sea R={(1,1),(1,2),(2,1),(2,2),(3,3),(4,4),(4,5),(5,4),(5,5)} una relacin de equivalencia sobre A={1,2,3,4,5}. Cul es la

particin originada por R.
5
[
]
A) {1,2,3,4,5}
B) {{1,2},{3},{4,5}}
C) {{1,2},{3,4},{5}}
D) {{1},{2},{3},{4},{5}}
2. Encuentre la relacin de equivalencia cuyas clases de equivalencia son: {a}, {b, d} y {c}
A) {(a,a),(b,b),(c,c},(d,d),(d,a),(b,c)}
B) {(a,a),(b,b),(c,c},(d,d),(a,c),(c,a)}
C) {(a,a),(b,b),(c,c},(d,d),(b,a),(d,c)}
D) {(a,a),(b,b),(c,c},(d,d),(b,d),(d,b)}

3. Encuentre la relacin de equivalencia cuyas clases de equivalencia son: [1]=[2]={1,2},[3]={3},[4]={4}.

A) {(1,1),(2,2),(3,3),(4,4),(1,3),(3,1)}
B) {(1,1),(2,2),(3,3),(4,4),(1,4),(4,1)}
C) {(1,1),(2,2),(3,3),(4,4),(1,2),(2,1)}
D) {(1,1),(2,2),(3,3),(4,4),(2,4),(4,2)}

4.

Sea R={(a,a),(a,b),(b,b),(b,a),(c,c),(d,d),(d,e),(e,d),(e,e)} una relacin de equivalencia sobre A={a,b,c,d,e}. Determine

cul es la particin originada por la relacin anterior sobre A.
[
]
A) {{a,b},{c,d},{e}}
B) {a,b,c,d,e}
C) {{a,b},{c},{d,e}}
D) {{a},{b},{c},{d},{e}}
5. Una relacin R sobre un conjunto A, que es reflexiva, simtrica y transitiva recibe el nombre de:
A) Relacin de orden parcial
B) Relacin de equivalencia
C) Conjunto parcialmente ordenado
D) Clase de Equivalencia

6.

Sea A={a,b,c,d} y sea S={{a,b},{c,d}} una particin sobre A. Determinar la relacin de equivalencia generada por
esta particin.
[
]
A) {(a,b),(b,a),(c,d),(d,c)}
B) {(a,a),(b,b),(a,b),(b,a),(c,c),(d,d),(c,d),(d,c)}
C) {(a,a),(b,b),(c,c),(d,d)}
D) {(a,c),(a,d),(c,a),(d,a),(b,c),(b,d),(c,b),(d,b)}
Sea R={(1,1),(1,2),(2,2),(2,1),(3,3),(3,4),(4,3), (4,4),(5,5) } una relacin sobre el conjunto A={1, 2, 3, 4, 5}.
Determinar cul es la particin sobre A originada por la relacin R.
[
]
A){{1,2},{3},{4,5}}
B){1,2,3,4,5}
C){{1,2},{3,4},{5}}
D){{1},{2},{3},{4},{5}}
7.

8. Sea X={1,2,3,4,5,...,10}y R={(x,y) t. q. (x y) es divisible por 5}. Determinar [2].

A) {2,7}
B) {5,10}
C) {7}

9. Sean A={1,2,3,...,20} y R={(a,b) t. q. (ab) es divisible por 4} una relacin sobre A. Determinar [1].
[
A) {1,5,9,13,17}
B) {1}
C) {1,11}
D) {4,8,12,16,20}

10. Sean A={1,2,3,...,20} y R={(a,b) t. q. (ab) es divisible por 5} una relacin sobre A. Determinar [5].
A) {5,10,15,20}
B) {5}
C)
D) {2,7,12,17}

D) {2, 7,10}

11. Sea A={1,2,3,,15}. Considere la relacin de equivalencia sobre A A definida por (a, b) (c,d) si ad = bc. Halle la
clase de equivalencia de (3,2)
[
]
A)
B) {2,3,4,6,9,10,12,15}
C) {(3,2),(6,4),(9,6),(15,10)}
D) {(3,2)}
12. Sea A={1,2,3,,15}. Considere la relacin de equivalencia ~ sobre A A definida por (a, b) ~ (c,d) si
a+d = b+c. Halle la clase de equivalencia de (2,11).
[
A) {(1,10),(2,11),(3,12),(4,13),(5,14,(6,15)}
B)
C) {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} D) {(2,11) }

13. Sea R={(1,1),(1,2),(2,1),(2,2),(3,3),(3,4),(4,3),(4,4),(5,5),(5,6),(6,5),(6,6)} una relacin sobre el conjunto

A = {1, 2, 3, 4, 5, 6}. Determinar cul es la particin originada por la relacin anterior sobre A.
A){{1,2},{3},{4,5,6}} B) {{1},{2},{3},{4},{5},{6}}
C){{1,2},{3,4},{5,6}}
D) {1,2,3,4,5,6}

14. Sea R la relacin tiene el mismo tamao que, definida en todos los subconjuntos finitos de
slo si |A| = |B|. Entonces R es:
A) Una relacin de orden parcial
B) Una relacin de equivalencia
C) Una relacin de orden total
D) Una relacin antisimtrica

, es decir, a R b si y
[
]

15. En una relacin de equivalencia sobre un conjunto A son vlidas las siguientes afirmaciones EXCEPTO
A) S = {[a] | a A} es una particin de A
B) Si a R b entonces [a] = [b]
C) Si [a] = [b] entonces [a] [b]
D) Si a R b entonces [a] [b] =

16. Sea R la relacin es semejante a, definida en el conjunto de todos los tringulos, es decir, T1 R T2 si y slo T1 es
semejante a T2. Entonces R es:
[
]
A) Una relacin de equivalencia
B) Una relacin de orden parcial
C) Una relacin de orden total
D) Una relacin antisimtrica
17. Sea R={(1,1),(2,2),(3,3),(4,4),(5,5),(6,6)} una relacin sobre A={1,2,3,4,5,6}. Determinar cul es la particin
originada por la relacin anterior sobre A.
[
]
A){{1,2},{3},{4,5,6}}
B){1,2,3,4,5,6}
C){{1,2},{3,4},{4,5}}
D){{1},{2},{3},{4},{5},{6}}
18. En una relacin de equivalencia sobre un conjunto A, cul de las siguientes afirmacin es vlida
A) Si a R b entonces [a] = [b]
B) Si a R b entonces [a] [b]
C) Si [a] = [b] entonces [a] [b] =
D) Si a R b entonces [a] [b] =
19. Coloque una S si la relacin es de equivalencia sobre {1, 2, 3, 4, 5} y una N si no lo es.
A) {(1, 1), (1, 3), (2, 2), (3, 1), (3, 3), (4, 4), (5, 5)}
B) {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)}
C) {(1, 1), (1, 3), (1, 5), (2, 2), (3, 1), (3, 3), (3, 5), (4, 4), (5, 1), (5, 3), (5, 5) }
D) {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4), (5, 5) }

[
[
[
[

]
]
]
]

TAREA 1.6
1. Coloque una S si la relacin es un Orden Parcial sobre
R = {(a, b) tal que a = b + 1}
S = {(a, b) tal que a b}
T = {(a, b) tal que a > b}

y una N si no lo es.

2. Coloque una S si la relacin es un Orden Parcial sobre

R = {(a, b) tal que a | b (divisin entera)}
S = {(a, b) tal que a + b
3}
T = {(a, b) tal que a = b*2}

y una N si no lo es.

[
[
[

]
]
]

[
[
[

]
]
]

3. Una relacin R sobre un conjunto A, que es reflexiva, antisimtrica y transitiva recibe el nombre de:
A) Orden parcial
B) Conjunto parcialmente ordenado
C) Conjunto totalmente ordenado
D) Orden total

4. Todas las siguientes relaciones sobre

son ordenes parciales EXCEPTO:
A) R={(x, y) t. q. x > y} B) R={(x, y) t. q. x | y}
C) R={(x, y) t. q. x

5. Qu propiedades posee la relacin sobre

A) Reflexiva y simtrica
C) Irreflexiva y simtrica

y}

D) R={(x, y) t. q. x

]
y}

B) Irreflexiva, antisimtrica y transitiva

D) Reflexiva, antisimtrica y transitiva

6.

Sean X = {1,2,3,4}y R = {(1,1),(1,2),(1,3),(2,2),(2,3),(3,3),(4,4)} una relacin de orden parcial sobre X. En los

siguientes conjuntos escriba una A si es una cadena, una B si es anticadena, una C si es cadena y anticadena o una D si
no es ninguno de los dos.
{2}
[
]
{2,4}
[
]
{1, 2, 3}
[
]
{1, 2, 3, 4}
[
]
7.

En un orden parcial R sobre un conjunto X, si a, b, c

EXCEPTO
A) b R b
B) b R a

X y si a R b y b R c las siguientes afirmaciones se cumplen

[
]
C) a R a
D) a R c

UNIDAD 4. PRINCIPIOS DE CONTEO

TAREA 4.1
1.

Cuntos nmeros telefnicos de siete dgitos podemos obtener si el primero, el quinto y el ltimo dgito no pueden ser
cero y se permiten repeticiones?
[
]
A) 7290,000
B) 72900,000
C) 10000,000
D) 70000,000
2.

Cuntos nmeros de 4 cifras pueden formarse a partir de los seis dgitos 1,2,3,5,7 y 8, que sean menores de 4,000 si no
se permiten repeticiones
[
]
A) 360
B) 160
C) 180
D) 120
3.

Cuntos automviles diferentes se pueden construir si dispones de 12 colores diferentes, carroceras de 4 modelos,
motores de 3 potencias y transmisin de 2 tipos?
[
]
A) 96
B) 72
C) 288
D) 144
4.

Cuntos nmeros pares de tres dgitos se pueden formar a partir de los dgitos 1, 2, 5, 6 y 9 si cada dgito se puede usar
slo una vez?
[
]
A) 36
B) 10
C) 100
D) 24
Los siguientes cuatro problemas se refieren a lo siguiente: En la fbrica de placas de automvil de un pequeo pas, cada
placa que se elabora consta de 2 letras y 3 dgitos. El alfabeto consta de 26 letras. Cuntas placas diferentes habr si:
5. El primer dgito no puede ser cero
[
]
A) 421,200
B) 468,000
C) 608,400
D) 676,000
6. No se permite que se repitan las letras y los dgitos
A) 421,200
B) 468,000

C) 608,400

7. No se permite repetir letras ni dgitos y el primer dgito no puede ser cero

A) 421,200
B) 468,000
C) 608,400
8. Se permite repetir letras y dgitos
A) 421,200
B) 468,000

C) 608,400

D) 676,000

D) 676,000

D) 676,000

Los siguientes dos problemas se refieren a que en una escuela se ofrecen cinco cursos por la maana y siete por la tarde.
Cuntas opciones tiene un alumno si quiere inscribirse en:
9. Un curso en la maana y otro en la tarde
[
]
A) 12
B) 7
C) 35
D) 5
10. Un nico curso
A) 5

[
B) 35

C) 7

D) 12

Los siguientes dos problemas se refieren a que en una escuela se ofrecen ocho cursos por la maana y seis por la tarde.
Cuntas opciones tiene un alumno si quiere inscribirse en:
11. Un curso en la maana y otro en la tarde
[
]
A) 48
B) 8
C) 14
D) 6
12. Un nico curso
A) 6

[
B) 18

C) 8

21

D) 14

Los siguientes cuatro problemas se refieren a que en Mxico un nmero de Seguro Social tiene 9 dgitos. Para formarlos se
permiten repeticiones. Cuntos nmeros distintos hay si:
13. Se toman todos los posibles nmeros que se puedan formar
[
]
A) (9) (10)
B) 910
C) 109
D) 9!
14. El primero y el ltimo dgito no pueden ser cero
A) (9) (7)
B) 107 92

C) 10

15. Ningn dgito puede ser un 8

A) (9) (9)
B) 89

C) 109

D) 99

16. Todos los dgitos deben ser pares

A) (9) (5)
B) 95

C) 59

D) 105

22

D) 9 9

TAREA 4.2
1.

Cuntas maneras diferentes hay de asignar la posicin de salida de 8 autos que Participan en una carrera de frmula
[
A) 40,320
B) 8
C) 56,000
D) 40,000

Los siguientes dos problemas se refieren a que en una escuela se ofrecen cinco cursos por la maana y siete por la tarde.
Cuntas opciones tiene un alumno si quiere inscribirse en:
2. Dos cursos en la maana y dos en la tarde
[
]
A) 210
B) 700
C) 35
D) 140
3. Todos los cursos posibles
A) C(12,5)*C(12,7)
B) P(12,5)*P(12,7)

[
C) C(12,12)

D) P(12,12)

Los siguientes dos problemas se refieren a que en una escuela se ofrecen ocho cursos por la maana y seis por la tarde.
Cuntas opciones tiene un alumno si quiere inscribirse en:
4. Dos cursos en la maana y dos en la tarde
[
]
A) 192
B) 420
C) 768
D) 48
5. Todos los cursos posibles
A) C(14,8)*C(14,6)
B) P(14,8)*P(14,6)

[
C) P(14,14)

D) C(14,14)

En una Copa de Ftbol participan 32 equipos. Los premios son copas de oro, plata, cobre y bronce del 1o al 4o lugar.
De cuntas formas pueden repartirse las copas, si un equipo solamente puede ganar una?
[
]
A) C(32,4)
B) 32!/4!
C) 32!
D) P(32,4)
6.

7.

De cuntas maneras puede un agricultor sembrar 5 productos diferentes en 5 campos agrcolas si solamente cultiva un
producto en cada campo
[
]
A) 120
B) 25
C) 10
D) 5
8.

En Alemania 2006 participan 32 equipos de ftbol. Los premios son medallas de oro, planta y bronce, al primero,
segundo y tercer lugar.De cuntas formas pueden repartirse las medallas, si un equipo solamente puede ganar una de
ellas?
[
]
A) 29,760
B) 32!/3!
C) 32!
D) 4,960
9. Cuntas cadenas de 8 bits tienen exactamente 3 ceros?
A) 3!
B) 5!
C) 56

D) 720

10. De un conjunto de 6 hombres y 7 mujeres, de cuntas maneras se puede elegir un comit de 5 personas.
A) 1,200
B) 154,440
C) 1,287
D) 65

11. En la final de la carrera de los 100 metros planos participan 8 finalistas. Los premios son medallas de oro, planta y
bronce, al primero, segundo y tercer lugar. De cuntas formas pueden repartirse las medallas, si un finalista solamente
puede ganar una de ellas?
[
]
A) 56
B) 8!/3!
C) 8!
D) 336
12. Cuntas cadenas de 8 bits tienen exactamente 5 ceros?
A) 3!
B) 56
C) 5!

D) 720

13. De cuntas maneras puede un agricultor sembrar 4 productos diferentes en 4 campos agrcolas si solamente cultiva un
producto en cada campo
[
]
A) 4
B) 8
C) 16
D) 24

23

14. De un conjunto de 8 hombres y 4 mujeres, de cuntas maneras se puede elegir un comit de 5 personas.
A) 792
B) 70
C) 495
D) 95,040

15. El gerente de CHEDRAUI desea implementar ventas nocturnas 3 veces a la semana. De cuntas maneras distintas se
pueden implementar dichas ventas.
[
]
A) 21
B) 35
C) 15
D) 10
16. Un cargamento de 50 microprocesadores contiene 4 defectuosos. De cuntas maneras puedo seleccionar 4
microprocesadores no defectuosos?
[
]
A) 67,115
B) 230,300
C) 163,185
D)60,720
17. De cuntas formas puede elegirse un comit de 4 republicanos, 3 demcratas y 2 independientes de un grupo de 10
republicanos, 12 demcratas y 4 independientes?
[
]
10
12
4
A)
B) P(10,4)*P(12,3)*P(4,2)
C) 10 * 12 * 4
D) P(10,4)+P(12,3)+P(4,2)
4

18. Cuntas ordenaciones de las letras ABCDEFGH contienen las letras DEFGH juntas y en ese mismo orden
A) 40,320
B) 24
C) 6,720
D) 56

19. De cuntas formas se pueden programar a tres conferencistas para tres reuniones diferentes si todos estn disponibles
en cualquiera de cinco fechas diferentes?
[
]
A) 24
B) 60
C) 120
D) 240
20. Supngase que tenemos 7 habitaciones y queremos asignar 4 de ellas como oficinas para programadores. De cuntas
maneras puede realizarse dicho acomodo?
[
]
A) 840
B) 120,960
C) 35
D) 210
21. Cuatro matrimonios compraron ocho lugares en la misma fila para un concierto. De cuntas formas diferentes se
pueden sentar si cada pareja debe estar junta?
[
]
A) 1,630
B) 70
C) 24
D) 8
22. De cuntas formas pueden asignarse siete cientficos en tres habitaciones de un hotel si una habitacin es triple y dos
son dobles?
[
]
A) 210
B) 7!
C) 640
D) 120
23. Un entrenador de baloncesto dispone de 12 jugadores Cuntos equipos de 5 jugadores puede formar?
A) 792
B) 95,040
C) 60
D)120

24. El gerente de AURRERA desea implementar rebajas sobre rebajas tres veces a la semana. De cuntas maneras
distintas se pueden implementar dichas rebajas.
[
]
A) 21
B) 35
C) 42
D) 210
25. En una compaa hay 30 obreros y 10 administrativos. De cuntas maneras se puede formar un comit compuesto por
3 obreros y 4 administrativos?
[
]
A) 1,200
B) 3,600
C) 900,000
D) 852,600

24

TAREA 4.3
1. Cuntas cadenas se pueden formar con las siguientes letras: BENZENE?
A) 120
B) 840
C) 5,040

D) 420

2. Cuntas cadenas se pueden formar con las siguientes letras: FANTASMA?

A) 56
B) 336
C) 6,720

D) 40,320

3. De cuntas maneras de pueden repartir 15 libros idnticos de matemticas entre 6 estudiantes.

A) 20,206
B) 15,504
C) 90
D) 6!

4.

Cuntas palabras pueden formarse reordenando las letras de la palabra SALESPERSONS, si las cuatro S, deben ser
consecutivas (juntas)?
[
]
A) 362,880
B) 181,440
C) 12!/2!
D)286,808
5.

Se tienen 5 pilas de pelotas, cada pila de diferente color, adems cada pila tiene al menos 6 pelotas. De cuntos modos
se pueden seleccionar 6 pelotas?
[
]
A) 6
B) 720
C) 210
D) 5,040
6.

De cuntas formas diferentes se pueden ordenar 3 focos rojos, 4 amarillos y 2 azules en una serie de luces navideas
con nueve portalmparas?
[
]
A) 9!
B) 24
C) 1,260
D) 940
Los siguientes cuatro problemas se refieren a lo siguiente: De cuntas formas diferentes se pueden ordenar las letras de
MISSISSIPPI si:
7. Se tiene que comenzar con una I
[
]
A) 840
B) 6,300
C) 3,780
D) 12,600
8. Las dos P deben estar juntas
A) 840
B) 6,300

C) 3,780

9. Las cuatro S deben estar juntas

A) 840
B) 6,300

C) 3,780

D) 12,600

10. Se debe comenzar y terminar con una S

A) 840
B) 6,300

C) 3,780

D) 12,600

11. Cuntas cadenas se pueden obtener con las letras de la palabra MATEMATICAS?
A) 1663,200
B) 1110
C) 11000,000

25

D) 12,600

D) 11!

TAREA 4.4
Los siguientes cinco problemas se refieren a una escuela de deportes en la que hay 140 alumnos de los cuales 40 toman

Bsquetbol, 50 Natacin, 45 Ciclismo, 7 Natacin y Bsquetbol, 6 Natacin y Ciclismo, 8 Bsquetbol y

Ciclismo; y 3 que toman los 3 cursos.
1. Cuntos alumnos distintos hay que toman uno o dos cursos nicamente
[
]
A) 102
B) 135
C) 117
D) 114
Cuntos alumnos distintos hay que no toman ninguno de estos cursos
A) 5
B) 23
C) 15

D) 18

Cuntos alumnos distintos hay que toman al menos un curso

A) 117
B) 102
C) 135

D) 114

Cuntos alumnos distintos hay que toman exactamente dos cursos

A) 18
B) 15
C) 12

D) 21

2.

3.

4.

Cuntos alumnos distintos hay que toman exactamente un curso

A) 135
B) 102
C) 114
5.

D) 117

Los siguientes cinco problemas se refieren a una escuela de artes marciales en la que hay 110 alumnos de los
cuales 30 toman Karate, 40 Tae Kwan Do, 35 Judo, 9 Karate y Tae Kwan Do, 11 Tae Kwan Do y Judo, 8
Karate y Judo; y 6 que toman los 3 cursos.
6. Cuntos alumnos distintos hay que toman uno o dos cursos nicamente
[
]
A) 67
B) 77
C) 83
D) 105
Cuntos alumnos distintos hay que no toman ninguno de estos cursos
A) 13
B) 5
C) 27
7.

Cuntos alumnos distintos hay que toman al menos un curso

A) 83
B) 105
C) 67

D) 77

Cuntos alumnos distintos hay que toman exactamente dos cursos

A) 28
B) 22
C) 16

D) 10

9.

10. Cuntos alumnos distintos hay que toman exactamente un curso

B) 107

C) 67

D) 20

8.

A) 77

D) 83

Los siguientes cinco problemas se refieren a una academia en la que hay 130 alumnos de los cuales 43 toman
Cermica, 57 Pintura y 29 Escultura, en Cermica y Pintura hay 10 alumnos, 5 en Pintura y Escultura, 5 en
Cermica y Escultura; y hay 2 que toman los 3 cursos.
11. Cuntos alumnos distintos hay que toman exactamente un curso
[
]
A) 109
B) 111
C) 95
D) 129
12. Cuntos alumnos distintos hay que toman al menos un curso

A) 111

B) 129

C) 129

13. Cuntos alumnos distintos hay que toman exactamente dos cursos

A) 19

B) 20

C) 16

26

D) 109

D) 14

14. Cuntos alumnos distintos hay que toman uno o dos cursos nicamente

A) 111

B) 109

C) 129

15. Cuntos alumnos distintos hay que no toman ninguno de estos cursos

A) 19

B) 11

C) 1

D) 95

D) 14

16. En una escuela hay 1,232 alumnos inscritos en el curso de ingls, 879 al curso de francs y 114 al de alemn.

Adems 103 estn inscritos en ingls y francs, 23 en ingls y alemn, 14 en francs y alemn y 7 en los tres
cursos. Cuntos estudiantes toman al menos un curso?
[
]
A) 2,092
B) 2,372
C) 2,225
D) 2,106
17. De 40 estudiantes, 20 estudian matemticas discretas, 14 lgebra, 10 clculo, 7 matemticas discretas y

lgebra, 5 matemticas discretas y clculo, 3 lgebra y clculo y 9 no estudian ninguna de las 3 materias.
Cuntos estudian las tres materias?
[
]
A) 5
B) 2
C) 7
D) 3

27

TAREA 4.5
1.

En una casa de huspedes hay 30 habitaciones. En una temporada de vacaciones llega una excursin con 35 personas
que quieren alojarse. De acuerdo a este suceso, qu nos asegura el Principio de Dirichlet?
[
]
A) Cada husped est en alguna habitacin.
B) Hay una habitacin que hospeda ms de un husped
C) Hay tres huspedes sin habitacin
D) Se tienen habitaciones donde puede recibir ms de un husped
2.

Cuntos alumnos habr en una clase para garantizar que al menos dos alumnos reciban la misma calificacin,
suponiendo que las calificaciones van de 0 a 10
[
]

A) 10

B) 11

C) 12

D) 13

3. Calcular el coeficiente del trmino xy3 que resulta del binomio (3x
A) 96
B) 96
C) 216

2y)4

4. Cuntos trminos tendr en total el desarrollo del trinomio (2x + 3y + z)3 ?

A) 7
B) 4
C) 10

D) 13

5. Determinar el coeficiente del trmino x4y7 que se obtiene al desarrollar (x+y)11

A) 308
B) 280
C) 56

D) 330

6. Calcular el coeficiente del trmino x2y2 que resulta del binomio (3x
A) 96
B) 96
C) 216

D) 216

2y)4

7. Cuntos trminos tendr en total el desarrollo del trinomio (x + y + z)2 ?

A) 3
B) 6
C) 7

D) 4

8. Determinar el coeficiente del trmino x5y5 que se obtiene al desarrollar (x+y)10

A) 45
B) 120
C) 210

D) 252

9. Determinar el coeficiente del cuarto trmino que se obtiene al desarrollar (x+3y)11

A) 8,910
B) 26,730
C) 4,455

D) 330

10. Determinar el coeficiente del trmino x5y7 que se obtiene al desarrollar (x+y)12
A) 495
B) 66
C) 924

D) 792

11. Obtenga el coeficiente del tercer trmino de (a + b)20

A) 20
B) 1

D) 190

12. Puesto que

A)

n b

n r

D) 216

C) 1,140

y sabiendo que n = a + b, entonces todas las siguientes afirmaciones son ciertas EXCEPTO
[
n
n
n
B) n
C) n
D) n
n a

28

a b

b a

UNIDAD 5. GRAFOS
TAREA 5.1
1. Determine el nmero de aristas que tiene el grafo K9?
A) 90
B) 72

Coloque la letra correcta de acuerdo al tipo de grafo. Nota: un grafo puede ser de ms de un tipo.
Conexo
A)
B)
C)
Simple
Completo

[
[
[

]
]
]

7.

C) 45

D) 36

2. Qu grado o valencia tendr cada vrtice de un grafo K6?

A) 6
B) 5
C) 7

D) 4

3. Es un grafo en el que hay datos asociados a sus lados

A) Ponderado
B) Conexo

C) Multigrafo

D) Subgrafo

4. Determine el nmero de aristas que tiene el grafo K10?

A) 90
B) 110

C) 45

D) 55

5. Qu grado o valencia tendr cada vrtice de un grafo Kn?

A) n 1
B) n
C) n + 1

D) n 2

6.

A)

8.

A)

Cul de los siguiente grafos representa un subgrafo generador para K4

B)

C)

Cul de los siguientes subgrafos es el complemento de

B)

9. Es un grafo en el que no existe lazos ni lados paralelos

A) Simple
B) Completo

D)

con respecto a K4

C)

D)

C) Conexo

D) No conexo

10. Todos los siguientes subgrafos son generadores de K4 EXCEPTO

A)

B)

C)

D)

11. Cul de los siguientes subgrafos es el complemento de con respecto a K4

A)

B)

C)

12. Se dice que un G es un subgrafo generador de G si contiene:

A) Algunos lados de G B) Todos los lados de G
C) Algunos vrtices de G

29

D)

[
]
D) Todos los vrtices de G

13. El grafo G2 es
G1

[
[
[
[
[
[

]
]
]
]
]
]

G2
B) Complemento de G1
D) Isomorfo bajo vrtices de grado 2 con G1

A) Isomorfo con G1
C) Subgrafo generador de G1

14. Es un grafo en la que siempre existe un camino entre cualquier par de vrtices
A) No conexo
B) Completo
C) Conexo

D) Simple

15. Qu tipo de grafo es el siguiente:

A) Completo (K5)

B) Simple

C) Ponderado

D) Dgrafo

16. Colocando la letra correcta de acuerdo al tipo de grafo (que puede ser de ms de un tipo)
2
2

Grafo ponderado
Grafo no simple
Grafo completo
Dgrafo
Grafo no conexo
Multigrafo

A)

B)

D)

C)

E)

F)

30

TAREA 5.2
1. Coloque una S si el grafo correspondiente contiene un circuito de Euler o una N en caso contrario.
A) K4
B) K9
C) K6
D) K3
a

]
]
]
]

b
c

Basndose en el grafo

[
[
[
[

contestar los cuatro problemas siguientes:

e

2. Cul de las siguientes sucesiones de lados es un camino?

A) (a, b, c, b, a, d)
B) (a, b, c, d, a, b)
C) (a, b, c, d, e, c)

D) (a, b, a, c, a, d)

3. Cul de las siguientes sucesiones de lados es un camino simple?

A) (a, b, c, e, d, a)
B) (a, b, c, d, e, c)
C) (a, b, c, a, d)

D) (a, b, c, e, d)

4. Cul de las siguientes sucesiones de lados es un circuito?

A) (a, c, d, a, b, a)
B) (a, b, c, e, d, c, a)
C) (a, b, c, d, c, a)

D) (a, b, a, c, a)

5. Cul de las siguientes sucesiones de lados es un circuito simple?

A) (a, b, c, e, d, a)
B) (a, b, c, d, c, a)
C) (a, c, e, d, c, a)

[
D) (a, b, c, e, d, c, a)

6. Coloque una S si el grafo correspondiente contiene un circuito de Euler o una N en caso contrario.
A) K11
B) K2
C) K4
D) K7
b
Basndose en el siguiente grafo

c
e

[
[
[
[

]
]
]
]

contestar los cuatro problemas que siguen:

7. Cul de las siguientes sucesiones de lados es un camino?

A) (a, b, c, b, a, e)
B) (a, b, c, d, e, c)
C) (a, b, c, d, a, b)

D) (a, b, a, e, a, b)

8. Cul de las siguientes sucesiones de lados es un camino simple?

A) (a, b, c, d, e)
B) (a, b, c, d, e, c)
C) (a, b, c, a, d)

D) (a, b, c, d, e, a)

9. Cul de las siguientes sucesiones de lados es un circuito?

A) (a, e, c, d, c, a)
B) (a, c, d, a, b, a)
C) (a, b, c, e, d, a)

D) (a, d, e, d, c, a)

10. Cul de las siguientes sucesiones de lados es un circuito simple?

A) (a, b, c, e, d, c, a)
B) (a, b, c, d, e, a)
C) (a, b, c, d, c, a)

[
D) (a, e, d, a, c, b, a)

11. Cul de los siguientes grafos tiene simultneamente un circuito de Euler y un circuito de Hamilton

A)

B)

C)

12. Sucesin de lados que incluye todos los lados de un grafo dado.
A) Circuito de Euler
B) Circuito de Hamilton
C) Circuito Simple

31

D)

D) Circuito

13. En el siguiente grafo, todas las sucesiones de lados representan un circuito de Hamilton EXCEPTO

D
F

A) ACBEDCA

B) ABCDEFA

C) BCDEFAB

D) CAFDEBC

Basndose en los siguientes grafos contestar los cuatro problemas que siguen:

G1

G2

G3

G4

14. Cules grafos tienen simultneamente un paseo y circuito de Euler?

A) G1 y G3
B) G1 y G4
C) G2 y G3

D) G1 y G2

15. Cules grafos no tienen un circuito de Euler?

A) G3 y G4
B) G1 y G2

D) G2 y G3

C) G1 y G3

16. Cul grafo tiene un paseo pero no un circuito de Euler?

A) G1
B) G2
C) G3

D) G4

17. Todos los grafos tienen un paseo de Euler EXCEPTO

A) G2
B) G4

D) G1

C) G3

18. El siguiente grafo tiene un paseo de Euler porque

A) Un nmero impar vrtices tienen grado par

C) Hay al menos dos vrtices de grado impar

B) Hay dos vrtices de grado impar

D) Algunos vrtices tienen grado par

19. El siguiente grafo tendr paseo de Euler, un circuito de Euler o ambos?

A) Circuito NO
Paseo NO

B) Circuito SI
Paseo NO

C) Circuito NO
Paseo SI

D) Circuito SI
Paseo SI

20. En un grafo definimos una camino o paseo de Euler si incluye

A) Todos los vrtices del grafo una y solo una vez
B) Todas las aristas del grafo una y solo una vez pero no a todos los vrtices
C) Todos los vrtices del grafo una y solo una vez pero no todas las aristas
D) Todas las aristas y a todos los vrtices del grafo una y solo una vez
b

21. El siguiente grafo tiene un paseo de Euler porque

A) Un nmero impar vrtices tienen grado par
C) Hay dos vrtices de grado impar

B) Hay al menos dos vrtices de grado impar

D) Algunos vrtices tienen grado par

22. El siguiente grafo contendr un paseo de Euler, un circuito de Euler o ambos?

A) Circuito NO
Paseo SI

B) Circuito SI
Paseo NO

C) Circuito NO
Paseo NO

23. Circuito que incluye todos los vrtices una vez, de un grafo dado:
A) Circuito de Euler
B) Circuito de Hamilton
C) Circuito Simple

32

D) Circuito SI
Paseo SI

D) Circuito

24. En un grafo definimos una camino o paseo de Hamilton si incluye

A) Todas las aristas del grafo una y solo una vez pero no a todos los vrtices
B) Todos los vrtices del grafo una y solo una vez
C) Todas las aristas del grafo una y solo una vez
D) Todos los vrtices del grafo y todas las aristas una y solo una vez

25. El siguiente grafo tendr paseo de Euler, un circuito de Euler o ambos?

26. Para que un grafo no dirigido G contenga un circuito de Euler es necesario que el grafo tenga
A) Todos los vrtices del mismo grado
B) Al menos dos vrtices de grado par
C) Algunos vrtices de grado par
D) Todos los vrtices de grado par

27. El siguiente grafo contendr un paseo de Euler, un circuito de Euler o ambos?

[
D) Para todo n impar

A) Circuito NO
Paseo NO

A) Circuito SI
Paseo SI

B) Circuito SI
Paseo NO

B) Circuito SI
Paseo NO

C) Circuito NO
Paseo SI

D) Circuito SI
Paseo SI

C) Circuito NO
Paseo NO

D) Circuito NO
Paseo SI
C

28. En el siguiente grafo.Cul sucesin de lados es un circuito de Hamilton

D
F

A) ACBEDCA

B) BCDEFACB

C) CAFDEBC

29. Para que valores de n el grafo completo Kn NO contiene un circuito de Euler

A) Para todo n par
B) Para cualquier n 3
C) Para todo n primo

D) CDEBAFDC

30. Basndose en el siguiente grafo, relacionar las columnas considerando que cada una de las sucesiones
de lados es un:

A) (c, e, a, d, e, c)
B) (c, d, e, a, c)
C) (a, b, c, d, e, c)
D) (a, b, c, d, e)

Camino
Camino y Circuito
Camino y Camino Simple
Camino, Circuito y Circuito Simple

c
d

[
[
[
[

]
]
]
]

31. Es un Coloque la letra S si el grafo no dirigido contiene circuito de EULER o una N en caso contrario.
G1
G2
G3
G4
G1
G2
G3
G4

[
[
[
[

]
]
]
]

32. Cul de los siguientes grafos tiene simultneamente un circuito de Euler y un circuito de Hamilton

A)

B)

C)

33

D)

TAREA 5.3
1.

La matriz de adyacencia que representa el siguiente grafo

es:

2.

3.

1
0
1
0
0

1
1
1
1
1

1
0
1
0
1

0
0
1
1
0

B) 0
1
1
1
1

1
0
1
0
0

1
1
0
1
1

1
0
1
0
1

La matriz de adyacencia del grafo completo K3 es:

A) 1 0 0
B) 1 1 1
0 1 0
1 1 1
0 0 1
1 1 1

1
0
1
1
0

1
0
1
0
0

1
1
0
1
1

1
0
1
0
1

0
0
1
1
0

D) 0
1
1
1
0

C) 0 1 1
1 0 1
1 1 0

1
0
1
0
0

1
1
0
1
1

1
0
1
0
1

0
0
1
1
0

D) 1 0 1
1 1 0
0 1 1

La matriz de incidencia que representa un grafo G con todos sus vrtices aislados entre si es:
A) 1 1 1 0 0
B) 1 1 1 1 1
C) 1 0 0 0 0
D)
0 0 1 1 1
0 0 0 1 0
0 1 1 1 1
0 0 0 0 0
1 0 0 0 1
1 0 0 1 0
1 1 0 1 0
0 1 1 0 0
0 1 0 0 1

1
0
1
0

0
1
1
0

1
0
0
0

D) 1
0
0
1

0
1
0
0

0
1
1
0

0
0
1
0

1
0
1
0

0
0
0
1

1
1
0
0

0
0
0
1

0
1
0
1

La matriz de incidencia del grafo completo K3 es:

A) 1 0 0
0 1 0
0 0 1

C) 1
0
1
1
1

4. Cul de las siguientes matrices de incidencia representa un grafo simple?

A) 1 0 1 1 1
B) 1 0 1 1 0
C) 1 1 0
0 1 0 1 0
0 1 0 1 1
0 0 1
0 0 1 0 0
0 1 1 0 0
0 1 0
1 1 0 0 1
0 0 0 0 1
0 0 1
5.

c
e

A) 0
1
1
1
0

B) 1 0 1
1 1 1
0 1 0

C) 1 1 1
1 1 1
0 0 0

D) 1 0 1
1 1 0
0 1 1

6. La matriz de incidencia que representa un grafo G con un exactamente un vrtice aislado es:
A) 1 1 1 0 0
B) 1 1 1 1 1
C) 1 0 0 0 0
D) 1
0 0 1 1 1
0 0 0 1 0
0 1 1 1 1
0
0 0 0 0 0
1 0 0 0 1
1 0 0 1 0
0
1 1 0 1 0
0 1 1 0 0
0 1 0 0 1
0

0
0
1
0

0
0
0
1

0
0
0
1

7. Todas las matrices de Incidencia representan grafos que contienen un paseo de Euler, EXCEPTO
A) 1 0 1 0 1
B) 1 0 1 1 0
C) 0 1 1 1 0
D) 1 1 1
1 1 0 1 0
0 1 1 0 1
0 0 0 1 0
1 0 0
0 1 0 0 1
1 1 0 0 0
1 1 0 0 1
0 0 0
0 0 1 1 0
0 0 0 1 1
1 0 1 0 1
0 1 1

0
1
1
0

0
1
1
0

8. La matriz de adyacencia del grafo completo K4 es:

A) 0 1 1 1
B) 1 1 1 1
1 0 1 1
1 1 1 1
1 1 0 1
1 1 1 1
1 1 1 0
1 1 1 1

0
1
1
1

C) 1
0
0
0

34

0
1
0
0

0
0
1
0

0
0
0
1

D) 1
1
1
0

0
1
0
0

1
1
0
1

1
0
1
1

9. Cul de las siguientes matrices de incidencia representa grafo que contienen un circuito de Euler
A) 0 0 1 1 1
B) 1 1 0 0
C) 1 1 1 0
D) 0 1 1
0 1 1 0 0
0 1 1 0
0 1 0 1
1 0 1
1 1 0 0 1
0 0 1 1
0 0 1 0
0 1 0
1 0 0 1 0
1 0 0 1
1 0 0 1
1 0 0

10. Las siguientes matrices de incidencia representan un grafo completo K3 EXCEPTO:

A) 1 0 1
B) 1 1 0
C) 1 0 1
D) 1 0 1
1 1 0
0 1 1
0 1 0
0 1 1
0 1 1
1 0 1
1 1 1
1 1 0

11. Determine el grafo que corresponde a la siguiente matriz de adyacencia

a
a
b
c
d
e

c
d

A)
b

c
d

B)

12. La matriz de incidencia que representa el siguiente grafo

e6

0
0
0
1
1

e2

0
1
1
0

0
0
1
0
1

0
0
1
1
0

c
d

D)

v2
e1

b
1
0
0
0
0

c
d

C)

0
1
0
0
0

0
0
1
1

es:

v1
v3
e8 e4
e3 e7
v 4 e5 v5

A) 0
1
1
1
0

1
0
1
0
0

1
1
1
1
1

1
0
1
0
1

0
0
1
1
0

B) 0
1
1
1
1

1
0
1
0
0

1
1
0
1
1

1
0
1
0
1

1
0
1
1
0

C) 1
0
1
1
1

1
0
1
0
0

1
1
0
1
1

1
0
1
0
1

0
0
1
1
0

D) 1
1
0
0
0

13. Arreglo numrico en el que no se pueden representar lados paralelos

A) Matriz de Incidencia B) Matriz de Adyacencia
C) Tabla Relacional
14. Cul de las siguientes matrices de incidencia representa un grafo simple?
A) 1 0 0 0 0
B) 1 0 1 1 0
C) 1 1 0 1 0
0 1 0 0 0
0 1 0 1 1
0 0 1 0 1
0 0 1 0 0
0 1 1 0 0
0 1 0 1 1
0 0 0 1 1
1 0 0 0 1
0 0 1 0 0

35

0
1
1
0
0

1
0
0
1
0

0
0
1
0
1

0
0
0
1
1

1
0
1
0
0

1
0
0
0
1

0
0
1
1
0

[
]
D) Funcin de asignacin
[
D) 1
1
0
0

1
1
0
0

1
1
0
0

1
1
0
0

1
1
0
0

TAREA 5.4
1.

Cul es una razn por la que los siguientes grafos no son isomorfos:

A) Sus vrtices tiene grados distintos

C) Algunas de sus aristas se cruzan
2.

Determine una razn por la cual los siguientes grafos son isomorfos
Bajo vrtices de grado 2

B) Se pueden ordenar los vrtices y lados

D) La cantidad de lados es la misma

Determine el nmero de regiones del siguiente grafo aplanable:

A) 11

B) La cantidad de vrtices y aristas es igual

D) La cantidad de caras es la misma

A) Tiene la misma matriz de incidencia

C) Se pueden eliminar vrtices grado 2
3.

B) 7

C) 5

D) 10

Basndose en los siguientes grafos contestar los cuatro problemas que siguen:

G1
G2
4. Cules grafos son de Kuratowski?
A) G2 y G3
B) G1 y G4

G3

G4
C) G2 y G4

D) G1 y G2

5. Cules grafos tienen un circuito de Hamilton?

A) Ninguno
B) Algunos

C) No se sabe

D) Todos

6. Cul grafo es aplanable?

A) G4
B) G3

C) G2

D) G1

7. Cul grafo tiene un circuito de Euler

A) G4
B) G3

C) G2

D) G1

Basndose en los siguientes grafos contestar los cuatro problemas que siguen:

G1
G2
8. Cules grafos son isomorfos?
A) G1 y G3
B) G1 y G2

G3

G4
C) G2 y G3

D) G2 y G4

9. Cules grafos tienen un paseo de Euler?

A) G1 y G3
B) G1 y G2

C) G2 y G3

D) G2 y G4

10. Cul grafo es completo?

A) G1
B) G2

C) G3

D) G4

11. Cules grafos tienen un circuito de Hamilton?

A) Ninguno
B) Algunos

C) Todos

D) No se sabe

12. Si G es un grafo aplanable, cundo un subgrafo G de G ser aplanable?

A) Nunca
B) A veces
C) No siempre

36

D) Siempre

13. Cuntas caras o regiones tiene el siguiente grafo aplanable

A) 6

B) 4

C) 7

B)

C)

B) 7

C) 5

D) 10

16. El grafo G2 es:

G1
G2
A) Complemento de G1
C) Isomorfo con bajo vrtices de grado 2 con G1

[
D)

15. Determine el nmero de regiones del siguiente grafo aplanable:

A) 11

D) 3

14. Determine cul de los siguientes grafos es aplanable

A)

B) Subgrafo generador del G1

D) Subgrafo del G1

17. El Grafo en el cual ninguna arista se cruza con otra se llama:

A) Simple
B) Completo
C) Aplanable

D) Dgrafo

18. Frmula de Euler para grafos aplanables (e=lados, v=vrtices y r=regiones)

A) v = 2 + e + r
B) r = v + e 2
C) e = r + v + 2

D) 2 = v

37

e+r

UNIDAD 6. RBOLES
TAREA 6.1
1. Cul de las siguientes proposiciones es verdadera?
A) Un rbol contiene exactamente un circuito
C) Un rbol de 5 vrtices es isomorfo a K5

[
D) Ms de 11 aristas

[
D) Ms de 9 vrtices

[
D) Ms de 10 aristas

[
D) Conjunto de corte

11. La matriz de incidencia de un rbol de n vrtices consta de

A) n renglones y n columnas
B) (n 1) renglones y n columnas
C) (n 1) renglones y (n 1) columnas
D) n renglones y (n 1) columnas

12. La matriz de adyacencia de un rbol de n vrtices consta de

A) n renglones y n columnas
B) n renglones y (n 1) columnas
C) (n 1) renglones y n columnas
D) (n 1) renglones y (n 1) columnas

13. Cantidad de 1s que tiene la matriz de adyacencia de un rbol de n vrtices

A) n 1
B) 2n 2
C) 2n 1

B) Un rbol es un grafo no conexo

D) Un rbol con 2 o ms vrtices tiene una hoja

2. Para que un grafo con 12 vrtice sea un rbol debe tener

A) 11 aristas
B) 12 aristas
C) Menos de 11 aristas
3. Todas son propiedades de un rbol EXCEPTO
A) Es un grafo en el cual el nmero de aristas es mayor que el nmero de vrtices
B) Es un grafo con e = v 1 que no contiene circuitos
C) Es un grafo en el cual existe un nico paseo entre cada par de vrtices
D) Es un grafo que es conexo
4. Para que una grafo con 9 aristas sea un rbol tiene que tener ...
A) Menos de 9 vrtices B) 8 vrtices
C) 10 vrtices
5.
A)

Todos los siguientes grafos son rboles EXCEPTO

B)

C)

6. Para que un grafo con 10 vrtices sea un rbol tiene que tener...
A) Menos de 10 aristas B) 10 aristas
C) 9 aristas
7.
A)

D)

Cul de siguientes grafos es un rbol

B)

C)

8. Un grafo G=(V,E) conexo con ____________ es un rbol.

A) e = v + 1
B) e = v 1
C) v = e 1
9. Todas son propiedades de un rbol EXCEPTO
A) Entre dos vrtices hay un nico camino
C) Si quitas cualquier arista se hace no conexo

D)

D) e = v + 2

B) Es no conexo
D) No tiene ciclos

10. Un grafo no dirigido conexo que no contiene circuitos recibe el nombre de:
A) rbol generador
B) Subrbol
C) rbol

38

D) 2n

TAREA 6.2
1. Un grafo dirigido es un rbol dirigido si se convierte en un rbol cuando se ignora:
A) Las direcciones de las aristas
B) Los vrtices
C) El grado de salida de los vrtices
D) El grado de entrada de los vrtices

2. Un vrtice de un rbol con grado igual a 1 se conoce como nodo:

A) Hoja
B) Rama
C) Padre

D) Hermano

3. Un vrtice de un rbol enraizado con grado de salida 0 se conoce como nodo:

A) Rama
B) Hoja
C) Padre

D) Raz

4. Un vrtice de un rbol enraizado con grado de salida diferente de 0 se conoce como nodo:
A) Rama
B) Hoja
C) Padre

D) Raz

5. Un vrtice de un rbol enraizado con grado de entrada 0 se conoce como nodo:

A) Rama
B) Hoja
C) Padre

D) Raz

6. Es un rbol donde cada nodo rama tiene exactamente m hijos

A) rbol enraizado
B) rbol de bsqueda binaria
C) rbol mario

[
]
D) rbol mario regular

7. Es un rbol donde cada nodo rama tiene a lo ms m hijos

A) rbol enraizado
B) rbol de bsqueda binaria
C) rbol mario

[
]
D) rbol mario regular

8.

Determine las caractersticas del siguiente rbol

A) Enraizado, ternario, altura 3

C) Enraizado, binario, altura 3

B) Enraizado, ternario, altura 4

D) Enraizado, binario, altura 4

Basados en los siguientes rboles, contestar los cuatro problemas que siguen:

T1

T2

T3

T4

9. Todos son rboles marios regulares EXCEPTO

A) T1
B) T2

C) T3

D) T4

10. Es un rbol ternario de altura 4

A) T1
B) T2

C) T3

D) T4

11. Es un rbol binario

A) T1

B) T2

C) T3

D) T4

12. Son conexos

A) Ninguno

B) Algunos

C) Solamente T3

D) Todos

39

Dados los siguientes rboles contestar los cuatro problemas que siguen:

T1

T2

T3

T4

13. Cul es ternario regular

A) T3
B) T4

C) T2

D) T1

14. Cules son marios regulares

A) T1 y T3
B) T2 y T3

C) T2 y T4

D) T1 y T4

15. Cules son marios no regulares

A) T1 y T3
B) T2 y T3

C) T2 y T4

D) T1 y T4

16. Cules son binarios

A) T1 y T3
B) T2 y T3

C) T2 y T4

40

D) T1 y T4

TAREA 6.3
1. Cul de siguientes conjuntos es un cdigo de prefijos
A){1,001,01,010}
B) {1,011,010,001,000}

C) {1,00,01,000,0001}

[
D) {1,01,10,000,001}

2. Todos los siguientes conjuntos son cdigos de prefijos EXCEPTO

A){1,01,001,000}
B){1,01,10,000,001}
C){11,10,01,000,001}

[
]
D){1,011,010,001,000}

3. Cul de siguientes conjuntos representa un cdigo de prefijos

A){0000,01,11,010,101} B){0000,01,11,001,101}
C){101,010,11,000,01}

[
]
D){000,0001,11,01,101}

4.

Determine cul de los siguientes rboles binarios representa el cdigo de prefijos {0000,11,001,101,01}

A)

5.

B)

C)

B){0,10,110,111}

C){001,110,00,10}

D)

Cul es el cdigo de prefijos obtenido del siguiente rbol binario

A){1,01,001,000}

D){00,11,000,111}

6. Coloque una S si el conjunto de sucesiones binarias dado define un cdigo de prefijos y una N en caso contrario44
{0000, 0001, 0010, 10, 01}
[
{1111, 1100, 1010, 10, 01}
[
{1101, 0100, 1101, 10, 01}
[
{0000, 0001, 1101, 10, 01}
[

41

]
]
]
]

TAREA 6.4
Dados los siguientes rboles, contestar los cuatro problemas que siguen:
15

12

10

18

15

12
6

10
6

8 14
14

14

18

8 12

10

18
15

T1

T2

T3

1. Es un rbol de bsqueda binaria

A) T1
B) T2

C) T3

D) Todos

2. Es un rbol binario
A) T1
B) T2

C) T3

D) Todos

3. Es un rbol binario regular

A) T1
B) T2

C) T3

D) Ninguno

4. Es un rbol enraizado
A) T1
B) T2

C) T3

D) Todos

Dados el siguiente grafo, contestar los cuatro problemas que siguen:

b

e2

e3

h
e4

e9

e1

e10
e
e7

e8
c

e11
g
e6

e5
f

5. Es un rbol generador del grafo

A) {e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11}
C) {e1, e2, e3, e4, e6, e9, e10}

B) {e1, e2, e3, e4, e5, e6, e7, e8}

D) {e1, e2, e3, e4, e5, e8}

6. Es un conjunto de corte
A) {e1, e2, e3, e4, e5, e6} B) {e1, e2, e3, e4, e5, e10}

C) {e1, e4, e9, e10, e11}

[
]
D) {e1, e4, e5, e9, e10, e11}

7. Es un rbol del grafo

A) {e1, e2, e3, e4, e6, e10} B) {e1, e2, e3, e4, e6, e7, e11}

C) {e1, e2, e3, e4, e5, e10}

[
]
D) {e1, e2, e3, e4, e5, e8, e9}

8. Si {e1, e2, e3, e4, e5, e7, e9} es un rbol de dicho grafo, encontrar su complemento
A) {e1, e2, e3, e4, e5}
B) {e6, e8, e10, e11}
C) {e1, e4, e5, e8}

D) {e6, e7, e10, e11}

Dados el siguiente grafo pesado, contestar los tres problemas que siguen:
b
2
g
1 3 3

a 2

9. Es el peso que debe tener su rbol generador mnimo

A) 37
B) 10

d4
4
5

C) 14

42

c
3 1
h
d
7 3
e

D) 29

10. Ser (a, b, h, g, f, e, d} un rbol del grafo?

A) Si
B) No

C) No se sabe

D) Faltan datos

11. Ser (a, b, h, g, f, e, d} un rbol generador del grafo

A) Si
B) No

C) No se sabe

D) Faltan datos

12. Cul ser el peso del rbol generador mnimo del grafo

2
8

6
4
A) 18

B) 25

C) 5

43

D) 7