5 Teoría de Grafos

5.2 Representación de Los Grafos

Representación por incidencia

Lista de incidencia

El grafo está representado por un arreglo de aristas, identificadas por un de pares de vértices, que son los que conecta esa arista.

 Matriz de incidencia

El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (conectado o no conectado).

Representación por adyacencia

 Listas de adyacencia

El grafo está representado por un arreglo de listas de adyacencia. Para un vértice i, la lista de adyacencia está formada por todos los vértices adyacentes a i. Puede construirse en tiempo lineal, y las inserciones pueden hacerse al principio de cada lista, con lo que se asegura tiempo constante.

 Matriz de adyacencia

Una matriz de adyacencia es una matriz M de dimensión n*n, en donde n es el número de vértices que almacena valores booleanos, donde M[i,j] es verdadero (o contiene un peso) si y solo si existe un arco que vaya del vértice i al vértice j. La inicialización llevaría un tiempo del O ( #(V²)).

Representación Gráfica

Un grafo se representa mediante un diagrama en el cual a cada vértice le corresponde un punto y si dos vértices son adyacentes se unen sus puntos

correspondientes mediante una línea, ejemplo:

5.2.1 Representación Matemática de los grafos

Por medio de la teoría de los grafos podemos resolver diversos problemas, como la síntesis para circuitos secuenciales, contadores, o sistemas de apertura. Se utiliza en diferentes áreas por ejemplo, en las áreas de Sistemas y Computación, en áreas de ingeniería. También por medio de ellas podemos responder preguntas tales como, ¿Qué tarea debo hacer primero?, ¿Qué tiempo es más corto?, ¿Cuál es el más barato?, y así podemos obtener caminos óptimos para las soluciones aplicando diversos algoritmos como puede ser el algoritmo de Floyd.  Un grafo G es un par (V,E) donde: o   V ={v1,…,vn} es un conjunto de vértices o   E = {e1,…,em} es un conjunto de aristas, o   Con cada ek Î {vi, vj}, con  vi, vj Î V, vi ≠ vj ·         Los vértices se representan como puntos y las aristas como líneas entre vértices ·         Ejemplo: o   G = (V,E) o   V = {a,b,c,d } o   E = {{a,b}, {b,c}, {a,c}, {a,d}, {d,b} } ·         Proponer otro recorrido: 5.2. Representación de los Grafos en la Computación Son utilizadas en la expresión de protocolos de comunicación es una estructura de datos, en concreto un tipo abstracto de datos el cual 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 desciende directamente del concepto matemático de grafo. Referencias Carrillo, A. (1 de marzo de 2014). sites.google.com. Obtenido de https://sites.google.com/site/matediscretasatilanocarrillo/unidad-3-relaciones-graficos-y-arboles/representacion-de-un-grafo Galindo, R. M. (8 de diciembre de 2016). sites.google.com. Obtenido de https://sites.google.com/site/matematicasmoralesgalindo/6-2-representacion-de-los-grafos/6-2-1-representacion-matematica-de-los-grafos Silva, G. (15 de enero de 2014). Prezi. Obtenido de https://prezi.com/garvdeqi8yxr/62-representacion-de-los-grafos/