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


Recorrido en anchura: El recorrido en anchura supone recorrer el grafo, a partir de un nodo dado, en niveles, es decir, primero los que están a una distancia de un arco del nodo de salida, después los que están a dos arcos de distancia, y así sucesivamente hasta alcanzar todos los nodos a los que se pudiese llegar desde el nodo salida.
Recorrido en profundidad: el recorrido en profundidad trata de buscar los caminos que parten desde el nodo de salida hasta que ya no es posible avanzar más. Cuando ya no puede avanzarse más sobre el camino elegido, se vuelve atrás en busca de caminos alternativos, que no se estudiaron previamente
reV

REPRESENTACION DE GRAFOS EN PROGRAMAS


Hay tres maneras de representar un grafo en un programa: mediante matrices, mediante listas y

mediante matrices dispersas.
Representación mediante matrices: La forma más fácil de guardar la información de los nodos es

mediante la utilización de un vector que indexe los nodos, de manera que los arcos entre los nodos se

pueden ver como relaciones entre los índices. Esta relación entre índices se puede guardar en una

matriz, que llamaremos de adyacencia.



Representación mediante listas: En las listas de adyacencia lo que haremos será guardar por cada nodo, además de la información que pueda contener el propio nodo, una lista dinámica con los nodos a los que se puede acceder desde él. La información de los nodos se puede guardar en un vector, al igual que antes, o en otra lista dinámica.



Representación mediante matrices dispersas: Para evitar uno de los problemas que teníamos con las listas de adyacencia, que era la dificultad de obtener las relaciones inversas, podemos utilizar las matrices dispersas, que contienen tanta información como las matrices de adyacencia, pero, en principio, no ocupan tanta memoria como las matrices, ya que al igual que en las listas de adyacencia, sólo representaremos aquellos enlaces que existen en el 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.