evaluacion resuelta utpl matematicas discretas enero 2017

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