Grafos

Es un conjunto de nodos o vértices, conectados por pares llamados arcos

·        El grado de un nodo es el numero de aristas que inciden en él

·        El orden de un grafo es el numero de nodos que tiene

·        Un grafo nulo tiene orden cero (0)

·        Dos nodos son adyacentes si un arco los une

·        En un grafo dirigido, si el nodo A es adyacente de B, no quiere decir que B sea adyacente de A

·        El camino es una secuencia de uno o mas arcos que conectan a dos nodos

·        La longitud de un camino está dado por la cantidad de nodos menos uno (n-1). Si una longitud es de cero (0), quiere decir que parte de él a él mismo

·        Un grafo es conectado, si siempre existe un camino para dos nodos cualesquiera, y es desconectado si es lo contrario

·        Un ciclo es cuando un nodo tiene un camino así mismos

TIPOS DE GRAFOS

·   Grado completo: también conocido como conexos, donde cada par de vértices está conectado con una arista

Grafo Euleriano: 

Es un grafo en el cual desde cualquier vertice se pueden recorrer todos los arcos llegando de nuevo al vertice de origen, los vertices pueden visitarse cuantas veces se nescecite, pero los arcos solo pueden recorrerse una vez

Grafo Hamilitoniano:

Es un grafo en el cual desde cualquier vertice se pueden recorrer todos los demas vertices, llegando de nuevo al vertice de origen sin repetir los nodos visitados los arcos pueden recorrese cuantas veces sean nescesarias

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. Para la administración de proyectos, utilizamos técnicas como PERT en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos. La teoría de grafos también ha servido de inspiración para las ciencias sociales, en especial para desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales y verifica la posición, centralidad e importancia de cada actor dentro de la red. 

 Representación de grafos en programas

Representación mediante matrices: La forma más fácil de guardar la información de los nodos es mediante la utilización de un vector que indexe los nodos, de manera que los arcos entre los nodos se pueden ver como relaciones entre los índices. Esta relación entre índices se  puede guardar en una matriz, que llamaremos de adyacencia.

                                                        

Representación de un grafo dirigido. 

Para la representación de la matriz se utilizara la siguiente condición: 

*0 el vértice i está conectado con el vértice j. 

*-1 el vértice i no está conectado con el vértice j. 

Representación mediante listas: En las listas de adyacencia lo que haremos será guardar por cada nodo, además de la información que pueda contener el propio nodo, una lista dinámica con los nodos a los que se puede acceder desde él. La información de los nodos se puede guardar en un vector, al igual que antes, o en otra lista dinámica.

•    Modelos con grafos:

 Los grafos se emplean en una gran variedad de modelos en diferentes áreas, en nuestro caso mostraremos algunos modelos empleados en el área computacional:

                                                            

Representación mediante listas: En las listas de adyacencia lo que haremos será guardar por cada nodo, además de la información que pueda contener el propio nodo, una lista dinámica con los nodos a los que se puede acceder desde él. La información de los nodos se puede guardar en un vector, al igual que antes, o en otra lista dinámica.

                                                         

·         Modelos con grafos:

 Los grafos se emplean en una gran variedad de modelos en diferentes áreas, en nuestro caso mostraremos algunos modelos empleados en el área computacional: 

Como cada segundo se crean páginas Web nuevas y otras desaparecen, hay más de mil millones de vértices y decenas de miles de millones de aristas. Hay muchas personas estudiando las propiedades del grafo de la red para entender mejor la naturaleza de la red de Internet.

Grafos de precedencia y procesamiento concurrente

Los programas informáticos, más que todo para los Sistemas Operativos, pueden ejecutarse más rápidamente si ciertas sentencias se ejecutan simultáneamente. Es importante no ejecutar sentencias que requieran el resultado de sentencias no ejecutadas. La dependencia de sentencias con respecto a sentencias previas se puede representar por medio de un grafo dirigido. Cada sentencia se representa por un vértice, y hay una arista de un vértice a un segundo si la sentencia representada por el segundo vértice no puede ejecutarse hasta la sentencia representada por el primero se ha ejecutado. A este tipo de grafo se le llama grafo de precedencia. Por ejemplo, el grafo nos dice que la sentencia S₅ no se puede ejecutar hasta que se ejecute S₁, S₂, y  S₄.

                                               

S1 a:= 0; S2 b:= 1 ;S3 c:= a+1 (necesita que s1 se ejecute para que s3 se ejecute); S4 d:= b+a (necesita que s1 y s2 se ejecute para que s4 se ejecute); S5 e:= d+1 (necesita que s4 se ejecute para que s5 se ejecute); S6 f:= d+c (necesita que s4 y s3 se ejecuten para que s6 se ejecute)