Estructura De Datos

Examen lunes 07 de mayo 2012
* ÁRBOLES BINARIOS
* Definición
* Operaciones básicas con arboles
* Altura
* Recorridos
* ÁRBOLES BINARIOS DE BUSQUEDA
* Definición
* Operaciones en ABB
* Mínimo y máximo sucesor y predecesor
* Buscar un elemento
* Insertar un elemento
* Borrar un elemento
* Movimientos
*Arboles degenerados
* ARBOLES AVL
* Definición
* Operaciones AVL
* Factor de equilibrio
* Rotaciones simple
* Rotaciones dobles
* Reequilibrados

* GRAFOS
* Conceptos básicos
* Definición formal con peso es V{(a,b,6)}
* Definición informal
* Grafo no dirigido
* Grafo conexo
* Matriz de adyacencia* Representación por lista de adyacencia
* Algoritmos de recorrido
* Algo de dijsktra
* Algo de Prim árbol de expiación mínima
* Algo de Floyd Warshall

Examen
Un Tema Práctico
Teórico

* GRAFOS:
Definición informal: Un grafo es formado por un conjunto de vértices (o nodos) y un conjunto de aristas que conectan vértices distintos, con almínimo una arista conectando un par de vértices.El grafo se representa con el par G = (V, A), donde V es el conjunto devértices y A el conjuntode arcos.
Definición formal:
V = {1, 4, 5, 7,9}
A = {(1,4), (4,1), (1,5), (5,1), (5,7), (7,5), (7,9), (9,7), (9,4),(4,9)}

Características:
-Grafos no dirigidos: Un arco o arista representa una relación entre dos nodos o vértices. Esta relación, alestar formado por dos nodos se representa por (u, v) siendo u, v el par de nodos. El grafo es no dirigido si los arcos están formados por pares de nodos no ordenados; se representa con un segmento uniendo los nodos u – v.
-Grafos dirigidos:Un grafo es dirigido, también conocido como disgrafo, si los pares de nodos que forman los arcos son ordenados; serepresentan con una flecha queindica ladirección de la relación, u -> v.

V = {C,D,E,F,H }
A = {(C,D), (D,F), (E,H), (H,E), (E,C)}

Dado el arco (u, v) de un grafo, se dice que los vértices u y v son adyacentes. Si el grafo es dirigido, el vértice "u es adyacente a v", y "v es adyacente de u".

En los modelos realizados con grafos, a veces, una relación entre dos nodos tiene asociada información,denominada factor de peso, en cuyo caso se dice que es un grafo valorado o grafo con peso también podemos encontrar el termino ponderado para denominar esto.
El grado es una característica que se refiere a los nodos de un grafo. En un grafo no dirigido, elgrado de un nodo es el número de arcos que contienen al nodo. En un grafo dirigido se distingueentre grado de entrada y grado de salida; gradode entrada de un nodo es el número de arcos quellegan (entran) al nodo y grado de salida es el número de arcos que salen del nodo.
Un camino (path) P de longitud n desde el vértice v0 a vn en un grafo G, es la secuencia de n+1vérticesv0, v1,v2,..., vn tal que (vi, vi+1) Є A (arcos) para 0 ≤ i ≤ n.
Un camino P = {v0, v1, v2,...,vn} es simple si todos los nodos que forman el camino son distintos,pudiendo ser iguales v0 y vn (los extremos del camino).
En un grafo dirigido, un ciclo es un camino simple cerrado. Por tanto, un ciclo empieza y terminaen el mismo nodo, v0 = vn y además debe tener más de un arco. Un grafo dirigido sin ciclos se conoce como Grafo Dirigido Acíclico.
Un grafo no dirigido es conexo si existe un camino entre cualquier par de nodos que forman elgrafo. Un grafodirigido, que tiene un camino entre cualquier par de nodos que forman el grafo se conoce como grafo fuertemente conexo.

Representaciones:
Matriz de adyacencia: La característica más importante de un grafo, es el conjunto depares de vértices que estánrelacionados, en otras palabras que son adyacentes. La forma más simple derepresentar estarelación es con una matriz, de tantas...