Grafos y arboles

GRAFOS
Es un diagrama que consta de un conjunto de elementos denominados nodos o vértices “v” y un listado de pareja. Conjunto de pareja que expresa la relación entre dichos elementos.
También conocido como representación grafica de los datos de una situación particular.

Datos: Relación entre ellos que no son precisamente jerárquica.

Se suelen usar muchos nombres al referirnos a loselementos de una estructura de datos. Algunos de ellos son:
 “elemento”.
 “ítem”.
 “asociación de ítems”.
 “registro”.
 “nodo”.
 “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 una terna 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

Línea que une a susdos vértices y con la que se construyen también caminos. Es decir, se simbolizan con líneas (unión de un vértice con otro) se les asigna un numero a la combinación de ambos.



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.

Clasificación o tipos de lasaristas:

 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. Unen a un nodo con otro y tienen relación con un par de vértices.
 Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
 Cruce: Son dos aristas que cruzan en unpunto.

Vértices

Son los puntos o nodos con los que está conformado un grafo. Es decir se indica por medio de un circulo y se les asigna un nodo o una letra.



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 tenemosun 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.

Caminos

Sean x, y “ V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía de aristas {x,v1}, {v1,v2},..., {vn,y}. En este caso
 x e y sellaman los extremos del camino
 El número de aristas del camino se llama la longitud del camino.
 Si los vértices no se repiten el camino se dice propio o simple.
 Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.
 Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.
 Llamaremos ciclo a un circuitosimple
 Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es accesible respecto a si mismo

Clasificación de grafos

Los grafos se pueden clasificar en dos grupos:

No Dirigidos: En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco.

Dirigidos:En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.


Grafos dirigidos y no dirigidos.

Ejemplos
G1 = (V1, A1)
V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}
G2 = (V2, A2) V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)}
G3 = (V3, A3)
V3 =...