Grafos y arboles

Universidad Nacional Experimental
De Los Llanos Occidentales
Ezequiel Zamora
Unellez
Barinas

INTEGRANTE:

Gómez Eleazar C.I. 19.071.108

Ing. En Informática
Sección: ES-02N.

Barinas, Noviembre de 2011

Índice
Grafos 2
Grafos 2
Aristas 2
Vértices3
Caminos3
Clasificación de grafos4
Grafos Eulerianos5
Grafos Conexos6
 Árboles6
Bosques deárboles6
Recorrido de un grafo6
Representación de grafos en programas7
Dígrafo (grafo dirigido)8
Aplicaciones de los dígrafos8
Grado de un grafo 8
Ciclo de un grafo8
Arboles Binarios8
Grado de un grafo 8
Ciclo de un grafo8
Arboles Binarios8
Árbol binario de búsqueda 9
Operaciones básicas10
Recorrido de un Árbol Binario10
Recorre el árbol por subárboles10
Clasificación deArboles Binarios11
Operaciones de árboles. Representación13
Uso de los árboles13

Introducción

Hoy en día podemos ver muchas cosas que nos pueden parecer de lo más cotidianas, carreteras, líneas telefónicas, líneas de televisión por cable, el transporte colectivo metro, circuitos eléctricos de nuestras casas, automóviles, y tantas cosas más; lo que no pensamos frecuentemente es que estos formanparte de algo que en matemáticas se denomina como grafos.
En este trabajo se tratará de explicar lo que son los grafos y arboles, sus tipos, y algunas derivaciones de ellos, así como su representación gráfica y en algunos casos su representación en algún programa informático.

Grafos
Desafortunadamente no existe una terminología estandarizada en la teoría de los grafos, por lo tanto es oportunoaclarar que las presentes definiciones pueden variar ligeramente entre diferentes publicaciones de estructura de datos y de teoría de grafos, pero en general se puede decir que un grafo como indica su nombre lo indica es la representación (para nuestro caso) gráfica de los datos de una situación particular, ejemplo:
Los datos contienen, en algunos casos, relaciones entre ellos que no esnecesariamente jerárquica. Por ejemplo, supongamos que unas líneas aéreas realizan vuelos entre las ciudades conectadas por líneas como se ve en la figura anterior (más adelante se presentaran grafos con estructuras de datos); la estructura de datos que refleja esta relación recibe el nombre de grafo.
Se suelen usar muchos nombres al referirnos a los elementos de una estructura de datos. Algunos de ellosson "elemento", "ítem", "asociación de ítems", "registro", "nodo" y "objeto". El nombre que se utiliza depende del tipo de estructura, el contexto en que usamos esa estructura y quien la utiliza.
En la mayoría de los textos de estructura de datos se utiliza el término "registro" al hacer referencia a archivos y "nodo" cuando se usan listas enlazadas, árboles y grafos.
También un grafo es unaterna G = (V,A,j ), en donde V y A son conjuntos finitos, y j es una aplicación que hace corresponder a cada elemento de A un par de elementos de V. Los elementos de V y de A se llaman, respectivamente, "vértices" y "aristas" de G, y j asocia entonces a cada arista con sus dos vértices.

Aristas
Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une.
Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.
* Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.
* Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.
*Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
* Cruce: Son dos aristas que cruzan en un punto.
Vértices
Son los puntos o nodos con los que está conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.
* Vértices Adyacentes: si tenemos un par de vértices de...