representacion de grafos

 REPRESENTACIÓN DE LOS GRAFOS.

Los grafos se pueden representar de diferentes maneras, como por ejemplo:

• 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 ( #(V2)).

 REPRESENTACIÓN MATEMÁTICA.

En matemáticas y ciencias de la computación, la teoría de grafos, también llamada teoría de las gráficas estudia las propiedades de los grafos (también llamados gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de partes de vértices llamados aristas. 

Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas por ejemplo, Dibujo computacional, en todas las áreas de Ingeniería. Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd.

 REPRESENTACIÓN COMPUTACIONAL.

Existen diferentes formas de representar un grafo (simple), además de la geométrica y muchos métodos para almacenarlos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.

• Estructura de lista:

• Lista de incidencia: Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas. 
• Lista de adyacencia: Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra. 
• Lista de grados: También llamada secuencia de grados o sucesión gráfica de un grafo no-dirigido es una secuencia de números, que corresponde a los grados de los vértices del grafo. 

• Estructuras matriciales:

• Matriz de adyacencia: El grafo está representado por una matriz cuadrada M de tamaño, donde es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento es 1, de lo contrario, es 0.
• 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 (1 - conectado, 0 - no conectado).

grafos

 

ELEMENTOS, CARACTERÍSTICAS Y COMPONENTES DE LOS GRAFOS.

ELEMENTOS Y CARACTERÍSTICAS.

Un grafo, G es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices. Los grafos representan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc. La notación G = A (V, A) se utiliza comúnmente para identificar un grafo. Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismo grafo..

COMPONENTES.

Se compone principalmente de:

• Aristas.

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. Si la arista 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.

          Estas a su vez pueden ser:

• 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. 

          Estos a su vez pueden ser: 

• Vértices Adyacentes: Si tenemos un par 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. 

5.1.1 TIPOS DE GRAFOS.

Hay 6 tipos principales de grafos:

• Grafo simple: Se dice que el grafo G = (V, E) es un grafo simple de grado n si todos sus vértices tienen grado n. 

• Grafo completo: Un grafo es completo si cada par de vértices está unido por una arista. Se denota por Kn al grafo completo de n vértices.

• Grafo bipartido: Un grafo es bipartido si V=V1?V2 y cada arista de E une un vértice de V1 y otro de V2. 

• Grafo bipartido completo: Un grafo es bipartido completo si V=V1?V2 y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V1 y el otro en V2. Se denota por Kr, donde V1 tiene r vértices y V2 tiene s vértices.

• Grafos planos: Un grafo plano es aquel que puede ser dibujado en el plano sin que ninguna arista se intersecta. 

• Grafos conexos: Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde "a" hacia "b".

• Grafo ponderado: Un grafo es ponderado si presenta los pesos de cada arista y se puede determinar la longitud de una ruta, la cual es la suma de todos los pesos de las aristas.