Qué es un grafo, descripcion de los grafos. PDF

Preview

Summary

Los grafos son una composición interesante de conjuntos de objetos que denominamos nodos. En ellos se almacena diferentes tipos de elementos o datos que podemos utilizar para procesar o conocer con fines específicos....

Description

• ¿Qué es un grafo? Los grafos son una composición interesante de conjuntos de objetos que denominamos nodos. En ellos se almacena diferentes tipos de elementos o datos que podemos utilizar para procesar o conocer con fines específicos. Adicionalmente estos nodos, suelen estar unidos o conectados a otros nodos a través de elementos que denominamos aristas. Los nodos pertenecientes a un grafo pueden contener datos estructurada o no estructurada y al interrelacionarse con otros nodos producen relaciones interesantes que podemos analizar con diferentes finalidades. Estos elementos son reconocidos por su capacidad de manejar altos volúmenes de datos y ser fácilmente procesados por motores de búsqueda o gestores de bases de datos orientados a grafos. Para representar un grafo podemos usar varios tipos de estructuras: ▪

Estructura de lista: como pueden ser las listas de adyacencia donde cada vértice tiene una lista de vértices los cuales son adyacentes a él.

▪

Estructura de matriz: como pueden ser las matrices de adyacencia donde el grafo está representado por una matriz cuadrada M de tamaño n cuadrado, donde n es el número de vértices.

• ¿Qué es un Vértice? Un vértice o nodo es la unidad fundamental de la que están formados los grafos. Un grafo no dirigido está formado por un conjunto de vértices y un conjunto de aristas (pares no ordenados de vértices), mientras que un grafo dirigido está compuesto por un conjunto de vértices y un conjunto de arcos (pares ordenados de vértices). En este contexto, los vértices son tratados como objetos indivisibles y sin propiedades, aunque puedan tener una estructura adicional dependiendo de la aplicación por la cual se usa el grafo; por ejemplo, una red semántica es un grafo en donde los vértices representan conceptos o clases de objetos.

Los dos vértices que conforman una arista se llaman puntos finales ("endpoints", en inglés), y esa arista se dice que es incidente a los vértices. Un vértice w es adyacente a

otro vértice v si el grafo contiene una arista (v,w) que los une. La vecindad de un vértice v es un grafo inducido del grafo, formado por todos los vértices adyacentes a v.

El grado de un vértice en un grafo es el número de aristas incidentes a él. Un vértice aislado es un vértice con grado cero; esto es, un vértice que no es punto final de ninguna arista. Un vértice hoja es un vértice con grado uno. En un grafo dirigido, se puede distinguir entre grado de salida ("outdegree", número de aristas que salen del vértice) y grado de entrada ("indegree", número de aristas que llegan al vértice); un vértice fuente es un vértice con grado de entrada cero, mientras que un sumidero es un vértice con grado de salida cero.

• ¿Qué son las Aristas? Una arista corresponde a una relación entre dos vértices de un grafo. Para caracterizar un grafo G son suficientes únicamente el conjunto de todas sus aristas, comúnmente denotado con la letra E (del término en inglés edge), junto con el conjunto de sus vértices, denotado por V. Así, dicho grafo se puede representar como G (V, E), o bien G = (V, E). Gráficamente las aristas se representan, para el caso de los grafos no dirigidos, como una línea que une a los dos vértices. Si el grafo es dirigido, entonces la arista se representa como una flecha, que parte del nodo origen y apunta al nodo destino. Algebraicamente, dados dos vértices a y b pertenecientes al conjunto V, una arista se define, para un grafo no dirigido, como el conjunto e = {a,b} (o {b,a}), en tanto que para un grafo dirigido, como el par ordenado e = (a,b) (donde (b,a) representaría una arista diferente, con el nodo origen y destino cambiados). Por otro lado, también es normal que las aristas lleven asociadas una etiqueta (un número, una letra o un valor cualquiera) que indica una información asociada a ambos vértices, a veces un coste o indicación del trabajo necesario para recorrer el camino de un vértice al otro. No es obligatorio que todo vértice esté unido con otro por una arista. Tales vértices se llaman vértices o nodos aislados . Tampoco es necesario que ambos nodos unidos por una arista sean distintos. Dado un vértice a, de existir una arista {a, a} o bien (a, a), entonces decimos que el grafo posee un bucle.

• ¿Cuáles son los tipos abstractos de datos grafo?

Un grafo en el ámbito de las ciencias de la computación es un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del concepto matemático de grafo.

• ¿Qué es un grafo dirigido? Un grafo dirigido (o dígrafo) G consiste de un conjunto de vértices y un conjunto de arcos E. A los vértices se les llama también nodos o puntos y a los arcos aristas dirigidas o líneas dirigidas. Un arco es un par ordenado de vértices (v, w) donde v es la cola y w la cabeza del arco. Un arco (v, w) se expresa también como v w y se dibuja como

Los vértices de un dígrafo pueden usarse para representar objetos, y los arcos relaciones entre los objetos. Un camino en simple si todos los vértices del camino son distintos. Un ciclo simple es un camino simple de longitud uno como mínimo, que empieza y termina en el mismo vértice. Un grafo etiquetado es un dígrafo en el que cada arco y/o vértice puede tener una etiqueta asociada. Una etiqueta puede ser un nombre, un costo o un valor de algún tipo de dato dado. Representaciones de grafos dirigidos: Pueden usarse varias estructuras de datos para representar un dígrafo, dependiendo su selección de las operaciones que se aplicarán a los vértices y arcos del dígrafo. Una representación común para un dígrafo G= {V, E} es la matriz de adyacencia. Suponiendo V= {1,2,…, n}, la matriz de adyacencia de G es una matriz A de nxn de valores binarios donde A[i] [j] es 1 si y sólo si hay un arco del vértice i a j, y 0 si no lo hay.

Otra representación relacionada es la matriz de adyacencia etiquetada donde A[i] [j] es la etiqueta del arco que va de i a j. Si tal arco no existe puede usarse una etiqueta especial para ese caso.

• ¿Qué es un grafo no dirigido? Es un tipo de grafo en el cual las aristas representan relaciones simétricas y no tienen un sentido definido, a diferencia del grafo dirigido, en el cual las aristas tienen un sentido y por tanto no son necesariamente simétricas. Todo grafo dirigido simétrico se puede representar como un grafo no dirigido. Por lo tanto, los grafos no dirigidos se pueden ver como un caso particular de grafos dirigidos. La siguiente figura representa un grafo no dirigido.

El grafo no dirigido de la figura está formado por: Vértices = {1, 2, 3, 4, 5} Lados = {(1,2), (1,3), ( 1, 4), (2, 4) , ( 3, 4 )} DEFINICIONES ADYACENCIA: Dos vértices son adyacentes si forman un lado. De la gráfica podemos decir que los vértices adyacentes al vértice 1 son 2,3 y 4. Los vértices adyacentes al vértice 3 son 1 y 4. INCIDENCIA: Un lado incide en los dos vértices que une. GRADO DE UN VÉRTICE: Es el número de lados que inciden en el vértice (número de ramificaciones que salen del vértice). De la gráfica podemos decir que el grado del vértice 1 es 3, el grado del vértice 3 es 2 etc. TRAYECTORIA I-J: Son los vértices por los que hay que pasar para ir desde el vértice I hasta el vértice J. De la gráfica podemos decir que tenemos dos trayectorias para ir del vértice 1 al vértice 3 T13 = {1, 4, 3} y T13= {1,2.4, 3}.

• ¿Qué es una matriz de adyacencia? Matriz cuadrada de orden NxN asociada a un grafo de orden N, donde sus filas y columnas se identifican con los vértices del grafo y en las celdas se indican la cantidad de aristas (o arcos salientes si es un dígrafo) a los nodos asignado a la fila y columnas en cuestión. Sea el grafo G= de orden N al mismo se asocia una matriz cuadrada M de NxN tal que: •

A cada fila se asocia un nodo de V.

•

A cada columna se asocia un nodo de V.

•

La celda Mi,j contiene la cantidad de aristas de A de la forma {i, j} ó (i, j).

La matriz de adyacencia asociada al grafo sería:

VENTAJAS Y DESVENTAJAS DE LA MATRIZ DE ADYACENCIA VENTAJAS: 1. Se puede determinar en un tiempo fijo y constante si un enlace(arco) pertenece o no al grafo. 2. Es fácil determinar si existe o no un arco o enlace, solo se debe posicionar en la matriz. 3. Es fácil determinar si existe un ciclo en el grafo, basta multiplicar la matriz por ella misma n veces hasta obtener la matriz nula (no hay ciclos) o bien una sucesión periódica de matrices (hay ciclo)

DESVENTAJAS: 1. Se requiere un almacenamiento |v|*|v|. Es decir O(n2). 2. Solo al leer o examinar la matriz puede llevar un tiempo de O(n2).

• ¿Qué es una lista de Adyacencia?

En teoría de grafos, una lista de adyacencia es una representación de todas las aristas o arcos de un grafo mediante una lista. Si el grafo es no dirigido, cada entrada es un conjunto o multiconjunto de dos vértices conteniendo los dos extremos de la arista correspondiente. Si el grafo es dirigido, cada entrada es una tupla de dos nodos, uno denotando el nodo fuente y el otro denotando el nodo destino del arco correspondiente. Una forma más eficiente, respecto al uso del espacio, de implementar un grafo conectado de forma rala es usar una lista de adyacencia. En una implementación de lista de adyacencia mantenemos una lista maestra de todos los vértices en el objeto Grafo y además cada objeto Vértice en el grafo mantiene una lista de los otros vértices a los que está conectado. En nuestra implementación de la clase Vértice usaremos un diccionario en lugar de una lista donde las claves del diccionario son los vértices, y los valores son las ponderaciones. La Figura 4 ilustra la representación mediante una lista de adyacencia para el grafo de la Figura 2.

Representación mediante una lista de adyacencia de un grafo La ventaja de la implementación mediante una lista de adyacencia es que nos permite representar de forma compacta un grafo ralo. La lista de adyacencia también nos permite encontrar fácilmente todos los enlaces que están directamente conectados a un vértice particular.

VENTAJAS Y DESVENTAJAS DE LAS LISTAS DE ADYACENCIA

VENTAJAS: 1. La lista de adyacencia requiere un espacio proporcional a la suma del número de vértices más el número de enlaces(arcos). Hace buen uso de la memoria. 2. Se utiliza bastante cuando el número de enlaces es mucho menor que O(n2) DESVENTAJAS: 1. La representación con lista de adyacencia es que puede llevar un tiempo O(n) determinar si existe un arco del vértice i al vértice j, ya que pueden haber O(n) vértices en la lista de adyacencia. Para el vértice i.

• ¿Cuándo un grafo es denso? Un grafo denso es un grafo en el que el número de aristas es cercano al número máximo de aristas posibles, es decir, a las que tendría si el grafo fuera completo. Al contrario, un grafo disperso es un grafo con un número de aristas muy bajo, es decir, cercano al que tendría si fuera un grafo vacío.

•

¿Qué es un camino?

En Teoría de Grafos, se llama camino a una secuencia de vértices dentro de un grafo tal que exista una arista entre cada vértice y el siguiente. Se dice que dos vértices están conectados si existe un camino que vaya de uno a otro, de lo contrario estarán desconectados. Dos vértices pueden estar conectados por varios caminos. El número de aristas dentro de un camino es su longitud. Así, los vértices adyacentes están conectados por un camino de longitud 1, y los segundos vecinos por un camino de longitud 2. Si un camino empieza y termina en el mismo vértice se le llama ciclo.

• ¿Qué es un recorrido de grafos? La operación de recorrer una estructura de datos consiste en visitar (procesar) cada uno de los nodos a partir de uno dado. De igual forma, recorrer un grafo consiste en visitar todos los vértices alcanzables a partir de uno dado. En muchas aplicaciones es necesario visitar todos los vértices del grafo a partir de un nodo dado. Algunas aplicaciones son: •

Encontrar ciclos

•

Encontrar componentes conexas

•

Encontrar árboles cobertores

Hay dos enfoques básicos: •

Recorrido (o búsqueda) en profundidad (depth-first search): La idea es alejarse lo más posible del nodo inicial (sin repetir nodos), luego devolverse un paso e intentar lo mismo por otro camino.

•

Recorrido (o búsqueda) en amplitud (breadth-first search): Se visita a todos los vecinos directos del nodo inicial, luego a los vecinos de los vecinos, etc.

Explicar el proceso de recorrido en profundidad de un grafo. A medida que recorremos el grafo, iremos numerando correlativamente los nodos encontrados (1,2,…). Suponemos que todos estos números son cero inicialmente, y utilizamos un contador global n, también inicializado en cero.

La estrategia de recorrido en profundidad es la siguiente: 1. Se toma un nodo “s” como comienzo, y se marca. 2. A continuación, se toma y se marca un nodo no marcado adyacente a “s”, y ese nodo pasa a ser el nuevo nodo de partida, dejando posiblemente por el momento al nodo inicial original con nodos no explorados. 3. La búsqueda continúa por el grafo hasta que el camino en curso finalice con un grafo de salida igual a cero, o bien en un nodo en que todos los nodos adyacentes estén marcados. 4. A continuación, la búsqueda vuelve al último nodo que todavía tenga nodos adyacentes sin marcar, y continúa marcando todos los nodos de forma recursiva hasta que ya no queden nodos sin marcar.

Es preciso marcar los nodos en la búsqueda en profundidad. Si no se hiciera esto, los grafos que contuvieran ciclos darían lugar a bucles infinitos. Un algoritmo de búsqueda o recorrido en profundidad consta de una única rutina principal que invoca a un procedimiento recursivo de la manera siguiente: Principal 1. Se marcan todos los nodos del grafo como no visitados. 2. Se invoca a recorrido_en_profundidad (s) para algún nodo inicial “s”.

Procedimiento recorrido_en_profundidad 1. Se marca y visita “s”. 2. Para cada vecino “w” de “s” Si el vecino “w” no está marcado Se invoca a recorrido_en_profundidad (w). El recorrido en profundidad persigue el mismo objetivo que el recorrido en anchura: visitar todos los vértices del grafo alcanzables desde un vértice dado. La búsqueda en profundidad empieza por un vértice “V” del grafo “G”; “V” se marca como visitado. Después se recorre en profundidad cada vértice adyacente a “V” no visitado; así hasta que no haya más vértices adyacentes no visitados. Esta técnica se denomina en profundidad porque la dirección de visitar es hacia adelante mientras que sea posible; al contrario que la búsqueda en anchura, que primero visita todos los vértices posibles en amplitud. La definición recursiva del recorrido en profundidad nos indica que tenemos que utilizar una “pila” como estructura para guardar los vértices adyacentes no visitados a uno dado. De igual forma que en el recorrido en anchura, hacemos uso de una lista de vértices para controlar los ya visitados. Los usos que pueden darse a este tipo de recorrido son: • •

Simular una red, a partir de un grafo y analizar su robustez para transferencia de información. Identificar bucles, los cuales son potenciales causantes de elevación de tráfico en recorridos.

Explicar el proceso de recorrido de anchura de un grafo. La idea del procedimiento BF S (G, v) es la siguiente: Se marca el nodo v. • Si todos los nodos adyacentes a v están marcados, entonces TERMINAR; si no, marcar todos los nodos v1, v2, … vk adyacentes a v que no estén marcados.

• Repetir el proceso con los nodos adyacentes a los nodos que se han marcado en el paso anterior Si G es conexo (es decir, si dos vértices cualesquiera de G siempre están conectados por un camino), entonces BF S (G, v) visita todos los nodos y aristas del grafo. A diferencia de lo que ocurría con el recorrido en profundidad, DF S, el recorrido en anchura, BF S, no tiene naturaleza recursiva. Por ello, es posible describir un esquema algorítmico iterativo del recorrido en anchura usando una cola que permita controlar las visitas a los nodos. procedimiento BF S(G, v) marcar (v) poner (v) en una COLA mientras la COLA no sea vacía hacer quitar el primer elemento w de la COLA para cada vértice x adyacente a w hacer si x no esta marcado entonces marcar x poner x en la COLA...