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 unpunto 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.
▪ AristasAdyacentes: 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 estaconformado 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...
tracking img