Teoria De Grafos Informatica 6915t

Grafos. Un grafo es un objeto matemático que se utiliza para representar circuitos, redes, etc. Los grafos son muy utilizados en computación, ya que permiten resolver problemas muy complejos. Grafos aplicados en la informática. En estructura de datos. Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto 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. Informalmente se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E, las aristas (edges en inglés). Formalmente, un grafo, G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V. Formas de representación. Existen diferentes implementaciones del tipo grafo: 

Matriz de adyacencias: se asocia cada fila y cada columna a cada nodo del grafo, siendo los elementos de la matriz la relación entre los mismos, tomando los valores de 1 si existe la arista y 0 en caso contrario.

int V,A; int a[maxV][maxV]; void inicializar() { int i,x,y,p; char v1,v2; // Leer V y A memset(a,0,sizeof(a)); for (i=1; i<=A; i++) { scanf("%c %c %d\n",&v1,&v2,&p); x=v1-'A'; y=v2-'A'; a[x][y]=p; a[y][x]=p;

} }



Lista de adyacencias: se asocia a cada nodo del grafo una lista que contenga todos aquellos nodos que sean adyacentes a él.

struct nodo { int v; int p; nodo *sig; }; int V,A; // vértices y aristas del grafo struct nodo *a[maxV], *z; void inicializar() { int i,x,y,peso; char v1,v2; struct nodo *t; z=(struct nodo *)malloc(sizeof(struct nodo)); z->sig=z; for (i=0; i v=y; t->p=peso; t->sig=a[x]; a[x]=t;

} }

t=(struct nodo *)malloc(sizeof(struct nodo)); t->v=x; t->p=peso; t->sig=a[y]; a[y]=t;

Búsqueda en profundidad. Se implementa de forma recursiva, aunque también puede realizarse con una pila. Se utiliza un array val para almacenar el orden en que fueron explorados los vértices. Para ello se incrementa una variable global id (inicializada a 0) cada vez que se visita un nuevo vértice y se almacena id en la entrada del array val correspondiente al vértice que se está explorando. La siguiente función realiza un máximo de V (el número total de vértices) llamadas a la función visitar, que implementamos aquí en sus dos variantes: representación por matriz de adyacencia y por listas de adyacencia. int id=0; int val[V]; void buscar() { int k; for (k=1; k<=V; k++) val[k]=0; for (k=1; k<=V; k++) if (val[k]==0) visitar(k); } void visitar(int k) // matriz de adyacencia { int t; val[k]=++id; for (t=1; t<=V; t++) if (a[k][t] && val[t]==0) visitar(t); } void visitar(int k) // listas de adyacencia { struct nodo *t; val[k]=++id; for (t=a[k]; t!=z; t=t->sig) if (val[t->v]==0) visitar(t->v); }

El resultado es que el array val contendrá en su i-ésima entrada el orden en el que el vértice i-ésimo fue explorado. Es decir, si tenemos un grafo con cuatro nodos y fueron explorados en el orden 3-1-2-4, el array val quedará como sigue: val[1]=2; // el primer nodo fue visto en segundo lugar val[2]=3; // el segundo nodo fue visto en tercer lugar val[3]=1; // etc. val[4]=4;

Una modificación que puede resultar especialmente útil es la creación de un array "inverso" al array val que contenga los datos anteriores "al revés". Esto es, un array en el que la entrada i-ésima contiene el vértice que se exploró en i-ésimo lugar. Basta modificar la línea val[k]=++id; Sustituyéndola por val[++id]=k;

Para el orden de exploración de ejemplo anterior los valores serían los siguientes: val[1]=3; val[2]=1; val[3]=2; val[4]=4;

Búsqueda en amplitud o anchura La diferencia fundamental respecto a la búsqueda en profundidad es el cambio de estructura de datos: una cola en lugar de una pila. En esta implementación, la función del array val y la variable id es la misma que en el método anterior. struct tcola *cola; void visitar(int k) // listas de adyacencia { struct nodo *t; encolar(&cola,k); while (!vacia(cola)) { desencolar(&cola,&k); val[k]=++id; for (t=a[k]; t!=z; t=t->sig) { if (val[t->v]==0) { encolar(&cola,t->v); val[t->v]=-1; } } } }

Es decir los grafos como tal nos ayudan a buscar y recopilar datos en un programa mediante el orden de jerarquización la cual nos facilita mucho el trabajo sobre

todo para relacionar datos el uno con el otro y formando operaciones de las mismas o ya bien para localizar funciones y nodos ya que sui jerarquización nos permite tener prioridades y uso fácil sobre ellos.

Grafos aplicados en las redes computacionales. Los grafos se ven reflejados en las redes computacionales ya que se debe istrar el flujo de datos las cuales deben de llevar una topología es aquí donde se ve reflejado con mayor forma. Con topologías como las de anillo, doble anillo, estrella, mixta, malla y árbol entre otras. Ya que en muchos de los casos la información es de ida y vuelta pero pueden cruzar el mismo plano ya que causarían conflicto, se deben crear redes de uso múltiple para eso son los grafos se denotan mucho en la utilización las topologías de árbol y doble anillo ya que la información puede dar miles de vueltas pero jamás puede cruzar el mismo si plano si que forman un ciclo ya sea por puentes rutas o caminos.

Los grafos son una manera de análisis para poder entender mejor como esta entrelazado nuestro programa o nuestra red es como un mapa detallado de lo que queremos lograr o ya tenemos así es más fácil el poder realizar cambios o incluso agregar nuevas redes o sectores de código Lo cual se utiliza mucho en programación pues una vez que se crea un programa se tiene que ir actualizando e incluso mejorando si no se hace un grafo con el debido detalle y alguien que no sea el que creo el programa intenta hacer cambios podría borrar algo vital y dejarlo inservible, En las redes para interconectar ciertos lugares y si se va a expandir saber dónde se puede hacer una unión sin alterar el flujo de datos de igual manera en un circuito se puede utilizar para realizar el diagrama es más que nada documentación para hacer algo se ve muy enredado o complicado sea más sencillo de entender o incluso para empezar algún proyecto se puede utilizar con las bases del proyecto ir desarrollándolo para dar solución o llegar la meta u objetivo deseado Si no se realizan bien los grafos por ejemplo en cuanto a los circuitos con el flujo de corriente o de los componentes que requiere un transistor para realizar cierta tarea lo cual serian dos grafos uno para la continuidad de la corriente y otro de procedencia indicando los lazos entre los transistores o chips En las redes podría quedar algún sector aislado de información si no se realiza correctamente o incluso en algún punto el flujo de datos se cortaría En programación se podría manejar el de procedencia muy bien pues podrías exponer todos los procesos detallados y sus requerimientos sin los cuales el programa sería inútil .

Otro ejemplo de grafos enfocándonos a la rama de la informática , lo podemos ver en las redes , particularmente en las redes sociales , si somos observadores no

tendremos trabajo en darnos cuenta que en la pantalla de inicio de Facebook (una de las principales redes sociales de la actualidad) se puede percibir una imagen que denota de manera muy explícita un grafo , la imagen de la que se hace referencia es la siguiente

El grafo se puede observar en la parte izquierda de la pantalla de inicio de Facebook , solo es una pequeña representación gráfica .Pero solo imagina la cantidad de grafos que se pueden desarrollar o demostrar en esta red social , podemos localizar grafos desde una comunidad muy pequeña y representarlo , hasta realizar un grafo y demostrarlo entre los continentes del planeta tierra . La imagen demuestra un pequeño grafo entre los continentes, los cuales pueden ser desde personas comunes o hasta representantes de alguna organización o líderes de alguna empresa. En fin en cuanto a esta rama de la informática hacemos referencia y principalmente enfocados en las redes sociales, podemos decir que prácticamente podemos encontrar todo tipo de grafos o casi todo tipo de grafos, ya que podemos encontrar diferentes maneras de desarrollar un grado desde hacerlo en el perfil de una solo persona, hasta desarrollarlo con todos los habitantes de un país, por lo cual podemos encontrar una gran diversidad de tipos de grafos. Aquí podemos dar el ejemplo aplicado en un grupo de Facebook , donde el nodo raíz o principal seria el creador del grupo y los demás del grupo serían los nodos que complementan el grafo , el grafo podría ser no dirigido y también se podría decir que es un grafo completo ya que todos los están unidos , ya que cualquier miembro puede dar un comentario y ser retroalimentado .

grafo completo En caso de representar un grafo dirigido , podemos representarlo con una página cerrada a retroalimentación (como la de grandes marcas comerciales , como Coca Cola , Telcel , Audi) en donde ellos siendo el nodo principal pueden mandar información (algún comentario o publicación en su página de Facebook ) la cual se transmitirá por el resto del grafo , pero tú no puedes retroalimentar ya que es imposible hacer una publicación en su página principal de Facebook y también se podría decir que este grafo es de tipo simple ya que no todos los están unidos

grafo simple