Grafos y arboles

GRAFOS Y ARBOLES

GRAFO


Es un conjunto de puntos y un conjunto de líneas, cada una de las cuales une un punto con otro. Los puntos se llaman nodos o vértices de un grafo y las líneas se llaman aristas o arcos.


¿QUÉ ES UN NODO?

Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él.

Aristas
Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.

Aristas Adyacentes:
Se dice que dos aristas son adyacentes si coinciden 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 esta 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 un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.

Vértice Aislado: Es un vértice de grado cero.

Vértice Terminal: Es un vértice de grado 1.

CLASIFICACION DE LOS GRAFOS


* DIRIGIDOS

Cada arco esta representado por un par ordenado de vertices, de forma que representan dos arcos diferentes.

* NO DIRIGIDOS

En este el par de vertices que representa un arco no esta ordenado


TIPOS DE GRAFOS


Grafo regular: Aquel con el mismo grado en todos los vértices.

Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto

Grafo completo: Aquel con una arista entre cada par de vértices

Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.

Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.

Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro





Grafos conexos: Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: “un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une”.
Grafos dirigido (bigrafo): A un grafo dirigido se le puede definir como un grafo que contiene aristas dirigidas, como en el siguiente caso.
RECORRIDOS DE UN GRAFO






ARBOLES




Los arboles son estructuras de datos no lineales.

Un árbol se define como una colección de nodos donde cada uno además de almacenar información, guarda las direcciones de sus sucesores.


Partes de un arbol



Hijo: Es aquel nodo que siempre va a tener un nodo antecesor o padre, son aquellos que se encuentran en el mismo nivel

Padre: Es aquel que tiene hijos y también puede tener o no antecesores.

Hermano: Dos nodos son hermanos si son apuntados por el mismo nodo, es decir si tienen el mismo padre.

Raíz: Es el nodo principal de un árbol y no tiene antecesores.
Hoja o terminal: Son aquellos nodos que no tienen hijos o también los nodos finales de un árbol.

Interior: Se dice que un nodo es interior si no es raíz ni hoja.



Nivel de un nodo: Se dice que el nivel de un nodo es el numero de arcos que deben ser recorridos, partiendo de la raíz para llegar hasta el.

Altura del árbol: Se dice que la altura de un árbol esel máximo de los niveles considerando todos sus nodos.

Grado de un nodo: se dice que el grado de un nodo es el número de hijos que tiene dicho nodo.

Grado del árbol: se dice que es el grado de un árbol es el máximo de los grados considerando todos sus nodos.


TIPOS DE ARBOLES

* Binario : Son arboles donde cada nodo solo puede apuntar a dos nodos.
* Binario de busqueda: Son arboles binarios ordenados.
* Arboles B: Arboles cuyos nodos pueden tener un numero multiple de hijos.