Document related concepts
Transcript
INF-526 Estructura de Datos MATRICULA ______________ Control de Lectura No. 7 Elaborado por: Mtro. Angel Asencio Tópico 7 NOMBRE ______________________________________________________ TEMA I. Realice el siguiente apareamiento: a) ___ Es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. b) ___ Es aquel que se define con la capacidad de poder contener aristas dirigidas y no dirigidas. c) ___ Es un árbol de grado 2, donde cada nodo tiene de 0 a 2 descendientes directos: el hijo izquierdo y el derecho. d) ___ Grafo en el que las aristas no están ordenadas. e) ___ Árbol en el que cualquier nodo puede tener cualquier número de hijos. f) ___ Grafo en el que las aristas son pares ordenados. g) ___ Es una colección de elementos entre los cuales existe una estructura jerárquica definida mediante una relación de paternidad entre los elementos. h) ___ Es un arbol binario y sus nodos son sub-árboles de búsqueda binarios y contienen información ordenada de tal que todos los elementos a la izquierda de la raíz son menores a la raíz y todos lo elementos a la derecha de la raíz son mayores a la raíz. 1) Arbol 2) Arbol Binario 3) Arbol general o multicamino 4) Árboles Binarios de Búsqueda (ABB) 5) Grafo 6) Grafo dirigido 7) Grafo no dirigido 8) Grafo mixto TEMA II. Relacione cada ítem de la izquierda con su correspondiente de la derecha: ____ Nodo que tiene al menos un hijo. ____ Existe si hay una sucesión de nodos que permitan llegar desde el nodo X hasta el nodo Y. ____ Nodo que no tiene hijos ____ Árbol formado por un nodo y sus descendientes. ____ Número de descendientes directos ____ Número de predecesores. ____ Profundidad máxima de cualquier nodo ____ Único nodo sin padre ____ Mayor grado de sus nodos 1. Raiz 2. Nodo interno 3. Nodo hoja (externo) 4. Descendiente 5. Descendiente directo 6. Subarbol 7. Arbol ordenado 8. Grado de un nodo 9. Grado del arbol 10. Profundidad de un nodo 11. Altura del Arbol 12. Camino TEMA III. Relacione cada ítem de la izquierda con su correspondiente de la derecha: ____ Número de aristas del camino = nº de nodos -1 ____ Aquel en el que todos los vértices son distintos (excepto el primero y el último que pueden ser iguales). ____ Es un grafo en el que cada arista tiene asociada una etiqueta o valor de cierto tipo. ____ Es una secuencia w1, w2, ..., wq V, tal que todas las aristas (w1, w2), (w2, w3), ..., (wq-1, wq) A.. ____ Es un grafo en el que existe una arista entre cualquier par de vértices ____ Grafo etiquetado con valores numéricos ____ Son todos los nodos unidos a v mediante una arista. ____ Es un grafo en el que hay un camino entre cualquier par de vértices ____ Número de arcos que inciden en él. Nodos adyacentes a un nodo v 1. Grafo etiquetado 2. Grafo con pesos 3. Camino de un vértice w1 a wq 4. Longitud de un camino 5. Camino simple 6. Ciclo 7. Ciclo simple 8. Subgrafo 9. Vértices conectados 10. Grafo conexo o conectado 11. Grafo completo 12. Grado de un vértice v 13. Matriz De Adyacencia TEMA IV. a) Explique la relación existente entre grafo y arbol. b) Dé ejemplo de en cuales situaciones se puede aplicar un árbol y en cuales se aplica grafos.
