REPRESENTACIÓN DE LOS GRAFOS; MATEMATICAS Y COMPUTACIONALES.

¿COMO SE REPRESENTAN LOS GRAFOS?

Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas). Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras.

 

Se podrían clasificar los grafos en 2 formas; los grafos dirigidos y los grafos no dirigidos. Los grafos no dirigidos como su nombre lo indica no poseen un sentido definido mientras los grafos dirigidos si tienen un orden:

 

 

_______________________________________________________________________

El orden de un grafo es un elemento importante de aprender cuando estamos navegando en las profundas aguas de esta teoría. Recientemente los grafos que son grafos han tomado la vanguardia del mundo tecnológico y ha despertado pasiones en muchos de nosotros.

Explicaremos a continuación algunos aspectos interesantes sobre qué es el orden de un grafo, cómo calcularlo y los diferentes tipos de orden.

ORDEN DE UN GRAFO

Como sabemos un grafo es un conjunto de nodos en los cuales se almacena información de diferentes tipos y que los nodos se conectan a través de aristas. Dependiendo de los tipos de conexiones o aristas que unan los nodos podemos darles algunas clasificaciones a los grafos.

Una vez entendido esto debemos profundizar en las propiedades de los grafos y conocer sobre su orden y tamaño. La teoría de grafos nos indica que el tamaño de un grafo se refiere de forma simple y llana al número de conexiones que posea un grafo.

Por su parte el orden de un grafo se define por el número o cantidad de vértices que tenga un grafo. Esto quiere decir que la forma y la direccionalidad que tengan los vértices influyen de forma significativa en la composición de un grafo. Esto aplica según la teoría especialmente en los grafos dirigidos.

__________________________________________________________________________

MATEMATICAS

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.

A nivel matemático podríamos definir un grafo “G” como un conjunto tanto de vértices (V) como de Aristas (E), representación gráfica;

G=(V, E)

La mayoría de algoritmos van a utilizar estas letras para representar los grafos, vértices y aristas. Habiendo definido esto, podemos decir que un grafo con;

V= 3

E= 5

 

 

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:

 

 

 

 ______________________________________________________________________________

REPRESENTACIÓN COMPUTACIONAL

Existen dos formas estándar a la hora de representar estos grafos (dirigidos y no dirigidos); las cuales son las siguientes:

Las listas encadenadas son muy utilices cuando se denominan grafos con mucho espacio, es decir que tienen muchos ceros; cuando tenemos grados donde el número de vértices es muy superior al número de aristas. En cambio en la matriz de adyacencia va muy bien cuando lo que buscamos es obtener en una forma rápida la conectividad entre dos nodos.

 

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

 

        Para mayor explicación de dicha representación de grafos puede consultar a el siguiente video: https://youtu.be/23pdz9VtIBo.

 

 

 

 EJERCICIO

Dado un grafo con matriz de adyacencia, ¿Cómo se representaría un grafo de acuerdo con los anteriores criterios? (Ayudate de la tabla). 

 

 

1.    El grafo es euleriano
2. El grafo es conexo
3.   Es un multígrafo