Grafos - programacion

Grafos
es la representación (para nuestro caso) gráfica de los datos de una situación particular, ejemplo:
La estructura de datos q se utiliza cuando se usan listas enlazadas, árboles y grafos es "nodo".

Un grafo se define como 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 deA se llaman, respectivamente, "vértices" y "aristas" de G, y j asocia entonces a cada arista con sus dos vértices.
Esta definición da lugar a una representación gráfica, en donde cada vértice es un punto del plano, y cada arista es una línea que une a sus dos vértices.

Aristas
Son las líneas con las que se unen los vértices de un grafo y con la que se construyen también caminos.
Si laarista 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 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 unpar 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.

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 se llaman 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 soniguales, el camino se llama circuito o camino cerrado.
▪ Llamaremos ciclo a un circuito simple
▪ 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
Podemos clasificar los grafos en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa unarco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.

Teniendo

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)}

Gráficamente estas tres estructuras de vértices y arcos se pueden representar de la siguiente manera:

[pic]
Algunos de los principales tipos de grafos son los que se muestran a continuación:

1. Grafo regular: Aquel con el mismo grado (numero de nodos que conectados a un nodo)en todos los vértices. Si ese grado es k lo llamaremos k-regular.

Por ejemplo, el primero de lossiguientes grafos es 3-regular, el segundo es 2-regular y el tercero no es regular

[pic]
1. Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos (si no tienen elementos en común) de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto

Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es
[pic]
3....