Notas y más : Terminología (Grafos

La terminología que manejaremos regularmente para el uso de grafos es la siguiente:

• CAMINO.Es una secuencia de vértices V1, V2, V3, ... , Vn, tal que cada uno de estos V1-&gtV2, V2-&gtV3, V1-&gtV3.

• LONGITUD DE CAMINO. Es el número de arcos en ese camino.

• CAMINO SIMPLE. Es cuando todos sus vértices, excepto tal vez el primero y el último son distintos.

• CICLO SIMPLE. Es un camino simple de longitud por lo menos de uno que empieza y termina en el mismo vértice.

• ARISTAS PARALELAS. Es cuando hay más de una arista con un vértice inicial y uno terminal dados.

• GRAFO CICLICO. Se dice que un grafo es cíclico cuando contiene por lo menos un ciclo.

• GRAFO ACICLICO. Se dice que un grafo es aciclíco cuando no contiene ciclos.

• GRAFO CONEXO. Un grafo G es conexo, si y solo si existe un camino simple en cualesquiera dos nodos de G.

• GRAFO COMPLETO ó FUERTEMENTE CONEXO.Un grafo dirigido G es completo si para cada par de nodos (V,W) existe un camino de V a W y de W a V (forzosamente tendrán que cumplirse ambas condiciones), es decir que cada nodo G es adyacente a todos los demás nodos de G.

• GRAFO UNILATERALMENTE CONEXO.Un grafo G es unilateralmente conexo si para cada par de nodos (V,W) de G hay un camino de V a W o un camino de W a V.

• GRAFO PESADO ó ETIQUETADO. Un grafo es pesado cuando sus aristas contienen datos (etiquetas). Una etiqueta puede ser un nombre, costo ó un valor de cualquier tipo de dato. También a este grafo se le denomina red de actividades, y el número asociado al arco se le denomina factor de peso.

• VERTICE ADYACENTE. Un nodo o vértice V es adyacente al nodo W si existe un arco de m a n.

• GRADO DE SALIDA.El grado de salida de un nodo V de un grafo G, es el número de arcos o aristas que empiezan en V.

• GRADO DE ENTRADA.El grado de entrada de un nodo V de un grafo G, es el número de aristas que terminan en V.

• NODO FUENTE.Se le llama así a los nodos que tienen grado de salida positivo y un grado de entrada nulo.

• NODO SUMIDERO.Se le llama sumidero al nodo que tiene grado de salida nulo y un grado de entrada positivo.

• 4.2.1 TERMINOLOGÍA DE GRAFOS

• Un grafo se compone por un conjunto de V vértices y un conjunto de A aristas. Cadaarista se identifica con el par de vértices que une. Los vértices de una arista sonentre si nodos adyacentes.

• - Grado de un nodo:

• Numero de aristas que contiene ese nodo. Si el grado de unnodo es 0, se dice que es un nodo aislado.

• - Grado de un grafo:

• Números de vértices de ese grafo.

• - Camino:

• Un camino C de longitud N de un nodo V1 a un nodo V2, se define comola secuencia de nodos por los que hay que pasar para llegar del nodo V1 a V2. Lalongitud es el numero de aristas que comprende el camino.El camino es cerrado si empieza y termina en el mismo nodo. El camino es simple sitodos los nodos de dicho camino son distintos a excepción de los de los extremosque pueden ser iguales.

• - Bucles:

• Aristas cuyos extremos son idénticos.

• - Aristas múltiples:

• Dos o mas aristas que conectan los mismos nodos.

• Tipos de grafos:

• -

• Grafo conectado o conexo:

• Existe un camino simple entre dos cualquiera desus nodos.-

• Grafo desconectado:

• Aquel en que existen nodos que no están unidos porningún camino.Los arboles son estructuras recursivas, por lo que los algoritmos maseficientes con arboles son los recursivos.

•

• -

• Grafo dirigido:

• Cada arista tiene asignada una dirección (identificada por unpar ordenado).-

• Grafo no dirigido:

• La arista esta definida por un par no ordenado.-

• Grafo sencillo:

• Aquel que no tiene ni bucles ni aristas múltiples.-

• Grafo múltiple o multígrafo:

• Permite la existencia de aristas múltiples obucles.-

• Grafo completo:

• Cada nodo del grafo es adyacente a todos los demás.-

• Grafo etiquetado con peso ponderado:

• Cada arista tiene asociado un valordenominado peso. Se usa para indicar algún criterio de evaluación como lalongitud o la importancia de la arista respecto a un parámetro.-

• Peso de un camino:

• La suma de los pesos de las aristas del camino.

• Representación de los grafos:

• Existen dos formas de representar un grafo:- Con memoria estática (Matriz adyacente): Matriz de N*N elementos donde Nes el numero de nodos del grafo. Cada posición M(i,j) indica si hay unaconexión o no entre los nodos que están asociados a la posición i y j de lamatriz.- Con memoria dinámica. Se utilizan 2 listas enlazadas:*Lista de nodos: Formada por todos lo vértices*Lista de adyacentes: Contiene las aristas del grafo.

Terminología (Grafos - Estructura de Datos)