A. Lea
detenidamente cada uno de los siguientes enunciados y elija una sola
opción que
corresponda a lo planteado.
1. ¿Una
gráfica dirigida consiste en?
a. Un
conjunto de vértices y en un conjunto de aristas, tal que cada arista se
asocia con un
par no ordenado de vértices
b. Un
conjunto de pesos en sus aristas
c. Un
conjunto de vértices y en un conjunto de aristas, tal que cada arista se
asocia con
un par ordenado de vértices
2. ¿Un
vértice aislado es aquel que?
a. Incide en
sus aristas
b. No incide
en ninguna arista
c. No consta
de lazos ni aristas paralelas
3. Un árbol
binario es aquel árbol con raíz en el que:
a. Cada
vértice tiene más de dos hijos
b. Cada
vértice tiene ningún hijo, un hijo o dos hijos
c. Cada
vértice tiene ningún hijo
4. ¿Cuál es
una de las condiciones que se debe satisfacer en una red de transporte?
a. Que un
vértice designado, el origen o fuente, no tenga aristas salientes
b. Que un
vértice designado, el origen o fuente, no tenga aristas entrantes
c. Que un
vértice designado, el origen o fuente, no tenga aristas
5. Un árbol
es una gráfica simple que satisface ¿qué condición?
a. Qué v y w
sean aristas, entonces existe una trayectoria simple única de v
a w
b. Qué v y w
sean vértices, entonces existe una subgráfica entre v y w
c. Que v y w
sean vértices, entonces existe una trayectoria simple única de
v a w
6. Un árbol
T se define como:
a. Aquel en
el cual un vértice se define como raíz
b. Una
gráfica simple en la cual existe una trayectoria única entre sus vértices.
c. Un árbol
en el cual su altura siempre es mayor a 2
7. En un
árbol de definición jerárquica:
a. Solo
puede poseer 2 nodos por cada nivel
b. Muestra
las relaciones entre los registros de una base de datos
c.
Representa los valores de sus nodos como cadenas de bits
8. Un árbol
es una gráfica conexa cuando:
a. Contiene
al menos un ciclo simple
b. Existe
una trayectoria simple de cualquier vértice a cualquier otro.
c. Los
vértices forman una gráfica acíclica.
9. Una
gráfica tiene un árbol de expansión cuando:
a. La
gráfica presenta varios ciclos.
b. La
gráfica es conexa y acíclica.
c. La
trayectoria desde el vértice 1 al vértice n es 1
10. Un árbol
de expansión mínima:
a. Es un
árbol de expansión de G con peso mínimo
b.
Representa un árbol con altura 2
c.
Representa un árbol con vértices de trayectoria simple.
11. El
algoritmo de Prim:
a. Realiza búsquedas
en anchura en un árbol
b. Agrega
aristas a un árbol hasta obtener un árbol de expansión mínima
c. Realiza
la eliminación de aristas en un árbol.
12. En un
árbol binario completo:
a. Cada
vértice del árbol puede tener más de 2 hijos
b. Todo
vértice del árbol tiene cero o dos hijos
c. La raíz
del árbol debe tener al menos 1 vértice
13. El
recorrido preorden de un árbol binario:
a. Primero
se visita el nodo izquierdo, luego el nodo raíz, y al final el nodo
derecho
b. Primero
de visita el nodo raíz, luego el nodo izquierdo y finalmente el
nodo derecho
c. Comienza
en la raíz y luego visita los nodos en forma horizontal de
derecha a
izquierda.
14. Los
árboles de decisión permiten:
a. Demostrar
que el algoritmo representado por el árbol es óptimo
b.
Representar una jerarquía de funciones
c. Balancear
los nodos del árbol
15. Un
procedimiento minimax se da cuando:
a. El
círculo busca el mínimo de sus hijos y el cuadro busca el máximo de
sus hijos
b. Se
realiza una búsqueda en anchura en un árbol binario
c. Se
recorre un árbol binario en preorden.
16. Una red
de transporte es una gráfica dirigida que posee:
a. Un
vértice llamado destino que no tiene aristas salientes
b. Un peso C
llamado capacidad que es un número negativo
c. Aristas
que no están conectadas entre si.
17. Los
flujos de una red de transporte:
a. No puede
exceder la capacidad definida para una arista
b. Puede
superar la capacidad de una arista
c.
Consideran los vértices fuente y destino para medir la capacidad.
18. Un flujo
máximo en G se define como:
a. El mayor
valor que puede alcanzar un flujo en una red de transporte
b. El flujo
que tiene la mayor cantidad de aristas
c. El flujo
cuyas capacidades se mantienen con valores negativos
19. Un corte
P en una red transporte es:
a. El
conjunto de vértices con valor negativo
b. El
conjunto de vértices etiquetados
c. El
conjunto de vértices no etiquetados
20. Se
define capacidad de corte a:
a. La suma
de las capacidades de las aristas pertenecientes al corte S
b. El valor
de la interrupción del flujo en la red
c. La
diferencia de las capacidades de un grupo de aristas determinado
21. Una
asignación máxima para una gráfica G bipartita con conjuntos ajenos de
vértices V y
W:
a. Se trata
de un conjunto de aristas que no tienen vértices en común
b. Se trata
de un conjunto de aristas cuya suma de capacidades es 0
c. Consiste
en una asignación E que contiene el máximo número de aristas
22. Una red
de acoplamiento
a. Es una
gráfica bipartita dirigida donde las aristas están dirigidas de los
vértices en
V a los vértices en W
b. Es una
red de transporte con flujos de capacidad con valor 0
c. Es una
gráfica dirigida con un nodo de origen y un nodo de destino
23. Un flujo
en una red de acoplamiento
a. Tiene una
capacidad de 0
b. Conecta
aristas de vértice común
c. Da una
asignación en la gráfica G
24. Un
acoplamiento completo:
a. Se da una
asignación en la gráfica para todos los vértices V y W
b. Tiene
flujos de capacidad 0
c. No
requiere de una arista de origen y una de destino
25. Si una
arista “e” es dirigida desde la fuente hacia el destino se dice que tiene:
a. Un flujo
mínimo de 0
b. Una
orientación apropiada
c. Una
orientación inapropiada
26. Una
gráfica G es conexa si:
a. Dados
cualesquiera dos vértices v y w en G, no existe una trayectoria de
v a w.
b. Dados
cualesquiera dos vértices v y w en G, existe una trayectoria de v a z.
c. Dados
cualesquiera dos vértices v y w en G, existe una trayectoria de v a
w.
27. Un ciclo
de Euler es:
a. Un ciclo
que incluye algunas de las aristas y todos los vértices de G.
b. Un ciclo
que incluye todas las aristas y todos los vértices de G.
c. Un ciclo
que incluye todas las aristas y algunos de los vértices de G.
28. Si una
gráfica es conexa, ¿cuántos componentes debe tener?
a. Ninguna
b. Dos
c. Una
29. El grado
de un vértice v es:
a. El número
de aristas que inciden en v.
b. El número
de vértices que inciden en v.
c. El número
de aristas que no inciden en v.
30. Diga si
la trayectoria (b,b) en la gráfica es una trayectoria simple, un ciclo, ó un
ciclo
simple.
a. Es un
ciclo
b. Es un
ciclo, ciclo simple
c. Es una
trayectoria simple
PRUEBA DE
ENSAYO
En cada uno
de los siguientes enunciados subraye el literal de la respuesta correcta.
Estrategias
de trabajo:
Desarrollar
el trabajo a distancia tomando en consideración las siguientes
recomendaciones:
99 Revise la
guía didáctica unidad 3, 4 y 5 paralelamente con el texto básico
el capítulo
de Teoría de gráficas, Árboles y Modelos de redes para poder
resolver los
ejercicios del 1 al 10.
1. ¿En qué
orden se procesan los vértices del siguiente árbol si se usa el recorrido
preordenado?
a.
CEDBIJHGFA
b.
CBDEAFIHJG
c.
ABCDEFGHIJ
2. Decida si
la gráfica tiene un ciclo de Euler ó Hamilton, y escriba su trayectoria.
a. Si tiene
ciclo de Hamilton, si tiene un ciclo de Euler.
b. No tiene
ciclo de Hamilton, no tiene un ciclo de Euler.
c. No tiene
ciclo de Hamilton, si tiene un ciclo de Euler.
3. La
longitud de la ruta (v1, e1, v2, e2, v4) del siguiente grafo es:
a. 1
b. 0
c. 2
